CSE 401: Compilers Fall 1997 (Henry)

Assignment 5 Lex, Yacc and NaNs

Due Monday, 03Nov97

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 individualliy.

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 alphas or the instructional mips machines. 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)

Refer to the email instructions the TA will post on how to copy the files calc.y, calc.l and Makefile. Copy them into a separate directory named "calc" so that 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", in any case. This means "Not a Number". You can call the function "double makenan()" to return a floating point number encoding a NaN. do NOT call atof to scan and convert this string.

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. Do NOT call |atof| to scan and convert this string.

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 note was added on 02Nov97:

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.

Unfortunately, the second "bird" is wearing a bullet proof vest and will not work as intended.

I made the (terrible) assumption that the instructional machines (sanjuan, orcas) running on alphas under DEC's version of unix would handle floating point operations per the IEEE standard for floating point arithmetic and so they would handle 0.0/0.0 correctly and yield Infinity. These systems do NOT do this correctly by default (even though they are supposed to be IEEE compliant), and as some of you have pointed out, will take a floating point exception and then "dump core".

I am unable to figure out the proper minimal fixup to make these systems do the right thing, since it involves interactions with the operating system and interactions with the compiler: one has to force the compiler to generate the correction instructions in anticipation of possible divisions by 0!

My terrible assumption was that the DEC alphas would implement IEEE correctly, since, after all, the sparc on my desk at work does, and the Tera machine does. Wrong!

So: you do not have to check that your little lex/yacc assignment implements IEEE boundary cases correctly (0/0, Inf+0, 0

Refer to the email instructions the TA will post on how 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).