Comparative Programming Languages
Homework 1

1. Given the grammar:

   E --> E + T
       | E - T
       | T
   T --> T * F
       | T / F
       | F
   F --> ( E )
       | number
   

   1. Give the parse tree and the leftmost derivation for the string 3 * (4 + 2) * 2
   2. Extend the grammar, adding a unary minus with a higher precedence than +, -, *, /
2. Given the grammar:

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

   list of the strings of length 6 or less that are in the language.
3. Prove that the following grammar is ambiguous
   (show that there are two valid parse trees for the same expression):

   S --> a S b S
   S --> b S a S
   S --> lambda
   

4. Write a grammar that generates integers of any length but with no leading zeros. Use the productions D --> 0 | ... | 9 in your grammar.
5. Consider the following grammar:

   A --> B C
   B --> a D
   C --> E f F G
   D --> h
   D --> b B c
   D --> C c
   E --> d
   E --> e
   F --> f F
   F --> a
   G --> C
   G --> g
   

   A is the start symbol, uppercase letters are non-terminals, lowercase letters are terminals.
   1. Give two strings in the language
   2. Compute First sets for all non-terminals
   3. Give a Recursive Descent parser for the grammar.