CS525 -- Programming Project Three

In this third part of the project, you will implement the type checker and the first part of the intermediate code generator for your semester project. You will not have to deal with functions or local data in this project. You will, however, have to deal with structured data and layout of data in the static region of memory.

You will have all the information that you need to know by the end of next week (e.g., by June 27th), and you will have enough information after class today (June 20th) to make a serious start. You have to read everything carefully and think about it before you start.

You may do this project alone, or in a group of two people. In the latter case, both will receive the same grade, and both are expected to understand the entire project.

If you read carefully, plan carefully, and divide up the work appropriately, this project is not that hard. Everything you need is spelled out explicitly in the notes, the textbook, and the Lex and Yacc book.

Details of the Project

For this final installment of the compiler you've been writing this semester, you must implement intermediate code generation for the grammar you used in the last assignment, with the following features.

• You must perform lexical and parse error checking and reporting as in the previous projects.
• You must generate code for all the constructs of the language except for function definitions and function calls; you can leave these grammar rules in place if you like, and simply assume that they will never be used in any of the test files for this project. Your program should read the source file from the standard input, as before, and output to the standard output the translation into the IC language we have presented in class and in the notes.
• You must implement break, continue, and the lazy evaluation of boolean expressions, using the technique of backpatching, as explained in class and in the notes (note that other cases of forward reference can be resolved using dummy non-terminals to store the appropriate addresses).
• The only type error will be if the modulus operator has a floating point argument; since its arguments might be expressions, this means that you need to implement the type-checking rules for int and float expressions, as described in class. If such a type error has been found, report the error and terminate compilation. You do not need to generate IC that distinguishes between ints and floats (notice that our IC language as given does not do this), so the modulus operator is the only possible source of type errors.

Using Yacc

Almost all of these techniques were discussed in class, in most cases with specific attribute grammars to show in detail how to effect the translation. Thus, there is nothing that original to do, you simply have to figure out how to do it in Yacc. You need to read the book first, plan out what you are going to do, and set realistic goals. START EARLY!!

I will be putting a sample file on the web very soon, which should contain all the essential features you need to know about. Before you do that, you should carefully read and think about the following sections in the Yacc and Lex book:

• Chapter 3, especially pp.64-67.
• Chapter 7, pp.182-184, on embedded actions.
• Chapter 7, pp.189 on using 0, -1, etc. (but you will not be considering these to be ``inherited'' attributes). You may not need to use$-1 and so on, but you may find it useful if you create your own explicit dummy non-terminals.
• Chapter 7, pp.201--205 on giving a type to the stack nodes for various grammar symbols.

There are two important ideas you need to have straight before starting. The first is how to use embedded actions, i.e., actions between the symbols on the rhs of the rule. The main difficulty is when you get reduce/reduce errors. Keep in mind that Yacc literally rewrites the grammar rule:

S :   A { action1; } B { action2; } C { action3; }

S :   A D1 B D2 C { action3; }  ;

D1 :  { action1; } ;

D2 :  { action2; } ;

The second thing you need to understand well before starting is how to give a record (i.e., ``struct'') type to the ``value stack'' in Yacc holding all the attributes you will need, and how to refer to these attributes in the actions. The basic idea is to use the %union command, and then type the symbols using either %token, or %type. Then you can simply consider the stack variables $$, $1, $2, etc. to be variables of the appropriate record type. (see p. 205, where for ``symbol value'' read ``stack cell'', and also look for UNION and YYSTYPE in the index).

This is not really very difficult, and just about everything you need to know is spelled out explicitly in the references just mentioned, or in the class notes. The class notes present an abstract view of the techniques, and your job is mostly to map this onto what Yacc expects.

As before, and as is appropriate for a 500-level class, you have a certain amount of flexibility in the choices you make in completing the project. Please check with me if you have concerns or questions about what to do or how to proceed.

What to Hand In

You must hand in the following by the due date and time, into the CS 525 slot in the Homework Station:

1. A brief project writeup, containing a cover page with the title of the course, the names of all group members, and a description of any assumptions you made, and problems you encountered, and any features you wish to draw my attention to. This need not be more than one page.
2. A printout of all Lex and Yacc source files, and a script file showing your parser running on all the test files. If you do not demonstrate your parser on one or more files, I will assume it does not work on that file.
3. Submit all lex and yacc source files, and a copy of the script files, into a directory called "proj3" in the group leader's Gsubmit directory.

Please put all this together NEATLY and make it easy for me to look over what you have done. Label all parts of your submission and either staple or put a clip on the entire writeup.