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.
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) 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.
# 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)
1
A(2, B)
print(2)
C():
input()
(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
}
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 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.
3