Quiz 4: Top-Down Parsing

Quiz Posted
(Thursdays)
Given in class
(Thursdays)
31 Jan 7 Feb
  1. Exercise 12 on page 110.
  2. Compute First and Follow sets for the grammar shown in Exercise 2 on page 137. Augment that grammar with the rule S-->Expr $.
  3. Exercise 1 on page 137, parts a and c.
  4. Exercise 2 on page 137.
  5. Exercise 4 on page 138. Recall that you must eliminate any left recursion, and make the predict sets distinct for each rule of any given nonterminal.
  6. Design a grammar whose language is the set of all regular expressions over $a$ and $b$. Examples of such regular expressions are: Your grammar must be unambiguous, and must enforce the precedence of * over concatenation over |; each operator is left associative.
Extra credit: While it is known that one can always eliminate left recursion from a grammar, it is not true that every grammar can be made LL(k). Construct an unambiguous grammar for a language that has no LL(k) grammar for any k.