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