Re: Reduce/Reduce conflict in Algol60 grammar

Chris F Clark <cfc@shell01.TheWorld.com> wrote:
# SM Ryan <wyrmwif@tsoft.org> writes:
# much that I had no quibbles with, but finished with this:
# > # [You could try building types into the grammar like boolean_variable
# > # and boolean_function_designator, but it's not going to be pretty. -John]
# >
# > Unless you use a two-level grammar, you cannot write enough productions.
#
# We are talking Algol 60 here, right? There seem to be two relevant
# types: numerics and booleans. Thus, the number of expression rules
# merely doubles. (In theory it could quadruple for that case, but that
# would mean one whould need operators that have a numeric expression on
# one side and a boolean on the other, which Algol 60 didn't.) If you


The problem is you can't distinguish Boolean variable from arithmetic
variable merely by looking variable characters themselves. You need to
match the variable to its declaration and that requires a context
sensitive grammar. In a context free grammar a Boolean variable and
arithmetic variable (or function names) are indistinguishable hence
the reduce-reduce conflict.


# were talking Algol 68, you would need a 2-level grammar, but an Algol
# 60 grammar should be hand-disambiguable, aside from the issue of
# typing a specific variable, for which the C-typedef solution (have the
# lexer return two different types) should suffice. Perhaps, SM means to


That's still using a context sensitive grammar.


--
SM Ryan http://www.rawbw.com/~wyrmwif/
[Has there ever been a useful truly context free parser? All the ones I've
written have cheated by using symbol table info to decide what symbol to
return for a variable name and the like. I presume that's what Chris
is suggesting. -John]

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