Re: Reduce/Reduce conflict in Algol60 grammar

>>>>> "Leonardo" == Leonardo Teixeira Passos <leonardo@dcc.ufmg.br> writes:


        Leonardo> Note the common part between primary and
        Leonardo> boolean_primary, which leads to the conflict. The only
        Leonardo> way that I could resolve this was to merge
        Leonardo> arithmetic_expression and boolean_expression, respecting
        Leonardo> the precedence estabelished, and then distinguish them
        Leonardo> through semantic actions.


I seem to recall that this was the standard solution in the 1960s. The
trouble is that it makes perfect sense for numbers and arithmetic
operators to be in a boolean expression.


For example, consider "i + 3*j > 100". You can't tell that it might
be a boolean expression until you get to the ">".


If you're really interested, you could check out "Computing: A Human
Activity" by Peter Naur, "Algol 60 Implementation" by Randell and
Russell, and "Programming Systems and Languages" edited by Rosen.
Also, Dijkstra wrote a couple of interesting papers on Algol 60
compilation:
        http://www.cs.utexas.edu/users/EWD/MCReps/MR35.PDF


The Naur book contains some papers that go into detail about the type
checking. The compiler described didn't build syntax trees. It did
"pseudo evaluation" where at compile time it would perform all of the
operations using a stack, but instead of actual values, all that was
stuck on the stack was type identifiers. An expression could be
"pseudo evaluated" and if at any point an operator was applied while
invalid types were on the stack, it was a type error. Also, the final
type of the expression could be determined by looking at the last type
left on the stack when the pseudo evaluation was finished.


Best of luck,
Andru
--
Andru Luvisi

Return to the comp.compilers page.
Search the comp.compilers archives again.