CSE 401 Autumn 2001 (Henry)

Assignment 5 (Lex, Yacc and NaNs)

($Revision: 1.8 $)

Due Monday, November 5, 2001

In this assignment you will be extending a simple calculator that I have written using lex and yacc. All of this assignment is to be done individually (no groups!).

Read about the use and representation of IEEE-format floating point numbers. There is a discussion of them in the computer architecture textbook by Hennessey and Patterson. See also this brief overfiew on IEEE format numbers.

Remember a fundamental rule of compiler construction: the compiler should not "mess" up floating point computations unless the compiler writer really, really, really knows what he/she is doing. None of us do.

This assignment should be straightforward.

First, you have a simple task to do.
Second, large parts of the assignment are covered verbatim in the text book.
Third, you are writing a compiler using a specification for a compiler compiler, and so many details are totally hidden.
Fourth, you are leveraging off of a foundation that I've already written.

You should not have to spend more than 2 hours on the assignment.

You must do this assignment on the instructional unix servers. It is unlikely that you'll get the right answers for the special floating point numbers on other boxes, such as on wintel boxes.

Read ASU 3.5 (lex) and 4.9 (yacc).

On the instructional unix machies, copy the files calc.l, calc.y and Makefile from the directory

/projects/cse/courses/cse401/01au/calc

into your own separate directory named "calc". This way you can keep this work separate from the other cse401 related work you are doing.

Extend the lexical specification to support floating point numbers, using the lexical structure we discussed in class. Use the C library routine double atof(const char *) to convert from base 10 ascii strings to floating point numbers. You will also be required to scan NaN and Inf; see below.

Change the synthesized attribute type (in the yacc %union declaration) to use the type double, instead of the type int. Extend the calculator as appropriate to print out double precision numbers, instead of ints.

Extend the calculator as appropriate to do infix binary +, -, * and /; to do unary prefix + and -; to do the 6 infix comparision operators; to do distfix () operator (eg, normal parenthesis). All these operators should have the conventional meaning, precedence and associativity. The comparison operators should be implemented so they return 1.0 on success and 0.0 on failure.

Extend the calculator as appropriate to recognize special prefix unary functions sin, cos, tan, asin, acos, atan; these prefix unary functions expect a single parenthesized argument, and should be implemented by calling the corresponding C library functions. (These functions manipulate radians, not degrees!) Read the man page for sin (eg, the Unix command man 3 sin) to learn about these trigonometric functions.

Extend the lexical specification to support two special floating point numbers. These floating point numbers have special lexical rules, and special arithmetic that is implemented directly by the underlying hardware.

One special floating point number lexically appears as NaN or NaNS, where the letters can be in either upper or lower case. NaN This means "Not a Number". You can call the function double makenan() to return a floating point number encoding a NaN. (On Linux machines, it seems that you can call the the routine atof to scan and convert this string, but these semantics are unlikely to work on non-Linux machines.)

One special floating point number lexically appears as "Inf", in any case. This means (positive) infinity. You can call the function double makeinf() to return a floating point number encoding an infinity. (On Linux machines, it seems that you can call the the routine atof to scan and convert this string, but these semantics are unlikely to work on non-Linux machines.)

Aside from scanning these numbers and calling the special functions to make instances of these special numbers, you do not have to do ANYTHING else special to parse or attribute NaNs or Infs. Everything else should be done for you by the runtime system or by the underlying hardware.

Experiment with expresssions like 0/0, Inf/Inf, NaN*0, 1<Nan, 1>Nan, and other expressions involving boundary conditions for real numbers.

This lex/yacc assignment was intended to "kill 2 birds with one stone": do a simple lex+yacc assignment (which entails copying pretty much directly from the text book, with some extensions), and to also "learn by experimentation" about some special floating point numbers.

Use the turnin program to turnin the source code calc.l and calc.y.

Your grammar should have no shift/reduce or reduce/reduce conflicts, as reported by yacc.

Examine the file named y.output which yacc produces to describe the state machine it produced. The output is a little terse. The output uses "_" (underscore) to mark the current location in an item instead of using the more normal convention "." (period) we have been using in class.