### Spring 2002, CSE 428: Assignment 1

Distributed: Jan 16.
Due: Thu 24 Jan in class.
Total maximum score: 100 points.

The purpose of this assignment is to provide experience with programming language syntax and context-free grammars.

1. [Points 20] Do exercise 2.7 (page 47) in the Tucker and Noonan book.

2. [Points 25] Consider the alphabet (set of terminal symbols) {a,b}
1. Define a grammar which generates all strings of the form   anbn+kak   for n, k natural numbers. For instance, lambda, ab, ba, abba, aabb, aabbba, abbbaa, etc.

Notation:   xm stands for the string obtained by repeating x m times.

2. Define a grammar which generates all strings on {a,b} with length at least 5.

3. [Points 25] Consider the following grammar for "boolean expressions":

```   BExp ::= false | true | BExp and BExp | BExp imp BExp | not BExp
```

1. Show that this grammar is ambiguous.
2. Define a non-ambiguous grammar for the same language by enforcing the following conventions:
• "not" has highest priority. "and" has intermediate priority, and "imp" has lowest priority.
• "and" is left-associative, and "imp" is right-associative.

4. [Points 30] The following grammar is motivated by declarations in C:

```
Non-terminals:  Declaration, Type, Declarator
Terminals:      int, char, *, number, name, '[', ']', '(', ')'

Declaration ::= Type Declarator
Type ::= int  |  char

Declarator  ::= * Declarator
| Declarator '[' number ']'
| Declarator '(' Type ')'
| '(' Declarator ')'
| name

```
Here, the start symbol is Declaration.
1. Prove that this grammar is ambiguous: that is, produce a word with two different derivation trees (draw the trees).
2. The constructs '[' number ']' and '(' Type ')' can be thought of as being postfix operators with a declarator as an operand. Suppose that * has lower precedence than these operators. Write an unambiguous grammar that generates the same strings as this grammar and make it easy to identify the components of a declarator.
3. Suppose that the first production for Declarator is changed to make * a postfix operator. That is, suppose that the first production for Declarator is changed into the following production:
Declarator ::= Declarator *
Why is the resulting grammar unambiguous?