1. [1 mark] Describe in English the sentences that will be produced by the following grammar.
Sentences consist of the terminal symbols a, b, c, y, and z. You must identify the
number (e.g. one, zero or more, zero or one, one or more) of occurrences of each symbol.
S → a S b b | X
X → c X | c Y
Y → y Y | z Y |
2. [1 mark] Write the BNF grammar rules for the language whose sentences have the
following structure
x
+(b | c | d)
∗
[k]
This is expressed in EBNF notation, where the + superscript indicates one or more occurrences,
and the ∗ superscript indicates zero or more occurrences. Alternation is expressed
by the (. . . | . . .) construct. An optional symbols are enclosed in square brackets: [. . .].
3. [1 mark] Consider the following grammar
assign → id := expr
id → A | B | C
expr → expr + term | term
term → term * f actor | f actor
f actor → id | - id
Now consider the sentence of the grammar:
A := - A + B * C
Produce a rightmost derivation of this sentence.
4. [1 mark] For the grammar and sentence in Question 3, show the parse tree for the
sentence.
5. [1 mark] For the grammar and sentence in Question 3, show the abstract syntax tree
for the sentence.
6. [1 mark] Consider the following grammar
S → a S | b S | T
T → T c | b |
Prove that the grammar is ambiguous.
1
7. [1 mark] Write an unambiguous grammar in BNF that describes the same language as
the grammar described in question 6.
8. [1 mark] Draw a single syntax diagram to describe the following EBNF grammar rule.
Assume ident and def parameter are defined elsewhere (you may simply refer to them in
your diagram). Terminal symbols are enclosed in boxes , and superscript ∗ means zero or
more occurrences. (N.B. Recall that the symbols ( ) [ ] and | are EBNF metasymbols and
will not appear in your diagram.)
parameter list → ( def parameter , )
∗
( * identif ier [ , ** identif ier ]
| ** identif ier
| def parameter [ , ] )
9. [2 marks] Write a small program in the ‘Go’ language that implements a simple linear
search function and tests it. Two example implementations in C and JavaScript are
provided. Your solution should mimic these programs, and produce very similar output.1
In particular:
• Implement 3 functions: main, test, and search. (Note that the JavaScript program
does not use a separate main function, but the C program does and your Go programs
will.)
• Use the same test array (values 5,3,9,11,71) and test strategy (try to find each value
in the array, and one value that is not in the array).
• Note that the C version passes an explicit array length value to test() and search(),
while the JavaScript does not. This is because JavaScript can check array sizes while
C can’t. Go, like JavaScript, can check array sizes, so you will not need the explicit
size parameter to these two functions.
Your Go search function should be different from the two provided examples on one key
aspect: it must return two values. The C/JavaScript search function returns a single
integer that is the index of the located value; if the value is not found then -1 is returned.
This is ‘bad’ programming as the single return value has two meanings: a ‘value found’
indicator and an array index. Go (like Haskell) can return multiple values. You should
use a Go function declaration like
func search(a []int, val int) (found bool, key int)
that returns a found value (true or false) as well as the index (key) value. If the index is
not found you can return any value for key as it will not be used.
Include a listing of the program in the assignment submission. I will not be compiling and
executing the code, so don’t submit a separate source file.
All you need to know about Go is at the language web site https://golang.org/. If you
wish you can download and install the Go system as documented there. (Linux users can
simply install the Go package: golang) It would be useful to compile your program to to
make sure it is correct, but it is not necessary for this assignment.