Re: Reduce/Reduce conflict in Algol60 grammar

Leonardo Teixeira Passos wrote:
> 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]


OR, instead of writing grammars that key off of terminals, use the
tokens, += << while, instead.


so that primary := '(' | ["].*["] | varname
etc.


for dangling if-else


you want to do,


if := 'if' truepart falseparts
truepart := '(' booltest ')' stmt
falsepart := 'else' stmt


boolops := [&] | [|]


etc
hope that helps.

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