CSCI 439: Lab 6 and bonus lab (Spring 2025)

Correction to parsing.cpp in the provided repo:

The parsePlist function neglects to add the identifier content as it inserts arguments.
You'll see the following line of code: 
// TBD: add to symbol table and set symindx for the parameter's identifier
Inserting the following line will set the identifier content 
// TBD: add to symbol table and set symindx for the parameter's identifier
subtree->childs[subtree->numChilds+1]->content = paramname;

The provided code parses and produces the abstract syntax tree, symbol table, and function table correctly for valid code, and also checks for undeclared/redeclared variables/procedures in valid scopes, but it does NOT include any type checking. I will not require/expect type checking or conversions as part of lab6.
The AST shouldn't be too bad to traverse, but if you're reading it the code that parses/builds the IR is U.G.L.Y. ... apologies!
I know folks are pretty swamped right now, and compiling to Marie (see below) could prove time consuming, so as an alternative for lab6 credit (not bonus credit) you can choose to have your translation program traverse the IR and produce the C++ equivalent. This should prove similar to earlier labs but actually working from the internal representation this time.

For lab 6 we'll be back to working with Vurbossity, this time aiming to 'compile' Vurbossity code into Marie assembly language (a very primitive assembly language, one you may have encountered in 162, with a web interpretter available). Marie does not have built-in support for reals, text operations, or even multiplication and division, so writing a translation from Vurbossity will require you to come up with Marie code templates to achieve those effects.

The starting repo for lab 6 includes a parser that reads Vurbossity source code and generates an intermediate representation consisting of two symbol tables (one for variables, one for procedures) and an abstract syntax tree, then calls a translate function to translate the intermediate representation into the target language.

At the moment, the 'translate' function just prints the abstract syntax tree content, it doesn't do any actual translation. Your task will be to expand/modify the program (in any way you see fit as long as the translation still works from the intermediate representation) to read the intermediate representation of valid Vurbossity code and produce corresponding Marie code from that.

To create translations for the entirety of Vurbossity into Marie would be a considerable undertaking, so each Vurbossity language feature has been assigned a marks value: up to the first 24 marks worth of features you successfully translate will count as your lab 6 mark (i.e. up to 24/24) and any additional features will count towards your bonus lab mark (again up to 24/24). Any optimizations you are able to apply to working features will also count towards the totals.
(Just in case anyone gets crazy enough on this to get more than 48 marks: it will be treated as 24/24 for lab6, 24/24 for the bonus lab, and the excess will be treated as a secondary bonus lab /24 that is directly added to your overall lab score.)

IMPORTANT DOCUMENTATION AND TEST CASE NOTE

In the repo README you need to explicitly list which of the language features and optimizations you have completed and wish to be marked on and which TESTCASES case demonstrates the correct functionality.

In the TESTCASES subdirectory you must include valid Vurbossity programs that illustrate your lab6 working correctly on those features. (Again, be sure your README clearly describes which test cases illustrate which feature translation or which form of optimization.)

Language feature marks/values

