## 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.

- A. Show the parse trees for the following:
.00034, 1E9, 3.14159, 1.2e-3
- B. Suppose that we change the first line of the EBNF to
Float ::= DigitSeq { Exponent } | DottedDigits { Exponent }

That is, we put curly brackets around the first occurrence of "Exponent".
What additional forms would the new definition allow? Why would that not be
correct?

### 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;
return(i);
next: ;
}
return(-1);
}

- A. Show how this routine can be written in C or another imperative language
without using gotos by using an extra Boolean variable.
- B. Show how this routine can be written in C or another imperative
language without using gotos or
an extra Boolean variable.