Re: Looking for formal definition of LALR(k)

Ziemowit Laski <laski@ics.uci.edu>
24 Oct 1998 01:50:19 -0400

          From comp.compilers

Related articles
Looking for formal definition of LALR(k) laski@ics.uci.edu (Ziemowit Laski) (1998-10-17)
Re:Looking for formal definition of LALR(k) KPRASAD@us.oracle.com (KPRASAD.US.ORACLE.COM) (1998-10-21)
Re: Looking for formal definition of LALR(k) matt@timmermans.no-spam-remove.org (Matt Timmermans) (1998-10-22)
Re: Looking for formal definition of LALR(k) laski@ics.uci.edu (Ziemowit Laski) (1998-10-22)
Re: Looking for formal definition of LALR(k) laski@ics.uci.edu (Ziemowit Laski) (1998-10-24)
| List of all articles for this month |

From: Ziemowit Laski <laski@ics.uci.edu>
Newsgroups: comp.compilers
Date: 24 Oct 1998 01:50:19 -0400
Organization: Compilers Central
References: <199810230525.WAA28269@mailsun2.us.oracle.com>
Keywords: parse, theory

KPRASAD.US.ORACLE.COM wrote:


> are you aware of a grammar that can be parsed by LR(k) and not LALR(k)?
> pl. provide examples
> thanks
> -kama


I don't have my dragon book next to me :), but I'll try to reconstruct the
example they gave: S -> aAa | aBb | bAb | bAa A -> c
        B -> c
The LR(k) parser will have two states {[A->c.|a],[B->c.|b]} and
{[A->c.|b],[B->c.|a]}, among others. When merged, they produce the LALR(k)
state {[A->c.|a,b],[B->c.|a,b]} with overlapping lookahead sets (i.e.,
reduce-reduce conflicts).


Zem


Post a followup to this message

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