Reduce/Reduce conflict in Algol60 grammar

Hi folks :)


As part of my current work I've been asked to find common conflicts that
occur in grammars of some well known programming languages.


As a start point, I've got the Algol60 revised report and typed the
corresponding grammar. I've faced a difficult reduce-reduce conflict in
the expression part, which is sthg like this:


expression ::=
arithmetic_expression |
boolean_expression |
designational_expression ;


arithmetic_expression ::=
simple_arithmetic_expression |
if_clause simple_arithmetic_expression ELSE arithmetic_expression ;


simple_arithmetic_expression ::=
term |
adding_operator term |
simple_arithmetic_expression adding_operator term ;


term ::=
factor |
term multiplying_operator factor ;


factor ::=
primary |
factor POWER primary ;


primary ::=
unsigned_number |
variable |
function_designator |
LPAR arithmetic_expression RPAR ;
...


boolean_expression ::=
simple_boolean |
if_clause simple_boolean ELSE boolean_expression ;


simple_boolean ::=
implication |
simple_boolean LOGEQ implication ;


implication ::=
boolean_term |
implication IMPLIES boolean_term ;


boolean_term ::=
boolean_factor |
boolean_term OR boolean_factor ;


boolean_factor ::=
boolean_secondary |
boolean_factor AND boolean_secondary ;


boolean_secondary ::=
boolean_primary |
NOT boolean_primary ;


boolean_primary ::=
logical_value |
variable |
function_designator |
relation |
LPAR boolean_expression RPAR ;
...


Note the common part between primary and boolean_primary, which leads to
the conflict. The only way that I could resolve this was to merge arithmetic_expression and
boolean_expression, respecting the precedence estabelished, and then
distinguish them through semantic actions.
Is there a solution that can be obtained by just rewriting the grammar?
[You could try building types into the grammar like boolean_variable
and boolean_function_designator, but it's not going to be pretty. -John]

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