John F. Curry Jcurry@ccs.neu.edu 021528278 COM3360 Class Project 12/497 PROJECT DECSRIPTION: For my COM3360 course project I selected a transfer of technology project regarding the development of an interpreter for the language "QUIRK 13" used in the COM3355 and COM3356 compiler courses taught at Northeastern University by Professor Clinger. The project team consisted only of myself. In COM355 (Compiler Design) a simple compiler was developed for this language for use on a MIPS platform. The class project in COM3355 was focused on the code generation phase of the compiler. The scanner and parser were supplied by the professor. A small library of system functions was also supplied. In COM3356 (Optimizing Compilers) the simple compilers developed in COM3355 were further developed to include simple optimizations so that more efficient code was generated by the compiler. For this project I chose to develop an interpreter rather than a compiler to simplify the testing phases of the project. In the prior projects, the MIPS code generated by the compiler was run on the SPIM simulator to verify accuracy. Since the development of this project was executed on a PC (were the SPIM simulator was not available) an interpreter was easier to test than a compiler. DIRECTORY All the Demeter - java source code for this project can be found at: /proj/demsys/com3360/f97/jcurry/project A series of directories is located there. The directories are phase 1 - phase 11, which represent the work for each of 11 phases of development in the growth plan, and 1 additional test directory that contains test input files. The files located in the final phase (phase 11) are: quirk.cd - File containing the grammars for the Quirk 13 language and environments used in the interpreter. main.beh - File containing main program. Main program creates initial empty environment, parses in program and evaluates program. program.beh - File containing simple procedure to evaluate programs. block.beh - File containing traversal and visitor to traverse blocks to expressions. expr.beh - File containing traversal and visitor to traverse most expressions. (Note, simple expressions (mathexpr) are in serrate file. mathexpr.beh - File containing traversal and visitor to traverse mathexpr to constants and blocks. env.beh - File containing multiple traversals and visitors to manage environments used in compiler. decllist.beh - File containing traversal and visitor to evaluate declarations in blocks. compiler.bat - Batch file used to compiler interpreter. run.bat - Batch file used to run interpreter with 49 input test files. test - A test directory containing the 49 input test files. CREDITS The original Quirk13 language and grammar were developed (as far as I know) by Professor Clinger for use in the COM3355 and COM3356 courses. My knowledge of this grammar is based upon Professor Clinger's class notes and handouts. Since the scanner and parser used in Professor Clinger's courses were supplied to me, I do not know if the grammar represented in the notes is a formal representation of what was used in his parser. The language used in my project closely resembles Quirk13, but is not an exact replica. I have made modifications where convientent to allow sentences of the grammar to be parsed by the parser generated by demeter - java. Most modifications were to simplify the original grammar to a LL (1) representation. Additionally, the current state of my interpreter does not handle the entire Quirk13 language. Unfortunately, more time is needed to continue development to support the entire Quirck13 language. GROWTH PLANS The project was developed in eleven iterative phases were each subsequent phase build upon prior phases. All source code was developed by myself in Demeter - java. No source code modifications to Demeter - java generated java code were made. Each phase of development followed the same pattern as follows: * Design LL(1) grammar and represent in .cd file. * Compile project to verify the grammar representation is correct. Do not write additional visitor code at this time. * Develop required test input files for functionality being added in this phase. * Execute interpreter against all test-input files (those from prior phases as well as those developed in this phase) to verify grammar did not regress and that grammar supports new language constructs. * Only after the .cd file compiles, and all test-input files are parsed correctly, add code to visitors to add new functionality. * Recompile and run against all test input files to verify correct functionality. The features implemented in each of the eleven phases of development were: 1. Support for blocks (w/o declarations), multiple expressions within block, and integer constants. 2. Support for integer addition and subtraction. 3. Support for integer multiplication and division, support for floating point functionality. 4. Support for promotion of integers to floats when needed, support for "+" and "-" unary operations. 5. Support for relational operations. 6. Support for read and write expressions (for boolean, float, integer, string). 7. Support for environments. 8. Support for declarations with blocks, support for "not" unary operation. 9. Support for if/then/else expression, parenthesized expressions, blocks as factors. 10. Support for assignments and while loops. 11. Support for procedure declarations and calls. FURTHER DEVELOPMENT Development of this project could continue in several areas: 1. Complete full Quirk13 grammar. Most notably the support for arrays, templates and additional representations of functions. 2. Re-implement Id class using characters in place of strings. Since strings currently represent identifiers, the parser requires that all identifiers be surrounded by double quotes. Although functional, this representation requires clumsy syntax while writing input files. 3. Implement a type-checker. Currently, there is no type checking functionality within the interpreter. One possible solution would be to develop a set of type checking visitor classes that could traverse the program in the same traversal pass as the evaluation visitors. 4. Increase functionality of interpreter to distinguish between L-context and R-context of references. Currently an additional piece of syntax "&" is required to obtain the value of a variable by dereferencing it's identifier. 5. Correct defect in read expressions. Currently the read expressions are unreliable when the programmed is parsed from an input file. If program is typed in at the window console the read expressions seem to work just fine. The read expressions currently read using the BufferedInputReader class. TEST INPUTS Approximately 49 small programs were written to test the functionality of the interpreter during development. These test input files are rather trivial testing the low level functionaltiy of the various quirk13 language constructs. The complete set of test input files is included in the test directory of this project. One example of an input file is as follows: { integer "x" = 40; integer "y" = 9; integer "subtract"(integer "a", integer "b") { &"a" - &"b"; } integer "add"(integer "a", integer "b") { &"a" + &"b"; } write integer &"subtract"(&"x";, &"y";); write integer &"add"(&"x";, &"y";); } The output supplied by running the interpreter on this input is as follows: integer > 31 integer > 49 49 ADDITIONAL INFORMATION During the development of the interpreter, I chose the break the functionality of the system into logical partitions. Each partition contained it's own traversal and visitor code. Although, multiple traversals exist, the program was only traversed once. For example, while evaluating a block, the visitor evaluating the block would call a separate visitor (with it's own traversal) to evaluate the list of declarations. The visitor evaluating the declarations would intern call the visitor responsible for expressions as needed. This recursive traversal would continue until the entire program had been traversed. The decision to break the system into multiple traversals and visitors was based on style preference. The system could have been implemented in one larger traversal and visitor. QUESTIONS Did you change the generated Java code? No, I did not change any generated Java code. If you had the privilege to have one of my graduate students as host or if you had interactions with the teaching assistant, an evaluation of their performance would be welcome. I did not have any interaction with other students or teaching assistant on this project.