Description
-
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
-
Give a leftmost derivation for the string aa ∗ aa + ∗. [10 points]
-
Give a rightmost derivation for the string aa ∗ aa + ∗. [10 points]
-
Give a parse tree for the string aa ∗ aa + ∗. [10 points]
-
Give an equivalent grammar without immediate left recursions. [10 points]
-
Is the grammar ambiguous? [10 points]
SUSTech CS323 – Compilers October 18, 2022
Exercise 2 (Top-Down Parsing): Consider the following grammar G:
S → aB
B→S∗B|
-
Construct the predictive parsing table for G. Please put down the detailed steps, including the calculation of FIRST and FOLLOW sets. [25 points]
-
Is the grammar LL(1)? [5 points]
-
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)
-
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
