Programming Languages assignment I

Assignment I

Due date Tuesday January 30.


1. Consider the grammar:

         S -> aS | aSbS | epsilon

where S is the only non-terminal, and epsilon is null string.

a) Show that the grammar is ambiguous, by giving two parse trees for the
string aab.

b) Show (by induction, e.g.) that this grammar generates strings such that in
any prefix of the string there are at least as many a's as b's. (Optional:
show that all such strings are generated by this grammar).

c) Find an unambiguous grammar that generates these strings.

2. Consider a simple language with the following non-terminals:

stat-seq   : a sequence of statements
if-stat    : if-statement, both branches have a sequence of statements
while-stat : a loop construct, whose body has a sequence of statements
func-def   : a function definition, whose body is a sequence of statements.
ret-stat   : a return statement
any-stat   : any of the above, assignment, goto, etc.,

Most languages have the semantic requirement that a function body have at least
one return statement somewhere, possibly nested in a loop or a conditional
statement.

For the non-terminals above, write the productions that enforce this rule,
namely that a function definition contain  at least one return statement.
You will want to introduce additional non-terminals.

Comment: this kind of semantic restriction can be expressed grammatically, but
as you will see, it makes the grammar larger and harder to understand, In
practice, this kind of restriction is better stated in prose, and such a rule
is not enforced by the parser of a compiler, but by a separate semantic check.