Homework 1: Syntax
Due
February 4
1. Given the following grammar rules:
unsigned_real → integer . integer
integer → digit | digit integer
digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
a) Write a complete leftmost derivation of the sentence (don't skip any steps): 624.93
b) Construct a complete parse tree for the sentence in part a).
2. Given the expression grammar in Example 2.8, construct complete parse trees for the sentences:
a) ( A + B ) * C
b) 4 + 6 * 2 * 3 - 9
3. Do parts (a) and (b) of Exercise 2.13 on p. 105.
4. Describe in English the language that the following grammar generates:
<S>
→ <A> <B> <C>
<A>
→
a <A> |
a <B>→
b <B> |
b <C>
→ c
<C> |
c
5. Do Exercise 2.10 on p. 104 (make the necessary modifications to the grammar in Example 2.8).
6. Define BNF grammar rules for a language that consists of binary strings with at least 3 consecutive 1 bits.
Examples:
Several valid strings in this language: 1011100101, 11111, 100101111
Several strings that are NOT valid: 1000110, 11011011, 10000000