CSE413

Midterm Exam

5/4/97

50 minutes. Closed book, closed notes. Please write directly on the test booklet.

1 point per part except as noted.

Definitions. Give a short definition of each of the following terms:

• Programming language

• Scope of a declaration

• Symbol table

Name three accepted "paradigms" of programming.

• 1.
• 2.
• 3.

A programming language without variables or loops (circle one):

• Is impossible
• Is possible but would be very limited in what it can do
• Might well be just as powerful as a language with variables and loops
• Is more powerful than any language with variables and loops.

Briefly describe the difference between...

• syntax and semantics.

• a compiler and an interpreter.

• a token and an identifier.

Given the following BNF grammar:

• <sentence> ::= <noun-phrase> <verb-phrase>
• <noun-phrase> ::= <article> <noun>
• <article> ::= a | the
• <noun> ::= dog | cat
• <verb-phrase> ::= <verb> <noun-phrase>
• <verb> ::= chases | sees

(2 pts.) Give a full parse tree for the sentence "the cat chases a dog". Use the space above and to the right.

(2 pts.) The sentence "the dog sleeps" cannot be derived from the grammar as given. Make changes to the above grammar so that "the dog sleeps" can be derived, but so that no ungrammatical (in the usual sense) English sentences can then be derived. Mark directly on the grammar, which is repeated below for convenience.

• <sentence> ::= <noun-phrase> <verb-phrase>
• <noun-phrase> ::= <article> <noun>
• article ::= a | the
• <noun> ::= dog | cat
• <verb-phrase> ::= <verb> <noun-phrase>
• <verb> ::= chases | sees

(2 pts.) Give (pure) BNF which generates exactly the same 'decl's as the following EBNF:

<decl> ::= [<class>] <tp> <id> {',' <id>} ';'

<tp> ::= float | real

<class> ::= long | short

(1 pt.) Suppose (cons X Y) has the value (a b c d). Give possible values for X and Y, or explain why this is not possible.

• X:
• Y:

Suppose (car X) has the value (a b c d). Give a possible value for X, or explain why there is no possible value.

• X:

(1 pt.) Suppose (list X Y) has the value (a b c d). Give possible values for X and Y, or explain why this is not possible.

• X:
• Y:

(4 pts.) Write a LISP function 'elim' which eliminates a given value from a list. The first argument is the value, and the second is assumed to be a list. Examples are shown to clarify how the function should work. Write your answer in the space to the right of the examples. Use a pure functional style.

(elim 'a '(b a c d a))

(b c d)

(elim 'a '(z q 40))

(z q 40)

(elim 'a '(1 (a) b z))

(1 (a) b z)

(elim '(a) '(1 (a) b z))

(1 b z)

(elim 'a '(a))

nil

(elim 'a nil)

nil

The following program is written in Pascal syntax (recall that 'writeln' is similar in effect to a C 'printf').

program ex;
var x: integer;
procedure p;
	begin
	writeln(x);
	end;
procedure q;
	var x: integer;
	begin x :=77;
	p;
	end;
begin (* main *)
	x := 99;
	q;
end.

Suppose lexical scope is used. What value, if any, does the program display when it runs?

Suppose dynamic scope is used. What value, if any, does the program display when it runs?

Mention three different examples of binding in C, and list them in order from earliest to latest. One should a really early binding, and one should be really late.

• 1.
• 2.
• 3.