Assignment 5 Compilers Solution

Complete the associated exercises before attempting the assignment
Aim
This assignment and its associated exercises provide an understanding of compilers and some limited experience in building a compiler using tools such as bison and flex.
Objectives
On completion of this assignment and its associated exercise, you will be able to:
• Explain the workings of a compiler
• Create applications that exploit a scanner generated using flex
• Write grammar rules for bison
• Write an interpreter that uses a parser generated using bison
• Write a simple compiler that generates executable code.
Task context – the PDP-11 compiler from the lecture notes
You are to extend the compiler system presented in the lectures.
This system generates PDP-11 code from source code in a simplified quasi-Basic language.
The generated code is in effect linked with a “libc” library that provides functions for reading and writing numbers (in both decimal and octal formats), and runs with “os” code. The “os” uses interrupt driven I/O; it supplies just two supervisor calls – readline and writeline.
You will start by downloading the code of the compiler system described in lectures (it is CompilerProtoProject.tar.gz in the Resources folder for the subject). This is the version that handles simple arithmetic expressions and while loops.
The project contains the parser.y and scanner.lex files that are used to generate the compiler.
The folder also contains the files libc.txt and os.txt that make up the “systems library” and “operating system” for this simplified example. There are also a number of example programs that can be compiled, with the compiled code being run on the simulator that was used in Task Group 2.

The lex file is similar to those that you have already worked with:
The grammar rules for the parser are presented in the lecture notes. Most are similar to those that you have already seen in the exercise, but things like the WHILE construct are a little more complex.
The language construct is: With something like this, code has to be emitted at several points. When the parser meets the WHILE token, it will have to set a label.
It must then handle the comparison which will produce some output instructions.
When it reaches the “DO” token, it must complete the code that allows for a jump to the end of the block if the comparison condition is not satisfied.
The statements must then be compiled. Finally, at the ENDWHILE, the parser must generate the code for a jump back to the start of the WHILE construct.
It also has to keep track of labels in a stack (this is necessary as one can have nested WHILE loops).
The handling of comparisons involves generation of code using PDP-11 instructions such as ble (branch on less than or equal):
(The code generated for a comparison is devised to set r0; r0 is set to zero if the comparison failed, or to 1 if it was satisfied. This r0 value is then tested in the code used to determine whether to jump past the while inner block.)
The code should work. It should generate a compiler that can handle the simple
programming language and generate working PDP-11 executables.
Try it. Build, and then run with one of the supplied quasi-Basic programs, e.g. test0.txt:
Compilation should have generated the file pdp11.txt with the generated code, the libc.txt code, and the osx.txt code.
You can view the PDP-11 instructions generated from that source program (right at the end of pdp11.txt):
The program can be loaded into the simulator that was used in Task group 2:
The code should assemble:
The code should run:
Try some of the other example programs as well:
test1.txt ( Requires input values).
test8.txt
(Have a look at the instruction sequence generated so as to gain an understanding of how code is generated for conditionals and for the overall WHILE construct with its labels and branch instructions.)
Task
We want more comparisons!
We want an ‘if test’!
OK – you extend the language and its compiler!
The comparisons should be fairly obvious. The version you downloaded dealt with “<” (less
than), and “=” (greater than or equal). What about the others?
You will need to handle “<=”, “==”, “!=”, “”. All you need do is add some new tokens, define the flex code for recognizing these:
Then compose the grammar rules that generate appropriate instruction sequences that use the different comparison instructions implemented in the PDP-11. You shouldn’t find that too hard and you should be able to test you compiler with WHILE constructs that use these additional comparisons.
The “if” test should take the form:
IF condition THEN
statements
ENDIF;
(Don’t try for ELSE, or ELSIF etc.)
You want to be able to process programs such as the following:
(The hardest part of implementing “IF … ENDIF;” will probably be keeping track of labels.
You will need to exploit, and maybe extend the code that handles labels for WHILE constructs. Of course, you should be able to handle IF constructs inside WHILE loops and
WHILE loops inside IF constructs).
Report
Your report should contain:
• scanner.lex
• parser.y
• examples of source code and generated PDP-11 instructions
• evidence that your generated PDP-11 code runs correctly.
Example:
(If pasting in screen shots of parser.y make sure that they are clear for the marker to read.)
Submission
Prepare your report and convert to PDF format as the file A5.pdf.
Submission is done electronically via a program called turnin that runs on “banshee” – the main CS undergraduate machine. You must first transfer your A5.pdf file to your home
directory on banshee (this is different from the home directory that you access on the Linux machines). You can transfer the file using a SSH file-transfer program. The Ubuntu OS allows you to open a file-browser connected to your banshee home directory – and you can simply drag your A5.pdf file across using the visual file browser.
For CSCI131, assignments are submitted electronically via the turnin system. For this assignment you submit your assignment via the command:
turnin -c csci131 -a 5 A5.pdf
This assignment will be due in the last week of session; consequently there will be NO late submissions.
The program turnin only works when you are logged in to the main banshee undergraduate server machine. From an Ubuntu workstation in the lab, you must open a terminal session on the local machine, and then login to banshee via ssh and run the turnin program.