For this part of the Ruby Interpreter Collec>on of Assignments we will be modifying our exis>ng Parser so that instead of prin>ng 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 a>[email protected] the extra credit (see Extra Credit [email protected] 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 deriva>ons. 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 ar>cle here: hHps://ruslanspivak.com/lsbasi-part1/ , they illustrate that in one of the series ar>cles. Here is the specific ar>cle in the series that introduces ASTs: 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.

Part 1

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:

• add a method in rb that allows you to swap the first child of a node
• instead of calling addChild everywhere in rb, there are at least 2 instances where you will need to call your new custom func>on instead (maybe called addAsFirstChild).

Part 2

This poten>al 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 wont 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 modifica>on of the first one. You could aHempt to create this second one so that instead of prin>ng 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 its compu>ng 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 cant 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 dont 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 wri>ng 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 par>al 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 s>ll 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 s>ll crash because of the the inner list ( 4 ).

( 1 2 ( 3 ( 4 ) ) )

In addi>on to swapping the first child of some nodes (part 1) you will also occasionally need to reverse an en>re 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.

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

( ( ( 1 2 ) 3 ) 4 ) ! Ill go over this in class

Screenshots No extra credit

input1.>ny

input2.>ny

input3.>ny

input4.>ny (this one has syntax errors)

input5.>ny (this one has syntax errors)

Extra credit MUST score 100 to get the +5 points, otherwise you simply get 20 pts for each test passed. input1.>ny (20 pts)

input2.>ny

input3.>ny

input4.>ny (this one has syntax errors)

input5.>ny (this one has syntax errors)

Extra credit (20 pts) MUST score 100 AND get 5 pts extra credit to qualify for these points. MUST pass BOTH test cases below to earn the [email protected] 20 points. input6.>ny

input7.>ny