Homework # 2
due Tuesday, February 10, 4:00 PM

Ambiguous Grammars

Some programming languages have ``if'' expressions:

<expr> ::= <expr> + <expr> | <expr> = <expr> | <expr> / <expr>
        |  if <expr> then <expr> else <expr> 
        |  <INTEGER> | <ID> | ( <expr> )

Thus one can write:

(if x = 0 then 1 else 10 / x ) + y

However the grammar above is ambiguous.

• Show three parse trees for the string ``if x = 0 then 1 else 10 / x + y''
• Rewrite the grammar to be unambiguous, where: if has lowest precedence, then =, then + and then /, with highest precedence. Both + and / should have left associativity, and = should be non-associative (x = y = z should be a syntax error).

Turn this part in on paper at the beginning of lecture.

Classical Sequence

Write a C++ main program square.cc that reads in an integer and then prints its square, and then exits. This program should be 10 lines long at most. Compile it using g++ on Unix in the following ways: (Hint: Compile from the source each time.)

• Compile to assembly language (square.s).
• Compile to object code (square.o).
• Compile to an executable (square).
• Compile to an executable without shared libraries using the -static option to g++ (square-static).

For each of the four artifacts produced in the previous stage, answer the following questions in a text file README:

• How many bytes long is the file?
• What does this file include other than the main function? The assembly language file is text and can be read. The other files can be viewed using the Unix utilities nm: it lists all the ``names'' in an object or executable file.
• What is ``main'' bound to in each artifact? (The tool nm gives the address each name is bound to. Use ``nm something | grep main'' to cut down the output to only lines with ``main'' in them.)

Submitting Your Work

You submit your program work by putting the files (square.cc and friends, as well as README) in the homework2 directory in your AFS class volume. You may do all your work in this directory, or you may wish to do your work in a different directory and copy things when correct into this directory. In any case, you will lose permission to write things in this directory after the deadline, which is 4:00pm on Tuesday, February 10th. In other words, you must be done before lecture starts.

The homework2 directory should include the following:

• square.cc
• square.s, square.o, square, square-static
• README.

About this document