10/20/21
Tutorial 11: Parsing
Q1; Factor the following grammar: C¨if E then S | if E then S else S C¨if E then S [else S | null]
Q2: Show that an LL(0) parser for this grammar would be inefficient.
S Input: i*i
E T+E T
S¨E E¨T+E | T T¨i*T | i
i * T i*i*ii
from
input Fail, no *
i
Fail, no +
i, 2nd i from the input
12
Q2a: Complete the parsing: i*i
S¨E E¨T+E | T T¨i*T | i
i * T
S Input: i*i
E
T+E T
i Fail, no + i * T
i
i*i*ii i*i*ii
from input
Fail, no *
i, 2nd i from from
the input
Fail, no *
i, 2nd i from the input
input
Q3: How do you improve upon the grammar in Question 2? Show how you parse the sentence i * i with your new grammar.
S¨E E¨T+E | T T¨i*T | i
S Input: i*i T¨i [*T | null] E
T i*i
E¨T [+E | null]
34
Q4: What problem will you encounter parsing the grammar below using an LL(0) parser?
E¨I | BE BE¨I = I I¨i
You fail to parse BE or the input i = i.
Q5: 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; :
56
1
10/20/21
Begin integer y; :
:
goto x;
:??
How do we know how many variables have been allocated in that block and what their values are?
It just doesn¡¯t make sense to jump into an inner block?
Begin real z; :
:
x: print(z); :
End; :
?
?
?
?
Q5a: OK, so what happens when you jump out to an outer block?
Begin integer y; :
goto x;
:
Begin real z, t;
:
Begin integer y; :
goto x;
:
End;
:
End;
:
x: print(y);
End
78
Begin integer y; :
goto x;
:
Begin real z, t;
What is the result of parsing the first ¡°goto x¡±?
:
Begin integer y; :
goto x;
:E n d ; :
End;
:
x: print(y);
End
Tree
……
/ ¡°y¡±
………
/ ¡° x ¡±
P2 flags /
Where?
print
F l a g s : Declared:Prov
goto x
/
Type: prov.label
Reserved or user-defined
Block level: 0
Offset: 0 Anything else?
P1
Pointer to code!
Begin integer y; :
goto x;
:
Begin real z, t;
What is the result of parsing the second ¡°goto x¡±?
:
Begin integer y; :
goto x;
:E n d ; :
End;
:
x: print(y);
End
Tree
……
/ ¡°y¡±
………
/ ¡° x ¡±
P2 flags / P1 P2 flags /
F l a g s : Declared:Prov
goto x /
print
Type: prov.label Reserved or user-defined Block level: 2
Offset: 0
P1
9 10
Begin integer y; :
goto x;
:
Begin real z, t;
What is the result of parsing ¡°x:¡±?
Tree
……
/ ¡°y¡±
………
/ ¡°x¡±
P1 P2 flags / P1 P2 flags /
:
Begin integer y; :
goto x;
print
:End;
:
End;
:
x: print(y);
End
goto x /
goto x
/
Did we miss something?
Begin integer y; :
goto x;
:
Begin real z, t;
What happens after ¡±;¡± at point *?
:
Begin integer y; :
goto x; *
print
Tree
……
/ ¡°y¡±
………
/ ¡°x¡±
P1 P2 flags / P1 P2 flags /
:End;
:
End;
:
x: print(y);
End
goto x /
goto x
/
11 12
2
10/20/21
Begin integer y; :
goto x;
:
Begin real z, t;
What happens after ¡±;¡± at point *?
Tree
……
/ ¡°y¡±
goto ………
/ ¡°x¡±
:
Begin integer y; :
goto x; *
print
:End; goto
:
End; x/ :
x: print(y);
End
x /
P1 P2 flags /
Need to de-reference the label x
What is the result of parsing ¡°x:¡±?
Tree ……
goto x/
goto x /
/ ¡°y¡±
… … …
/ ¡°x¡± P1 P2 flags
print
Flags:
Declared: Yes
Type: label Reserved or user-defined Block level: 0
Offset: 0
You create P3 and update the flags
13 14
Begin integer y; :
goto x;
:
Begin real z, t;
:
Begin integer y; :
goto x;
:
End;
:
End;
:
x: print(y);
End
What about memory allocation?
y Blk2 zt B l k 1 y Blk0
Q6: 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;
/ ¡°x¡±
P1 P2 flags /
/ ¡°x¡±
P1 P2 flags /
/ ¡°y¡±
P1 P2 flags /
/ ¡°y¡± P1 P2 flags
/
15 16
Q7: Explain what happens when the parser reaches the end of the program.
Begin integer y; :
goto x;
:
Begin real z;
:Begin
:goto x; :
End;
:
x: print(z); :
End;
:
End
It generates an error for undeclared label x.
Q7: And, how does the compiler detect such errors?
goto x;
:Begin real z; :
Begin
:goto x; :
End;
:
x: print(z); :
End;
:
End
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.
Begin integer y; :
17 18
3
10/20/21
Parsing
Provide one derivation for the sentence aaabbbccc from the grammar G:
1. S¨aBC
2. S¨aSBC
3. aB¨ab
4. bB¨bb
5. CB¨BC
6. bC ¨bc
7. cC¨cc
S¨2 aSBC¨2 aaSBCBC¨1 aaaBCBCBC¨3 aaabCBCBC¨5 aaabBCCBC¨4 aaabbCCBC¨5 aaabbCBCC*¨5 aaabbBCCC ¨4 aaabbbCCC¨6 aaabbbcCC ¨7 aaabbbccC¨7 aaabbbccc
At step 7(marked *) you use rule 5 to shift the B to the front and not rule 6 to convert bC to bc.
19
What are the three desiderata for the design of programming languages?
An ambiguous grammar
An effective implementation
An underlying machinery powerful enough to support its interpretation
19 20
4