Comp 271 compiler project part 1

Goals

• Introduction to the virtual machine and the compiler
• using a HashSet
• designing and defining the scoped symbol table
  

Overview

• original version 1.0: smachine1.zip
• version 1.1: smachine1.1.zip

• reserved-word detection using a HashSet (see isIdent() for the wrong way to do this)
• IdentInfo class for all relevant identifier information (procedure/variable/constant, location (for procedures), location/global-v-local (for variables) and value (for constants). Note that constants do not have locations!
  
• use of IdentInfo in compileFactor, compileIdentStmt
• implementation of the actual SymbolTable class, implemented by any way you choose, so as to support newScope(), lookup(String idname), and allocate(String idname). You will also have to have a way of getting the total current table size, to use in the ALLOC machine code (cs.emit(Machine.ALLOC, symTable.stackFrameSize() ??). See the Week 13 notes for more information about scopes.
  

For this part 1, do not worry about functions.

The above is Version 1; I am likely to have a version 2 containing corrections. In that case I will attempt to make available both the fixed version, and also a set of patches in case you've already done a lot to version 1 and don't want to redo them.

As a first approximation, just get the single-scope version working, and then worry about nested scopes.

The stubs of the methods allocate(), lookup(), newScope(), and endScope() are at the end of Compiler.java. You may change these as you wish; actually, you will quite likely wish to make them all methods of some SymbolTable class. My idea is to use allocate() like insert(); that is, if the identifier is already defined in the current scope then that's an error. If it's defined in a previous scope, then the previous definition remains, but is "shadowed" until the end of the current scope. lookup() is for looking up after the declaration; it is now an error if an identifier doesn't have an appropriate existing definition. Both would return an IdentInfo object, which you would then update with appropriate mutators. (If you do this right, you are mutating the "original" object still in the symbol table, and so you don't need a separate update step, but an update step is ok too). After every declaration and every end-of-scope, you will need to emit an ALLOC instruction defining the current size; I have added a hypothetical function stackFrameSize() that is in reality likely to be a method of SymbolTable. Finally, newScope() is a directive to the Symbol Table to "create" a new scope level, and endScope() will delete that scope level.

Be sure that you include somewhere the appropriate end-of-scope emit of the ALLOC instruction. Also be sure you do not enable the cs.emit(Machine.ALLOC, ...) in compileDeclaration() until you make it generate the correct value! When you do, you can comment out the ALLOC in compileFunction() (or set isLHack = false).

Note that you have a fair amount of design here! One really simple implementation is to use a singly linked list, where newscopes put more entries on the front of the list, and endscope() restores the list head to a previously saved value, thus effectively discarding a collection of the most recent entries. Another implementation is to use a list of HashMaps. One elegant solution is to us a single HashMap, but to have the entry for an identifier correspond to a list of declarations of progressively more-recent scopes; to implement endScope() you would then need a list of all the identifiers that had been defined in the most recent scope, so you could "pop" one declaration-object from that identifier's list.

To submit your project, create a zipfile and email it to me at pld@cs.luc.edu. You may send me just part 1, for earlier grading, or wait until the final due date (the end of the last week of class).