Exercises 02

Exercise 1

Show that the grammar

A -> − A
A -> A − id
A -> id

is ambiguous by finding a string that has two different syntax trees. Now make two different unambiguous grammars for the same language:
a) One where prefix minus binds stronger than infix minus.
b) One where infix minus binds stronger than prefix minus.
Show the syntax trees using the new grammars for the string you used to prove the original grammar ambiguous.

Exercise 2

The dangling-else problem happens when the conditional statements are parsed using the following grammar.

S -> S; S
S -> id := E
S -> if E then S
S -> if E then S else S

Find an unambiguous grammar that accepts the same conditional statements and matches the else statement with the nearest unmatched if.

Exercise 3

We call a production rule “left recursive” if it is of the form $A\rightarrow A\alpha$ . Similarly a right recursive rule is defined as $A\rightarrow\beta A$ . Show that any context free grammar that contains both left and right recursive rules for a single LHS nonterminal should be ambiguous.

Exercise 4

Compute the First and Follow sets for the nonterminals of the following grammar $\Sigma=\{a,b,c,d\}$ .

S  ->  SAa | ε
A  ->  ABb | ε
B  ->  BCc | ε
C  ->  d

Exercise 5

Find nullable, First and Follow sets for this grammar, then construct the LL(1) parsing table.

S' -> S$
S  ->
S  -> X S
B  -> \ begin { WORD }
E  -> \ end { WORD }
X  -> B S E
X  -> { S } 
X  -> WORD
X  -> begin
X  -> end
X  -> \ WORD

Exercise 6

The following grammar recognizes the language $L = \{a^nb^{n+m}\mid n,m\in\mathbb{N}\}$ .

S -> aSb | A
A -> bA  | ε

Show that no predictive descent parser can correctly predict the correct production rule for every element of $L$ .