| Question | Points | Score |
| 1 | 30 | |
| 2 | 2 | |
| 3 | 2 | |
| 4 | 2 | |
| 5 | 2 | |
| 6 | 2 | |
| 7 | 10 | |
| 8 | 15 | |
| 9 | 15 | |
| 10 | 20 | |
| Total: | 100 |
(1) (30 points) Mark each question as either True (T) or False (F) by circling either T or F.
a. F C++ is Considered by many to be the first object-oriented programming language.
b. F FORTRAN was designed as a programming language for business applications.
c. T LISP was originally developed for Artificial Intelligence problems.
d. F A strongly typed programming language is one that detects all type errors at either compile time or run time.
e. F A non-terminal that occurs on the far left of any production rule is left associative.
f. T A function or operator exhibits subtype polymorphism if one or more of its parameter types have subtypes.
g. F A language system involving the classical sequence typically has a step involving the loading of the source code into an interpreter.
h. F In ruby like in Java and ML we can add type annotations in order to help the interpreter, as well as other programmers, understand the code.
i. T EBNF was designed to make context free grammars easier to read. It does not offer any more descriptive power than BNF.
j. T Associativity rules only apply to operators of the same precedence.
k. T The order of production rules is not significant, i.e., two grammars with identical rules but given in a different order will always define the same language.
l. F Overloading functions and operators can only be done in dynamically type languages because of their greater flexibility.
m. F An advantage of using an interpreted language is that it runs faster than compile code.
n. T Subtypes are a superset of the super-type’s features.
o. F In Java, like in ML, the explicit conversion from one type to another is a form of coercion.
(2) (2 Points) Give the ML type corresponding to the following set: {true, false} -> {true, false}
`bool -> bool`
(3) (2 points) Context free grammars are used to capture which aspect of a programming language?
B. Syntax
(4) (2 points) Circle all of the following types that are constructed types:
B. Ruby String
E. ML int list
(5) (2 points) In Ruby, a method returns?
B. The value of the evaluation of the expression last evaluated in the method
(6) (2 points) Circle all of the following that are Object Oriented Languages.
A. C\#
C. Java
E. Perl
(7) What is the binding time for each of the following in a C/C++ program? State the binding time as precisely as possible (language-definition time, language-implementation time, compile time, link time, load time, or runtime)
a. (2 points) The size in memory of a variable of type int.
Language Implementation Time
b. (2 points) The location in memory of a global static variable.
Load Time
c. (2 points) The size in memory of a pointer.
Language Implementation Time
d. (2 points) The values(s) assigned to a variable.
Runtime
e. (2 points) The code for the `printf` function.
Link Time
(8) Answer these questions about the following grammar. The starting symbol is <re>
<do> ::= <me> | <do> % <me>
<re> ::= <do> & <re> | <do>
<me> ::= ( <re> ) | a | b
a. (2 points) Which operator has higher precedence?
%
b. (2 points) What is the associativity of the `%` operator?
left-associative
c. (2 points) Does this grammar describe a finite or infinite language?
infinite
d. (2 points) Is this grammar ambiguous?
No
e. (4 points) Rewrite this grammar using EBNF, considering the version of EBNF
provided in the book which adds only the grouping symbols `[ ]`, `{ }`, and
`( )`.
<re> ::= <do> [& <re>]
<do> ::= [<do> %] <me>
<me> ::= ( <re> ) | a | b
f. (3 points) Draw a parse tree to explain the string: `b & a % (a & b)`
<re>
|
-------------------------
| | |
<do> & <re>
| |
<me> <do>
| |
b --------------------
| | |
<do> % <me>
| |
<me> <re>
| |
a ----------------
| | |
( <re> )
|
----------------
| | |
<do> & <re>
| |
<me> <do>
| |
a <me>
|
b
(9) Suppose there are three variables X, Y, and Z with these types:
X: integer that is divisible by 3
Y: integer that is divisible by 12
Z: integer
For each of the following assignments, knowing nothing about the values of the variables except their types, answer whether a language system can tell before running the program whether the assignment is safe? Answer Yes or No and explain why.
a. (5 points) `X := Y`
Yes, as Y is a proper subset of X
b. (5 points) `X := X + Y`
Yes, as (X + Y) is a proper subset of X
c. (5 points) `X := Z`
No, as X is a subset of Z
(10) Consider an unknown language with a left-associative - operator that is overloaded to have the following types: int * real -> real, int * int -> int, real * int -> real, and real * real -> real. Suppose the variable i has type int and the variable r has type real. For each - operator in each of the following expressions, say which type of - is used:
a. (5 points) `r - i`
r - i: real * int -> real
b. (5 points) `r - i - r`
r - i: real * int -> real
i - r: real * real -> real
c. (5 points) `r - (i - r)`
i - r: int * real -> real
r - (): real * real -> real
d. (5 points) `i - r - i - (i - r)`
(i - r): int * real -> real
i - r: int * real -> real
r - i: real * int -> real
i - (): real * real -> real