Re: Help needed on LALR(1) ambiguity

Sven-Olof Nystrom <svenolof.nystrom-nospam@bredband.net>
Tue, 18 Nov 2008 15:40:46 +0100

          From comp.compilers

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)
| List of all articles for this month |

From: Sven-Olof Nystrom <svenolof.nystrom-nospam@bredband.net>
Newsgroups: comp.compilers
Date: Tue, 18 Nov 2008 15:40:46 +0100
Organization: A noiseless patient Spider
References: 08-11-055
Keywords: parse
Posted-Date: 18 Nov 2008 19:11:22 EST

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



Post a followup to this message

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