Re: Help needed on LALR(1) ambiguity

philip.k.chow@gmail.com writes:
> 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.


Generally speaking, you should try to avoid right-recursive grammars
when using LR-parsers, not just for efficiency reasons but also because
LR parsers sometimes have trouble handling complex right-recursive
grammars.


In your example, making the second production of "Names" left-recursive
makes the grammar LALR(1). Yacc detects no conflicts for the following
grammar:




%token ID
%token ALL
%token BAR
%token COLON
%token COMMA


%start expr


%%


expr : ID
          | ALL ID
          | ALL decl BAR expr


names : ID COLON
            | names COMMA ID


decl : names expr COMMA decl
          | names expr


%%




Indeed, the following grammar is LR(0)


A -> AB
A -> xx
B -> x


while its mirror image is not even LR(1):


A -> BA
A -> xx
B -> x




Sven-Olof NystrC6m

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