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?