Computer Science 3675
Fall 2003
Homework set 1

Due: Sep 23, at the beginning of class.

  1. (Exercise 8, page 45) Where are programming language features typically put more to the test, in libraries or in application programs?

  2. (Exercise 4, page 68) The syntax of C allows an expression to be just a semicolon. Such a statement performs no action. Give an example where an extraneouse semicolon (easily overlooked by a programmer) vastly changes the meaning of a C program. The program must compile both with and without the semicolon. (Hint: consider a while loop.)

  3. (Exercise 6, page 69) Using grammar (3.8.1-3.8.8), draw a parse tree for expression 3+4+8. Does addition associate to the left or to the right according to this grammar?

  4. (Exercise 7, page 69) Using grammar (3.8.1-3.8.8), draw a parse tree for expresion (4)+5*(6+2).

  5. (Exercise 8, page 69) Show that grammmar (3.5.2) is ambiguous. Assume that there is a simple kind of statement s and a simple kind of expression e, and do not worry about the detal of those.

  6. (Exercise 11, page 102) Assume that arrays are stored using sequential representation. How long, as a function of n, does it take torun the loop of Figure 5.1(a). Give the answer to within a constant factor (big-O notation). If a linked representation were used for array A, instead of a sequential representation, how long would it take?

  7. (Exercise 4, page 113) What are the advantages of a relocating mark/sweep garbage collector over a garbage collector that uses reference counts?

  8. (Exercise 2, page 122) Write an Astarte pattern match that binds t to the third member of a quadruple called q. (So q has the form (a,b,c,d).) Astarte allows you to use a plain question mark for an anonymous variable, which is one whose value you don't care about.

  9. (Exercise 4, page 122) In Astarte, expression <::> creates a new box, or variable, that has no name. Show how to create a new variable and to call it x.

 

Grammar (3.8.1-3.3.8) is as follows. 

 
  <expression>      ::= <sum-expression>
                    |   <expression> = <sum-expression>

  <sum-expression>  ::= <prod-expression>
                    |   <sum-expression> + <prod-expression>

  <prod-expression> ::= <factor>
                    |   <prod-expression> * <factor>

  <factor>          ::= number
                    |   ( <expression> )

Grammar (3.5.2) is a follows. 

  <statement> ::= if <expression> then <statement> else <statement>
               |  if <expression> then <statement>