Study on Compilers

Reverse polish machine

• The entire code of reverse polish machine is present in the reverse-polish folder
• Support for divison and bracketing was added in the reverse polish compiler
• To test the working reverse polish machine use make test (inside the reverse polish folder)
• The compiler is able to perform basic arithmetic operations
• The tests can be found in test.expr
• The output after running make test is visible in the command line

Tiger Compiler

• The entire code for the tiger compiler can be found in the tiger folder in the root of the repository. Thus all the files and directories talked about below are contained in the tiger folder itself unless specifically specified
• The tiger compiler is made for compiling the tiger language
• The syntax for the tiger language can be viewed through the tests found in tests/test.expr file.
• The tiger language supports the following features -
  • Variable assignments
  • Variable manipulation using aithmetic operations including addition, multiplication and subtraction
  • Parantheses support
  • Variables can be assigned and updated using parenthesized expressions involving other vairables and constants
  • Supports for loops. Features in for loop -
    • Local declaration of statements
    • When a variable declared outside the for loop is reassigned a value inside the for loop then after the for loop ends, the older value is stored back in the variable again
    • The variable used as an iterator for the loop is also treated as a local variable
  • Printing of expressions is supported using print <expr> command where the expression is first evaluated and then printed. Each print statement is executed in a new line (like python)!
• Running the compiler -
  • To run the compiler, use make test inside the tiger direcotry. This will generate the mips code corresponding to the test code in tests/test.expr in out.mips file
  • To check to correctness of the mips code generated, use make spim, which will generate the output corresponding to the mips code in out.mips in the terminal
  • You can also use make spim for directly executing both of the above steps together
  • Use make clean to clear the executables
• Extras -
  • The compiler features printing of basic blocks in order to know the control flow of the compiler and can be helpful in debugging. To print the basic blocks of MIPS assembly code corresponding to the the test case file, use make basics. The generated basic blocks are printed in both the terminal and is stored in the basics.out file
• File Structure -
  Parsing - The code for parsing the files can be found in the lexer folder inside the tiger directory. The lexer is responsible for making the AST corresponding to input file. The AST structure can be found in lib/ast.sml
  IR code generation - This is done using the src/translate.sml file. The supporting files include IR/ir.sml and IR/temp.sml which contain the how the IR is represented
  MIPS assemble program generation - This is a step by step process which first involves register allocation (done using register-alloc/register-allocation.sml) and then printing the MIPS assembly code (done using src/machine.sml). The supporting file includes mips/mips.sml which is contains the MIPS structure
  Others - The code execution of the entire compiler is done from src/ec.sml. The code for basic blocks building can be found in lib/basic-blocks.sml. The ML Basis, which specifies specific file order can be found in ec.mlb and bb.mlb files

Tiger Compiler with Tree IR

• The entire code for the tiger compiler built based on Tree IR and canonization can be found in tiger_tree folder in the root of the repository.Thus all the files and directories talked about below are contained in the tiger folder itself unless specifically specified
• All the features mentioned above can be found in the tiger tree compiler as well, except the for loop support in tiger language
• Run make test and / or make spim inside the tiger_tree folder to test the code
• make basics can be run similarly inside the tiger_tree folder to print the basic blocks for the corresponding test code
• The tree based IR can be found in IR/tree_ir.sml. The translation to tree IR and canonization can be found in src/translate_ir.sml and src/canonization.sml respectively
• Other file structures and specifics remain similar to that of the tiger compiler without tree IR as specified before

Other independent assignments

• The target/mips.sml file was created in order to capture the MIPS syntax in sml. This file is used in both the tiger and tiger_tree compiler and can be found inside the mips folder of their directories as well
• The graph.sml contains the representation of a generic directed graph in sml. These can be used in future with the compiler to represent its control flow graph. Supports several functions including but not limited to adding new nodes and edges to the graph separately, successor and predecessor of a node, listing all the nodes in graph etc.

TODOs

• Add more functionalities to the tiger language like handling functions
• Make canonization for tiger_tree more generic