2019/10/26 Workshop 11 – Code Generation: Computer Systems (2000_7081 Combined)
Workshop 11 – Code Generation
Code Generation Overview
In this workshop you will write a code generator that uses an abstract syntax tree output by the recursive descent parser for the simple programming language described in the previous workshop.
To help you get started we have provided a working parser, parser.cpp, a skeleton of a code generator, translator.cpp and a library of useful functions that we use in most programming workshops and assignments. The library implements a tokeniser for the example language, an abstract syntax tree that can be read or written as XML, symbol tables and an output buffer. The library functions that you can use are described in the .h files in the includes sub-directory. The tokeniser functions are described in the tokeniser.h file, the abstract syntax tree functions are described in the abstract-syntax-tree.h file, the symbol tables are described in the symbols.h file and the output buffer is described in the iobuffer.h file. You may not need to use all of this functionality in this workshop.
Participation Marks
Up to 5 participation marks are available for every workshop, 2 for preparation, 1 for attendance and 2 for completing an activity.
Attendance
One participation mark will be awarded if you attend a workshop and your presence is recorded using our practical marker (https://cs.adelaide.edu.au/services/pracmarker/) . Do not click on “flag me for marking” button until a supervisor is standing next to you and is ready to record your presence. The flag is only to speed up the data entry and is not visible for very long.
Workshop 11 Background Reading
Before attending the workshop you should read the full workshop description, review the startup files provided below and you may wish to re-read chapter 11 of the textbook.
Workshop 11 Preparation Activity
Two participation marks will be awarded for completion of this preparation activity if it is completed at least 10 minutes before the workshop that you attend but not more than 1 week before.
Note: in example commands % is the shell’s prompt, it is not part of the command.
Note: the web submission system will record 0 marks for completing this activity, the 2 marks are awarded later when your attendance is recorded by the pracmarker but, only if the activity was completed before attending a workshop.
1. Make a new directory in your svn repository to keep your files for this workshop:
% svn mkdir -m workshop11 https://version-control.adelaide.edu.au/svn/
11
https://myuni.adelaide.edu.au/courses/44936/pages/workshop-11-code-generation?module_item_id=1374198 1/4
2019/10/26 Workshop 11 – Code Generation: Computer Systems (2000_7081 Combined)
2. Check out a working copy of your new svn directory.
3. Change to the workshop11 directory:
% cd ~/cs-projects/workshop11
4. Copy the workshop 11 startup files into the workshop11 directory. The startup files are in the zip file attached below.
5. Review the startup file parser.cpp. This a working version of the parser that you could have written in last week’s workshop and is the source code for bin/parser.
6. Compile a skeleton version of the translator program to be implemented in this workshop using the command:
% make notest
The executable program, translator, is compiled using the file translator.cpp and the precompiled library file lib/lib.a. The main function in the translator program calls the parseProgram() and passes it an abstract syntax tree constructed by the function ast_parse_xml().
7. Add the new files to your svn repository:
8. Goto the Web Submission System and make a submission to the Workshop 11 assignment. A successful submission that passes the preparation tests will complete the preparation activity.
Workshop 11 Activity
Two participation marks will be awarded for completing the following activity. This need not be completed during the workshop but no participation marks will be awarded if the activity is not completed by Friday 5pm of week 11
After completing each part of the following activity, commit your changes to svn:
% svn commit -m workshop11-activity
After each commit, go to the Web Submission System and make a submission to the Workshop 11 assignment. A successful submission that passes any of the codegen tests for input example1.test or example3.test will complete the workshop activity.
Code Generation – VM Code
Write a code generator for the simple programming language described in the previous workshop that will produce the equivalent Hack Virtual Machine code. You should do this by adding code to the translator.cpp file that will traverse an abstract syntax tree produced by bin/parser that you could have written in the previous workshop.
% svn co https://version-control.adelaide.edu.au/svn/
workshop11
% svn add Makefile Makefile-extras bin includes lib lib/*/lib.a tests parser.cpp translator translator.cp
p
% svn commit -m “Workshop 11 Startup Files”
https://myuni.adelaide.edu.au/courses/44936/pages/workshop-11-code-generation?module_item_id=1374198 2/4
2019/10/26 Workshop 11 – Code Generation: Computer Systems (2000_7081 Combined)
To simplify your task you can make the assumption that the abstract syntax tree you have been provided has been correctly constructed and that it also corresponds to a syntactically correct program. The get_* () functions provided by the abstract syntax tree implementation always check that the node they are asked to operate on is of the correct kind. If they encounter the wrong kind of node a fatal error is reported.
In general, a correctly constructed tree will have one node for each term in the grammar, that is, one node per parseXXX() function in the original parser. Therefore, the code generator should also be able to be structured with matching parseXXX() functions where each function takes a node to process as its sole argument. In the case of our example language we do not have statement or term nodes but we can still have parseStatement() and parseTerm() functions. Theses functions inspect the node they are actually passed and call the appropriate parseXXX() function to process it.
The abstract syntax tree represents variables by a node that records their name, type, segment and offset. Since all variables are of the same type, are stored in the same segment and the names are not used in the generated code, the only information that is required for code generation is the offset. Therefore, there is no need to use symbol tables in your translator program.
Example Parse Function
Assuming that we have a correctly constructed abstract syntax tree, the parseLetStatement() function in the translator could be written as:
The node passed to parseLetStatement() should be the result of a call to create_let(). It should have two fields, variable is an identifier and expression is an expression. The variable also has a field offset containing the variable’s location in the local segment. The first thing this code does is access the variable and then access the variable’s offset. Next, it passes the expression to the parseExpression() function and assumes that it will generate the code to place the value being assigned onto the top of the stack. Finally it pops that value off the stack and into the variable.
Virtual Machine Output
The virtual machine code produced should be prefixed by the following function header:
function Main.main x
where the value x is the number of identifiers declared in the program. You should note that the parseDeclarations() function returns an integer parameter for this purpose. The first identifier should be referred to as local 0, the second as local 1, and so on.
The virtual machine code produced should be terminated with the following two commands:
// ast create_let(ast variable,ast expression)
static void parseLetStatement(ast n)
{
ast var = get_let_variable(n) ;
int localOffset = get_variable_offset(var) ;
parseExpression(get_let_expression(n)) ;
write_to_output(“pop local ” + to_string(localOffset) + “
”) ;
}
https://myuni.adelaide.edu.au/courses/44936/pages/workshop-11-code-generation?module_item_id=1374198 3/4
2019/10/26 Workshop 11 – Code Generation: Computer Systems (2000_7081 Combined)
If you do this, you should be able to test your generated code by running your program in the VMEmulator.
Limited VM Operators
The Hack Virtual Machine lacks a number of useful operators. The builtins that you can use are limited to, add (“+”), sub (“-“), lt (“<“), gt (“>“) and eq (“==”). In order to generate correct code for multiply (“*”) and divide (“/”) you need to call the Math.multiply() and Math.divide() functions provided by the Jack Operating System. In order to generate code for the missing logical operators you can generate two operators where the second one is logical not. For example, “<=” can be implemented as gt followed by not. The skeleton translator.cpp file contains functions translate_op() and translate_relop()that will generate the correct VM code for each kind of operator token.Automatic TestingSo that you can test your code generator, we have provided example programs in the tests directory in the zip file attached below. You can test your code generator as follows: % make testTesting student translator against Pxml-vm files.| Test Input | bin/parser | translator |Expected Test Output|Test ResultChecking “cat tests/example1.test| ./bin/parser | ./translator | diff – tests/example1.test.Pxml-vm ” -test failedChecking “cat tests/example3.test| ./bin/parser | ./translator | diff – tests/example3.test.Pxml-vm ” -test failedIf you want to add more tests of your own, place the test input file in the tests directory with a name ending in .test. Then run the following command to generate the expected test output:% make test-addStartup FilesThe startup files in the attached zip file should work on most 64-bit Linux systems and on a Mac. Please see the Startup Files for Workshops and Assignments (https://myuni.adelaide.edu.au/courses/44936/pages/startup-files-for-workshops-and-assignments) page for more information.workshop-codegen.zip (https://myuni.adelaide.edu.au/courses/44936/files/5215187/download?wrap=1)push constant 0returnhttps://myuni.adelaide.edu.au/courses/44936/pages/workshop-11-code-generation?module_item_id=1374198 4/4
Reviews
There are no reviews yet.