CS代写 COMP712 Tutorial #11: Syntax Analysis – cscodehelp代写

COMP712 Tutorial #11: Syntax Analysis

1. Factor the following grammar:

C if E then S | if E then S else S

C if E then S [else S | null]

2. Show that an LL(0) parser for this grammar would be inefficient.

S ES

E T+E | T
T i*T | iE

Hint: Consider parsing i * i.
T + E
T

Have to parse i * i again!
i * T

FAIL, no +

i
i * T

FAIL, no *

3. How do you improve upon the grammar in Question 1? Show how you parse the sentence i * i with your new grammar.

Use factoring to produce E T [+E | null] and T I [*T | null]

S

E

T

i * T

i

4. What problem will you encounter parsing the grammar below using an LL(0) parser?

E I | BE
BE I = I
I i

You will fail to parse BE or the input i = i.

5. What problem does one face in designing a language that allows “goto” to jump into a label declared in an inner block as shown below.

Begin integer y;
:
:
goto x;
:
Begin real z;
:
:
x: print(z);
:
End;
:

This would cause problem in allocating storage during run time! Henceforth, this is usually not allowed.

6. What is de-referencing? Show what happens to the symbol table when the parser reaches the point “*” in the program.

Begin integer r;
:
:
:
Begin real x, y;
:
end;*
:
End;

“y”

flags

/
P1
P2
/

“x”
/

flags

/
P1
P2

De-referencing is the process of removing references in the symbol table to variables declared in the current block as the parser finishes parsing that block.

Begin integer r;
:
:
:
Begin real x, y;
:
end;*
:
End;

“y”

flags

/
P1
P2
/

“x”
/

flags

/
P1
P2
/
/

7. Explain what happens when the parser reaches the end of the program. How does a compiler detect such errors?

Begin integer y;
:
:
goto x;
:
Begin real z;
:
:
Begin
:
goto x;
:
:
End;
:
x: print(z);
:
End;
:
:
End

It generates an error because the first label for x is not declared. To detect such errors, the compiler needs to maintain a list of forward referenced variables. At the end, anything left on the list would be undeclared and hence an error.

Leave a Reply

Your email address will not be published. Required fields are marked *