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.