CS130 - Spring 2003 - Homework Assignment #1

Homework Assignment #1
(due on 05/10 at the beginning of class)

Problem #1: History

(10 point) Based on your reading of Chapter 2 in the book, answer the following questions:

1. Why was the slowness of interpretation of programs acceptable in the early 1950s?
2. Which language is considered the ancestor of COBOL and who designed it?
3. What are two reasons why Java is safer than C++
4. What are two languages whose use was mandated by the U.S. Dept. of Defense?
5. Which language first introduced the ability to reference a cross section of an array? (e.g., view the 3rd column of a matrix as a vector)
6. What was the main application of the SNOBOL language?
7. From which three languages did PL/I borrow many of its constructs?
8. Which language had its syntax described in BNF for the first time?
9. Which functional language has a syntax close to that of an imperative language?
10. Which was the first widely used language to do away with punched cards and paper tapes and to rely on an actual terminal?

Problem #2: BNF grammar

(10 points) Write the BNF grammar for the Ada case statement, as described on page 327 of your book. You can assume that the following nonterminals are defined in the full grammar:

<stmt> a statement
<expr> an expression
<const_expr> a constant expression

Problem #3: Operator Precedence

Consider the following grammar, G:

<exp> --> <exp> + <mulexp> | <mulexp>
<mulexp> --> <mulexp> * <divexp> | <divexp>
<divexp> --> <divexp> / <rootexp> | <rootexp>
<rootexp> --> ( <exp> ) | a | b | c | d

a. (10 points) Add to G a right-associative operator '%', whose precedence is between '+' and '*', thus obtaining a new grammar G'. b. (10 points) Add to G' a unary operator '#', whose precedence is the highest, thus obtaining a new grammar G''. c. (10 points) Modify G'' so that the '*' and the '/' operators have the same precendence and are both right-associative.

Problem #4: Axiomatic Semantics

a. (5 points) Compute the weakest precondition for the following statement and postcondition (assume that all variables are integers):

a = 3 * (b - 1) - 2 { a > 3 }

b. (15 points) Compute the weakest precondition for the following statement and postcondition (assume that all variables are integers):

if (a != 3) a = 2*a - 1; else a -= 2; ; { a > 0 }

Problem #5: Expressions

Consider the following program in C syntax:

int foo (int *i) { *i *= 3; return 1; } void main () { int x = 5; x = x + foo (&x); if ((x++) || (foo (&x))) x+=10; printf("%d\n",x); }