COMP3220-Ruby Parser II (AST) Solved

For this part of the Ruby Interpreter Collecon of Assignments we will be modifying our exisng Parser so that instead of prinng parser output, it will build an AST (abstract syntax tree) that our interpreter can use to “run” programs wriHen in the Tiny Language.

Details
I have given you all the files necessary to complete the assignment. You will need to modify Parser.rb so that it builds the AST while it is parsing a file.  

I have included an AST.rb file that defines an AST node object that can be used to build this tree. It also has a method that can print the tree in list format (convenient since our interpreter will be wriHen in a list-based language!).  

You should NOT modify AST.rb unless you are aemp@ng the extra credit (see Extra Credit sec@on below). 

I have done some of the work for you in Parser, so that you can use that as an example of how you should proceed. At the end of this document are screenshots showing what correct output should look like given some input files that I will also provide to you for debugging.

Note: We are building an AST and NOT a parse tree. What is the difference anyway!? The difference is that a Parse Tree  

 parse tree would look much like the examples we went through in class when we compared parse trees to derivaons. They would INCLUDE every rule in our class as root nodes or sub nodes in the tree. However, an  AST (Abstract Syntax Tree) 

AST ONLY includes the actual lexemes that are needed to be interpreted. If you take a look at the compiler series arcle here: hHps://ruslanspivak.com/lsbasi-part1/ , they illustrate that in one of the series arcles. Here is the specific arcle in the series that introduces AST’s: hHps://ruslanspivak.com/lsbasi-part7/ .  

For our assignment, we will always start with a program node as the root of the whole tree. That is the only “not concrete” thing that should be part of our tree.  

Extra Credit (25 pts) – must score 100 to qualify for any extra credit points. Otherwise, you only get 20 pts per test 
case passed.
  
Part 1 (5 pts)
Because of the way our grammar is defined (and because we want to produce a tree in list format) our tree WILL be nested correctly BUT our operands will be in reverse order. Since it is something that is consistent, it is an easy problem to handle in our interpreter (we already know it will behave this way, so just read in the operands in reverse order).  

However, it is possible to produce the tree in list form with the operands in correct order. In order to do this, you will need to modify the AST.rb class. One way to do this is to:

1)     add a method in AST.rb that allows you to swap the first child of a node  

2)     instead of calling addChild everywhere in Parser.rb, there are at least 2 instances where you will need to call your new custom funcon instead (maybe called addAsFirstChild).

Part 2 (20 pts)
This potenal issue is a bit harder to fix (and describe) and requires that you (1) have a really good understanding of exactly how this AST tree works and (2) how our interpreter is going to process our tree (specifically that any math operator (except for equal) requires at least 2 operands). So, (- 3 4) is ok, but (- 4) is not. Scheme can actually handle this, but our interpreter won’t be able to. See examples below.   

To get a really good understanding of how our AST tree is being built, I would recommend studying the toStringList() method in AST.rb to understand how its going through the tree in order to print things. You could then create a second toStringList() in AST.rb that is a modificaon of the first one. You could aHempt to create this second one so that instead of prinng the Token AND the Lexeme, it ONLY prints the lexeme. This will actually end up giving you something you can copy and paste into scheme to verify if it’s compung the answer correctly.   

Example of the problem:  

1 – 2 – 3 – 4 is -8.  

You can type that into a calculator and get the correct result. However, you can’t type that into scheme (the way it is wriHen) and get a correct result. Since scheme is a list-based language, it expects that the first item in the list be the operator.  

If you don’t aHempt the first part of the extra credit (5 pts), this is what your parser will produce. You can get this string exactly, by simply removing the Token names (or by wring a second toStringList() method that will print lexemes only). In this example, we are not reversing first operand (we can handle this in Interpreter). You can paste the paral tree below into scheme and it will produce a result, however, our interpreter will not be able to process it because there is an operator with just a single operand in this list; the inner ( - 4 ).  

( - 2 ( - 3 ( - 4 ) ) 1 )   ! scheme will give you -6 as a result, which is sll incorrect, even though it runs

If you do aHempt the first part of the extra credit (5 pts), this is what your parser will produce. Note that we STILL have that inner list ( - 4 ) where the minus operator has only a single operand, the 4. Although you could type this expression into scheme and it would give you a correct result, our interpreter will sll crash because of the the inner list ( - 4 ).

( - 1 2 ( - 3 ( - 4 ) ) )

In addion to swapping the first child of some nodes (part 1) you will also occasionally need to “reverse” an enre subtree. You can think about this as if you were “flipping” a sub-tree over, where the boHom (the leaf/leaves) become the new root and the top (the root) becomes the new leaf/leaves. Doing this would produce a tree that scheme could use to correctly calculate a result AND our interpreter will ALSO be able to use the tree to produce the correct output.

Connuing the example above, this method would produce the following list that would be correct for our interpreter.

( - ( - ( - 1 2 ) 3 ) 4 ) ! I’ll go over this in class

Screenshots No