HW4_sol

1Answer:
(1) A leftmost derivation for the sentence "a(aa)":

E ⇒lm L ​

⇒lm (S ) ​

⇒lm (SS )​

⇒lm (ES )​

⇒lm (aS )​

⇒lm (aE )​

​
⇒lm (aL) ​

⇒lm (a(S ))
​

⇒lm (a(SS ))
​

⇒lm (a(ES ))
​

⇒lm (a(aS ))
​

⇒lm (a(aE ))
​

⇒lm (a(aa))
​

(2) Grammar after eliminating left recursion:

E → L ∣ a

L → (S )

′
​ ​

S → ES

′ ′
S → SS ∣ ε

(3) First and Follow sets of non-terminal symbols after removing left recursion:

First(E ) = First(S ) = {a, (}

First(L) = {(}

′
First(S ) = {a, (, ε}
​ ​

Follow(E ) = Follow(L) = {a, (, ), $}

′
Follow(S ) = Follow(S ) = {a, (, )}

(4) LL(1) Parsing Table:

a  (  )  $

E E→a E→L

L L → (S)

S S → ES' S → ES'

S′ S′ → SS′ | ε S′ → SS′ | ε S′ → ε

(5) Parsing process for the sentence "aa":

Input String Parse Stack Parsing Action

(aa)$ E$ E→L

(aa)$ L$ L → (S)

(aa)$ (S)$ match-advance

aa)$ S)$ S → ES′

HW4_sol 1
 aa)$ ES′)$ E→a

aa)$ aS′)$ match-advance

a)$ S′)$ S′ → SS′

a)$ ES’S′)$ S → ES′

a)$ ES′S′)$ E → aS’

)$ S′S′)$ S′ → ε

)$ S′)$ S′ → ε

)$ )$ match-advance

$ $ Parsing successful

2Answer:
(1)

(2)

(∗(a ∣ ε)

(3) SLR Parsing Table:

First sets:

First(E ) = First(S ) = {a, (}

​ ​

First(L) = {(}

Follow sets:

Follow(E ) = Follow(L) = {a, (, ), $}

​ ​

Follow(S ) = {a, (, )}

SLR Parsing Table:

action goto

HW4_sol 2
 State a ( ) $ E L S

0 s4 s1 2 3

1 s4 s1 5 3 6

2 acc

3 r1 r1 r1 r1

4 r2 r2 r2 r2

5 r5 r5 r5

6 s4 s1 s7 5 3 8

7 r3 r3 r3 r3

8 s4 s1 r4 5 3 8

(4) Parsing process for the input string "(aa)":

Remaining Input Parsing Stack Action

(aa)$ 0 shift

aa)$ 0(1 shift

a)$ 0(1a4 reduceE → a 

a)$ 0(1E5 reduceS → E 

a)$ 0(1S6 shift

)$ 0(1S6a4 reduceE → a 

)$ 0(1S6E5 reduceS → E 

)$ 0(1S6S8 reduceS → SS 

)$ 0(1S6 shift

$ 0(1S6)7 reduceL → (S ) 

$ 0L3 reduceE → L 

$ 0E2 accept

HW4_sol 3