Tristan Schmelcher
2004-08-03 01:56:37 UTC
These are my solutions to the Winter 2001 final, including the drawing
questions. I've checked them with one person already. 6c gets gimped up by the
e-mail, but you can probably still understand it.
1)
a)
(I did this question based on the DLX reference info that was on the exam
sheet. If you changed the assembly to MIPS assembly and then assembled that,
it might be different.)
Assume bits that aren't required are zeroed.
Assume "16_" indicates a hexadecimal numeral.
0: 00000001 00001101 10011000 00001011 = 0x010D980B
4: 01110001 00100001 11111110 11111111 = 0x7121FEFF
8: 11000001 00000000 00000000 00000000 = 0xC1000000
12: 11000101 00000000 WWWWWWWW WWWWWWWW = 0xC500WWWW
16: 000011QQ QQQQQQQQ QQQQQQQQ QQQQQQQQ = 0x0QQQQQQQ
20: 00010010 00110100 01010110 01111000 = 0x12345678
24: 01001000 00011111 00000000 00000000 = 0x481F0000
b)
(Never heard of it. Must be a DLX thing.)
c)
lhi, 0x000C, 0x8
d)
llo, 0xC, wb
offs26, 0x10, q
e)
main, 0x0000000C
x, 0x00000000
2)
(I did this question using the MIPS assembly instructions instead of the DLX
ones.)
a)
--> o --s--> o --u--> o --b--> (o) --u--> (o)
|
|--d--> o --i--> o --v--> (o) --u--> (o)
|
|--m--> o --u--> o --l--> --t--> (o) --u--> (o)
|
|--a--> o --d--> o --d--> (o) --u--> (o)
|
i--> (o) --u--> (o)
b) add(|i)(|u)|sub(|u)|div(|u)|mult(|u)
c)
<start> -> <instruction>
<start> -> <label>: <instruction>
<instruction> -> add $<reg>, $<reg>, $<reg>
<instruction> -> addu $<reg>, $<reg>, $<reg>
<instruction> -> addi $<reg>, $<reg>, <immed16>
<instruction> -> addiu $<reg>, $<reg>, <immed16>
<instruction> -> sub $<reg>, $<reg>, $<reg>
<instruction> -> subu $<reg>, $<reg>, $<reg>
<instruction> -> div $<reg>, $<reg>
<instruction> -> divu $<reg>, $<reg>
<instruction> -> mult $<reg>, $<reg>
<instruction> -> multu $<reg>, $<reg>
<instruction> -> jr $<reg>
<instruction> -> jalr $<reg>
<label> -> <char>
<label> -> <char> <label>
Where <char> is any alphanumeric character or underscore, <reg> is any integer
numeral in [0, 31], and <immed16> is any integer numeral in [-65536, 65535].
(MIPS labels might have to start with a letter, or something. I wasn't sure on
that. Also, a strict reading of the question suggests that I should have
written out the complete rules for <reg> and <immed16> and that I should have
written out the rule for <char> using '...', but I didn't feel like doing any
of those things.)
3)
(Done as a MIPS question, of course.)
addInt:
lw $1, 0($30)
bne $1, $0, else
lw $1, 4($30)
jr $31
else: addi $30, $30, -12
lw $1, 12($30)
addi $1, $1, -1
sw $1, 0($30)
lw $1, 16($30)
addi $1, $1, 1
sw $1, 4($30)
sw $31, 8($30)
jal addInt
lw $31, 8($30)
addi $30, $30, 12
jr $31
4)
a)
There are two distinct parse trees for "at##". The derivations that produce
them are:
<S> => at<S>
=> at#<U>
=> at##
and
<S> => <V>
=> a<X>
=> at<X>
=> at##
Hence the grammar is ambiguous.
b)
(at)*(##|at*##|tt*##)
c)
(These statements are both true, but they are basically guesses.)
- The regex for L(G) is more concise than the CFG for L(G).
- Giving a CFG for L(G) makes it unclear as to whether L(G) is regular or not,
whereas giving a regex makes it clear.
5)
a)
Nullable:
Q - F
S - T
V - F
U - F
X - T
First:
Q - a,c,t,q,#
S - a,c,t,q
V - c,t
U - q
X - c
Follow:
Q - EOF
S - #
V - t,c
U - a,t
X - a,t
Predict:
(The EOF column is missing from the exam sheet. It should have been there,
even though it's all Es.)
q a c t # EOF
Q 1 1 1 1 1 E
S 4 2 3 3 5 E
V E E 6 7 E E
U 8 E E E E E
X E 9 10 9 E E
b)
All LL(1) grammars are unambiguous, and we did not encounter an error when
making the predictor table, so this grammar is LL(1) and hence unambiguous.
6)
a)
"Syn" means that an attribute is synthetic, which is that it is computed
bottom-up. "Inh" means that in attribute is inherited, which is that it is
computed top-down.
All of the attributes in this example are "Syn".
b)
Assume that our code must manage the three global variables itself.
==== <FL> -> <Stmts> ====
<FL>.code = ".globl main\n" +
"main:\n" +
"\tadd\t$5, $0, $0\n" + // F is always in $5
"\tadd\t$6, $0, $0\n" + // L is always in $6
<Stmts>.code +
"\ttrap\t10\n";
==== <Stmts>1 -> <Stmt> <Stmts>2 ====
<Stmts>1.code = <Stmt>.code + <Stmts>2.code;
==== <Stmts> -> epsilon ====
<Stmts>.code = "";
==== <Stmt> -> PrintVar(<Var>) ====
<Stmt>.code = "\tadd\t$4, $0, $" + <Var>.reg + "\n" +
"\ttrap\t1\n";
line_num++;
print_num++;
==== <Stmt> -> PrintLine ====
<Stmt>.code = "\taddi\t$4, $0, " + line_num + "\n" +
"\ttrap\t1\n";
line_num++;
print_num++;
==== <Stmt> -> PrintPrint ====
<Stmt>.code = "\taddi\t$4, $0, " + print_num + "\n" +
"\ttrap\t1\n";
line_num++;
print_num++;
==== <Stmt> -> Tip(<Var>) ====
<Stmt>.code = "\taddi\t$" + <Var>.reg + ", " + <Var>.reg + ", 1\n";
line_num++;
==== <Stmt> -> Swap(<Var>1, <Var>2) ====
<Stmt>.code = "\tadd\t$1, $0, $" + <Var>2.reg + "\n" +
"\tadd\t$" + <Var>2.reg + ", $0, $" + <Var>1.reg + "\n" +
"\tadd\t$" + <Var>1.reg + ", $0, $1\n";
line_num++;
==== <Stmt> -> Max(<Var>1, <Var>2) ====
String skipLbl = "FL_" + (label_num++);
<Stmt>.code = "\tslt\t$1, $" + <Var>1.reg + ", $" + <Var>2.reg + "\n" +
"\tbeq\t$1, $0, " + skipLbl + "\n" +
"\tadd\t$" + <Var>1.reg + ", $0, $" + <Var>2.reg + "\n" +
skipLbl + ":\n";
line_num++;
==== <Stmt> -> Boo(<Var>1, <Var>2) ====
String endLbl = "FL_" + (label_num++);
String loopLbl = "FL_" + (label_num++);
<Stmt>.code = "\taddi\t$1, $0, 1\n" +
loopLbl + ":\n" +
"\tslt\t$2, $" + <Var>1.reg + ", $1\n" +
"\tbne\t$2, $0, " + endLbl + "\n" +
"\tmult\t$" + <Var>1.reg + ", $" + <Var>2.reg + "\n" +
"\tmflo\t$" + <Var>2.reg + "\n" +
"\tj\tloopLbl\n" +
endLbl + ":\n";
line_num++;
==== <Var> -> F ====
<Var>.reg = 5;
==== <Var> -> L ====
<Var>.reg = 6;
c)
Start with:
line_num = 1;
print_num = 0;
label_num = 0;
|--|----------------|
|FL|.globl main\n |
| |main:\n |
| |add $5, $0, $0\n|
| |add $6, $0, $0\n|
| |(1a) |
| |trap 10\n |
|--|----------------|
|
|
V
|-------|-------| |------|----------------| |-----|-|
|<Stmts>|(1)(2a)| ----> |<Stmt>|addi $5, $5, 1\n| ----> Tip( |<Var>|5| )
|-------|-------|(1a) |------|----------------|(1) |-----|-|
| line_num = 2; |
V |--> F
|-------|-------| |------|----------------|
|<Stmts>|(2)(3a)| ----> |<Stmt>|addi $4, $0, 2\n| ----> PrintLine
|-------|-------|(2a) | |trap 1\n |
| |------|----------------|(2)
| line_num = 3;
| print_num = 1;
V
|-------|-------| |------|----------------| |-----|-| |----
-|-|
|<Stmts>|(3)(4a)| ----> |<Stmt>|add $1, $0, $6\n| ----> Swap( |<Var>|5| ,
|<Var>|6| )
|-------|-------|(3a) | |add $6, $0, $5\n| |-----|-| |----
-|-|
| | |add $5, $0, $1\n| | |
| |------|----------------|(3) |--> F |-
-> L
| line_num = 4;
V
|-------|-------| |------|------------------| |-----|-| |---
--|-|
|<Stmts>|(4)(5a)| ----> |<Stmt>|slt $1, $5, $6\n | ----> Max( |<Var>|5| ,
|<Var>|6| )
|-------|-------|(4a) | |beq $1, $0, FL_0\n| |-----|-| |---
--|-|
| | |add $5, $0, $6\n | | |
| | |FL_0:\n | |--> F
|--> L
| |------|------------------|(4)
| line_num = 5;
| label_num = 1;
V
|-------|------| |------|----------------|
|<Stmts>|(5)(6)| ----> |<Stmt>|addi $4, $0, 1\n| ----> PrintPrint
|-------|------|(5a) | |trap 1\n |
| |------|----------------|(5)
| line_num = 6;
| print_num = 2;
V
|-------|--|
|<Stmts>| | ----> epsilon
|-------|--|(6)
7)
a)
(define filter
(lambda (L p)
(cond
( (null? L) () )
( (p (car L)) (cons (car L) (filter (cdr L) p)) )
( else (filter (cdr L) p) )
) ) )
b)
(define tv
(letrec
( (eff-tv
(lambda (n v_of_n-1 v_of_n-2 end)
(if (= n end)
(+ v_of_n-1 (* 2 v_of_n-2))
(eff-tv (+ 1 n) (+ v_of_n-1 (* 2 v_of_n-2)) v_of_n-1 end)
) ) ) )
(lambda (n)
(cond
( (>= n 2) (eff-tv 2 3 2 n) )
( (= n 1) 3 )
( (= n 0) 2 )
( else #f )
) ) ) )
d)
1: ()
2: 49
3: "atom"
4: a
5: a
6: (6)
9)
a) Linker
b) Lexical
c) C
d) False
e) Lexical
f) True
g) False
h) False
i) LL(1) = "Reads from the [L]eft, produces a [L]eftmost-derivation, and looks
ahead [1] character."
j) (1) Concatenate the code, (2) handle relocation issues based on relocation
tables, (3) build new list of symbols, and (4) resolve references.
k) They can be passed as parameters and returned from functions.
----------------------------------------
This mail sent through www.mywaterloo.ca
questions. I've checked them with one person already. 6c gets gimped up by the
e-mail, but you can probably still understand it.
1)
a)
(I did this question based on the DLX reference info that was on the exam
sheet. If you changed the assembly to MIPS assembly and then assembled that,
it might be different.)
Assume bits that aren't required are zeroed.
Assume "16_" indicates a hexadecimal numeral.
0: 00000001 00001101 10011000 00001011 = 0x010D980B
4: 01110001 00100001 11111110 11111111 = 0x7121FEFF
8: 11000001 00000000 00000000 00000000 = 0xC1000000
12: 11000101 00000000 WWWWWWWW WWWWWWWW = 0xC500WWWW
16: 000011QQ QQQQQQQQ QQQQQQQQ QQQQQQQQ = 0x0QQQQQQQ
20: 00010010 00110100 01010110 01111000 = 0x12345678
24: 01001000 00011111 00000000 00000000 = 0x481F0000
b)
(Never heard of it. Must be a DLX thing.)
c)
lhi, 0x000C, 0x8
d)
llo, 0xC, wb
offs26, 0x10, q
e)
main, 0x0000000C
x, 0x00000000
2)
(I did this question using the MIPS assembly instructions instead of the DLX
ones.)
a)
--> o --s--> o --u--> o --b--> (o) --u--> (o)
|
|--d--> o --i--> o --v--> (o) --u--> (o)
|
|--m--> o --u--> o --l--> --t--> (o) --u--> (o)
|
|--a--> o --d--> o --d--> (o) --u--> (o)
|
i--> (o) --u--> (o)
b) add(|i)(|u)|sub(|u)|div(|u)|mult(|u)
c)
<start> -> <instruction>
<start> -> <label>: <instruction>
<instruction> -> add $<reg>, $<reg>, $<reg>
<instruction> -> addu $<reg>, $<reg>, $<reg>
<instruction> -> addi $<reg>, $<reg>, <immed16>
<instruction> -> addiu $<reg>, $<reg>, <immed16>
<instruction> -> sub $<reg>, $<reg>, $<reg>
<instruction> -> subu $<reg>, $<reg>, $<reg>
<instruction> -> div $<reg>, $<reg>
<instruction> -> divu $<reg>, $<reg>
<instruction> -> mult $<reg>, $<reg>
<instruction> -> multu $<reg>, $<reg>
<instruction> -> jr $<reg>
<instruction> -> jalr $<reg>
<label> -> <char>
<label> -> <char> <label>
Where <char> is any alphanumeric character or underscore, <reg> is any integer
numeral in [0, 31], and <immed16> is any integer numeral in [-65536, 65535].
(MIPS labels might have to start with a letter, or something. I wasn't sure on
that. Also, a strict reading of the question suggests that I should have
written out the complete rules for <reg> and <immed16> and that I should have
written out the rule for <char> using '...', but I didn't feel like doing any
of those things.)
3)
(Done as a MIPS question, of course.)
addInt:
lw $1, 0($30)
bne $1, $0, else
lw $1, 4($30)
jr $31
else: addi $30, $30, -12
lw $1, 12($30)
addi $1, $1, -1
sw $1, 0($30)
lw $1, 16($30)
addi $1, $1, 1
sw $1, 4($30)
sw $31, 8($30)
jal addInt
lw $31, 8($30)
addi $30, $30, 12
jr $31
4)
a)
There are two distinct parse trees for "at##". The derivations that produce
them are:
<S> => at<S>
=> at#<U>
=> at##
and
<S> => <V>
=> a<X>
=> at<X>
=> at##
Hence the grammar is ambiguous.
b)
(at)*(##|at*##|tt*##)
c)
(These statements are both true, but they are basically guesses.)
- The regex for L(G) is more concise than the CFG for L(G).
- Giving a CFG for L(G) makes it unclear as to whether L(G) is regular or not,
whereas giving a regex makes it clear.
5)
a)
Nullable:
Q - F
S - T
V - F
U - F
X - T
First:
Q - a,c,t,q,#
S - a,c,t,q
V - c,t
U - q
X - c
Follow:
Q - EOF
S - #
V - t,c
U - a,t
X - a,t
Predict:
(The EOF column is missing from the exam sheet. It should have been there,
even though it's all Es.)
q a c t # EOF
Q 1 1 1 1 1 E
S 4 2 3 3 5 E
V E E 6 7 E E
U 8 E E E E E
X E 9 10 9 E E
b)
All LL(1) grammars are unambiguous, and we did not encounter an error when
making the predictor table, so this grammar is LL(1) and hence unambiguous.
6)
a)
"Syn" means that an attribute is synthetic, which is that it is computed
bottom-up. "Inh" means that in attribute is inherited, which is that it is
computed top-down.
All of the attributes in this example are "Syn".
b)
Assume that our code must manage the three global variables itself.
==== <FL> -> <Stmts> ====
<FL>.code = ".globl main\n" +
"main:\n" +
"\tadd\t$5, $0, $0\n" + // F is always in $5
"\tadd\t$6, $0, $0\n" + // L is always in $6
<Stmts>.code +
"\ttrap\t10\n";
==== <Stmts>1 -> <Stmt> <Stmts>2 ====
<Stmts>1.code = <Stmt>.code + <Stmts>2.code;
==== <Stmts> -> epsilon ====
<Stmts>.code = "";
==== <Stmt> -> PrintVar(<Var>) ====
<Stmt>.code = "\tadd\t$4, $0, $" + <Var>.reg + "\n" +
"\ttrap\t1\n";
line_num++;
print_num++;
==== <Stmt> -> PrintLine ====
<Stmt>.code = "\taddi\t$4, $0, " + line_num + "\n" +
"\ttrap\t1\n";
line_num++;
print_num++;
==== <Stmt> -> PrintPrint ====
<Stmt>.code = "\taddi\t$4, $0, " + print_num + "\n" +
"\ttrap\t1\n";
line_num++;
print_num++;
==== <Stmt> -> Tip(<Var>) ====
<Stmt>.code = "\taddi\t$" + <Var>.reg + ", " + <Var>.reg + ", 1\n";
line_num++;
==== <Stmt> -> Swap(<Var>1, <Var>2) ====
<Stmt>.code = "\tadd\t$1, $0, $" + <Var>2.reg + "\n" +
"\tadd\t$" + <Var>2.reg + ", $0, $" + <Var>1.reg + "\n" +
"\tadd\t$" + <Var>1.reg + ", $0, $1\n";
line_num++;
==== <Stmt> -> Max(<Var>1, <Var>2) ====
String skipLbl = "FL_" + (label_num++);
<Stmt>.code = "\tslt\t$1, $" + <Var>1.reg + ", $" + <Var>2.reg + "\n" +
"\tbeq\t$1, $0, " + skipLbl + "\n" +
"\tadd\t$" + <Var>1.reg + ", $0, $" + <Var>2.reg + "\n" +
skipLbl + ":\n";
line_num++;
==== <Stmt> -> Boo(<Var>1, <Var>2) ====
String endLbl = "FL_" + (label_num++);
String loopLbl = "FL_" + (label_num++);
<Stmt>.code = "\taddi\t$1, $0, 1\n" +
loopLbl + ":\n" +
"\tslt\t$2, $" + <Var>1.reg + ", $1\n" +
"\tbne\t$2, $0, " + endLbl + "\n" +
"\tmult\t$" + <Var>1.reg + ", $" + <Var>2.reg + "\n" +
"\tmflo\t$" + <Var>2.reg + "\n" +
"\tj\tloopLbl\n" +
endLbl + ":\n";
line_num++;
==== <Var> -> F ====
<Var>.reg = 5;
==== <Var> -> L ====
<Var>.reg = 6;
c)
Start with:
line_num = 1;
print_num = 0;
label_num = 0;
|--|----------------|
|FL|.globl main\n |
| |main:\n |
| |add $5, $0, $0\n|
| |add $6, $0, $0\n|
| |(1a) |
| |trap 10\n |
|--|----------------|
|
|
V
|-------|-------| |------|----------------| |-----|-|
|<Stmts>|(1)(2a)| ----> |<Stmt>|addi $5, $5, 1\n| ----> Tip( |<Var>|5| )
|-------|-------|(1a) |------|----------------|(1) |-----|-|
| line_num = 2; |
V |--> F
|-------|-------| |------|----------------|
|<Stmts>|(2)(3a)| ----> |<Stmt>|addi $4, $0, 2\n| ----> PrintLine
|-------|-------|(2a) | |trap 1\n |
| |------|----------------|(2)
| line_num = 3;
| print_num = 1;
V
|-------|-------| |------|----------------| |-----|-| |----
-|-|
|<Stmts>|(3)(4a)| ----> |<Stmt>|add $1, $0, $6\n| ----> Swap( |<Var>|5| ,
|<Var>|6| )
|-------|-------|(3a) | |add $6, $0, $5\n| |-----|-| |----
-|-|
| | |add $5, $0, $1\n| | |
| |------|----------------|(3) |--> F |-
-> L
| line_num = 4;
V
|-------|-------| |------|------------------| |-----|-| |---
--|-|
|<Stmts>|(4)(5a)| ----> |<Stmt>|slt $1, $5, $6\n | ----> Max( |<Var>|5| ,
|<Var>|6| )
|-------|-------|(4a) | |beq $1, $0, FL_0\n| |-----|-| |---
--|-|
| | |add $5, $0, $6\n | | |
| | |FL_0:\n | |--> F
|--> L
| |------|------------------|(4)
| line_num = 5;
| label_num = 1;
V
|-------|------| |------|----------------|
|<Stmts>|(5)(6)| ----> |<Stmt>|addi $4, $0, 1\n| ----> PrintPrint
|-------|------|(5a) | |trap 1\n |
| |------|----------------|(5)
| line_num = 6;
| print_num = 2;
V
|-------|--|
|<Stmts>| | ----> epsilon
|-------|--|(6)
7)
a)
(define filter
(lambda (L p)
(cond
( (null? L) () )
( (p (car L)) (cons (car L) (filter (cdr L) p)) )
( else (filter (cdr L) p) )
) ) )
b)
(define tv
(letrec
( (eff-tv
(lambda (n v_of_n-1 v_of_n-2 end)
(if (= n end)
(+ v_of_n-1 (* 2 v_of_n-2))
(eff-tv (+ 1 n) (+ v_of_n-1 (* 2 v_of_n-2)) v_of_n-1 end)
) ) ) )
(lambda (n)
(cond
( (>= n 2) (eff-tv 2 3 2 n) )
( (= n 1) 3 )
( (= n 0) 2 )
( else #f )
) ) ) )
d)
1: ()
2: 49
3: "atom"
4: a
5: a
6: (6)
9)
a) Linker
b) Lexical
c) C
d) False
e) Lexical
f) True
g) False
h) False
i) LL(1) = "Reads from the [L]eft, produces a [L]eftmost-derivation, and looks
ahead [1] character."
j) (1) Concatenate the code, (2) handle relocation issues based on relocation
tables, (3) build new list of symbols, and (4) resolve references.
k) They can be passed as parameters and returned from functions.
----------------------------------------
This mail sent through www.mywaterloo.ca