EECS 356: Programming Language Concepts, Written Exercise 1 due Friday, February 9, 2018 in class
Problem 1: Consider the following ambiguous BNF grammar:
<C> → <C>?<C>:<C>|<V>=<C>
<C> → <C>&&<C>|<C>||<C>|!<C>|<V>|true|false|(<C>) <V> → x|y|z
Rewrite the grammar so that it is no longer ambiguous and has the following properties:
The operators have the following precedence, from highest to lowest: ( ), !, &&, ||, ?:, =.
The !, ?:, and = operators are right associative, and the && and || operators are left associative.
Problem 2: Consider the following grammar (yes, it is ambiguous but that is unimportant). The subscripts are used to distinguish otherwise identical non-terminals for the purpose of the questions below.
<start1 > <start2 > <stmt1 > <stmt2 > <declare1 > <type1 > <type2 > <assign1 > <expression1 > <expression2 > <op>
<value1 > <value2 > <value3 > <var> <integer> <float>
→ <stmt3> ; <start3> → <stmt4 >
→ <declare2 >
→ <assign2 >
→ <type3> <var>
→ int
→ double
→ <var> = <expression3>
→ <expression4> <op> <expression5> → <value4 >
→ +|-|*|÷ → <var>
→ <integer>
→ <float>
→ a legal name in the language
→ a base 10 representation of an integer
→ a base 10 representation of a floating point number
Suppose our static semantic description has five attributes:
type = typetable(<var>) = inittable(<var>) = typebinding = initialized =
{ integer, double }
{ integer, double, error }
{ true, false, error } (<var>, { integer, double }) (<var>, { true, false })
typetable maps each possible variable name to its declared type, and inittable maps each possible variable name to a boolean indicating whether the variable has been assigned a value. Initially, both typetable and inittable will map all possible variable names to error to indicate that the variables have not been declared in the program.
typebinding maps a single variable name to its declared type, and initialized maps a single variable name to whether it has been assigned a value.
For each subscripted non-terminal, provide a rule to calculate its type, table, inittable, typebindig, and ini- tialized attributes, if that non-terminal requires that attribute. Each attribute should either be inherited or synthesized, but not both. For example, here are two such rules:
<value2>.type := integer
<declare1>.initialized := (<var>, false)
(Here I am using := to create a mapping so you can use = to mean only mathematical equality.)
Problem 3: Suppose we want to enforce the following rules in the grammar from Problem 2:
(a) The type of the expression must match the type of the variable in all assignment statements.
(b) A variable must be declared before it can be used.
(c) A variable must be assigned a value as its first use in the program.
Where in the parse tree should these rules be checked (i.e. at which non-terminals), and write the precise tests that should be done at those non-terminals using the attibutes available.
Problem 4: You have the following code on which the programmer included desired precondition and postconditions and included (hopefully) correct loop invariants on each of the loops. Given the stated post- condition (i.e. goal) for the code, you are to:
a) State whether the given loop invariants are correct, and if not to give corrected loop invariants.
b) For each numbered statement, give the correct weakest precondition for that statement.
c) Determine whether the weakest precondition for statement 1 is logically inferred from the stated precon- dition of the code.
Precondition: n ≥ 0 and A contains n elements indexed from 0 1. bound = n;
/* Loop invariant: A[bound,..,(n-1)] is sorted (non-decreasing) and A[bound] >= A[0,..,bound-1] */
2. while (bound > 0) {
3. 4.
5. 6. 7. 8. 9. 10.
11.
12.
Postcondition: A[0] ≤ A[1] ≤ …≤ A[n-1]
Problem 5: Let Mstate be a denotational semantic mapping that takes a syntax rule and a state and produces a state. Define the Mstate mapping for the following three syntax rules assuming we allow side effects, that is, assuming expressions and conditions can change the values of variables.
}
t = 0;
i = 0;
/* Loop invariant: A[t] is the largest element of A[0,..,t] */
while (i < bound-1) {
if (A[i] > A[i+1]) { swap = A[i];
A[i] = A[i+1]; A[i+1] = swap; t=i+1;
} i++;
}
bound = t;
<assign> → <if> → <while> →
<var> = <expression>
if <condition> then <statement1> else <statement2> while <condition> <loop body>
Assume we have the following mappings defined:
Mvalue takes a syntax rule and a state and produces a numeric value (or an error condition).
Mboolean takes a syntax rule and a state and produces a true / false value (or an error condition). Mname takes a syntax rule and produces a name (or an error condition).
Add takes a name, a value, and a state and produces a state that adds the pair (name, value) to the state. Remove takes a name and a state and produces a state that removes any pair that contains the name as the first element.
You may assume the Add and Remove mappings do not produce errors.