|
CS3723 Programming Languages, Spring 2014 Answers to Recitation 3 1. Translation of $ id + id * id ^ id $ to intermediate code, where the 4 id's are tagged with a, b, c, and d. Grammar with semantic actions:
P −−> E
E −−> E + T output("+");
E −−> E - T output("-");
E −−> T
T −−> T * S output("*");
T −−> T / S output("/");
T −−> S
S −−> F ^ S output("^");
S −−> F
F −−> ( E )
F −−> id output(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 output("a");
$F + id * id ^ id $ reduce: S −−> F
$S + id * id ^ id $ reduce: S −−> F
$T + id * id ^ id $ reduce: E −−> T
$E + id * id ^ id $ shift
$E+ id * id ^ id $ shift
$E+id * id ^ id $ reduce: F −−> id output("b");
$E+F * id ^ id $ reduce: S −−> F
$E+S * id ^ id $ reduce: T −−> S
$E+T * id ^ id $ shift
$E+T* id ^ id $ shift
$E+T*id ^ id $ reduce: F −−> id output("c");
$E+T*F ^ id $ shift
$E+T*F^ id $ shift
$E+T*F^id $ - reduce: F −−> id output("d");
$E+T*F^F $ - reduce: S −−> F
$E+T*F^S $ - reduce: S −−> F ^ S2 output("^");
$E+T*S $ - reduce: T −−> T * S output("*");
$E+T $ - reduce: E −−> E + T output("+");
$E $ - reduce: P −−> E
$P $ - accept
Arithmetic expression: $ id + id * id ^ id $
Translation to RPN: a b c d ^ * +
2. 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);
3. MIPS assembly code: (The stuff in black is the translation of the five assignments into MIPS. The code in green is added so that it will be a complete program, using our conventions.
main: addu $s7, $ra, $zero
la $s1, M
l.d $f2, 64($s1)
l.d $f4, 16($s1)
mul.d $f6, $f2, $f4
s.d $f6, 80($s1)
l.d $f2, 56($s1)
l.d $f4, 80($s1)
mul.d $f6, $f2, $f4
s.d $f6, 88($s1)
l.d $f2, 88($s1)
l.d $f4, 8($s1)
add.d $f6, $f2, $f4
s.d $f6, 96($s1)
l.d $f2, 80($s1)
l.d $f4, 96($s1)
div.d $f6, $f2, $f4
s.d $f6, 104($s1)
l.d $f2, 24($s1)
l.d $f4, 104($s1)
add.d $f6, $f2, $f4
s.d $f6, 112($s1)
# Print result + newl
li $v0, 3
l.d $f12, 112($s1)
syscall
li $v0, 4
la $a0, NewL
syscall
# Stuff at end ################
addu $ra, $s7, $zero
jr $ra # ret
.data
.align 3
M: .double 0.,1.,2.,3.,4.
.double 5.,6.,7.,8.,9.
.space 208 # a to z
NewL: .asciiz "\n"
The output of running the MIPS program is:3.14159292035398252 ( = 355/113), a surprisingly close approximation to pi for such a simple program. |