Bottom-Up Eval.of S-Attributed Definitions(cont.) Production Semantic Rules L→E return print(val[top-1]) E→E1+T val[ntop]val[top-2]+val[top] E→T T→T1*F val[ntop]val[top-2]val[top] T→F F→(E) val[ntop]=val[top-1] F→digit At each shift of digit,we also push digit.lexval into val-stack. At all other shifts,we do not put anything into val-stack because other terminals do not have attributes (but we increment the stack pointer for val-stack). CS308 Compiler Theory 16
Bottom-Up Eval. of S-Attributed Definitions (cont.) Production Semantic Rules L → E return print(val[top-1]) E → E1 + T val[ntop] = val[top-2] + val[top] E → T T → T1 * F val[ntop] = val[top-2] * val[top] T → F F → ( E ) val[ntop] = val[top-1] F → digit • At each shift of digit, we also push digit.lexval into val-stack. • A ll h hif d hi i At all ot her shifts, we do not put anything into va l-stac k because other terminals do not have attributes (but we increment the stack pointer for val -stack). CS308 Compiler Theory 16 stack pointer for val stack)
Canonical LR(O)Collection for The Grammar LoL→.L L→I:'→L· *→9 L→.Er rl:L→Er。 T,l:E→E+T. T→T。*F E→，E+T El2:L→Er ±→lg:E→E+。T E4 E→。T E→E。+T T→.T*F 5 T→，T*F T→.F d T→。F T→l:E→T F→.(E) *6 F→.(E) T→T,*F F→。d F→。d F→l4:T→F Ig: T→T*,F l5:F→(.E) F→.(E) Ele:T-→Tp. E→.E+T E F→。d (5 E→。T d6 T→。T*F T→。F 110F→(E)s F→。(E) ）→13：F→(E) E→E.+Tt F→。d 4 d→l6:F-→d. 5 ⊙6 CS308 Compiler Theory 17
Canonical LR(0) Collection for The Grammar L’ → . L L → . E r L’ → L . L →Er . E →E+T . T → T *F I 0: I1: I 7: I11: r L E T * 9 . E → .E+T E → . T T → .T*F L → E . r E → E .+T E →E+ . T T → .T*F T → . F ( ) T → T .*F I 2: I I 8: E T F ( d + 6 5 4 T → . F F → .(E) F → . d E → T . T → T .*F T → F F → . ( E ) F → . d I 4: I 3: T F * 6 T → F . F → ( .E) E → .E+T T →T* . F F → .(E) F → . d T →T*F . I 4: I 5: I12: I 9: E F ( ( 5 E → . T T → .T*F T → . F F (E) F →(E . ) E E +T F →(E) . I10: I13: E T d ) 3 6 F → .(E) F → . d F → d . E → E .+T I 6: F ( d d + 3 5 4 8 CS308 Compiler Theory 17 6 F → d . d 6
Bottom-Up Evaluation -Example .At each shift of digit,we also push digit.lexval into val-stack stack val-stack input action semantic rule 0 5+3*4r s6 d.lexval(5)into val-stack 0d6 5 +3*4r F→d F.val=d.lexval-do nothing 0F4 5 +3*4r T→F T.val=F.val-do nothing 0T3 5 +3*4r E→T E.val=T.val-do nothing 0E2 5 +3*4r s8 push empty slot into val-stack 0E2+8 5- 3*4r s6 d.lexval(3)into val-stack 0E2+8d6 5-3 *4r F→d F.val=d.lexval-do nothing 0E2+8F4 5-3 *4r T→F T.val=F.val-do nothing 0E2+8T11 5-3 *4r s9 push empty slot into val-stack 0E2+8T11*9 5-3- 4r s6 d.lexval(4)into val-stack 0E2+8T11*9d6 5-3-4 F→d F.val=d.lexval-do nothing 0E2+8T11*9F12 5-3-4 r T→T*F T.val=T.val*F.val 0E2+8T11 5-12 E→E+T E.val=E.val*T.val 0E2 17 r s7 push empty slot into val-stack 0E2r7 17- $ L→Er print(17),pop empty slot from val-stack 0L1 17 $ acc CS308 Compiler Theory 18
Bottom-Up Evaluation -- Example • At each shift of digit, we also push digit.lexval into val-stack. stack val -stack input action semantic rule semantic rule 0 5+3*4r s6 d.lexval(5) into val-stack 0d6 5 +3*4r F →d F.val=d.lexval – do nothing 0F4 5 +3*4r T → F T val=F val T.val=F.val – do nothing do nothing 0T3 5 +3*4r E →T E.val=T.val – do nothing 0E2 5 +3*4r s8 push empty slot into val-stack 0E2+8 5- 3 4r * s6 d lexval(3) into val d.lexval(3) into val-stack 0E2+8d6 5-3 *4r F →d F.val=d.lexval – do nothing 0E2+8F4 5-3 *4r T →F T.val=F.val – do nothing 0E2 8T11 + 5-3 *4r s9 push empty slot into val push empty slot into val-stack 0E2+8T11*9 5-3- 4r s6 d.lexval(4) into val-stack 0E2+8T11*9d6 5-3-4 r F →d F.val=d.lexval – do nothing 0E2+8T11*9F12 5-3-4 r T →T*F T.val=T1.val*F.val 0E2+8T11 5-12 r E →E+T E.val=E1.val*T.val 0E2 17 r s7 push empty slot into val-stack 0E2r7 17- $ L → E r print(17), p o p em pty slot from val-stack CS308 Compiler Theory 18 p ( ) p p py 0L1 17 $ acc