The name of the course is called Compilers. We are using a tool called ANTLR.
Exercise 1
Consider the context-free grammar
S → S S + |S S* | a
a. Show how the string aa + a* can be generated by this grammar.
b. Construct a parse tree for this string.
c. What language does this grammar generate? Justify your answer.
Exercise 2
What language is generated by the following grammars? In each case justify your answer. Also describe each language informally using a sentence or two in English.
a. S → 0 S 1 | 0 1
b. S → + S S | - S S | a
c. S → S ( S ) S | ε
d. S → a S b S | b S a S |'
e. S → a | S + S | S S | S * | ( S )
Exercise 3
Which of the grammars in Exercise 2 are ambiguous?
Exercise 4
Construct a syntax-directed translation scheme that translates arithmetic expressions from infix notation into prefix notation in which an operator appears before its operands; e.g., -xy is the prefix notation for x - y. Give annotated parse trees for the inputs 9-5+2 and 9-5*2.
Programming Assignment
A really simple Scheme (RSS) expression takes one of two forms: a floating-point literal whose value is itself; or an application in which the function named by an operator is applied to the (argument) values of two expressions (its operands). A RSS program is a sequence of one or more newline-terminated expressions. Here is the syntax, with nonterrninals in italics, and tokens in uppercase or enclosed in apostrophes:
prog → (expr NEWLINE)+
expr → DOUBLE
| '(' RATOR expr expr ')'
RATOR → '+' | '*'|'/'|'^'
A floating-point literal (DOUBLE) is represented by one or more digits, optionally preceded by a minus sign, and optionally followed by a radix point (.) and zero or more digits. An operator is one of the standard symbols for the four basic arithmetic operations and exponentiation.
The program evaluates and prints each of the top-level expressions (i.e., that appears on its own line). In this example, user input is bold, and AZ is used to simulate end-of-file:
> java RSS
(+ 2 3.0)
(/ 9 (+ 2 1) )
84.3
(^ 2 3)
(+ (* 3 -4) (- 12 6) )
^Z
5.0
3.0
84.3
8.0
-6.0