Assignment :

Exercise 1: Consider the context-free grammar:

5 → SS + \ss* \ a

and the string aa + a*.

a) Give a leftmost derivation for the string.

b) Give a rightmost derivation for the string.

c) Give a parse tree for the string.

d) Is the grammar ambiguous or unambiguous? Justify your answer.

e) Describe the language generated by this grammar.

Exercise 2: Repeat Exercise 1 for each of the following grammars and strings:

a) S     0 5 1 1 0 1 with string 000111.

Exercise 3: Design grammars for the following languages:

a) The set of all strings of 0s and 1s such that every 0 is immediately followed by at least one 1.

b) The set of all strings of 0s and 1s that are palindromes; that is, the string reads the same backward as forward.

c) The set of all strings of 0s and 1s with an equal number of 0s and 1s.

Exercise 4: The following is a grammar for regular expressions over symbols a and b only, using + in place of I for union, to avoid conflict with the use of vertical bar as a metasymbol in grammars:

rexpr        rexpr + rterm | rterm

rterm        rterm rfactor  \ rfactor

rfactor      rfactor * / rprimary

rprimary    a|b

a) Left factor this grammar.

b) Does left factoring make the grammar suitable for top-down parsing?

c) In addition to left factoring, eliminate left recursion from the original grammar.

d) Is the resulting grammar suitable for top-down parsing?

Programming Assignment:

A moderately simple Scheme (MSS) expression is similar to those of our previous language VSS, but supports the Boolean type in addition to the floating-point type. This includes the literals true and false, in addition to Boolean and relational operators. There is also a conditional if expression. Here is the grammar:

Prog         →   expr+

expr         →   DOUBLE
               |    BOOLEAN
               |    ID
               |   '(' RATOR expr* ')'
               |   '("def ID expr ')'
               |   '("if expri exprz exprj
BOOLEAN  →   'true' | 'false'
RATOR     →   ARITHMETIC I RELATIONAL I BOOLEAN
ARITHMETIC → '+' | '-' | '*' + '/'
RELATIONAL → '=' |'>'|'<'
BOOLEAN     → '&' |'|' |'!'

The conditional expression first evaluates its first expression expr₁ to obtain testVal. If testVal is true then the conditional expression evaluates to the value of expr₂, and if testVal is false then it evaluates to the value of expr J (it is a semantic error if expri is not of Boolean type).

You may wish to distinguish between Boolean and floating-point values when evaluating expressions to ensure semantic correctness, but I do not require such runtime error checking. It is also not required that you distinguish between Boolean and floating-point expressions in your grammar (e.g., your grammar need not enforce that the conditional's test expression is of type Boolean). Also, it's not required that you implement the Boolean operators (and, or, and not), but you should implement the relational operators (equal, greater-than, and less-than).

I suggest that you revise the representation of values in your interpreter. One way is to define a Val class capable of wrapping a Double or a Boolean value. Your symbol table, which stores variable bindings, would bind identifiers to Val objects, literals and variables would evaluate to Val objects, and operators would input a list of Val arguments and output a Val object.

As in the previous assignment (VSS language), your interpreter evaluates the top-level expressions in order and prints the value of the last expression. For programs that contain more than one top-level expression, all but the last one are generally there for side-effect. Here are some sample runs:

> java run
(def a (if (< 5 7) 2 4))
(* a 6)
^Z
12.0

> java run

(def flag (= 6 (+ 3 5)))
(if flag (+ 1 2) (* 3 4))
^Z
12.0

This illustrates semantics involving the Boolean type:

true => true
(! true) => false
(&) => true // identity for and
(& true) => true
(& true false) => false
(|) => false // identity for or
(| false) => false
(> 7) true // each element is > than its successor
(> 7 5) =>. true
(> 7 5 2) =>. true
(> 7 8 5 3) => false
(< 4 6) =>, true
(= 4 (+ 2 2)) =>, true
(= 3 3 7) => false
(!(< (+ 2 2) (* 2 3))) => false
(if true 3 4)              => 3.0
(if (< 6 3) 5 (* 6 3))  => 18.0
(if (= 3 (+ 2 1))
(if true 4 5)

(if false 6 7)) => 4.0