Question

Show a complete bottom-up parse, including the parse stack contents, input string, and action for the string below using the parse table

String: (id+id) * id

Grammar(language) :

E -> E + T |E * T | T

T -> (E) | id

Parse table:

R-reduce S-Shift - Error id S4 S5 S6 S7 Accept R1 R1 R1 R1 4 S4 S5 R6 R6 R6 R6 S4 S5 10 7 S4 S5 S6 R2 R3 R5 S7 R2 R3 R5 S11 R2 R3 R5 8 R2 R3 R5 10 Firsrt(T) = {c, id Follow(E) S,+,*.)) First(E)[c, id) Follow(T)-($,+,*

Then show a rightmost derivation for the string above and show how the bottom up parse correctly finds all of the handles.

Answer 1

It seems one accidental mistake in The Table given by you. In row I3, It will be R4 instead of R1.

I have provided modified table below(bolden)

R-reduce S-Shift - Error id S4 S5 S7 Accept S6 R4 R4 R4 R4 4 S4 S5 R6 R6 R6 R6 S4 S5 10 7 S4 S5 S6 R2 R3 R5 S7 R2 R3 R5 S11 R2 R3 R5 8 R2 R3 R5 10 Firsrt(T) -[c, id Follow(E) S,+,*.)) First(E)[c, id) Follow(T) (S,+,

The following is the answer

Bottom up Parsing with given parsing table

Configuration of stack content and input string

   Stack                                                  InputString

I1 x1S1 x2S2..xmSm                       ai ai+1..    am$

                                                I1: initial Items,

x1: symbols   Sm: state , ai: symbols in input string

Parsing rule:

Check the entries in Action Table.

1. If ACTION[sm,ai]=Shift N, then make a shift move , the configuration will be as below

I1 x1S1 x2S2..xmSm aiN                ai+1..    am$

1. If ACTION[sm,ai]=Reduce a->? ,then make a reduce move, Configuration will be as below

I1 x1S1 x2S2..xmSm xm-rSm-rAN              ai ai+1..    am$

Where r=len[?],   A=Production head

N: entry in the GOTO[sm-r,A]                   

1. If ACTION[sm,ai]=ACCEPT, ,parsing completed successfully.
2. If ACTION[sm,ai]=EROR,   the string cannot be parsed

TAC ACTION Shift 4 shift 5 Reduce by R6 ieT->id Reduce by R4 le E->T Shift 6 shift 5 Reduce by T->id Reduce by E->E+T shift 11 Reduce by T->(E) Reduce by E->T shift 7 shift 5 Reduce by T->id Reduce by E->E*T ACCEPT (idtid) id$ idtid)Fid $ tid)*id$ tid)*id$ tid)*id$ id) *id $ 1 (4 1 (4 id5 1 (4 T3 1 (4 E8 1 (4 E8 +6 1 (4 E8 +6 id5 1 (4 E8 +6 T9 1 (4 E8 1 (4 E8111 1 T3 1 E2 1 E2 7 1 E2 *7 id5 1 E2 *7 T10 1 E2 id $ id $ id $ *id $ *id $ 치d $

2 ナナブブ