NAME__________________________
CSCI 4430 Sample Final Exam 1



Sample Final Exam
CSCI 4430 Programming Languages



- DO NOT OPEN THIS EXAM UNTIL TOLD TO DO SO!
- READ THROUGH THE ENTIRE EXAM BEFORE STARTING TO WORK.
- YOU ARE ALLOWED 5 “CHEAT” PAGES ONLY.


This exam is worth 340 points.

Make sure you have 14 pages counting this one; there are 9 questions. If you need
more room for an answer than is provided, please use the back of the page and indicate
that you have done so. If you re-do a question, please make clear what is your final
answer.

Read through each entire question before starting to answer it. Starred “**” questions
may take longer to answer/think through, so please budget your time appropriately. Be
clear and brief in your explanations (when the answer is text, write at most 2-3
sentences).

The following is for the use of graders


1. __________/20

2. __________/30

3. __________/30

4. __________/45

5. ___________/45

6. ___________/40

7. ___________/60

8. ___________/40

9. ___________/30
TOTAL POINTS:___________/340
NAME__________________________
CSCI 4430 Sample Final Exam 2

1. Grammars (20 points)

a) (10pts) Consider a grammar that generates Scheme lists, disallowing quotes. Assume that
number and symbol are tokens, generated by the scanner, so they do not need grammar
productions. Add productions below to complete a legal context-free grammar.

list_element → number | symbol | list























b) (10pts)** Think about parsing the lists defined by this grammar. Can you write a predictive parser for
this grammar? Briefly explain why or why not?



NAME__________________________
CSCI 4430 Sample Final Exam 3

2. LL Parsing (30points)
Consider the following grammar over terminals (,[,), and ]. S is the starting symbol of the grammar.

S → T S | [ S ]S | ε
T → ( X )
X → T X | [ X ] X | ε


a) (15pts)** Fill in the table below with the FIRST and FOLLOW sets for the nonterminals in this
grammar:

FIRST FOLLOW
S



T




X







b) (10 points)** Fill in the LL(1) parsing table below:

( [ ]

) $$
S




T



X






c) (5 points) Is this grammar LL(1)? Explain briefly why or why not.










NAME__________________________
CSCI 4430 Sample Final Exam 4

3. LR Parsing (30 points)

Consider the following grammar over terminals +, if and int:

S → E
E → int | E if E | E + E

a) (10 pts) This grammar is ambiguous. Show two parse trees for string int + int if int








b) (20 pts) Below is a partial CFSM for the grammar:

Complete state 0 by performing closure on the item listed.

Fill in the elements of states 3 and 4.

Fill in the missing labels (6 of them).

Fill in the “reduce by …” labels on states 5 and 6 below:

Label on state 5: “reduce by E → E + E on ________”

Label at state 6: “reduce by E → E if E on _________”


S → • E E → E • + E
E → E • if E
S → E •




E → int •
E → E + E •
E → E • + E
E → E • if E
E → E if E •
E → E • + E
E → E • if E


E
int
+
if






0
2
1
3
4
5
6
int
int
NAME__________________________
CSCI 4430 Sample Final Exam 5

4. Scoping (45 points). Assume a programming language that uses static (i.e. lexical) scoping for
non-local variables and dynamic scoping (with shallow binding) for lookup of function definitions. Use
the run-time stack to the right to hand-simulate the execution of the program, and show the values of the
variables, each dynamic link, and each lexical link.

a) (20pts) Show the run-time stack before exiting procedure R due to the call of R
in main.Q /****/, writing (lexically) qualified names for all procedures (e.g., main.Q()).
Use as many of the frames as you need.

b) (25pts) Show the output of this execution below.

main()
{ integer: m=10, k=0;
procedure P()
{ integer: k=1;
procedure R()
{ integer: m=0;
k = 4;
}//end P.R
print “#2”, m, k;
Q();
print “#3”, m, k;
}//end main.P
procedure R()
{ integer: m=6;
k = 5;
}//end main.R
procedure Q()
{ k = 2;
R(); /****/
}//end main.Q
print “#1”, m, k;
P();
}//end main

