S02 Final Solutions

[James Schofield]

I thought I'd post my solutions for the S02 practice final. I haven't
had a chance to verify these with anyone else, but I hope they're mostly
correct. Feel free to post any corrections :)


1a)
addi $30, $30, -4
sw $4, 0($30)
jal mystery
addi $30, $30, 4
add $6, $0, $1

1b)
add $4, $0, $9
sll $9, $9, 2
add $9, $9, $3
lw $9, 0($9)

2a)
Define: I = ii(ii)* ; M = m(mm)* ; L = lambda
Then, the RE is: (M|L)(IM)*(I|L)

2b)
Transitions (start state, input character, end state):
A,x,B
A,y,D
B,z,B
B,y,C
D,y,C
D,z,BD
BD,z,BD
BD,y,c

Accepting states: A and C

2c)
<S> -> <A><S>
<S> ->
<A> -> <B><C>
<B> -> x<B>
<B> ->
<C> -> y
<C> -> z

3a)
Show two distinct parse trees to represent the same input.

3b)
<E> -> <F>o<E>
<E> -> <F>
<F> -> <F>^<G>
<F> -> <G>
<G> -> 1
<G> -> 2

4a)
NT N? First Follow t v x y z EOF
<S> n tvxy EOF 1 2 1 1 E E
<A> y x tyz 3 E 4 3 3 E
<B> y yz t 6 E E 5 6 E
<C> y z t 7 E E E 8 E
<D> y xy t 8 E 8 8 8 E

4b)
<S> -> a<A>
<A> -> a<B>
<A> -> <B>
<B> -> c<C>
<C> -> c
<C> ->

4c)
<S> -> c<A>
<A> -> ab<A>
<A> ->

5a)
I don't think we covered this this term...

5b)
Pushes the symbol in "next" onto the stack; reads the next input symbol
into "next".

5c)
Pops the right-hand side of a rule off the stack, and pushes on the
left-hand side of the rule.

5d)
No, it would not be possible to construct the LR(1) DFA if the CFG was
ambiguous.

6)
Notes about my implementation: I use $1, $2, and $4 as scratch registers
(i.e. I don't worry about backing them up). <Expr> always leaves its
result in $1.

Attributes:
<Stmts>.code String Synthetic
ID.name {A,B} Synthetic
<Stmt>.code String Synthetic
<Expr>.code String Synthetic


<Stmts>1 -> <Stmts>2 <Stmt> SEMI
<Stmts>1.code = <Stmts>2.code + <Stmt>.code

<Stmts> ->
<Stmts>.code = ".word A\n" +
".word B\n"

<Stmt> -> IN ID
<Stmt>.code = "\ttrap 5\n" +
"\tsw $2, 0(" + ID.name + ")\n"

<Stmt> -> OUT <Expr>
<Stmt>.code = <Expr>.code +
"\tadd $4, $1, $0\n" +
"\ttrap 1\n"

<Stmt> -> ID ASSIGN <Expr>
<Stmt>.code = <Expr>.code +
"\tsw $1, 0(" + ID.name + ")\n"

<Expr>1 -> <Expr>2 MULOP ID
<Expr>1.code = <Expr>2.code +
"lw $2, 0(" + ID.name + ")\n" +
"mult $1, $2\n" +
"mflo $1\n"

<Expr> -> ID
<Expr>.code = "lw $1, 0(" + ID.name + ")\n"

7a) 55
7b) 11EF
7c) 1100 0001
7d) 1011 1111

8)
Address Hex
00000000 6007001C
00000004 ACE90004
00000008 2331FFF6
0000000C 02979820
00000010 94130000
00000014 0BFFFFFC
00000018 03E00008
0000001C FFFFFFF1

Relocation:
LLO, -, 00000000

Imports:
OFFSET16, 00000010, on

Exports:
im, 00000000
x, 00000018

9a) 0
9b) ((1 2) (1 2 3 4))
9c) ("scheme" "is" "fun") [ha :P]
9d) 35
9e) ((1 2) ((1 2 3 4)))

10)

(define parse
(lambda (in)
(cond
((null? in) #t)
((equal? (car in) 'y) (parse (cdr in)))
((null? (cdr in)) #f)
((and (equal? (car in) 'x) (equal? (cadr in) 'x)) (parse (cddr in)))
(else #f)
)))

11)

(define iterate
(lambda (proc n)
(lambda (x)
(letrec
((do-iterate
(lambda (proc n x)
(if (> n 0)
(proc (do-iterate proc (- n 1) x))
x
))))
(do-iterate proc n x)
))))


12)

(define M
(lambda (n)
(letrec
((M-it
(lambda (i x3 x2 x1)
(if (> i 0)
(M-it (- i 1) x2 x1 (+ x1 (* 2 x3)))
x3
))))
(M-it n 0 1 3)
)))

[Hansel Ip]

Jimmy, on behalf of everyone trolling your post for exam solutions -
thank you!


Maybe one small correction I noticed, I think for Q8 the fifth assembled
MIPS code line (00000010) should be 14130000 instead of 94130000... since
the opcode for bne is 000101... unless I missed something.

Thanks again,


-HI

[James Schofield]

I think for Q8 the fifth assembled MIPS code line (00000010) should be
14130000 instead of 94130000...

Yup, you're right.

Also, for 4(a), the table should be

NT N? First Follow t v x y z EOF
<S> n tvxyz EOF 1 2 1 1 E E
<A> y x tyz 3 E 4 3 3 E
<B> y yz t 6 E E 5 6 E
<C> y z t 7 E E E 8 E
<D> y xyz t 9 E 9 9 9 E

There was a mistake in the first and last lines. Thanks to Alicia for
catching this one!

James

[Andrew Craik]

Hey,

Just one little correction to the mips code for the grammar question,
ID.name needs to be used with llo and lhi to get the address into a register
then that register can be used with the lw of offset 0, you can't use a
label in that position. For example:

<Expr>1 -> <Expr>2 MULOP ID
<Expr>1.code = <Expr>2.code +
"lw $2, 0(" + ID.name + ")\n" +
"mult $1, $2\n" +
"mflo $1\n"

should be

<Expr>1 -> <Expr>2 MULOP ID
<Expr>1.code = <Expr>2.code +
"llo $2, " + ID.name + "\n" +
"lhi $2, " + ID.name + "\n" +
"lw $2, 0($2)\n" +
"mult $1, $2\n" +
"mflo $1\n"

assumingthe code surrounding the change is ok, which it seems to be

Andrew

Post by James Schofield
I thought I'd post my solutions for the S02 practice final. I haven't
had a chance to verify these with anyone else, but I hope they're mostly
correct. Feel free to post any corrections :)
1a)
addi $30, $30, -4
sw $4, 0($30)
jal mystery
addi $30, $30, 4
add $6, $0, $1
1b)
add $4, $0, $9
sll $9, $9, 2
add $9, $9, $3
lw $9, 0($9)
2a)
Define: I = ii(ii)* ; M = m(mm)* ; L = lambda
Then, the RE is: (M|L)(IM)*(I|L)
2b)
A,x,B
A,y,D
B,z,B
B,y,C
D,y,C
D,z,BD
BD,z,BD
BD,y,c
Accepting states: A and C
2c)
<S> -> <A><S>
<S> ->
<A> -> <B><C>
<B> -> x<B>
<B> ->
<C> -> y
<C> -> z
3a)
Show two distinct parse trees to represent the same input.
3b)
<E> -> <F>o<E>
<E> -> <F>
<F> -> <F>^<G>
<F> -> <G>
<G> -> 1
<G> -> 2
4a)
NT N? First Follow t v x y z EOF
<S> n tvxy EOF 1 2 1 1 E E
<A> y x tyz 3 E 4 3 3 E
<B> y yz t 6 E E 5 6 E
<C> y z t 7 E E E 8 E
<D> y xy t 8 E 8 8 8 E
4b)
<S> -> a<A>
<A> -> a<B>
<A> -> <B>
<B> -> c<C>
<C> -> c
<C> ->
4c)
<S> -> c<A>
<A> -> ab<A>
<A> ->
5a)
I don't think we covered this this term...
5b)
Pushes the symbol in "next" onto the stack; reads the next input symbol
into "next".
5c)
Pops the right-hand side of a rule off the stack, and pushes on the
left-hand side of the rule.
5d)
No, it would not be possible to construct the LR(1) DFA if the CFG was
ambiguous.
6)
Notes about my implementation: I use $1, $2, and $4 as scratch registers
(i.e. I don't worry about backing them up). <Expr> always leaves its
result in $1.
<Stmts>.code String Synthetic
ID.name {A,B} Synthetic
<Stmt>.code String Synthetic
<Expr>.code String Synthetic
<Stmts>1 -> <Stmts>2 <Stmt> SEMI
<Stmts>1.code = <Stmts>2.code + <Stmt>.code
<Stmts> ->
<Stmts>.code = ".word A\n" +
".word B\n"
<Stmt> -> IN ID
<Stmt>.code = "\ttrap 5\n" +
"\tsw $2, 0(" + ID.name + ")\n"
<Stmt> -> OUT <Expr>
<Stmt>.code = <Expr>.code +
"\tadd $4, $1, $0\n" +
"\ttrap 1\n"
<Stmt> -> ID ASSIGN <Expr>
<Stmt>.code = <Expr>.code +
"\tsw $1, 0(" + ID.name + ")\n"
<Expr>1 -> <Expr>2 MULOP ID
<Expr>1.code = <Expr>2.code +
"lw $2, 0(" + ID.name + ")\n" +
"mult $1, $2\n" +
"mflo $1\n"
<Expr> -> ID
<Expr>.code = "lw $1, 0(" + ID.name + ")\n"
7a) 55
7b) 11EF
7c) 1100 0001
7d) 1011 1111
8)
Address Hex
00000000 6007001C
00000004 ACE90004
00000008 2331FFF6
0000000C 02979820
00000010 94130000
00000014 0BFFFFFC
00000018 03E00008
0000001C FFFFFFF1
LLO, -, 00000000
OFFSET16, 00000010, on
im, 00000000
x, 00000018
9a) 0
9b) ((1 2) (1 2 3 4))
9c) ("scheme" "is" "fun") [ha :P]
9d) 35
9e) ((1 2) ((1 2 3 4)))
10)
(define parse
(lambda (in)
(cond
((null? in) #t)
((equal? (car in) 'y) (parse (cdr in)))
((null? (cdr in)) #f)
((and (equal? (car in) 'x) (equal? (cadr in) 'x)) (parse (cddr in)))
(else #f)
)))
11)
(define iterate
(lambda (proc n)
(lambda (x)
(letrec
((do-iterate
(lambda (proc n x)
(if (> n 0)
(proc (do-iterate proc (- n 1) x))
x
))))
(do-iterate proc n x)
))))
12)
(define M
(lambda (n)
(letrec
((M-it
(lambda (i x3 x2 x1)
(if (> i 0)
(M-it (- i 1) x2 x1 (+ x1 (* 2 x3)))
x3
))))
(M-it n 0 1 3)
)))

[James Schofield]

Hey, thanks Andrew, that makes sense.

James

Post by Andrew Craik
Hey,
Just one little correction to the mips code for the grammar question,
ID.name needs to be used with llo and lhi to get the address into a register
then that register can be used with the lw of offset 0, you can't use a
<Expr>1 -> <Expr>2 MULOP ID
<Expr>1.code = <Expr>2.code +
"lw $2, 0(" + ID.name + ")\n" +
"mult $1, $2\n" +
"mflo $1\n"
should be
<Expr>1 -> <Expr>2 MULOP ID
<Expr>1.code = <Expr>2.code +
"llo $2, " + ID.name + "\n" +
"lhi $2, " + ID.name + "\n" +
"lw $2, 0($2)\n" +
"mult $1, $2\n" +
"mflo $1\n"
assumingthe code surrounding the change is ok, which it seems to be
Andrew

[Jason Pang]

Hey James - thanks for the solutions! It's a great resource for us less-keen
;)

1b)
add $4, $0, $9 <<<<<< I think this line should read: add $9,

$0, $4 (destination comes first in MIPS)

sll $9, $9, 2
add $9, $9, $3
lw $9, 0($9)

The way you've implemented it now would overwrite the index that is stored
in register $4 with an unknown value in $9.
Probably just a typo, or that we're too into studying for 222 and remember
too much of Coldfire where destination comes last.

And there is a less efficient and equivalent way to implement it (for those
of us that don't ever remember to use sll... ):

addi $9, $0, 4 }
mult $9, $4 } which basically does what the first two lines does in
James' prog
mflo $9 }

THANKS!
JP (or Pang, whatever strikes your fancy)

[Felix Lo]

For 9c)

the one with scheme is fun, aren't there 3 missing brackets so that the
scheme code won't return anything (error / just won't run).

I typed it in scm and it is missing 3 brackets (unless my printout of this
final exam is wrong....)


Felix

Post by James Schofield
I thought I'd post my solutions for the S02 practice final. I haven't
had a chance to verify these with anyone else, but I hope they're mostly
correct. Feel free to post any corrections :)
1a)
addi $30, $30, -4
sw $4, 0($30)
jal mystery
addi $30, $30, 4
add $6, $0, $1
1b)
add $4, $0, $9
sll $9, $9, 2
add $9, $9, $3
lw $9, 0($9)
2a)
Define: I = ii(ii)* ; M = m(mm)* ; L = lambda
Then, the RE is: (M|L)(IM)*(I|L)
2b)
A,x,B
A,y,D
B,z,B
B,y,C
D,y,C
D,z,BD
BD,z,BD
BD,y,c
Accepting states: A and C
2c)
<S> -> <A><S>
<S> ->
<A> -> <B><C>
<B> -> x<B>
<B> ->
<C> -> y
<C> -> z
3a)
Show two distinct parse trees to represent the same input.
3b)
<E> -> <F>o<E>
<E> -> <F>
<F> -> <F>^<G>
<F> -> <G>
<G> -> 1
<G> -> 2
4a)
NT N? First Follow t v x y z EOF
<S> n tvxy EOF 1 2 1 1 E E
<A> y x tyz 3 E 4 3 3 E
<B> y yz t 6 E E 5 6 E
<C> y z t 7 E E E 8 E
<D> y xy t 8 E 8 8 8 E
4b)
<S> -> a<A>
<A> -> a<B>
<A> -> <B>
<B> -> c<C>
<C> -> c
<C> ->
4c)
<S> -> c<A>
<A> -> ab<A>
<A> ->
5a)
I don't think we covered this this term...
5b)
Pushes the symbol in "next" onto the stack; reads the next input symbol
into "next".
5c)
Pops the right-hand side of a rule off the stack, and pushes on the
left-hand side of the rule.
5d)
No, it would not be possible to construct the LR(1) DFA if the CFG was
ambiguous.
6)
Notes about my implementation: I use $1, $2, and $4 as scratch registers
(i.e. I don't worry about backing them up). <Expr> always leaves its
result in $1.
<Stmts>.code String Synthetic
ID.name {A,B} Synthetic
<Stmt>.code String Synthetic
<Expr>.code String Synthetic
<Stmts>1 -> <Stmts>2 <Stmt> SEMI
<Stmts>1.code = <Stmts>2.code + <Stmt>.code
<Stmts> ->
<Stmts>.code = ".word A\n" +
".word B\n"
<Stmt> -> IN ID
<Stmt>.code = "\ttrap 5\n" +
"\tsw $2, 0(" + ID.name + ")\n"
<Stmt> -> OUT <Expr>
<Stmt>.code = <Expr>.code +
"\tadd $4, $1, $0\n" +
"\ttrap 1\n"
<Stmt> -> ID ASSIGN <Expr>
<Stmt>.code = <Expr>.code +
"\tsw $1, 0(" + ID.name + ")\n"
<Expr>1 -> <Expr>2 MULOP ID
<Expr>1.code = <Expr>2.code +
"lw $2, 0(" + ID.name + ")\n" +
"mult $1, $2\n" +
"mflo $1\n"
<Expr> -> ID
<Expr>.code = "lw $1, 0(" + ID.name + ")\n"
7a) 55
7b) 11EF
7c) 1100 0001
7d) 1011 1111
8)
Address Hex
00000000 6007001C
00000004 ACE90004
00000008 2331FFF6
0000000C 02979820
00000010 94130000
00000014 0BFFFFFC
00000018 03E00008
0000001C FFFFFFF1
LLO, -, 00000000
OFFSET16, 00000010, on
im, 00000000
x, 00000018
9a) 0
9b) ((1 2) (1 2 3 4))
9c) ("scheme" "is" "fun") [ha :P]
9d) 35
9e) ((1 2) ((1 2 3 4)))
10)
(define parse
(lambda (in)
(cond
((null? in) #t)
((equal? (car in) 'y) (parse (cdr in)))
((null? (cdr in)) #f)
((and (equal? (car in) 'x) (equal? (cadr in) 'x)) (parse (cddr in)))
(else #f)
)))
11)
(define iterate
(lambda (proc n)
(lambda (x)
(letrec
((do-iterate
(lambda (proc n x)
(if (> n 0)
(proc (do-iterate proc (- n 1) x))
x
))))
(do-iterate proc n x)
))))
12)
(define M
(lambda (n)
(letrec
((M-it
(lambda (i x3 x2 x1)
(if (> i 0)
(M-it (- i 1) x2 x1 (+ x1 (* 2 x3)))
x3
))))
(M-it n 0 1 3)
)))

[Jason Pang]

9c runs fine for me. I don't see any missing brackets - they match up okay
for me

(cons "scheme" (cons (car '("is" "not" "fun")) ( cdr (cdr '("is" "not"

"fun")))))
CALL car ("is" "not" "fun")
RETN car "is"
CALL cdr ("is" "not" "fun")
RETN cdr ("not" "fun")
CALL cdr ("not" "fun")
RETN cdr ("fun")
CALL cons "is" ("fun")
RETN cons ("is" "fun")
CALL cons "scheme" ("is" "fun")
RETN cons ("scheme" "is" "fun")
("scheme" "is" "fun")

[Ali Navrozally]

Hey
I think
<S> n tvxyz EOF 1 2 1 1 E E
should be
<S> n tvxyz EOF 1 2 1 1 1 E
Let me know what you think.
Thanks,
Ali

----- Original Message -----
Newsgroups: uw.ece.ece251
Sent: Sunday, August 01, 2004 10:00 PM
Subject: Re: S02 Final Solutions

Post by Hansel Ip
Jimmy, on behalf of everyone trolling your post for exam solutions -
thank you!
Maybe one small correction I noticed, I think for Q8 the fifth assembled
MIPS code line (00000010) should be 14130000 instead of 94130000...

since

Post by Hansel Ip
the opcode for bne is 000101... unless I missed something.
Thanks again,
-HI