Re: Reduce/Reduce conflict in Algol60 grammar

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
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
use the 2-level grammar to attach types to variable names--in which
case, he is technically (theoretically) correct, but practically
wrong, since few compiler writers go that route, given that the
C-typedef solution is far more practical.


All that being said, I would say that in general putting types
(e.g. distinguishing syntactically between numeric and boolean
expressions) in one's grammar is a bad idea. It is a poor match for
the technology. As noted above, some part of the grammar explodes in
size, being doubled, tripled, or worse depending on the number of type
combinations that are relevant. That makes the grammar more fragile
and more inefficient to process. Worse, when the user makes a typing
error, that is when they use an expression of one type where another
type is expected, the error reporting and recovery of a parser is
generally worse than the error reporting and recovery of "semantic
action code" (that is code which checks the types after the parsing is
done).


However, for some small cases, one can do it. One can use the grammar
for type checking. I would be real surprised if Algol 60 wasn't in
that class. Moreover, the rules I read looked like they could be hand
type-disambiguated, that is you could rewrite the rules to carry type
information to everywhere it is needed, presuming one could type the
atoms (literals and variables) using the C-typedef hack. Note that
this type disambiguation is exactly equivalent to computing
synthesized attributes, which is how one normally does it in semantic
action code. And, I will state categorically that, if one can compute
a result as a synthesized attribute, where the attribute has a type
that has only a fixed number of values (in this case boolean and
numeric), then one can change a grammar by rewriting a fixed number of
rules to carry and enforce that synthesized attribute. Since, I know
Algol 60's type system can be computed by such a synthesized
attribute, I believe the rules can be rewritten to disambiguate the
types in the grammar.


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)
------------------------------------------------------------------------------

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