CSE 428: Home Assignments

Distributed: Jan 21.
Due: Jan 28 in class.
Total maximum score: 100 points.

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

[Points 30] Exercise 2.4 in Sethi
[Points 20] Exercise 2.6 in Sethi (Note: "Parse tree" in Sethi means "Derivation tree")

[Points 30] Consider the following grammar for "boolean expressions":
```
   BExp ::= true | false | not BExp | BExp and BExp | BExp -> BExp
```
- Show that this grammar is ambiguous
- Define a non-ambiguous grammar for the same language by enforcing the following conventions:
  - "not" has priority over "and", and "and" has priority over "->"
  - "and" is left-associative, and "->" is right-associative.
[Points 20] Define a grammar which generates all palindromes over the English alphabet. Note: a palindrome is any string which reads the same backward as forward. For example, the empty string, "a", "aa", "aba", and "abba" are palindromes, whereas "ab", "abb", and "abc" are not.