Problem Set 1

Assigned: Jan. 24.
Due: Feb. 7

Note: Problem sets will be discussed in recitation the Monday after they are due. Therefore, they will be accepted late with a penalty of 1 point out of 10 until the time of the recitation Monday but not later.

Problem 1

The syntactic form of floating point constants in C can be defined in the following EBNF: (from C: A Reference Manual by Samuel Harbison and Guy Steele Jr.)
Float ::= DigitSeq Exponent   |   DottedDigits { Exponent }
Exponent ::= [e|E] { [+ | -] } DigitSeq
DottedDigits ::= DigitSeq .   |   DigitSeq . DigitSeq   |   . DigitSeq
DigitSeq ::= Digit+
Digit ::= 0   |   1   |   2   |   3   |   4   |   5   |   6   |   7   |   8   |   9

In the above, terminals are shown in boldface; superscript +, as in "Digit+", means 1 or more repetitions; curly brackets as in "{ Exponent }" means optional, and square brackets, as in "[e|E]" are for grouping.

Problem 2

Scott, exercise 6.1.

Problem 3

A. Convert the following expression into prefix and into postfix:
[X - (X*X*X/3)]/[1 - (X*X/2)]

B. Prefix and postfix notations are unambiguous without the need for parentheses, precedence rule, or associativity rules, assuming that every operator takes a fixed number of arguments. However, in most programming languages, the minus sign - can be used either as a unary or a binary operator. Give an example of a prefix expression using the minus sign which is ambiguous unless the two usages are distinguished.

Problem 4

Scott, exercise 6.7.

Problem 5

(Modified from Scott, exercise 6.16): In an article entitled " 'GOTO considered harmful' considered harmful" (CACM 30(3):195-196 March 1987) Frank Rubin argued that avoiding the use of gotos inevitably led to ugly coding. His example was the problem of finding an all-zero row in an n*n array. His solution using a goto was essentially as follows (translated into C and somewhat modified):
int firstZeroRow(int n, x[][])

{ for (int i= 0; i < n; i++) {
     for (int j=0; j < n; j++)
       if (A[i][j] != 0) goto next;
     next: ;