exercises

16. dialogue notations and design

EXERCISE 16.8 [extra - not in book]

Here are two different BNF specifications of an English Policeman:

Specification BNF1

sentence   :=     empty
               | 'hello' sentence
               | '(' sentance ')' sentence

Specification BNF2.

sentence   :=    'hello'
               | sentence sentence
               | '(' sentence
               | sentence ')'

The traces (a)-(q) represent potential 'sentences'. For each one, say whether it is a valid trace for 'sentences' for either Spec. BNF1, Spec BNF2, neither or both.

(a) hello
(b) hello (hello)
(c) ((hello)
(d) ()
(e) (hello) hello
(f) ((hello)) hello
(g) hello () hello
(h) (hello hello)
(i) ) hello (
(j) hello ) ( hello
(k) hello ()
(l) (hello) hello (hello)
(m) (hello ( (hello) hello
(n) (((hello))))
(o) ((((hello))))
(p) ((((hello())))
(q) (((hello())))

answer available for tutors only

(a) hello both
(b) hello (hello) both
(c) ((hello) 2 only
(d) () 1 only
(e) (hello) hello both
(f) ((hello)) hello both
(g) hello () hello 1 only
(h) (hello hello) both
(i) ) hello ( neither
(j) hello ) ( hello 2 only
(k) hello () 1 only
(l) (hello) hello (hello) both
(m) (hello ( (hello) hello 2 only
(n) (((hello)))) 2 only
(o) ((((hello)))) both
(p) ((((hello()))) neither
(q) (((hello()))) 1 only

Other exercises in this chapter

ex.16.1 (ans), ex.16.2 (ans), ex.16.3 (ans), ex.16.4 (ans), ex.16.5 (tut), ex.16.6 (tut), ex.16.7 (tut), ex.16.8 (tut), ex.16.9 (tut), ex.16.10 (tut), ex.16.11 (open)

all exercises for this chapter