Homework # 2
due Tuesday, February 8, 3:30 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 1 = 2 then 3 else 4 * 5 + 6''
• 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).

First Experience with ML

I assume you have a computer you can install software on. Install SML on your own computer. Start up a session and evaluate the following two expressions:

Time.now();
if 1 = 2 then 3 else 4 * 5 + 6;

Print out the window with the contents of this session. Indicate which of the three parse trees SML/NJ chose for the second expression.

Standard compilation sequence

Write a file square.cc:

#include <iostream>
using namespace std;

int main()
{
  int i;
  cin >> i;
  cout << i*i;
  exit(0);
}

On miller or weise, compile this program to assembly (g++ -S square.cc) and to object file (g++ -c square.cc) and to an executable (g++ square.cc). Answer the following questions:

1. Look in the assembly file (square.s) and find out in the function main how it refers to cin. Show that here.
2. Use the program c++filt to convert that ``mangled'' name into a readable name. What is the full name of cin ? Why does C++ mangle the name?
3. What other functions exist in the assembly file? Give their unmangled names.
4. Use /usr/ccs/bin/elfdump to examine the object file, square.o. How does the file refer to exit ?
5. Look at the relocation table for the text segment: .rel.text. What does _ZNSolsEi refer to? Why is it there? Why is there no entry for int i; ?
6. Use the command ldd on the executable a.out. This indicates what shared libraries are used by the executable and where they (currently) can be found. List each and investigate what each does; report why each is being used.

Submitting Your Work

If you do not have your own computer, see me, and I will give you you an alternate assignment.

Turn in your answers on paper.

About this document