1 Requirements
2 Bottom-Up Parsing Exercises (100 points)
Exercise 1 (Simple LR): Consider the following grammar G:
S → aB
B → S ∗ B | ϵ
2. Is the grammar SLR(1)? [5 points]
3. If your answer to the above question is “yes”, then can the SLR(1) parser accept the input string aaaa***? If the input string can be accepted, please list the moves made by the parser; otherwise, state the reason. If your answer to the above question is “no”, please explain why the grammar is not SLR(1). [10 points]
1
Exercise 2 (Canonical LR): Consider the grammar G in Exercise 1:
2. Is the grammar LR(1)? [5 points]
3. If your answer to the above question is “yes”, then can the canonical LR(1) parser accept the input string aaaa***? If the string can be accepted, please list the moves made by the parser; otherwise, state the reason. If your answer to the above question is “no”, please explain why the grammar is not LR(1). [10 points]
Exercise 3 (Lookahead LR): Consider the grammar G in Exercise 1:
1. Construct the LALR(1) parsing table for G. Please put down the detailed steps, including the merging of LR(1) item sets. [15 points]
2. Is the grammar LALR(1)? [5 points]
3. If your answer to the above question is “yes”, then can the LALR(1) parser accept the input string aaaa***? If the string can be accepted, please list the moves made by the parser; otherwise, state the reason. If your answer to the above question is “no”, please explain why the grammar is not LALR(1). [10 points]
2
