CS3342 – Assignment 2 due Feb. 24, 2021
1. (20pt) Consider the following grammar:
S′ −→ S$$ S −→ aSa S −→ ε
(1) (10pt) Prove that G is not SLR(1). (Use the definition on the last slide of the Syntax chapter.)
(2) (10pt) Construct G′, equivalent with G, that is SLR(1). Prove that G′ is SLR(1). You can use jflap to compute the parse table and show there is no conflict; include the jflap answer (whole window) in your answer.
Solution:
(1)
10pt for correct identification of the conflict; 0pt for using Jflap only, without explanation
The first state of the parser is:
S′ −→ •S$$ S −→ •aSa S −→ •
There is a shift/reduce conflict between the last two items: a ∈ first(aSa) ∩ follow(S). An alternative solution uses the state obtained from the first by reading a:
S −→ a•Sa S −→ •aSa S −→ •
and which has the same shift/reduce conflict as above.
(2)
9pt for any correct grammar; 1pt for using Jflap
S′ −→ S$$ S −→ aaS S −→ ε
An equivalent grammar, G′, is:
Jflap SLR(1) construction shows no conflict.
1
2. (20pt) Consider the following program in a language where variables are automatically initialized with 0 and x, y, z are constants that were defined before the program fragment shown.
int a;
f(n) { a = n; }
g() { print a; }
h() { f(x); g(); }
k() { int a; g(); f(y); }
f(z); g(); k(); g(); h(); g();
(1) (16pt) Give the output of the program for (a) static scoping and (b) dynamic scoping. Explain your answer by running the program in each case step by step, including full details concerning variable assignments and output of print statements.
(2) (4pt) Find for what values of x,y,z the output of the program is the same with static or dynamic scoping.
Solution:
(1)
for each (a)-(b), 1pt for correct description of each function call (6pt), 2pt for correct output
(a) There are two variables a: global and local. With static scoping, the local a is never used, as f() and g() both refer to the global a.
Program run for static scoping:
initialize global a to 0
f(z): set global a to z
g(): print global a = z
k(): initialize local a to 0; print global a = z; set global a to y
g(): print global a = y
h(): set global a to x; print global a = x
g(): print global a = x
Output:
z, z, y, x, x
(b) With dynamic scoping, the local a will be used when inside k():
Program run for dynamic scoping:
initialize global a to 0
f(z): set global a to z
g(): print global a = z
k(): create binding to local a, initialize local a to 0; print local a = 0; set local a to y; when k() ends, the local binding is destroyed a and refers again to global a
g(): print global a = z
h(): set global a to x; print global a = x
g(): print global a = x
Output:
z, 0, z, x, x
(2)
3. (20pt) Consider the two Python programs below:
The two outputs are the same if and only if y = z = 0.
2
4pt for correct answer, subtract 2pt for each error
# program P1
def A(I, P):
def B():
print(I) ifI>2:
P() elifI>1:
A(3, P) else:
A(2, B)
def C():
print(2)
I= input() A(I, C)
(1) (1pt) Find the differences between the source code of the two programs.
(2) (2pt) Find the output of each program for all possible real values of I.
(3) (2pt) Find the real values of I for which the two programs have the same output.
(4) (15pt) Explain the output of each program in all details. For all possible cases, provide drawings of the stack showing the frames for all subroutines and the static links indicating which procedure each P refers to and which variable the I in print(I) refers to. Provide as much information as necessary to clarify what happens during the running of the programs.
Solution:
(1)
(2)
(3) (4)
1pt for the meaningful difference
The difference is in the ”I > 1” branch: P1 has A(3, P) whereas P2 has A(3, B). (There is also a difference in the first line comments, but that does not affect the behaviour.)
1pt for each correct set; error such as < instead of ≤, etc., will subtract 0.5pt I, for I ≤ 1
P1 output =
2, for I ≤ 1
2, for I > 1
# program P2
def
def
A(I, P):
def B():
print(I)
if I > 2:
P() elif I > 1:
A(3, B) else:
I= A(I, C)
A(2, B)
print(2)
C():
input()
P2output= I,for1
2pt for correct set; error such as < instead of ≤, etc., will subtract 1pt The same output, 2, is obtained for I ≥ 2.
1pt for each of the 12 occurrences of P and 3 occurrences of I that need to be correctly identified as to what they refer to.
Due to the structure of the conditional statements in the programs, which is the same in the two programs, there are three cases to consider depending on the value of I: I ≤ 1, 1 < I ≤ 2, and I > 2. The diagrams below show what happens with each program in each case.
Deep binding is used in both programs, because this is what Python uses. The difference between the two programs is that P1 calls A(3, P), whereas P2 calls A(3, B).
In the first case, this makes the static links in P1 go one frame deeper in the stack, causing P1 to print I, whereas P2 prints 2.
In the second case, this makes P1 call the deeper C and print 2, whereas P2 calls B, which prints the deeper I.
The difference between the two programs matters only in the first two cases. In the third case, both call C that always prints its own 2.
3
4. (20pt) Consider the C-style switch statement.
(1) (15pt) Write an S-attributed LL(1) grammar that generates C-style switch statements and check that all labels of the arms of the switch instructions are distinct. In order to do that, the starting nonterminal, S, will have an attribute dup that will store all the duplicate values. There are no duplicate values on the arms of the switch statement if and only if S.dup = ∅. Therefore, your grammar is required to eventually compute the attribute dup of S.
For simplicity, assume that the conditional expression of the statement and the constant ex- pressions labelling the arms are expr tokens and that each arm has a statement that is a stmt token; the break and default parts are omitted as their role is irrelevant for our problem. Each expr has an attribute val provided by the scanner that gives the value of the expression. Explain why your grammar works as required. For LL(1), you can use jflap to compute the parse table and show there is no conflict; include the jflap answer (whole window) in your answer.
(2) (5pt) Using this attributed grammar, draw a decorated parse tree for the following switch instruction:
switch ( expr ) {
case 1 :
case 2 :
case 3 : stmt
case 2 : stmt
case 2 :
case 3 : stmt
4
}
Show all attributes and arrows indicated what attributes are used to compute each value.
Solution:
(1)
arm list −→
◃ arm list.set = case list.set ∪ more arms.set
◃ arm list.dup = case list.dup ∪ more arms.dup ∪ (case list.set ∩ more arms.set)
5pt for syntactically correct grammar, 8pt for correct S-attributed grammar, 2pt for LL(1) jflap argument
The grammar is shown below. We have to separate arms and cases since an arm can have any number of cases. All constants are accumulated in the attribute set for both cases and arms. The sets stored in the attribute set are intersected with each other and with the values val of expression to detect duplicates. The sets of constants and duplicates are copied to left-hand sides and passed up the tree all the way to the root.
S −→
◃ S.dup = arm list.dup
switch(expr){armlist}
case list stmt more arms
more arms −→
◃ more arms.set = arm list.set
arm list
◃ more arms.dup = arm list.dup
more arms −→
◃ more arms.set = ∅
ε
◃ more arms.dup = ∅
case list −→
◃ case list.set = {expr.val} ∪ more cases.set
◃ case list.dup = more cases.dup ∪ ({expr.val} ∩ more cases.set)
more cases −→
◃ more cases.set = case list.set
case expr : more cases
case list
◃ more cases.dup = case list.dup
more cases −→
◃ more cases.set = ∅
ε
◃ more cases.dup = ∅
Jflap LL(1) shows no conflict.
(2)
5pt for correct tree; 0.5pt subtracted for each error
5
5. (20pt) Consider the following SLR(1) grammar G for arithmetic expressions:
E −→ EAT E −→ T
T −→ TMF T −→ F
F −→ -F
F −→ ( E ) A −→ +|- M −→ *|/
F −→ id
(1) (15pt) Construct an attributed grammar, based on G, that computes the type and value of an expression assuming that id’s have, form the scanner, two attributes: type, which can be int or float and val, which is a number. In any operation, if one operand is a float, then both operands are converted to float using the operation n = float(n); e.g., float(2) = 2.0; the operation can be performed only between operands of the same type.
The grammar does not have to be L-attributed.
(2) (5pt) Using this attributed grammar, draw a decorated parse tree for the following expres- sion: (4 + -2.0) * 3. Show all attributes and arrows indicated what attributes are used to compute each value.
Solution:
(1) 6pt for correct type, 7pt for correct val, 2pt for correct operators
6
(2)
E1
E T1
−→ E2 AT
◃ if (E2 .type == float) then
T .type = float; T .val = f loat(T .val) ◃ if (T .type == float) then
E2.type = float; E2.val = float(E2.val)
◃ if (E2 .type == float or T .type == float) then E1 .type = float
else E1.type = int
◃ E1 .val = A.op(E2 .val, T .val)
−→ T
◃ E.type = T .type; E.val = T .val
−→ T2MF
◃ if (T2 .type == float) then
F .type = float; F .val = f loat(F .val) ◃ if (F .type == float) then
T2.type = float; T2.val = float(T2.val)
◃ if (T2 .type == float or F .type == float) then T1 .type = float
else T1.type = int
◃ T1 .val = M .op(E2 .val, T .val)
F A A M M F
◃
−→
◃
−→
◃
−→
◃
−→
◃
−→
◃
−→
◃
F1 .type = F2 .type; ( E )
F .type = E.type; +
A.op = add –
A.op = sub *
M .op = mult / M.op=div id
F .type = id.type;
−→ F
◃ T.type = F.type;
T
F1 −→-F2
T.val = F.val
F1 .val = −F2 .val
F .val = E.val
F .val = id.val
5pt for correct tree; 0.5pt subtracted for each error
7
READ ME!
Submit all your answers as a single pdf file on owl.uwo.ca. Solutions should be typed but high quality hand written solutions are acceptable. (Source code, if required, is submitted as separate files.)
You are allowed to use jflap (jflap.org) for your solutions, whenever possible.
The solutions should provide sufficient detail to support your claim. A simple yes/no answer without any supporting arguments is not given any marks. Note also that understanding the questions is part of solving the assignment. You are encouraged to ask questions when you have problems understanding, but try your best first. It is more important to learn than merely getting the assignment done.
Self-reported absences can be used to extend the deadline by 48h. In this case, you must label “SELF-REPORTED ABSENCE” clearly at the top of the assignment and submit it by email to cs3342@uwo.ca instead of OWL.
8