|
CS3723 Programming Languages, Fall 2013 Answers to Recitation 4 A. 1. Top-down, left-most derivation sequence: E ⇒ E+T ⇒ T+T ⇒ T*F+T ⇒ F*F+T ⇒ a*F+T ⇒ a*b+T ⇒ a*b+F ⇒ a*b+c ⇒ a*b+c Bottom-up, right-most derivation sequence, backwards: a+b*c ⇒ F+b*c⇒ T+b*c ⇒ E+b*c ⇒ E+F*c ⇒ E+T*c ⇒ E+T*F ⇒ E + T ⇒ E A. 2. Top-down, left-most derivation sequence: E ⇒ T ⇒ T*F ⇒ F*F ⇒ a*F ⇒ a*(E) ⇒ a*(E+T) ⇒ a*(T+T) ⇒ a*(F+T) ⇒ a*(b+T) ⇒ a*(b+F) ⇒ a*(b+c) Bottom-up, right-most derivation sequence, backwards: a*(b+c) ⇒ F*(b+c) ⇒ T*(b+c) ⇒ T*(F+c) ⇒ T*(T+c) ⇒ T*(E+c) ⇒ T*(E+F) ⇒ T*(E+T) ⇒ T*(E) ⇒ T*F ⇒ T ⇒ E B. 1. a. Shift-reduce parse of $ b ( ( a a ) a ) b $ Stack Curr Rest of (top rt) Symb Input Action -------------------------------- $ b ((aa)a)b$ shift $b ( (aa)a)b$ shift $b( ( aa)a)b$ shift $b(( a a)a)b$ shift $b((a a )a)b$ reduce M → a $b((M a )a)b$ shift $b((Ma ) a)b$ shift $b((Ma) a )b$ reduce L → Ma) $b((L a )b$ reduce M → (L $b(M a )b$ shift $b(Ma ) b$ shift $b(Ma) b $ reduce L → Ma) $b(L b $ reduce M → (L $bM b $ shift $bMb $ - reduce S → bMb $S $ - acceptB. 1. c.: b ( ( ( a a ) a ) a ) b B. 2. a.: a. Shift-reduce parse of $ id ^ id ^ id $ Stack CurrS Rest Action (Top rt) Symb of Input $ id ^ id ^ id $ shift $id ^ id ^ id $ reduce: F → id $F ^ id ^ id $ shift $F^ id ^ id $ shift: $F^id ^ id $ reduce: F → id $F^F ^ id $ shift $F^F^ id $ shift $F^F^id $ - reduce: F → id $F^F^F $ - reduce: S → F $F^F^S $ - reduce: S → F ^ S $F^S $ - reduce: S → F ^ S $S $ - reduce: S → T $T $ - reduce: E → T $E $ - reduce: P → E $P $ - accept B. 2. b. Translation of $ id + id * id ^ id $ to intermediate code Grammar with Semantic Actions:
P ---> E P.tag = E.tag; output("print(" + P.tag + ")");
E1 ---> E2 + T E1.tag = "temp" + nextint();
output(E1.tag + "=" E2.tag + "+" T.tag);
E1 ---> E2 - T E1.tag = "temp" + nextint();
output(E1.tag + "=" E2.tag + "-" T.tag);
E ---> T E.tag = T.tag;
T1 ---> T2 * S T1.tag = "temp" + nextint();
output(T1.tag + "=" T2.tag + "*" S.tag);
T1 ---> T2 / S T1.tag = "temp" + nextint();
output(T1.tag + "=" T2.tag + "/" S.tag);
T ---> S T.tag = S.tag;
S1 ---> F ^ S2 S1.tag = "temp" + nextint();
output(S1.tag + "=" F.tag + "^" S2.tag);
S ---> F S.tag = F.tag;
F ---> ( E ) F.tag = E.tag;
F ---> id F.tag = id.tag;
Stack
(top rt, Curr Rest of
tag blw) Symb Input Action Semantic Action
--------------------------------------------------------------------------------------------------
$ id + id * id ^ id $ shift
$id + id * id ^ id $ reduce: F → id F.tag = id.tag;
a
$F + id * id ^ id $ reduce: S → F S.tag = F.tag;
a
$S + id * id ^ id $ reduce: S → F T.tag = S.tag;
a
$T + id * id ^ id $ reduce: E → T E.tag = T.tag;
a
$E + id * id ^ id $ shift
a
$E+ id * id ^ id $ shift
a
$E+id * id ^ id $ reduce: F → id F.tag = id.tag;
a b
$E+F * id ^ id $ reduce: S → F S.tag = F.tag;
a b
$E+S * id ^ id $ reduce: T → S T.tag = S.tag;
a b
$E+T * id ^ id $ shift
a b
$E+T* id ^ id $ shift
a b
$E+T*id ^ id $ reduce: F → id F.tag = id.tag;
a b c
$E+T*F ^ id $ shift
a b c
$E+T*F^ id $ shift
a b c
$E+T*F^id $ - reduce: F → id F.tag = id.tag;
a b c d
$E+T*F^F $ - reduce: S → F S.tag = F.tag;
a b c d
$E+T*F^S $ - reduce: S1 → F ^ S2 S1.tag = "t" + nextint();
a b c d output(S1.tag + "=" + F.tag + "^" + S2.tag);
$E+T*S $ - reduce: T1 → T2 * S T1.tag = "t" + nextint();
a b t1 output(T1.tag + "=" + T2.tag + "*" + S.tag);
$E+T $ - reduce: E1 → E2 + T E1.tag = "t" + nextint();
a t2 output(E1.tag + "=" + E2.tag + "+" + T.tag);
$E $ - reduce: P → E P.tag = E.tag;
t3
$P $ - accept output("print(" + P.tag + ")");
t3
Intermediate code output:
t1 = c ^ d;
t2 = b * t1;
t3 = a + t2;
print(t3);
|