Here is the complete set of answers formatted cleanly and line-by-line so you can easily copy
and paste it directly into your Word or Google Document without any formatting issues.
Question 1: LR(0) Items, SLR Parsing, and Conflicts
Assumption for Question 1: The provided grammar text had a few OCR (optical character
recognition) errors. I am using the standard pointer-assignment grammar commonly used to
teach this exact shift/reduce conflict:
Grammar:
S -> L = R
S -> R
L -> * R
L -> id
R -> L
Input String: * id = id
a) Canonical Collection of LR(0) Items
First, we add the augmented start symbol S' -> S.
Item Set 0 (I0):
S' -> .S
S -> .L = R
S -> .R
L -> .* R
L -> .id
R -> .L
Item Set 1 (I1) = goto(I0, S):
S' -> S.
Item Set 2 (I2) = goto(I0, L):
S -> L . = R
R -> L.
Item Set 3 (I3) = goto(I0, R):
S -> R.
Item Set 4 (I4) = goto(I0, *):
L -> * . R
R -> . L
L -> . * R
L -> . id
Item Set 5 (I5) = goto(I0, id):
L -> id.
Item Set 6 (I6) = goto(I2, =):
S -> L = . R
R -> . L
L -> . * R
L -> . id
Item Set 7 (I7) = goto(I4, R):
L -> * R.
Item Set 8 (I8) = goto(I4, L) and goto(I6, L):
R -> L.
Item Set 9 (I9) = goto(I6, R):
S -> L = R.
(b) SLR Parsing Table
To build the table, we need the FOLLOW sets:
FOLLOW(S) = { $ }
FOLLOW(L) = { =, $ }
FOLLOW(R) = { =, $ }
(Note: 's' means shift, 'r' means reduce, and the numbers are states or grammar rules).
c) Trace and Shift-Reduce Conflicts
Identify the Conflict:
In State 2 (I2), there is a Shift/Reduce conflict on the terminal "=".
The parser can SHIFT to State 6 (based on S -> L . = R).
The parser can REDUCE by rule 5 (based on R -> L., since "=" is in FOLLOW(R)).
Because both actions exist in the same table cell, this grammar is NOT SLR(1).
Trace of input "* id = id" (Resolving the conflict by choosing Shift):
Step Stack Input Buffer Action
1 0 * id = id $ Shift to 4
2 0 * 4 id = id $ Shift to 5
3 0 * 4 id 5 = id $ Reduce by L -> id (goto 8)
4 0 * 4 L 8 = id $ Reduce by R -> L (goto 7)
5 0 * 4 R 7 = id $ Reduce by L -> * R (goto 2)
6 0 L 2 = id $ Shift to 6 (Conflict resolved)
7 0 L 2 = 6 id $ Shift to 5
8 0 L 2 = 6 id 5 $ Reduce by L -> id (goto 8)
9 0 L 2 = 6 L 8 $ Reduce by R -> L (goto 9)
10 0 L 2 = 6 R 9 $ Reduce by S -> L = R (goto 1)
11 0 S 1 $ Accept
Question 4: Syntax-Directed Translation and Intermediate Code
a) SDTS for a Desk Calculator
This Syntax-Directed Translation Scheme (SDTS) evaluates arithmetic expressions utilizing a
synthesized attribute called "val".
Production Rule Semantic Rule
L -> E \n print([Link])
E -> E1 + T [Link] = [Link] + [Link]
E -> T [Link] = [Link]
T -> T1 * F [Link] = [Link] * [Link]
T -> F [Link] = [Link]
F -> ( E ) [Link] = [Link]
F -> digit [Link] = [Link]
) Semantic Rules for Switch Statement utilizing Backpatching
Given construct: switch (expr) { case 1: stmt1; case 2: stmt2; default: stmt3; }
Semantic Actions and Intermediate Code Generation:
Evaluate the main expression:
[Link] = evaluate(E)
Generate the conditional jump tests for the cases:
test1_instr = nextinstr()
emit('if', [Link], '== 1 goto _')
test2_instr = nextinstr()
emit('if', [Link], '== 2 goto _')
default_instr = nextinstr()
emit('goto _')
Process Case 1:
M1 = nextinstr()
generate_code(stmt1)
J1_instr = nextinstr()
emit('goto _') // Jump out of switch block
Process Case 2:
M2 = nextinstr()
generate_code(stmt2)
J2_instr = nextinstr()
emit('goto _') // Jump out of switch block
Process Default:
M3 = nextinstr()
generate_code(stmt3)
Apply Backpatching to fill in the target labels for the tests:
backpatch(makelist(test1_instr), M1)
backpatch(makelist(test2_instr), M2)
backpatch(makelist(default_instr), M3)
Merge exit lists to handle jumps out of the switch block:
[Link] = merge([Link], merge([Link], [Link]))
[Link] = merge([Link], makelist(J1_instr))
[Link] = merge([Link], makelist(J2_instr))