CS606 assignment # 2 solution

CS 606 Compiler Constructions

Fall 2011

Total Marks = 20

Deadline

Your assignment must be uploaded / submitted before or on November

16, 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

| e