## CSci 4651 Problem set 1.

### Due Monday, February 8th at 11:59pm (by e-mail)

### 26 points

### All textbook problems are in section 1.18

#### Problem 1 (6 points)

Problem 1 p. 23 (please submit your kernel language programs).

#### Problem 2 (5 points)

Modify GenericPascal so that one can pass to the function not only the operation to combine
the list elements, but also the starting row value (currently 1) and the element added as
"padding" when shifting rows (currently 0).

Check that you can generate the original Pascal triangle by passing 1 for the starting row value
and 0 as padding.

Generate a triangle by starting with the row of 1, using 2 for padding, and multiplication
as a combining function. How many rows does one need to compute to produce a value of 2^64 **or higher** [Corrected on 2/4] as
the highest value in a row? Please explain your answer.

#### Problem 3 (5 points)

Exercises 7, 8 on p. 24. Submit the corrected code for 8.

#### Problem 4 (10 points)

Construct an EBNF for a language of boolean constants `T, F`

(that stand for `true, false`

), operations `not, and, or`

, and parentheses. In the language:

`not`

has the highest precedence, meaning that it refers to the smallest element that follows it. For instance, `not T or F`

should be parsed as if parentheses are as follows: `(not T) or F`

,
`and`

has a higher precedence than `or`

, so `T or F and T`

is parsed as `T or (F and T)`

,
- both
`and`

and `or`

are left-associative, i.e. `T or T or F`

is parsed as `(T or T) or F`

,
- parentheses overwrite any default rule, just like in arithmetic expressions.

Show parse trees for the following expressions:
`T or not F and not T and F`

`not (T or F) and not T`

#### How to submit

Submit your file(s) to me by e-mail. The subject must be
**Problem Set N**, where N is the problem set number.

Handwritten problems can be scanned and attached (good quality scanning, please!) or submitted
in class or in my office in person. If submitting handwritten work, please clearly write
your name and problem set number on it.

CSci 4651 course web site.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.