CS3342 – Assignment 2
due Feb. 24, 2021
1. (20pt) Consider the following grammar:
S0 ! 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 G0, equivalent with G, that is SLR(1). Prove that G0 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.
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.
3. (20pt) Consider the two Python programs below:
# program P1
def A(I, P):
def B():
print(I)
if I > 2:
P()
elif I > 1:
A(3, P)
else:
A(2, B)
def C():
print(2)
I = input()
A(I, C)
# program P2
def A(I, P):
def B():
print(I)
if I > 2:
P()
elif I > 1:
A(3, B)
else:
A(2, B)
def C():
print(2)
I = input()
A(I, C)
(1) (1pt) Find the di↵erences 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.
1
(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.
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
default : stmt
}
Show all attributes and arrows indicated what attributes are used to compute each value.
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.
2
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 sucient 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
[email protected] instead of OWL.
3

欢迎咨询51作业君