0
$\begingroup$

I understand the concept of LR(1) parsing and lookahead symbols. I have the solution to the exercise and it does not agree with my solution.

I'm trying to fill the LR(1) parsing table for the grammar below:

S->xAz 
S->BAx
A->Ay
A->e
B->yB
B->y

Ι don't have to extend the grammar since S does not appear in any right hand side of any rule.

First(A)=y,e
First(Ax)=x,y
First(B)=y
First(Ay)=y

Lookahead symbols in brackets.

So, I0 = Closure(S->.xAz($) , S->.BAx($) ) =

S->.xAz($)
S->.BAx($)
B->.yB(x,y)
B->.y(x,y)

When i try GOTO(0,x) i think that i should go to:

S->x.Az($)
A->.Ay(z)
A->. (z) 

To find the lookahead symbol for A->. & A->.Ay i take First(z). But the official book solution says the lookeahead is (z,y). Where does that y comes from?

Thank you in advance!

$\endgroup$
0
$\begingroup$

Since $A\to .Ay$ is in the state constructed for $GOTO(0, x)$, $A\to .A(y)$ and $A\to .(y)$ are also in that state. These combine with the other items for the same productions, which have lookahead $z$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you so much! If we combine the items that have the same LR(0) but different lookahead symbols, eg A->.Ay(z) & A->Ay(y) we also show that the grammar is LALR(1), correct? $\endgroup$ – Nikos Dec 1 '19 at 3:57
  • $\begingroup$ @Nikos: No. The combination of items for LALR(1) grammars has to do with combining items from two different LR(1) states. Here, we're simply looking at a single LR(1) state, and the combination of lookahead sets is essentially a notational convenience (so that the same item doesn't appear twice in the same state). $\endgroup$ – rici Dec 1 '19 at 4:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.