Name:

CSC447: Concepts of Programming Languages

Midterm Exam

October 16, 1996

School of Computer Science, Telecommunications,

and Information Systems

DePaul University

Fall 1996

Sections 101/103

This is a closed-book, closed-note exam. Write your name at the top of the exam and do

not open the exam until you are told to do so.

There are a total of 100 points on this exam. Feel free to do the questions in any order. You will have two hours to complete the exam.

Problem 1 (10 points)

Which of the strings below are in the following grammar:

<P> ::= [<Q>] | (<P>) | R

<Q> ::= <R> | <Q>, <R>

<R> ::= x | y | z

1. z			yes / no

2. (x) 			yes / no

3. [y] 			yes / no

4. (x , y) 		yes / no

5. [(x) , y] 		yes / no

6. ([x, y]) 		yes / no

7. [[x , y], z] 		yes / no

8. [x , y, z] 		yes / no

9. ([x , y, z])		yes / no

10. ((([x , y, z, x])))	yes / no

Problem 2. (5 points)

Write a BNF grammar for the language composed of all binary numbers that contain at least three consecutive 1’s. The language should include the strings 011101011, 000011110100 and 1111111110, but not 0101011.

Answer:

Problem 3. (5 points)

What are the three components of a programming language definition (the three parts of the programming language structure).

Answer:

Problem 4. (10 points)

Answer:

Problem 5. (10 points)

Describe the stack contents (the activation records) for the following program at the point where p(4) is called.

program main 

procedure p(x);

var a;

begin

a := x + 1;

q;

p(a);

end;

procedure q (x);

begin

print x;

end;

begin

a := 2;

p(2);

end.

Answer:

Problem 6. (10 points)

Consider the language described by the following BNF grammar:

<EXP> ::= <INT> | <EXP> + <EXP> | <IDENT> += <EXP>

<INT> ::= <DIGIT> | <DIGIT> <INT>

<DIGIT> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0

<IDENT> ::= a | b | c | d

Suppose that the ‘+’ operators is left-associative and the ‘+=’ operator is right-associative. Furthermore, the ‘+’ operator has the highest operator precedence.

Insert the implied parenthesis in each of the following two expressions:

a += b += 1 + 1 + 2

a += b + c + d += 5 + 3 + 1

Problem 7. (10 points)

Mark bound, binding, free occurrences of all the identifiers in the following lexically scoped program. Put a circle around the binding occurrences, underline the bound occurrences and a square around any free occurrences. Also draw an arrow from each bound occurrence to its binding occurrence.

program test;

var n : integer;

procedure b (n : integer);

var m, p : integer;

begin

m := m + n;

b;

end;

procedure c (m : integer);

begin

m := m + p;

end;

begin

c (n);

end.

Problem 8. (20 points)

Consider the following program:

program Main(…);

var Y: integer;

procedure P(X: integer);

begin

x := x + 1;

write (x, y;

end;

begin

y := 1;

P(Y);

write(Y);

end.

Give the three numbers printed in the case that the parameter passing method is:

• call by reference
• call by value
• call by value-result
• macro expansion

Answer:

Problem 9. (10 points)

Consider the following program and describe the result of running the program (give the two numbers that will print) with both lexical scoping and dynamic scoping.

program dynamic(input, output);

var i : integer;

procedure show;

begin

write (i);

i := 3;

end;

procedure small;

var i : integer;

begin

i := 2;

show;

end

begin

i := 1;

show;

small;

end.

Answer:

Problem 10. (10 points)

Describe the output of the following program:

@in = ("test data", "val 1 : one ", "val 2 : two ", "val 3 : three ");

($h1, @in) = @in;

foreach $i (0 .. $#in) {

($key, $val) = split(/: /,$in[$i],2);

@keyList = (@keyList, $key);

@values = (@values, $val );

}

print ("HW ",@keyList,"\n","1 ", @values);

Answer: