Exercise 1: Build syntax tree
We consider the following grammar for expressions (which
is the grammar Version 6 of the course
notes)
E --> T | E - T | E + T
T --> SE | T * SE | T / SE
SE --> V | C | ( E )
V --> A | B
C --> 0 | 1 | 2 | 3
Please write down the syntax tree for the following expression:
A + ( 2 + B ) / ( 2 * A )
Exercise 2: Modify grammar
We consider the same grammar as in Exercise 1. Your task
is to modify the grammar in order to allow for the exponentiation operator
** in expressions. The priority of this operator should be higher than
the priority of * and /, and the order of evaluation in the case of multiple
exponentiation operators should be from right to left, that is, the value
of the expression 3 ** 3 ** 3 should be 3 ** 9, and not 9 ** 3 = 3 ** 6
).
Exercise 3: Understand grammar
We consider the following grammar (with root symbol A):
A --> a A a | b B c
B --> b B | B c | b |
c
Please explain in some words what is the language generated
by this grammar. (Note: your answer could start like this: The language
generated by this grammar consists of all strings formed from the alphabet
{a, b, c} which have the following property .... )
Exercise 4: Ambiguity
Question (1): Is the grammar of Exercise 3 ambiguous
? -- Explain why it is ambigous or why it is not ambiguous.
Question (2): Is the following grammar ambiguous
? -- Explain why it is ambigous or why it is not ambiguous.
Grammar (with root symbol A):
A --> a A c | a A | b
Note: Does this grammar make you think of somethings
discussed in class ?
Exercise 5: Design a grammar
Write down a grammar which generates all sentences of
the following form:
A sentence starts with an x, then has a certain number
of y (at least 2), then a certain number of z (possibly none) followed
by one u and a certain number of v, and finally terminated by another x.
The number of y and the number of v must be equal.
(Note: This is an example of a "garden grammar": think of x as a fence, y as red flowers, v as blue flowers, u as a house and z as some small bushes. The grammar describes gardens that have some bushes in the middle next to a house, some red and blue flowers (equal numbers) on both sides and a fence around.)
Exercise 6: Regular languages
We consider the following regular grammar (with root
symbol A):
A --> a A | c A | b B
| epsilon
B --> a B | c C
C --> a A
Question (1): Why is this grammar regular ?
-- Explain in a few words.
Question (2): Build an automaton that accepts
exactly the language generated by the above grammar.
Question (3): Write down a regular expression
that defines exactly the language generated by the above grammar.
Exercise 7: LL(1) grammars
Question (1): Is the grammar of Exercise 6 LL(1)
? -- Explain in a few words.
Question (2): Is the following grammar LL(1) ?
-- First please calculate the sets FIRST and FOLLOW that are important
for this example. Then explain why the grammar is LL(1) or is not LL(1).
A --> a B C | c C
B --> b C | D
C --> b C | c
D --> A B D | d
Question (3): Same as Question (2), except that
the grammar now has the additional rule B --> epsilon.
