Part a (translation rules)
exp -> exp + term exp1.trans = exp2.trans + term.trans
-> exp - term exp1.trans = exp2.trans - term.trans
-> term exp.trans = term.trans
term -> term * factor term1.trans = term2.trans * factor.trans
-> term / factor term1.trans = term2.trans / factor.trans
-> factor term.trans = factor.trans
factor -> INTLITERAL factor.trans = INTLITERAL.value
-> ( exp ) factor.trans = exp.trans
Part b (translation actions with numbers)
exp -> exp + term termTrans = pop(); #1
expTrans = pop();
push(expTrans+termTrans);
-> exp - term termTrans = pop(); #2
expTrans = pop();
push(expTrans-termTrans);
-> term // do nothing
term -> term * factor facterTrans = pop(); #3
termTrans = pop();
push(termTrans*factorTrans);
-> term / factor factorTrans = pop(); #4
termTrans = pop();
push(termTrans/factorTrans);
-> factor // do nothing
factor -> INTLITERAL push(INTLITERAL.value) #5
-> ( exp ) // do nothing
Part c (CFG with action numbers)
exp -> exp + term #1
-> exp - term #2
-> term
term -> term * factor #3
-> term / factor #4
-> factor
factor -> #5 INTLITERAL
-> ( exp )
Non-LL(1) CFG with action numbers
exp -> exp + term #1
-> exp - term #2
-> term
term -> term * factor #3
-> term / factor #4
-> factor
factor -> #5 INTLITERAL
-> ( exp )
Transformed to be LL(1)
exp -> term exp'
exp' -> epsilon
-> + term #1 exp'
-> - term #2 exp'
term -> factor term'
term' -> epsion
-> * factor #3
-> / factor #4
factor -> #5 INTLITERAL
-> ( exp )
Actions of the predictive parser on input 2+3*4
input so far stack semantic stack action
------------ ----- -------------- ------
2 exp EOF pop, push "term exp'"
2 term exp' EOF pop, push "factor term'"
2 factor term' exp' EOF pop, push "#5 INTLITERAL"
2 #5 INTLITERAL term' exp' EOF pop, do action
2 INTLITERAL term' exp' EOF 2 pop, scan
2+ term' exp' EOF 2 pop, push nothing
2+ exp' EOF 2 pop, push "+ term #1 exp'"
2+ + term #1 exp' EOF 2 pop, scan
2+3 term #1 exp' EOF 2 pop, push "factor term'"
2+3 factor term' #1 exp' EOF 2 pop, push "#5 INTLITERAL"
2+3 #5 INTLITERAL term' #1 exp' EOF 2 pop, do action
2+3 INTLITERAL term' #1 exp' EOF 3 2 pop, scan
2+3* term' #1 exp' EOF 3 2 pop, push "* factor #3"
2+3* * factor #3 #1 exp' EOF 3 2 pop, scan
2+3*4 factor #3 #1 exp' EOF 3 2 pop, push "#5 INTLITERAL"
2+3*4 #5 INTLITERAL #3 #1 exp' EOF 3 2 pop, do action
2+3*4 INTLITERAL #3 #1 exp' EOF 4 3 2 pop, scan
2+3*4 EOF #3 #1 exp' EOF 4 3 2 pop, do action
2+3*4 EOF #1 exp' EOF 12 2 pop, do action
2+3*4 EOF exp' EOF 14 pop, push nothing
2+3*4 EOF EOF 14 pop, push nothing
2+3*4 EOF 14 empty stack, input accepted
final translation = 14