CS606 Compiler Construction Assignment#02 Solution & Discussion Due Date:16-11-2011

[+ M.Tariq Malik]

Question # 1:

Consider the following Grammar and remove the left-factoring from it.

A  xByA/xByAzA/a

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.

 

 

[+ M.Tariq Malik]

See the attached file for CS606 Assignment#02 Fall 2011

[+ M.Tariq Malik]

Assignment Statements:

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

 

[+ M.Tariq Malik]

one more idea solution of CS606 assignment#02 fall 2011