Project 3: PDef AST

For this project, you will modify the starter code from GitHub (the PDef Parser) to construct an abstract syntax tree (AST). This will require creating classes that correspond to non-terminals in the grammar. It is these classes that will be used by the parser to construct the AST.

You will also implement a traverse() method that does a depth first (postorder) traversal of the AST to output its structure, and an overloaded toString() method to do pretty printing of the AST.

This project makes significant use of inheritence, polymorphism, and method overloading.

As done in previous projects, you’ll first develop a solution for PDef-lite, then expand to PDef. It is expected that you have read chapters 7 and 14 of Programming Languages Through Translation. This project corresponds to the guided tutorial as described in those sections.

Recall that the grammar rules for PDef-Lite and PDef are as follows.

PDef-lite

Edit main() in PDef.java so that the first line output is your name.

Compile as follows (see Piazza for compiling shortcuts for Mac/Windows, if interested):

javac PDef.java debug/*.java parser/*.java tokenizer/*.java exceptions/*.java syntaxTree/*.java

Complete activity 44 on p. 247
Complete activity 45 on p. 247-248. Pay attention to Figure 14.5
Complete activity 46 on p. 249-250. You will see many methods in Parser.java that will be used for the PDef implementation. For now, just work on the methods tha correspond to non-terminals in PDef-lite. Apply your solution to the three test files in the Test-PDefL folder. Here is what my solution produces:
- test0 output:
```
DeclarationST
DeclarationST
AssignmentST
BlockST
BlockST
```
- test1 output:
```
DeclarationST
BlockST
BlockST
BlockST
```
- test2 output:
```
DeclarationST
DeclarationST
AssignmentST
BlockST
```
Complete activity 47. When copying code from the bottom of p. 251, note that the variable names you use in your toString() method will need to match the state variables from your AssignmentST class. If your AssignmentST state variable names are source and target, then no problem. When finished, this completes the implementation of the AST construction for PDef-lite. Note that you will need to print the AST from PDef.java to see the output. Here is what my solution produces:
- test0 output:
```
List: 
  Declaration: [type int, name a ]
  List: 
      Declaration: [type int, name b ]
      Assignment: [target a, source b ]
```
- test1 output:
```
List: 
  List: 
      List: 
          Declaration: [type int, name y ]
```
- test2 output:
```
List: 
  Declaration: [type int, name a ]
  Declaration: [type float, name b ]
  Assignment: [target a, source b ]
```

PDef

Complete activity 48, part 1. The UML diagram in Figure 14.7 doesn’t show it, but the new classes will also need the traverseST() and toString(String) methods. You may find it very useful at this stage to make a list of the PDef non-terminals and the corresponding syntax tree class names.
Complete activity 48, part 2. Note that in Parser.java, the grammar rule is given with each parse method. Some of those grammar rules are for PDef-lite (look at parseAssignment(), for example). Make sure you update the grammar rule in the comment before trying to update the parse method. Also, some of these changes will require an analogous change in the corresponding syntax tree you created.

Section 14.6 describes “flatenning” the expression grammar. The grammar shown on p. 254 is incorrect. Below is the correct flattened PDef grammar. This is the grammar used in the methods provided in Parser.java.
```
Exp 	 --> Term RestExp
RestExp	 --> (addT | subT) Term RestExp
Term	 --> Factor RestTerm
RestTerm --> (mulT | divT | modT) Factor RestTerm
Factor 	 --> intT | floatT | identT | lpT Exp rpT
```
Remember also that the revised parser methods are constructing the syntax tree, so where the parse methods used to all be void methods, now each parse method for a non-terminal must return an instance of the class for that non-terminal.

Apply your solution to the two test files in the Test-PDef folder. Here is what my solution produces:
- test0 output:
```
DeclarationST
DeclarationST
AssignmentST
AssignmentST
BlockST
```
- test1 output:
```
DeclarationST
DeclarationST
AssignmentST
DeclarationST
AssignmentST
BlockST
AssignmentST
BlockST
```

Complete activity 48, part 3. Pay particular attention to the mention of toString() versus toString(String) on p. 257. Apply your solution to the two test files in the Test-PDef folder. Here is what my solution produces:

test0 output:

List: 
  Declaration: [type int, name a ]
  Declaration: [type int, name b ]
  Assignment: [target a, source ( a + ( b * 2 ) ) ]
  Assignment: [target a, source ( ( 5 * 2 ) - ( a / b ) ) ]

test1 output:

List: 
  Declaration: [type int, name x ]
  Declaration: [type float, name y ]
  Assignment: [target y, source ( x + 3 ) ]
  List: 
      Declaration: [type int, name a ]
      Assignment: [target a, source ( x + y ) ]
  Assignment: [target y, source x ]

How to submit

Make sure your code compiles, runs as expected, and is committed and pushed to GitHub.