11 Oct 2006 23:22:06 -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) |

Re: Reduce/Reduce conflict in Algol60 grammar bobduff@shell01.TheWorld.com (Robert A Duff) (2006-10-14) |

Re: Reduce/Reduce conflict in Algol60 grammar DrDiettrich1@aol.com (Hans-Peter Diettrich) (2006-10-14) |

[1 later articles] |

From: | "idknow@gmail.com" <idknow@gmail.com> |

Newsgroups: | comp.compilers |

Date: | 11 Oct 2006 23:22:06 -0400 |

Organization: | Compilers Central |

References: | 06-10-036 |

Keywords: | algol60, syntax |

Posted-Date: | 11 Oct 2006 23:22:06 EDT |

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.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.