Programming Languages assignment I
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.