10 Oct 2006 23:35:00 -0400

Related articles |
---|

Reduce/Reduce conflict in Algol60 grammar leonardo@dcc.ufmg.br (Leonardo Teixeira Passos) (2006-10-10) |

Re: Reduce/Reduce conflict in Algol60 grammar luvisi@andru.sonoma.edu (Andru Luvisi) (2006-10-11) |

Re: Reduce/Reduce conflict in Algol60 grammar idknow@gmail.com (idknow@gmail.com) (2006-10-11) |

Re: Reduce/Reduce conflict in Algol60 grammar wyrmwif@tsoft.org (SM Ryan) (2006-10-11) |

Re: Reduce/Reduce conflict in Algol60 grammar cfc@shell01.TheWorld.com (Chris F Clark) (2006-10-12) |

Re: Reduce/Reduce conflict in Algol60 grammar wyrmwif@tsoft.org (SM Ryan) (2006-10-13) |

Re: Reduce/Reduce conflict in Algol60 grammar kenrose@nc-sys.com (Ken Rose) (2006-10-14) |

[3 later articles] |

From: | Leonardo Teixeira Passos <leonardo@dcc.ufmg.br> |

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.