1 Requirements
2 Required Exercises (100 points)
Exercise 1 (Grammar Basics): Consider the following context-free grammar G:
S→SS+ | SS∗ | a
1. Give a leftmost derivation for the string aa∗aa+∗. [10 points]
2. Give a rightmost derivation for the string aa∗aa+∗. [10 points]
3. Give a parse tree for the string aa∗aa+∗. [10 points]
4. Give an equivalent grammar without immediate left recursions. [10 points]
5. Is the grammar ambiguous? [10 points]
1
Exercise 2 (Top-Down Parsing): Consider the following grammar G:
S→aB
B→S∗B | !
1. Construct the predictive parsing table for G. Please put down the detailed steps, including the calculation of FIRST and FOLLOW sets. [25 points]
2. Is the grammar LL(1)? [5 points]
3. Can an LL(1) parser accept the input string aaaa***? If yes, please list the moves made by the parser; otherwise, state the reason. Before parsing, please resolve conflicts in the parsing table if any. [20 points]
3 Optional Exercise (10 bonus points)
1. Justify your answer to Question 5 of Exercise 1. You do not need to provide a very rigorous proof. Informal explanations/examples are also acceptable.
2
