COMP-302 Fall 2016 Midterm Practice Questions page 3
Answers
1. Do the JavaScript regular expressions /ˆ$/ and /ˆ\n?/ match exactly the same things? Explain why or why not.
No. Consider “\n” as input. The first form matches only the empty string,
so does not match. The second form, however, would match.
2. Which of the following will match the string “aaa”?
a) /ˆ((a+)+)+/ d) /ˆa*aaa/
g) /ˆ((a*)+)+/
b) /ˆ(aa)+aa*/
e) /ˆa*a+a*a/
h) /ˆ(((a+)+)+)*/
c) /ˆ(aaa)*/ f) /ˆa+a+a+/ i) /aa$/
They all match.
3. Describe (very briefly) in words what would be matched by the regular expression /a*(ba*ba*)*/. Give
an equivalent, unambiguous BNF grammar suitable for LL(1) parsing. Show the parse tree for “baabaaabb”.
The language describes all strings consisting of pairs of b’s with 0 or more
intervening or surrounding a’s. (Used inside the match() API in JavaScript, it
actually can match any string, as a 0-length match is valid for this expression.)
Grammar: (e is the empty string):
START -> As Pairs
As -> a As | e
Pairs -> b As b As Pairs | e
This is unambiguous and suitable for LL(1) since the non-terminals
begin with distinct tokens.
parsing: baabaaabb
START —– /\
As Pairs
— ————- |/|\\\
e bAsbAsPairs
— — —————
/\ /\ / | \ \ \
a As a As b As b As Pairs
— — — — —–
/\ /\ | | |
aAs aAs — — | /\ e aAs
— | e
e e e
COMP-302 Fall 2016 Midterm Practice Questions page 4
4. Arguments in function calls must be evaluated before being bound to their respective parameters, but the order of evaluation can differ: given a call foo(1+2,2+3), a language may require left to right ordering, so we evaluate 1+2 before 2+3, or right to left (or have no requirements).
Using JavaScript syntax (but not assuming it is JavaScript), give a function that tests if function argument evaluation order is left to right or right to left. Your code should consist of a self-contained function of no ar- guments, evalTest(), returning boolean true if the evaluation order is left→right, and false for right→left.
function evalTest() {
var i=0;
function testit(a,b) { return i; }
return testit(i=1,i=2)==2;
}
5. Another language choice is in static vs dynamic scoping. Using JavaScript syntax (but not assuming it is JavaScript), write a self-contained function of no arguments scopeTest() that would return the string “static” under static scoping, and “early” if there is early/deep dynamic scoping, and “late” if there is late/shallow dynamic scoping.
function scopeTest() {
var i=”static”;
function inner1() { return i; }
function inner2() { return i; }
function outer(f) {
var i=”late”;
if (f()!=inner2())
return “early”;
return inner1();
}
return outer(inner1);
}
COMP-302 Fall 2016 Midterm Practice Questions
page 5
6. Assume you have the following simple function
factorial(n) {
if (n==0) return 1;
var x = n*factorial(n-1);
return x;
}
Show the environment/scope chain for the invocation “factorial(3);” assuming static scoping. For each en- vironment include the bindings stored. Show the environment/scope chain for same invocation, assuming dynamic scoping. Would the computation result be different with dynamic scoping?
With static scoping we will get 4 environments for the 4 calls,
each pointing to the outermost environment in which factorial
was defined.
+———————+ +———–+
| factorial: function | <-- | n: 3 | | | |x:6 | +---------------------+ +-----------+
ˆˆ
| |
||
| |
| |
| +----------- |
ˆ +-----------+ +-------|n:2 | |x:2| +-----------+ +-----------+ |n:1 | |x:1| +-----------+
|
|
+--------------- | n: 0 |
+--------------+
| x: undefined |
+--------------+
With dynamic scoping we get a linear chain, but it doesn’t change
behaviour in this case:
+---------------------+ +-----------+ +-----------+ +-----------+ | factorial: function | <-- | n: 3 | <-- | n: 2 | <-- | n: 1 | | | |x:6 | |x:2 | |x:1 | +---------------------+ +-----------+ +-----------+ +-----------+
ˆ
|
+--------------+
| n: 0 |
| x: undefined |
+--------------+
COMP-302 Fall 2016 Midterm Practice Questions page 6
7. Suppose you wanted to add iteration to WML. Schematically, you want a template
{{iter|i|update|cond|f}}
which repeatedly invokes f for a sequence of values starting at i and modified each iteration by update,
stopping when cond returns a non-empty string. Note that f, cond, and update are template closures. For example, an invocation
{{iter|3
|{:‘|x|{{#expr|{{{x}}}-1}}:} |{:‘|x|{{#ifeq|{{{x}}}|-1||!}}:} |{:‘|x|{{{x}}}...:}
}}
Results in the output “3...2...1...0...”. Give the definition for iter.
{:iter|i
|update
|cond
|f
|{{#if|{{ {{{cond}}}|{{{i}}}}}
|{{ {{{f}}}|{{{i}}}}}{{iter|{{ {{{update}}}|{{{i}}}}}
|{{{update}}}
|{{{cond}}}
|{{{f}}}}} }}:}
8. Suppose you have the following λ-calculus expression, λ g.(λ x.(g (x x))) (λ x.(g (x x)))
(a) Give an equivalent WML template; call it Y.
{:Y|g|{{ {:‘|x|{{ {{{g}}}|{{ {{{x}}}|{{{x}}} }} }} :}
|{:‘|x|{{ {{{g}}}|{{ {{{x}}}|{{{x}}} }} }} :} }} :} (b) What would happen if you evaluate {{Y|{:‘|x|a{{{x}}}:}}} ?
It should generate an infinite sequence of a’s, but will in practice just give
a too much recursion error.