The value of each translated vurbossity feature is as listed below, with part marks available if a feature is partially handled as long as the README clearly indicates what is/is not handled so far. Some of these features are heavily weighted because of the complexity of the language feature itself, while some others are heavily weighted because of the lack of direct support in Marie (i.e. first you'll have to work out a means of accomplishing the desired functionality within the limitations of Marie).

    translation to marie (up to 60 marks possible)
  • procedure definitions and calls: 8
  • real number handling (literals/expressions): 8
  • text handling (literals/expressions): 8
  • full implementation of scoping rules: 8
  • math expressions: 6 (including building div/mult/rem)
  • if loops: 4
  • conditional expressions: 4 (including and/or/not)
  • assignment statements: 3
  • variable declarations: 3 (global/local)
  • read/write statements: 2
  • implicit type conversions: 2 (int to real where needed)
  • literals: 2
  • basic main routine of statements: 2

    optimizations (will give up to 24 marks, where applied appropriately to working features)
  • constant folding: 4 (including valid expression re-arranging)
  • inlining procedures: 4
  • replacing repeated code segments with procedure calls or loops: 4
  • unrolling loops: 4
  • eliminating redundant computations: 4
  • eliminating unused variables: 2
  • anything else 2+?
    (... describe what you've done and we can work out an appropriate value ...)

The IR structure

The IR has a symbol table and function table (essentially the same as the lab2 sample solution) plus an abstract syntax tree.

The node types and tree structure for the AST are as follows:

The initial translate output

The translate function provided in the initial repo just does a simple traversal of the IR, printing the node types/children as it goes, then prints a summary of the symbol and function tables. A sample run on a short vurbossity program is shown below. 

COM a shorter example but with a few features

gdef foo text

pdef f left real i right
begin
   write "you passed "
   write i
   write "type something"
   read foo
   write "you wrote"
   write foo
end

main
begin
   vdef x real
   set x left add 10 2.3 right
   call f left x right
end



 Start of program, 2 subtrees:
   Start of globals, 2 subtrees:
      Start of gvar_def, 2 subtrees:
         Leaf node: is_str
         Leaf node: identifier (symbol table index 0) (content foo)
      End of gvar_def
      Start of function, 3 subtrees:
         Leaf node: identifier (function table index 0) (content f)
         Start of arglist, 2 subtrees:
            Leaf node: is_real
            Leaf node: identifier (content i)
         End of arglist
         Start of block, 6 subtrees:
            Start of write_stmt, 1 subtrees:
               Leaf node: str_lit (content "you passed ")
            End of write_stmt
            Start of write_stmt, 1 subtrees:
               Leaf node: identifier (content i)
            End of write_stmt
            Start of write_stmt, 1 subtrees:
               Leaf node: str_lit (content "type something")
            End of write_stmt
            Start of read_stmt, 1 subtrees:
               Leaf node: identifier (content foo)
            End of read_stmt
            Start of write_stmt, 1 subtrees:
               Leaf node: str_lit (content "you wrote")
            End of write_stmt
            Start of write_stmt, 1 subtrees:
               Leaf node: identifier (content foo)
            End of write_stmt
         End of block
      End of function
   End of globals
   Start of main_fun, 1 subtrees:
      Start of block, 3 subtrees:
         Start of lvar_def, 2 subtrees:
            Leaf node: is_real
            Leaf node: identifier (symbol table index 1) (content x)
         End of lvar_def
         Start of set_stmt, 2 subtrees:
            Leaf node: identifier (content x)
            Start of add_op, 2 subtrees:
               Leaf node: int_lit (content 10)
               Leaf node: real_lit (content 2.3)
            End of add_op
         End of set_stmt
         Start of funcall, 2 subtrees:
            Leaf node: identifier (function table index 0) (content f)
            Leaf node: identifier (content x)
         End of funcall
      End of block
   End of main_fun
 End of program

===Symbol table===
Table row 0, scope 0, name foo, type 3
Table row 1, scope 2, name x, type 2
-----

===Function table===
Table row 0, name f, arity 1, args:  i(2)
-----


*The integer values for types are a bit different than in the lex/yacc labs, and come from an enumerated
type in the ast.h file (0 for invalid, 1 for int, 2 for real, 3 for text, 4 for bool).

Sample output

Below is one (very) simple Vurbossity program and potential equivalent translations into C++ and Vurbossity. (Your actual translations don't need to look exactly like this, it's just showing one possible approach.)

VurbossityC++Marie
 main
 begin
    vdef x integer
    vdef y integer
    read x
    read y
    set x left add x y right  
    write x
 end

 #include <iostream>
 using namespace std;

 int main()
 {
    int x;
    int y;
    cin >> x;
    cin >> y;
    x = (x + y);
    cout << x << endl;  
    return 0;
 }

main,    input
         store     x  
         input
         store     y
         load      x
         add       y
         store     x
         output
         halt

 x,      dec       0
 y,      dec       0

Marie

There are quite a number of Marie resources available, here are a handful: