Mock exam (4 questions, time one hour)
This is an exercise for students to prepare for their final
exams (as promised). It aims to
give students familiarity with the style of examiners. It is by no means similar to the actual
exam (however there will be no twist in the actual one).
1) scanner
Given the following FSM. 1 is the
starting state and X is the acceptant state. Given the following input stream, break
it into "token". If there
is an error, indicate the position where the error occurs and restart from the
next character. (It will be easier
to draw the diagram first, I did it this way because of
my limit of input).
state
input next
state
1 A B C 1
;
X
0 1 2
3 2
+
3
2 0 1 2 3 1
[ X
3 +
X
-
X
input
a) 011[AB;+++-
b) ACA+-A02;1[++
c) ;020A++A[;
2) Context free grammar
Given a CFG, write a recursive descent parser in pseudo code
(in style of nut or C)
the terminals are ( ) + - * / id
CFG
E -> E O E | (E) |
id
O -> + | - | * | /
3) parser
Given a parser program, which sentences pass this parser
correctly?
A parser "fundef" starts with one token in hands "tok". (lex) reads the
next token. (expect
t) checks if tok is t, if not it reports an error and stops. (ex) parses an expression (whatever it is). (return 1) means success, (return 0) means fail. [This piece of code is modified from my
real parser from a part of Som language.]
(def
fundef () ()
(if (eq tok
IDEN )
(do
(lex)
(args)
(expect
EQ)
(lex)
(ex)
(return
1))
; else
(return
0)))
(def
args () ()
(do
(while (eq tok
IDEN)
(lex))
(if (eq tok '|')
(do
(lex)
(local)
(return
1))
; else
(return
1))))
(def
local () ()
(do
(while (eq tok
IDEN)
(lex))
(return 1)))
sentences
a) IDEN IDEN | IDEN
EQ ex
b) ex IDEN EQ IDEN
c) IDEN IDEN EQ IDEN
ex
4) code generation
Given a source program, its parse tree and an instruction
set. Write the output code.
You have to write the sequence of code according to some fixed rule with respect to the parse tree (similar to automatic generation). Do not use your own assembly language programming skill to translate from the source directly.
source
if A == 1 then B = 11
else if A == 2 then B = 22
else B = 33
parse tree
<if>
|
---------------------
|
|
|
<cond> <then> <else>
|
|
|
== <assg> <if>
|\ =
|
| \ |\
--------------------
A 1
| \
|
|
|
B 11 <cond> <then> <else>
|
|
|
== <assg> <assg>
|\ =
=
| \
|\ |\
A 2 | \ | \
B 22 B 33
instruction set
r is a register capable of holding
a variable
im is an immediate value (constant)
flag is an internal flag holds a
boolean value
instruction
meaning
eq r,im
if r == im then flag = true
set r,im
r = im
jmp-if-true <label> if flag == true goto <label>
jmp-if-false <label> if flag == false goto <label>
jmp <label>
goto <label>
14 September 2009