CS 3304
Solutions to Homework Assignment 1
July 10, 1997

[4] 1.

Chapter 2, Problem 18. You are asked whether a programming language should be designed by a committee or by a single master architect. Give at least two pros and cons for each approach. Then give your opinion and justify it.

Here are some possible pros and cons for each approach:

Either approach can succeed admirably or fail miserably. A reasonable case can be made for either approach.

[6] 2.

While reading Chapter 2, locate 8 characteristics that a programming language may have. List each characteristic along with the first programming language that had the characteristic and the designer(s) of that language.

A reasonably complete listing of these characteristics can be found in Figure .

  
Figure: Characteristics of programming languages

[6] 3.

Chapter 3, Problem 2, parts c and d.

Here is some EBNF for a C switch statement:

Note a subtle difference between `{' (a terminal) and ` ' (a metacharacter for EBNF). A syntax diagram is

Here is some EBNF for a C union declaration:

A syntax diagram is

[6] 4.

Chapter 3, Problem 4.

a.

Here is the leftmost derivation

with the corresponding parse tree in Figure .

  
Figure: Parse tree for Problem 3.4(a)

b.

Here is the leftmost derivation

and the corresponding parse tree in Figure .

  
Figure: Parse tree for Problem 3.4(b)

c.

Here is the leftmost derivation

and the corresponding parse tree in Figure .

  
Figure: Parse tree for Problem 3.4(c)

d.

Here is the leftmost derivation

and the corresponding parse tree in Figure .

  
Figure: Parse tree for Problem 3.4(d)

[6] 5.

Chapter 3, Problem 6.

Since unary minus is to have higher precedence than plus or times, it must be applied to a factor. Adding the nonterminal and appropriate rules (below) specifies the optional application of unary minus to a factor.

[6] 6.

Chapter 3, Problem 9.

a.

We can derive abcd as follows:

Hence the string is in the language generated.

b.

From the rules involving , we see that if b is followed by a symbol in a sentence, then that symbol must be c. Hence acccbd cannot be in the language generated.

c.

We argue by contradiction that acccbcc is not in the language generated. Suppose acccbcc is a sentence. The only way to obtain a b is by the rule . Hence must be a sentential form. The only rule that has on the right-hand side is . Since there is only one a in acccbcc, this rule is applied at most once. We conclude that the following derivation steps hold for any derivation of acccbcc:

(We use the notation for ``derives in zero or more steps''.) Such a derivation is clearly impossible. Hence acccbcc is not in the language generated.

d.

First observe that every nonterminal generates strings of length at least one (no empty strings). The start symbol generates b and, through , strings of one or more c's. Otherwise, all sentences start with the derivation step . Since acd is not b, is not all c's, and is not of length at least 4, it cannot be in the language generated.

e.

We can derive accc as follows:

Hence the string is in the language generated.

[6] 7.

Chapter 3, Problem 12, part f.

One possible operational semantics for the switch statement can be found in Figure .

  
Figure: Operational semantics for the switch statement

[6] 8.

Chapter 3, Problem 14.

a.

The weakest precondition is

b.

The weakest precondition is

[8] 9.

Derive the weakest precondition for the following loop and the given postcondition:

 B<>while   ¯a > b

				do   ¯a := a + 1

						 ¯b := b + 2

		 {a + b = c}

Assume that a, b, and c are integer variables. Also argue that execution of the loop always terminates.

We need to think separately about the cases a;SPMgt;b and .

If a;SPMgt;b before the loop is encountered, then the loop body is executed some number of times, call it k; so k;SPMgt;0. Every time the loop is executed, a-b decreases by 1. Hence, after k executions of the loop body, we have a=b and loop execution is complete. Also, every time the loop is executed, a+b increases by 3. Hence, after k executions of the loop body, a+b increases by 3k. Since we want a+b=c, we need the precondition to imply

when a;SPMgt;b.

If , then we just need the precondition to imply a+b=c.

Putting both cases together, we arrive at the weakest precondition

Termination follows because a-b decreases by 1 each time the loop body is executed and the loop condition is a;SPMgt;b.

[6] 10.

Chapter 3, Problem 15, part d.

A C for statement has the form

where , , and are expressions and is a C statement. Let s=(mem,i,o) represent an arbitrary state. To obtain the denotational semantics mapping function for the for statement, we need to define the value

To simplify the discussion, define

the state after initialization by . The semantic mapping is then

About this document ...

This document was generated using the LaTeX2HTML translator Version 96.1 (Feb 5, 1996) Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.

The command line arguments were:
latex2html -split 0 -t CS 3304 Solutions to Homework Assignment 1 solvehw1.

The translation was initiated by cs3304sm class account on Thu Jul 17 09:19:23 EDT 1997