This is a sample of the sort of thing you can expect in the two module assessments.

It consists of six multi-choice questions. It shouldn’t take you more than an hour to do. In the actual assessments you will have 24 hours from the time they go live to complete them and upload your answers to Sulis. This is to allow for potential issues with Sulis.

The questions may require you to write small programs. Make sure you have access to a version of flex and a C-compiler.

Upload your answers in the form:

i.e., a simple line of text consisting of a question number followed by a space, followed by an answer letter, all repeated six times and separated by spaces. If you don’t know an answer, and don’t want to guess, put a dash after the question number (as in response 5 above).

Each question is worth 5 marks (i.e. 5% of the total module marks). Any incorrect answer will attract a penalty of -1.6 marks.

1. Consider this grammar.

A   →   Aa l a l e

What language does it define and what is the “most elegant” (i.e.  shortest) equivalent grammar?

A.  {a＋},   A → Aala.          B.  {aa* },   A → aAla.

C.  {a* },    A → aAlela.       D.  {a* },     A → aAle.

5 marks (-1.6 marks for incorrect).

Answer is D. C is an equivalent grammar, but not the shortest here. A and B are both the wrong language. 

2. Convert the following EBNF grammar to equivalent right-recursive BNF.

A   →   B { a B }

B   →   b { c b }

A.   A    →   BA\                            B.   A    →   BA\   A\     →   aBA\                                    A\     →   aBA\ A\     →   e                              A\     →   aB   B    →   bB\                                         B    →   bB\     B\     →   cbB\                                       B\     →   cbB\  B\     →   e                              B\     →   cb

C.   A   →   AaB                  D.   A   →   BaB A   →   B                              B   →   bcb   B   →   Bcb

B   →   b

5 marks (-1.6 marks for incorrect).

Answer is A. B is not an equivalent grammar. C is left-recursive. D is just wrong, not

even close to the EBNF.

3. Find the LL(1) Predict sets for this grammar. Is it LL(1)?

X   →   a X b  l  Y c X l d

Y   →   X y Y  l  e

A. B. C. D.

Yes.

No.

Yes.

No.

5 marks (-1.6 marks for incorrect).

Answer is D. It’s not LL(1) because of non-null intersections between sets (1) & (2) on a, (2), (3) on d and (4) & (5) on c (productions (1), (2) & (3) have a common lhs, X , as do (4) & (5), Y). C gives the right sets but the wrong answer about LL(1). A and B have the wrong predictor sets. 

4. Consider the procedure definition

PROCEDURE p1(a, REF b, REF c, d);

BEGIN

b := a * c - 3 * d;

END;

What assembly code is generated for the assignment statement?

A.    Load FP-4            B.    Load FP-4             C.    Load FP-4            D.    Load FP-4 Load FP-2                     Load FP-3                     Load FP-2                    Load FP-3 Mult                               Mult                               Load [SP]                     Load [SP] Load #3                         Load #3                        Mult                               Mult

Load FP-1                     Load FP-1                     Load #3                        Load #3    Mult                               Mult                               Load FP-1                    Load FP-1 Sub                               Sub                               Mult                               Mult          Store FP-3                    Store FP-2                    Sub                               Sub

Load FP-3                    Load FP-2 Store [SP]                    Store [SP]

5 marks (-1.6 marks for incorrect).

Answer is C. D has the addresses of b & c mixed up. A is treating everything as value parameters, and so is B, but with addresses mixed up.

5. This is a graph of an NFA for the regular expression (ablac)* d.

e

1                   3

0                                                              5

c

Use the subset construction to convert it to a DFA. Select the version generated by the subset construction from the options below.

b

d

b

b|c

5 marks (-1.6 marks for incorrect).

Answer is B. A is a correct DFA for the question’s NFA, but is not produced directly by the subset algorithm (although the state minimisation algorithm can generate it from the output of the subset algorithm).  C and D correspond to the regular expression a(blc)* d. C is the output ofapplying the Thompson construction to a(blc)* d, followed by the subset algorithm. D follows this with the state minimisation algorithm (which wasn’t covered in the module, in case you are wondering).