Summer 2017, Test 1

1a. What was the first widely used programming language?

1b. When was it developed?

1c. What were its main limitations?

2. What is the difference between imperative, functional, logic
(declarative), and object-oriented languages?

3a. Assuming that the notion of <variable> is already
defined, describe boolean expressions in Java in BNF form. The
only constants are true and false. (Feel free to ignore non-lazy
operations.)

3b. Why do we need to describe languages in BNF form? Why cannot we just describe them in English?

4a. Translate the following EBNF description into BNF:

<variable> := <letter> {<letter> | <digit> | _}

<letter> := a | ... | z | A | ... | Z

<digit> := 0 | ... | 9

<variable> := <letter> {<letter> | <digit> | _}

<letter> := a | ... | z | A | ... | Z

<digit> := 0 | ... | 9

4b. Why do we need EBNF?

5a. Show, on an example, that the following description of
propositional expressions containing || is ambiguous:
<expression> := <variable> | <expression> ||
<expression>.

5b. Show how to make this description unambiguous.

6a. What is the strongest postcondition for the following program:
{a > 0.0} a = 2 * a + 3;

6b. What is the weakest precondition for the following program: a = 2 * a + 3; {a > 0.0}

7. Describe a state diagram for the computer to detect Java
fixed-point real numbers.

8. Use bottom-up approach to parse the following expression: (a ||
b) && (c && d || e) || f && (g || h). Remember that "and" has
higher priority than "or".

9. Use pre-and post-conditions to prove that the following Java
program for computing a + b is correct:

int sum = a; for (int i = 1; i <= b; i++) {sum++;}

10. Describe, step-by-step, memory allocation and values of all
the variables for the program segment from Problem 9. Assume that
a = 3, b = 2, that the variable b was the last variable allocated
before this program segment, and that the hex address of the
variable b is 2017.