CS 412/413
Introduction to Compilers
Spring 2002

Homework 2: Syntax Analysis

due: Monday, February 18, in class

1. Write an unambiguous grammar for each of the following languages:

   a) Strings of a's followed by b's which have twice more a's than b's
   b) Strings of a's and b's with the same number of a's and b's

2. a) Calculate nullable, FIRST, FOLLOW for the following gramar:

   S -> u B D z 
B -> B v | w
D -> E F
E -> y | e
F -> x | e

   b) Construct the LL(1) parsing table and give evidence that this grammar is not LL(1)
   d) Give an LL(1) grammar which accepts the same language and build the LL(1) parsing table for that grammar  
   

3. Consider the following grammar:

E -> E + E  |  E * E  |  ( E ) |  num 

This is an ambiguous grammar. We would like an unambiguous  grammar where multiplication (*) has higher precedence over addition (+). 
a) write an LL(1) grammar which accepts the same language and respects the desired operator precedence
b) show the derivation tree for the expression 1+2*3*4+5
c) write an LR(1) grammar which accepts the same language, respects the desired operator precedence, and is such that multiplication is left-associative, and addition is right-associative.

4. Show that this grammar is LALR(1), but not SLR:

   S -> A a  |  b A c  |  d c  |  b d a  
A -> d

5. Show that the following grammar is LR(1), but not LALR(1):

   S -> A a  |  b A c  |  B c  | b B a
A -> d
B -> d