CS3342: Organization of Programming Languages — Winter 2021
—Midterm Exam —

1. (20pt) Python strings are single-line character sequences surrounded by single or double quotation marks. Com-ments are either single-line character sequences that start with # and end at the end of the line, \n, or multi-line comments (technically they are multi-line strings but we call them comments here) surrounded by three consec-utive double quotes,   

(a) (14pt) Build a scanner for identifying Python strings and comments. Your scanner will be a deterministic finite automaton (such as the one on page 57 of textbook) that will identify only three types of tokens: (a) strings, (b) single-line comments, and (c) multi-line comments. That is, the scanner will not skip comments but rather identify those as tokens.

(b) (6pt) The scanner reads as far as it can to identify the longest tokens. After finding a valid token, it starts the next token with the character right after the previous; if this is a white space (blank, tab, newline), then it skips all white spaces. The scanner finds an error when it cannot process the next character in a non-final state; in this case, all characters until the next white space and all consecutive white spaces that follow are ignored and the scanner resumes scanning with the next character.

Give the output of the scanner for the following input; explain the output in detail using the scanner by running your finite automaton (show the states and transitions) on the input:

"abc  # ##\n

(The last '\n' is to clarify there is a newline at the end.)

2. (30pt) Consider a language where assignments can appear in the same context as expressions; the value of a = b = c equals the value of c. The following grammar, G, generates such expressions that includes assignments in addition to additions and multiplications:

0. P ―> E $$

(a) (2pt) What is the value of the expression: a = 5 + (b = 2 + 6 * 4)$$?

(b) (3pt) Show a parse tree for the string: id = id + (id = id + id * id)$$.

(c) (10pt) Compute, for each production A ——> a, first(q) and follow(A) using the algorithm on the next page; FlRST(a) is computed by the string_FIRST procedure. For each token added to each set, indicate the pair (step,prod), where 1 — step — 3 is the step in the algorithm (marked as [T],図，③；see next page) and 0 — prod — 9 is the production involved; indicate (0, —) when step 回 is used for terminals. (You can use jflap to help you, but you need to provide the information as mentioned. Information from jflap alone will not receive any points.)

(d) (5pt) Using the information computed above, show that this grammar is not LL(1). (You need to use the definition on the last slide of the Syntax chapter.)

(e) (10pt) Modify this grammar to make it LL(1). You can use jflap to check this; include the jflap table computation (include the jflap window).

一一EPS values and FIRST sets for all symbols:

for all terminals c, EPS(c) := false; F旧ST(c):

for all nonterminals X, EPS(X) := if X ——> e then true else false; FIRST(X) := 0 repeat

(outer) for all productions X —> 匕 * ...玖,

(inner) for i in 1 .. k

1 add I IHSl ir.-} to " «X)

if not EPS(K) (yet) then continue outer loop

EPS(X) := true

until no further progress

一一 Subroutines for strings, similar to inner loop above:

function string_EPS(Xi X2 ... X_n) for i in 1 .. h

if not EPS(Xi) then return false return true

function string_FIRST(Xi X2 ・.. X〃) return_value := 0 for z in 1 .. n

add FIRST(Xj) to return_value if not EPS(Xj) then return

一 FOLLOW sets for all symbols:

for all symbols X, FOLLOW(X) := 0 repeat

for all productions A — a B /?,

2 add srrrngJ HSIJS) to 丨 0丄O'MB)

ror all productions A —> a B

or A —> ol B 8, where string_EPS(/3) = true,

FOLLOW(八)to FOLLOW")

until no further progress

一 PREDICT sets for all productions:

for all productions A —> a

PREDICTS —> a) := string_F旧ST(q) U (if string_EPS(a) then FOLLOW(A) else 0)

3. (20pt) Consider the following pseudocode:

int x = 0

set_x (int n) { x = n }

print_x() { print(x) }

f() { set_x(1); print_x() }

g() { int x = 0; set_x(2); print_x() }

set_x(0); f(); print_x(); g(); print_x()

(a) (10pt) What is the output of the program if it uses static scoping?

(b) (10pt) What is the output of the program if it uses dynamic scoping?

Explain each answer by running the program statement by statement and detailing what happens.