CS 606 Compiler Constructions Solution of Assignment # 02 Fall 2011

Question # 1:
Consider the following Grammar and remove the left-factoring from it.
A 􀃆 xByA/xByAzA/a
B 􀃆b
Solution
A 􀃆 xA'/xA'zA/a
A' 􀃆ByA
Now
A 􀃆 xA'/xA'zA/a
A 􀃆 B'/B'zA/a
B'􀃆xA'
B 􀃆b
Question # 2:
Consider the following CFG.
statement--> variable ASSIGNOP expr
| procedure_call
| block
| IFTOK expr THENTOK statement ELSETOK statement
| WHILETOK expr DOTOK statement
Three of the productions for statement begin with non-terminals:
variable--> ID | ID LBRK expr RBRK
procedure_call--> ID | ID LPAR expr_list RPAR
block--> BEGINTOK opt_statements ENDTOK
No remove the left factoring from the given grammar.
Solution
In the productions for statement we replace nonterminals:
variable, procedure_call, and block, by the right-sides of their
productions to obtain:
statement--> ID ASSIGNOP expr
| ID LBRK expr RBRK ASSIGNOP expr
| ID
| ID LPAR expr_list RPAR
| BEGINTOK opt_statements ENDTOK
| IFTOK expr THENTOK statement ELSETOK statement
| WHILETOK expr DOTOK statement
Now every production for statement begins with a terminal but
four of the productions begin with the same terminal, ID, so we add a
new nonterminal, statement_rest, to the grammar and left factor ID
out of those four productions to obtain:
statement--> ID statement_rest
| BEGINTOK opt_statements ENDTOK
| IFTOK expr THENTOK statement ELSETOK statement
| WHILETOK expr DOTOK
statement statement_rest--> ASSIGNOP expr
| LBRK expr RBRK ASSIGNOP expr
| LPAR expr_list RPAR