You should submit your homework using the submit command "submit cs331 hw2 <yourFile>" between now and 11:59pm Wednesday, February 23. For this homework and future ones, we will accept homeworks up to three days late with a penalty of 10% for each day of lateness.

Problem one: recognizing sentences in a language (30 points)

Consider the following grammar:

<S> -> <A> a <B> b
<A> -> <A> b | b
<B> -> a <B> | a

Which of the following sentences are in the language generated by this grammar? (10 points each)

(1a) baab

(1b) bbbab

(1c) bbaaaaa

Problem two: expression grammar (30 points)

  <exp> ::= <id> | <int> | <exp>+<exp> | <exp>*<exp>
  <id>  ::= X | Y | Z
  <int> ::= <d> | <d> <int>
  <d>   ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

(2a) (10 points) Rewrite this grammar such that a unary negation operator can be applied to integer constants, but not to other expressions.

(2b) (10 points) Rewrite this grammar to allow octal constants of the form o0 or o777, that is, the letter 'o' followed by one or more digits in the range 0-7.

(2c) (10 points) Rewrite this grammar to allow identifiers consisting of either a single letter (X, Y, or Z) or a single letter followed by no more than two digits in the range 0-9. So X, Y1, and Z02 are valid identifiers, but not X123.

Problem three: an expression grammar (25 points)

Consider the following unambiguous grammar for arithmetic expressions similar to those discussed in class.

E -> E+T | E-T | T
T -> T*F | T/F | F
F -> (E) | VAR | INT
VAR -> a | b | c
INT -> 0 | 1 | 2| 3 | 4| 5 | 6 | 7 | 8 | 9

(3a) 5 points. What are the terminal symbols? What are the pre-terminal symbols? What are the non-terminal symbols? Does this grammar define a finite or an infinite language?

Take this grammar to be complete -- there are no other rules that we have not shown you.

(3b) 10 points. Modify this grammar to allow an exponentiation operator (^) so that we can write expressions like a+b^c*a. Make sure that your modified grammar is unambiguous. Give the exponentiation operator higher precedence than the other binary operators and (unlike the other binary operators) make it associate to the right.

Hint: Obviously you will have to modify and/or add grammar rules to do this. You might find it convenient to add a new non-terminal symbol. The formalism you use to describe your grammar is not important -- use any of the common notations you've seen in class.

(3c) 10 points. What is the leftmost derivation that your grammar assigns to the expression a^2^b*(c+1)? You may find it convenient to sketch the parse tree for this expression first, and then figure out the leftmost derivation from that.

Problem four: EBNF to BNF (15)

Assume that you have already been given grammars for the non-terminals <iden> and <expr> which represent identifiers and expressions, respectively. Rewrite the following EBNF grammar in BNF. You may create new non-terminal symbols if you wish.

<statement> ::= <ident> = <expr>
<statement> ::= IF <expr> THEN <statement> [ ELSE <statement> ] END
<statement> ::= WHILE <expr> DO <statement> END
<statement> ::= BEGIN <statement> {; <statement>} END