• Requirements
You are expected to complete all required homework exercises and encouraged to complete the optional ones. For submission, please put all your answers in a single PDF file and submit it via the assignment channel on SAKAI. The name of the file should follow the format “studentID_A#” (e.g., 30003554_A3). Late submissions are allowed within one week after the deadline (grace period). If you submit your assignment during the grace period, your score will be 80% of the score you could get if the submission was made in time. Assignment submitted after the grace period will not be graded, meaning that you will get a zero for the assignment.
• 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
SUSTech CS323 - Compilers October 18, 2022
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]
• 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
