CS 3360 Design and Implementation of Programming Languages
Summer 2017, Test 1

Name: __________________________________________________________

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

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.