This page is not finished. Please disregard for now.
Unlike previous projects, Project 7 is broken into two seperate projects: Early and Full. The Early project tests your compiler on non-recursive (simple) functions. The Early project is also worth less points, and won't have a late period.
For this project you will further upgrade LOLcode by adding the capacity for user-defined functions. You will need to make modifications to all five stages of your compiler (lexical analysis, syntax analysis, semantic analysis, conversion to LMAOcode, and final output to ROFLcode.)
You must implement two main additions to the language: function definitions and function calls.
See the LOLcode specification for details regarding LOLcode function syntax.
A function definition in LOLcode begins with the keywords HOW IZ I, followed by the name of the function, zero or more argument declarations, a statement that is the function body, ending with IF U SAY SO and the return type of the function. As with flow control statements, the statement following a function definition can (and typically will) be a block.
Anywhere inside a function body can be a FOUND YR (return) command, followed by an expression. When a return is reached, the function should evaluate the expression and return its value to the location from which the function was called. Note that every function must end with a return command (you do not need to implement void functions). (Every test case will follow this rule.) A FOUND YR command is not legal outside of a function. Here is an example function definition:
HOW IZ I product_by_addition YR arg1 ITZ A NUMBR AN YR arg2 ITZ A NUMBR MKAY O RLY? SAEM arg1 AN 1 YA RLY FOUND YR arg2 NO WAI FOUND YR SUM OF arg2 AN I IZ product_by_addition YR DIFF OF arg1 AN 1 AN YR arg2 MKAY OIC IF U SAY SO ITZ A NUMBR
Function definitions can occur only in the global scope, and an exception should be raised if one is defined in a deeper scope. Likewise, you should throw a "function redefinition" exception if a function name is defined twice.
Function calls start with I IZ are are followed by a function name and arguments. In addition to incorporating your functions into your symbol table, you also need to make sure that all aspects of the function calls are semantically correct (i.e., that the return value of the function is legal in the current context, and that the arguments being passed in match the argument types in the function definition).
For example, if you were writing a program where you were trying to calculate the high score between two players, you might have something like:
I HAS A high_score ITZ A NUMBR AN ITZ I IZ max YR score1 AN YR score2 MKAY VISIBLE "And the high score is: " AN high_score
Your functions are required to be able to run recursively, so plan ahead carefully with your memory management. Prior to a recursive call, certain memory wintin the function must be backed-up to the stack to ensure that the callee doesn't overwrite needed values.
We recommend that you take the following steps to implement functions in your compiler:
Your parser should be able to recognize function definitions, as described above, as well as return statements. Note that the contents of a function should be in a new scope, including any function arguments.
Additionally you should allow function calls within expressions. The AST node that represents a function call should contain a pointer to that function's entry in the symbol table, and it should have one sub-tree for each argument.
Setup conversion to LMAOcode. Start each function with a start label and then write out its body, ending with code that will jump back to where the call was made with the appropriate return value. Once you have this piece working, you can test basic functionality. Next, you need to make sure that any time a function is called, you backup all non-global variables onto a stack, restoring them after you return from this function. This added ability will allow you to run recursive functions in Good Lang.
Two new commands in the intermediate code will facilitate this implementation: "push" and "pop". Push will save any variable on an internal control stack. For example "push s5" will store the value from s5 onto the stack. Likewise pop will remove a scalar value from the stack. So, "pop s27" will grab the top value on the stack and put it in the s27 variable.
Handle recursive function calls
The real trick here is to know when to backup variables on to the stack, and which variables to pay attention to. When to backup variables: you only need to back up variables if you are in a function definition and you are calling a function. If a new iteration of THIS function gets called again before the current one finishes, the values of all the currently live variables might change. Which variables to backup: all active variables in your symbol table above scope 0. You know that the define must happen in scope 0, so all active variables above scope 0 must have been created inside this function. Back up these variables (including temporaries!) to the stack immediately before calling a new function and restore them immediately after.
As with previous projects, we are only testing if an exceptions was raised, rather than the exact exception class. But, more informative error messages are more useful in debugging.
See Project 6.
When you submit your program, you must include in a folder called "Project7":