For this homework assignment, submit your answers as a PDF file (no other
file format, PDF only!) The PDF file must have the name 1234567890.pdf
(replace 1234567890 with your own student ID number).
Late homework assignments will not be accepted, unless you have a valid
written excuse (medical, etc.). You must do this assignment alone. No
team work or “talking with your friends” will be accepted. No copying from
the Internet. Cheating means zero.
Note: EXPLAIN your answers in DETAIL for all the questions below.
Consider the following context-free grammar for arithmetic expressions:
E -> E + E
E -> E * E
E -> id
where ¡¯+¡¯, ¡¯*¡¯, and ¡¯id¡¯ are tokens.
1) Augment the grammar with a new nonterminal E¡¯.
2) Use the Sets-of-Items Construction Algorithm to construct the sets of
LR(0) items for the augmented grammar of Question 1. Construct at the same
time the corresponding DFA. Explain in detail every step.
Note: during the construction of the sets of items and the DFA, always
consider the grammar symbols in the following order: +, *, id, E
You will lose points if you consider grammar symbols in a different order.
3) Construct the SLR(1) parsing table, based on the results of Question 2.
Explain in detail.
Note: grammar symbols at the top of the table must appear in the following
order from left to right: +, *, id, $, E.
You will lose points if you use a different order. State numbers start
from zero.
4) What is the problem with the SLR(1) parsing table you constructed in
Question 3? What is the original cause of the problem?
5) Manually modify the SLR(1) parsing table of Question 3 to solve the
problem. The resulting table must encode the usual behavior for arithmetic
expressions (+ and * are left-associative, and * has precedence over +).
Justify in detail each of your modifications.
Hint: as you try to solve the problem, look at the sets of items, the DFA,
and the parsing table. Remember that, when a parser uses the parsing
table, the content of the parser¡¯s stack corresponds to a path in the DFA.
6) Use the modified SLR(1) parsing table from Question 5 to parse the
following input:
id + id + id * id * id
7) Construct a derivation and a parse tree based on the results of Question
6. Verify that the shape of the parse tree is coherent with the way you
modified the SLR(1) parsing table in Question 5. Explain how you verify
that.