Chapter 4 Exercises

1. 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).

2. Show that the following grammar is not LL(1)

   A --> d A

   A --> d B

   A --> f

   B --> g

3. Show that the following grammar is not LL(1).

   S --> X d

   X --> C

   X--> B a

   C -->

   B --> d

4. Write algorithms for computing FIRST and FOLLOW.
5. Rewrite the table in Example 4, as a programming procedure (using your favorite high-level language).
6. 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 xyxyy.

   (d) Draw the parse tree.

7. 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) = { +, ) }

8. 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.

9. (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).

10. 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.
11. (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.

12. 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:

    IF c THEN IF c THEN a ELSE a

    associating "ELSE" with the closest IF, i.e., choose the table entry that will enforce this:

13. Compute the FIRST and FOLLOW sets for all the nonterminals in the executable part of RoBOTL statements.