Chapter 4 Exercises

For the expression grammar
E --> E + T | T
T --> T * F | F
F --> (E) | Id
find (a) FIRST (T), FIRST (T * Id) and (b) FOLLOW (E).
Show that the following grammar is not LL(1)
A --> d A
A --> d B
A --> f
B --> g
Show that the following grammar is not LL(1).
S --> X d
X --> C
X--> B a
C -->
B --> d
Write algorithms for computing FIRST and FOLLOW.
Rewrite the table in Example 4, as a programming procedure (using your favorite high-level language).
Given the grammar:
S --> XX
X -->xX
X --> y
(a) Show that it is LL(1).
(b) Create a parsing table.
(c) Parse the string xyyx .
(d) Draw the parse tree.
For the grammar:
E --> T E'
E' --> + T E' |
T --> F T'
T' --> * F T' |
F --> Id | (E)
(a) Show that the FIRST (E) = { (, Id }
(b) Show that FOLLOW (T) = { +, ) }
Consider the grammar: E --> E + T | T
T --> T * F | F
F --> (E) | Id
(a) Left-recursion: Show what would happen if we tried to parse a*b + c using this grammar.
(b) Eliminate the left-recursion from each production of this grammar to produce the grammar in Example 7.
(a) Show that the grammar
E --> E + E | E - E | E * E | E / E | ( E ) | Id
is ambiguous (produces more than one parse is for a given input).
(b) Show that an ambiguous grammar cannot be LL(1).
The procedure for elimination of left-recursion need not be used if the grammar is not left-recursive. Write an algorithm that will test a grammar for left-recursion.
(a) Show that the assignment statement grammar of Chapters 1 and 2 has an indirect form of common prefix. The process of showing that it is not LL(1) will expose this.
(b)Derive an algorithm for eliminating this problem.
Parsing non-LL(1) languages top-down anyway: It is sometimes possible tp parse a non-LL(1) or even ambiguous language top-down by resolving the choices at parse time. Consider the following grammar which abstracts IF-THEN-ELSE statements (i = F, t = THEN, e = ELSE, a = terminal statement c= condition):
```
        S -->i  E  t S 
                |  i  E  t  S  e  S 

                |  i  E  t  S  e  S 

        E --> c
```
(a) Show that this grammar is not LL(1)
(b) Create an LL(1) parsing table. (Since the grammar is not LL(1), there will be at least one double entry.)
(c) Show a top-down parse for:
associating "ELSE" with the closest IF, i.e., choose the table entry that will enforce this:
Compute the FIRST and FOLLOW sets for all the nonterminals in the executable part of RoBOTL statements.