Recall the grammar for the tiny language used in our discuss

Recall the grammar for the tiny language used in our discussion of recursive-descent parsing. Let us extend the grammar to allow both if-then and if-then-elsestatements:

Show that the grammar is now ambiguous.

Solution

Parser implementation :

final int IF=1, THEN=2, ELSE=3, BEGIN=4, END=5, PRINT=6,
SEMI=7, i=8, ;
int tok = getToken();
void advance() {tok=getToken();}
void eat(int t) {if (tok==t) advance(); else error();}
void S() {switch(tok) {
case IF: eat(IF); E(); eat(THEN); S();
eat(ELSE); S(); break;
case BEGIN: eat(BEGIN); S(); L(); break;
case PRINT: eat(PRINT); E(); break;
default: error();
}}
void L() {switch(tok) {
case END: eat(END); break;
case SEMI: eat(SEMI); S(); L(); break;
default: error()

Conclusion :

FIRST(E+T) = {id, i ( } FIRST(T) = {id, i, ( }
Upon encountering (4*2)+6, which production do we choose
if we only know the first token, ( .
This shows that grammar is now ambiguous.

  E -> i