CS314 Fall 2007
Assignment 2

#1. Scott Ch 2, #2.9a. 

b. Give an example of a sentence in this language (abaa is not an
acceptable answer) and show its parse tree.

c. Give an example of a sequence in (a|b)* which is not in the
language generated by nonterminal S. 

d. Can the statements in the language generated by this grammar be
parsed deterministically in top-down fasion, if you are allowed to see 1 token
lookahead in the input stream? (i.e., intuitively, this is what an
LL(1) language is defined to be.) Justify your answer briefly.

#2. The following grammar generates a subset of the formulae in propositional
logic:

     P ::= a|b|c|...|z
     P ::= P ^ P
     P ::= P v P (here v is the or symbol)
     P ::= P --> P
     G ::= P

a. Is this grammar ambiguous? Justify your answer

b. Usually we interpret x-->y-->w as if it were grouped as:
(x-->(y-->w)).  What does this mean about the precedence of and the
associativity of the implication operator (-->)?

c. Using the usual relative precedences for and (^) and or (v), write a new 
unambiguous grammar for this subset of propositional logic formulae.

#3.(Note this was problem 4 on assignment 1)
    Assume you have a language with binary operators $, @, and %.
    Expressions in this language may contain variables  that consist
    of one lower case letter and single digit constants.

 a. Give a context-free grammar in BNF which implements the following 
    associativity and precedences"

        $,@ left associative;  % right associative;

        $ weakest precedence, % stronger precedence, @ strongest precedence

 b. Give the parse tree and abstract syntax tree generated by your
    grammar for the expression: a$b$1%3@5%a$d.