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