#Homework 3#

Due date: 2016-06-17

---

1. #####Consider the context-free grammar:
   S -> S S + | S S * | a and the string aa + a*.

   1. Give a leftmost derivation for the string.
   2. Give a rightmost derivation for the string.
   3. Give a parse tree for the string.

2. #####Construct unambiguous context-free grammars for each of the following languages.

   1. Arithmetic expressions of integers and identifiers with the four binary operators +, -, *, /.
   2. Add unary plus and minus to the arithmetic operators of the previous question.

3. #####Is it possible, by modifying the grammar in any way, to construct a predictive parser for the language of Question 1 (postfix expressions with operand a)?

4. #####Compute FIRST and FOLLEW for the grammar of Question 1.

5. #####For the SDD shown below, give annotated parse trees for the following expressions:

   1. (3+4)*(5+6) n.
   2. 1*2*3*(4+5) n.