Help needed on LALR(1) ambiguity

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

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