COMP442_6421-Abstract Syntax Tree Generation Solved

This assignment is about complementing the parser developed in assignment 2 with syntax-directed translation to generate an abstract syntax tree (AST) data structure that is going to be used in the later stages of the compiler as an intermediate representation. The parser must still include the features developed in assignment 2.  

 

The assignment handout includes two example source files. These files should be used as-is and not be altered in any way. Completeness of testing is a major grading topic. You are responsible for providing appropriate test cases that test for a wide variety of valid cases in addition to what is in the example source files provided.   
 

Implementation
•   Parser augmented with syntax-directed translation: implementation of syntax-directed translation in the existing parser for the purpose of generating an AST data structure. The result of the execution of the parser should be the creation of an AST data structure that corresponds to the parse tree as identified by the parsing process. The tree must be an AST, and not a parse tree. This tree will become the intermediate representation used by the two following assignments.  

•   AST output: The generated tree should be output to a file in a format that allows easy visualization of the structure of the tree. This can be a simple text representation of the tree structure or a graphiz dot representation (see examples in the assignment handout). This file must allow the marker to quickly verify that the generated AST is in fact correct with regards to the parsed program. When parsing a file named, for example, originalfilename, the parser should write into a file named originalfilename.outast a text representation of the abstract syntax tree representing the original program.  

•   Test cases : Provide a set of source files that enable to test the AST generation for all syntactical structures involved in the language.  

•   Driver: Include a driver that parses all your test files. For each test file, the corresponding outast files should be generated (in addition to all the files that were generated by the previous assignments).  

        

Analysis:                                                                                    
 
 
Attribute grammar that clearly indicates where each of the semantic actions are inserted in the grammar’s right hand sides, as well as a list of all the semantic actions and a brief description of their respective effect. See slide set 8.5 for an example – document Section 1.
ind 2.1
5 pts 
Design/implementation:                   
 
 
Description/rationale of the overall structure of the solution and the roles of the individual components used in the applied solution – document Section 2.
ind 4.3
5 pts
Correct implementation of syntax-directed translation implemented as part of a top-down predictive parser following the grammar given in this handout, which is generating and AST (not a parse tree) data structure that correctly represents any valid program given in input.  
ind 4.4
20 pts 
Output of the AST in an outast file.                 
ind 4.4
5 pts 
Completeness of test cases.                                                               
ind 4.4
10 pts
Use of tools:
 
 
Description of tools/libraries/techniques used in the analysis/implementation. Description of other tools that might have been used. Justification of why the chosen tools were selected – document Section 3.   
ind 5.2
2 pts
Successful/correct use of tools/libraries/techniques used in the analysis/implementation.
ind 5.1
3 pts
Total