4.9 Consider the following grammar: lexp→atom|list atom →number|identifier list→(lexp-seq) lexp-seq→lexp, lexp-seq|lexp a. Left factor this grammar. b. Construct First and Follow sets for the nonterminals of the resulting grammar. c. Show that the resulting grammar is LL(1). d. Construct the LL(1) parsing table for the resulting grammar. e. Show the actions of the corresponding LL(1) parser, given the input string (a,(b,(2)),(c)).

a. Left factored grammar:

lexp → atom | list
atom → number A | identifier A
A → ε | , lexp A
list → ( lexp-seq )
lexp-seq → lexp B
B → ε | , lexp-seq

b. First and Follow sets:

FIRST(lexp) = {number, identifier, (}
FOLLOW(lexp) = {), ,}

FIRST(atom) = {number, identifier}
FOLLOW(atom) = {), ,}

FIRST(A) = {ε, ,}
FOLLOW(A) = {), ,}

FIRST(list) = {(}
FOLLOW(list) = {), ,}

FIRST(lexp-seq) = {number, identifier, (}
FOLLOW(lexp-seq) = {)}

FIRST(B) = {ε, ,}
FOLLOW(B) = {)}

c. The grammar is LL(1) because each nonterminal has distinct sets of FIRST and FOLLOW symbols, and there are no conflicts in the LL(1) parsing table.

d. LL(1) parsing table:

| | number | identifier | ( | ) | , |
|------------|--------|------------|-----|-----|-----|
| lexp | atom | atom | list | | |
| atom | number | identifier | | | |
| A | ε | , lexp A | | ) | , |
| list | | | ( lexp-seq ) | | |
| lexp-seq | atom | atom | list | | |
| B | ε | , lexp B | | ) | , |

e. Parsing the input string `(a,(b,(2)),(c))`:

| Stack | Input | Action |
|-------|-------|--------|
| $ | (a,(b,(2)),(c))$ | shift, push ( |
| $(, $ | a,(b,(2)),(c))$ | shift, push a |
| $(, a, $ | ,(b,(2)),(c))$ | shift, push , |
| $(, a, ,, $ | (b,(2)),(c))$ | shift, push ( |
| $(, a, ,, (, $ | b,(2)),(c))$ | shift, push b |
| $(, a, ,, (, b, $ | ,(2)),(c))$ | shift, push , |
| $(, a, ,, (, b, ,, $ | (2)),(c))$ | shift, push ( |
| $(, a, ,, (, b, ,, (, $ | 2)),(c))$ | shift, push 2 |
| $(, a, ,, (, b, ,, (, 2, $ | )),(c))$ | shift, pop 2, pop (, reduce to atom |
| $(, a, ,, (, b, ,, atom, $ | ),(c))$ | shift, pop atom, reduce to lexp |
| $(, a, ,, (, list, $ | ),(c))$ | shift, pop ), reduce to lexp-seq |
| $(, a, ,, lexp-seq, $ | ,(c))$ | shift, push , |
| $(, a, ,, lexp-seq, ,, $ | (c))$ | shift, push ( |
| $(, a, ,, lexp-seq, ,, (, $ | c))$ | shift, push c |
| $(, a, ,, lexp-seq, ,, (, c, $ | ), $ | shift, pop c, pop (, reduce to atom |
| $(, a, ,, lexp-seq, ,, atom, $ | ) | shift, pop atom, reduce to lexp |
| $(, a, ,, list, $ | ) | shift, pop ), reduce to lexp-seq |
| $(, lexp, $ | $ | shift, push $ |
| $ | $ | accept |