Output:
procedure
___main_____
lexical-link xxxx
dynamic-link xxxx





procedure ________
lexical-link
dynamic-link






procedure ________
lexical-link
dynamic-link






procedure ________
lexical-link
dynamic-link






procedure ________
lexical-link
dynamic-link






NAME__________________________
CSCI 4430 Sample Final Exam 6

5. Parameter Passing (45 points)

a) (20pts) What does the program print, assuming that each argument/parameter is passed according to
the qualifier on it. For value-result, assume all argument l-values are calculated at procedure entry.

Note: print a[0..3] means print a[0],a[1],a[2],a[3]

{ int a[4];
int h, k, j;
function p(int x : by reference,
int y : by name,
int z : by value-result)
{
j := 4;
x := x*2;
z := x*3;
a[y] := k;
print "in p ", h, j, k, a[0..3];
}

/* initialize a[m] to (3-m) */
a[0]=3; a[1]=2; a[2]=1; a[3]=0;

h := 1;
j := 2;
k := 6;

print "before ", h, j, k, a[0..3];

call p(a[j], (j-1), a[h]); (***)

print "after ", h, j, k, a[0..3];
}

Output:
NAME__________________________
CSCI 4430 Sample Final Exam 7

b) (5pts) How would you change the call to p at (***) so that after returning from that call, a[2] would have
been modified to 6 ?




call p( ___________, ______________, ____________);



**c) (20pts) Complete the following program fragment in the shortest possible way (fewest and shortest
statements) so that the output will be different if parameter passing was by reference versus by value-
result. Indicate in each case what the output would be.

integer A = 10, B = 20;

procedure p(integer x)
{
________________________________

________________________________

________________________________

________________________________

}

main()
{

p(A);
print(“A=”,A,”B=”,B);

}

i. Output in case of pass by-reference: ________________________________

ii. Output in case of pass by-value-result: ________________________________
NAME__________________________
CSCI 4430 Sample Final Exam 8

6. Types and Type equivalence (40 points)
a (25pts) Consider the following type and variable declarations.

type TI = integer; //equivalent to C’s typedef int TI;
type TTI = TI;
type TPI = ref integer;//equivalent to C’s typedef int * TPI
type TPI2 = ref TI;
type TPPTI = ref TPI;
type AI = [0:10] integer;
type ATPI = [1:20] TPI;
type ATI = [0:10][0:10] TI;
var a : integer;
var b : TTI;
var c : TPI;
var d : TPI2;
var e : TTI;
var f : ref float;
var g : ref float;
var h : TPPTI;
var j : ATPI;
var k : ATI;
var l : AI;

Assume that the array type includes the array dimensionality, but not array bounds.

For each of the pairs of variables in the first column of the table above, put YES in the column labeled
NameEq exactly when their types are equivalent according to the rules of loose name equivalence, and
YES in the column StructEq when their types are equivalent according to the rules of structural type
equivalence.

b (15pts) Consider the following type declarations in C:

struct B{ char x; int y;};
typedef struct B A;
struct { A a; A *next;} aa;
struct { struct B a; struct B *next;} bb;
struct { struct B a; struct B *next;} cc;

A a; struct B b;

Circle the assignments that result in “incompatible types” error? Why?

a = b;

aa = bb;

bb = cc;






NameEq StructEq
a, b
c, d
b, e
h, j
c, f
f, g
k, l
NAME__________________________
CSCI 4430 Sample Final Exam 9
7. Comparative Programming Languages (60 points, 15 each)
Assume you have a symbol table whose keys are variable names and whose entries are symbolic values
that correspond to the type of that variable. In our Scheme homework and Haskell examples we have seen
how to search such a table to find the value corresponding to a given key. Here, we want to do the
opposite, namely we want a function get_vars that finds all the variables in the table of a given type.

