Reduce/Reduce conflict in Algol60 grammar

Leonardo Teixeira Passos <>
10 Oct 2006 23:35:00 -0400

          From comp.compilers

Related articles
Reduce/Reduce conflict in Algol60 grammar (Leonardo Teixeira Passos) (2006-10-10)
Re: Reduce/Reduce conflict in Algol60 grammar (Andru Luvisi) (2006-10-11)
Re: Reduce/Reduce conflict in Algol60 grammar ( (2006-10-11)
Re: Reduce/Reduce conflict in Algol60 grammar (SM Ryan) (2006-10-11)
Re: Reduce/Reduce conflict in Algol60 grammar (Chris F Clark) (2006-10-12)
Re: Reduce/Reduce conflict in Algol60 grammar (SM Ryan) (2006-10-13)
Re: Reduce/Reduce conflict in Algol60 grammar (Ken Rose) (2006-10-14)
[3 later articles]
| List of all articles for this month |

From: Leonardo Teixeira Passos <>
Newsgroups: comp.compilers
Date: 10 Oct 2006 23:35:00 -0400
Organization: POP-MG/RNP
Keywords: algol60, question
Posted-Date: 10 Oct 2006 23:35:00 EDT

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]

Post a followup to this message

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