Exercises 02

Exercise 1

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

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 2

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 3

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 4

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$ .