For example, in Scheme we would store the table as a list
((x int) (y real) (z list) (w int))
Here the first element of each sublist is the key (the variable) and the second element is the value (or
variable type). The call (get_vars ‘int ‘((x int)(y real)(z list)(w int)))yields the
list (x w).

Recall several higher order functions in Scheme that may be useful:
(define (foldl op lis id)
(if (null? lis) id (foldl op (cdr lis) (op id (car lis)))))

(define (foldr op lis id)
(if (null? lis) id
(op (car lis) (foldr op (cdr lis) id))))

(define (map f lis) (if (null? lis)
'()
(cons (f (car lis)) (map f (cdr lis)))))

a. Write a Scheme function get_vars that finds all variables of a given type;

(define (get_vars type llist)_________________________






NAME__________________________
CSCI 4430 Sample Final Exam 10

b. Write a Python function to accomplish the same task. Note; the following built-in operations in
Python on dictionaries may be of use: keys(), values(), has_key(),
update(dict), len(dict), indexing or the following built-in operations on Python lists:
+ (concatenate), append(ele), del list[k] (element deletion),
indexing [..]. List comprehensions may be of use too. Function returns list of variables in
dict of type type.

def get_vars (type, dict)__________________________


















c. Write a Haskell function to accomplish the same task.

get_vars :: String -> [(String,String)] -> [String]

get_vars type env = ______________________________
NAME__________________________
CSCI 4430 Sample Final Exam 11

d. Now write the predicate get_vars(Type,Sym,Vars) in Prolog. The predicate has three
parameters. The first is the type to be searched for, the second is the symbol table (as a list) to search,
and the third is the list of variables found to be of that type. So when the predicate is called, e.g.,

?- get_vars(int, [[x,int],[y,real],[z,list],[w, int]],V)

we expect the answer V = [x, w].

get_vars(Type,Sym,Vars):-
NAME__________________________
CSCI 4430 Sample Final Exam 12

8. Scheme and functional programming (40 points)
a (10pts). Recall higher orde function map

(define (map f lis) (if (null? lis)
'()
(cons (f (car lis)) (map f (cdr lis)))))

Now we want to construct a new higher order mapp function that takes three arguments, f a function of two
variables and two lists xs, ys, and applies f to corresponding elements of each list and returns the resulting list of
values. For example, (mapp ‘+ ‘(1 2) ‘(3 4)) returns (4 6). Fill in the definition of mapp below (use as many lines
as you need):

(define (mapp f xs ys) (cond ((null? xs) '())
((null? ys) '())

________________________________________________________



___________________________________________________________


b (10pts) Now define a function makepairs which uses mapp to build a list of pairs such that the first
element in the pair comes from the first list and the second element of the pair comes from the second
list. For example, (makepairs ‘(1 2 3) ‘(a b c)) would return ((1 a) (2 b) (3 c)). Assume both lists are
the same length.










NAME__________________________
CSCI 4430 Sample Final Exam 13

c (20pts)** Suppose we want to create a different set of pairs, that is all pairs whose first element comes
from the first list and whose second element comes from the second list. For example,
(all_pairs ‘(1 2) ‘(3 4)) returns ((1 3) (1 4) (2 3) (2 4)) (Note: order of the pairs in the list does not matter.)
Write the function all_pairs below.

You may use a helper function or foldl/foldr.

(define (all_pairs xs ys)
NAME__________________________
CSCI 4430 Sample Final Exam 14

9. Lambda Calculus (30 points)

a (10pts) Reduce the term (λx. x x) ((λy. y) (λz. z)) using normal order (i.e., by-name) reduction.









b (10pts) Reduce the term (λx. x x) ((λy. y) (λz. z)) using applicative order (i.e., by-value)
reduction.







c (10pts) Consider the following combinators:

true = λx.λy.x
false = λx.λy.y
not = λx.((x false) true)

Show that not (not x) →β … →β x where x is true or false. Hint: to save writing, first reduce not
(not x) as much as possible.





















欢迎咨询51作业君