• Requirements
You are expected to complete all required exercises in this assignment. For submission, please put all your answers in a single PDF file and submit it via the assignment channel on SAKAI.
• Bottom-Up Parsing Exercises (100 points)
Exercise 1 (Simple LR): Consider the following grammar G:
S → aB
B→S∗B|ϵ
1. Construct the SLR(1) parsing table for G. Please put down the detailed steps, including the calculations of LR(0) item sets. For the calculations of closures, GOTO targets, and FIRST/FOLLOW, you may choose not to put down the internal details. [20 points]
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
SUSTech CS323 - Compilers November 8, 2022
Exercise 2 (Canonical LR): Consider the grammar G in Exercise 1:
1. Construct the canonical LR(1) parsing table for G. Please put down the detailed steps, including the calculations of LR(1) item sets. For the calculations of closures, GOTO targets, and FIRST/FOLLOW, you may choose not to put down the internal details. [20 points]
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, in-cluding 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
