Re: LR(1) resolving SLR(1) reduce/reduce conflict

gvcormac@speedy.uwaterloo.ca (Gordon Cormack)30 Mar 2003 21:40:18 -0500

From comp.compilers

Related articles
LR(1) resolving SLR(1) reduce/reduce conflict haberg@math.su.se (2003-03-30)
Re: LR(1) resolving SLR(1) reduce/reduce conflict gvcormac@speedy.uwaterloo.ca (2003-03-30)
Re: LR(1) resolving SLR(1) reduce/reduce conflict haberg@math.su.se (2003-03-31)
Re: LR(1) resolving SLR(1) reduce/reduce conflict gvcormac@speedy.uwaterloo.ca (2003-04-05)
Re: LR(1) resolving SLR(1) reduce/reduce conflict haberg@math.su.se (2003-04-07)
| List of all articles for this month |

 From: gvcormac@speedy.uwaterloo.ca (Gordon Cormack) Newsgroups: comp.compilers Date: 30 Mar 2003 21:40:18 -0500 Organization: A poorly-installed InterNetNews site References: 03-03-181 Keywords: parse, LR(1) Posted-Date: 30 Mar 2003 21:40:18 EST

Hans Aberg <haberg@math.su.se> wrote:
>Is it possible for LR(1) to resolve a reduce/reduce conflict appearing in
>SLR(1)?

The following grammar is LR(1) but not SLR(1) or LALR(1)

S -> A x B x
S -> B y A y
A -> w
B -> w

In the LR(0) machine you have a state that looks like this:

A -> w .
B -> w .

SLR(1) uses follow(A) = {x,y} as the lookahead for the first item
and follow(B) = {x,y} as the lookahead for the second,
so ther's a reduce-reduce conflict.

LR(1) has two different states:

A -> w . { x }
A -> w . { y }

and

A -> w . { y }
A -> w . { x }

Neither state has a conflict.

LALR(1) merges these two LR(1) states, because they have the same
core. The net results is the same as for SLR(1) - a reduce-reduce conflict.

Post a followup to this message