Fri, 14 Nov 2008 08:41:03 -0800 (PST)

Related articles |
---|

Help needed on LALR(1) ambiguity philip.k.chow@gmail.com (2008-11-14) |

Re: Help needed on LALR(1) ambiguity cdodd@acm.org (Chris Dodd) (2008-11-17) |

Re: Help needed on LALR(1) ambiguity armelasselin@hotmail.com (Armel) (2008-11-17) |

Re: Help needed on LALR(1) ambiguity svenolof.nystrom-nospam@bredband.net (Sven-Olof Nystrom) (2008-11-18) |

Re: Help needed on LALR(1) ambiguity philip.k.chow@gmail.com (2008-11-18) |

Re: Help needed on LALR(1) ambiguity Danny.Dube@ift.ulaval.ca (2008-12-01) |

From: | philip.k.chow@gmail.com |

Newsgroups: | comp.compilers |

Date: | Fri, 14 Nov 2008 08:41:03 -0800 (PST) |

Organization: | Compilers Central |

Keywords: | LALR, question |

Posted-Date: | 15 Nov 2008 06:13:19 EST |

Hello:

I'm trying to remove ambiguity from the following LALR(1) grammar.

Currently our tool uses tricky lexer hacks to get it to parse,

but I was hoping someone with more expertise can help make it LALR(1):

(The full grammar contains many many rules and has tricky features

that make it not LL(k), so LL(k) and pred-LL(k) and PEG are not an

option for us. The large grammar also makes GLR performance

unacceptable unfortunately):

Expr : ID ;

Expr : ALL ID ;

Expr : ALL Decl BAR Expr ;

Names : ID COLON ;

Names : ID COMMA Names ;

Decl : Names Expr COMMA Decl ;

Decl : Names Expr ;

Forcing the shift-reduce decision one-way-or-the-other doesn't work,

since sometimes it really should shift, and sometimes it should

reduce. I've also tried several standard techniques of grammar

refactoring, but I haven't succeeded.

To help get an intuition for the language (which is a well known

standard language), here are some simple examples of legal sentences:

---

// the value of a

a

// the expanded value of a

all a

// y is true for every possible values of a and b selected from x

all a,b:x | y

// y is true for every possible values of a and b selected from "all x"

all a,b: all x | y

---

Here is a tricky sentence that demonstrates why it's hard:

all a: all b, c: all d | x

This has only one legal parse (parentheses added for clarification):

all (a:all b), (c:all d) | x

Note that in the correct parse, b and d belong to two different

subtrees.

As far as I can tell, the LALR(1) parsing table gets confused because

when matched from the right, everything except the first 3 tokens look

like they should be parsed totally differently like this: (where b and

d now are part of the same subtree):

all (b,c : all d) | x

If any one has suggestions, please let me know. Thanks!

Sincerely,

C

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.