Sonoma State University
Department of Computer Science
CS-460: Programming Languages
Programming Assignment 5: Abstract Syntax Tree

Objective:

  • Write a program in C or C++ that creates an Abstract Syntax Tree (AST) based on the Concrete Syntax Tree (CST) you created in programming assignment 3. An Abstract Syntax Tree is not a clone of a Concrete Syntax Tree. Your program should utilize an LCRS binary tree (Left-Child, Right-Sibling) to store your AST. Your program should also display the resulting AST in breadth-first order. You may output your AST as text to the screen as long as I can identify adjacent children and adjacent siblings in the tree. I have provided fancy graphics-based LCRS binary trees to (hopefully) make it easy for you to visually see the expected results for the input test files I have provided below. You are not required to generate PDF output or use fancy graphics output of any kind for this assignment.

Please note:

Input test files to determine the effectiveness of your programming assignment five solution:

The output from your programming assignment five solution should look like the following files:

Uploading your programming project files

  • Please upload your source code and a Makefile as a zip or gzipped-tar file.

Programming Assignment 5 Rubric

CRITERIA RATINGS POINTS
Compilation:
Will the program compile with GNU compiler?		 Proficient
2 points
Makefile provided. Student's assignment five program is written in C or C++ and compiles with gcc (GNU C compiler) or g++ (GNU C++ compiler) without syntax errors on GNU/Linux. No external libraries (besides standard built-in C/C++ libraries) are required to build the project.		 Satisfactory
1 point
Student's assignment five program is written in C or C++ and compiles on GNU/Linux with gcc or g++. A Makefile is not included. Extra external library dependencies may be required to compile and run student's assignment three program besides standard built-in C/C++ libraries.		 Below Expectation
0 points
Makefile not included. Student's assignment five program fails to compile with gcc or g++ on GNU/Linux.		 2 points
Parsing Implementation:
How was the parsing technique implemented?		 Proficient
3 points
Student's assignment five program uses procedurally-driven deterministic finite-state automaton (DFA) to parse Boolean and numerical expressions.		 Below Expectation
0 points
Student's assignment five program implements a table-driven DFA to parse Boolean and numerical expressions; OR student's assignment five program implements a combination of procedurally-driven and table-driven DFA when parsing Boolean and numerical expressions; OR student's assignment five program fails to use a DFA (table or procedural) to parse Boolean and numerical expressions.		 3 points
Abstract Syntax Tree Implementation:
How was the the Abstract Syntax Tree implemented?		 Proficient
3 points
Student's assignment five program utilizes a Left-Child, Right-Sibling binary tree representation to store an Abstract Syntax Tree (AST).		 Below Expectation
0 points
Student's assignment five program fails to properly create a Abstract Syntax Tree (AST) using a binary tree. There may be structural flaws with the AST.		 3 points
Boolean Expressions Representation:
How are Boolean expressions represented in the Abstract Syntax Tree?		 Proficient
6 points
Student's assignment five program implements the Shunting Yard algorithm to convert Boolean expressions from infix notation to postfix notation. Boolean expressions are listed in the Abstract Syntax Tree in postfix notation. The Boolean expressions in postfix notation follow operator precedence. Boolean expressions in postfix notation may have parenthesis removed (if applicable) if such parenthesis are no longer necessary for operator precedence (compared to infix notation)		 Below Expectation
0 points
Student's assignment five program stores Boolean expressions in infix notation in the Abstract Syntax Tree; OR Boolean expressions are nonexistent.		 6 points
Numerical Expressions Representation:
How are numerical expressions represented in the Abstract Syntax Tree?		 Proficient
6 points
Student's assignment five program implements the Shunting Yard algorithm to convert numerical expressions from infix notation to postfix notation. Numerical expressions are listed in the Abstract Syntax Tree in postfix notation. The numerical expressions in postfix notation follow operator precedence. Postfix notation may have parenthesis removed (if applicable) if such parenthesis are no longer necessary for operator precedence (compared to infix notation)		 Below Expectation
0 points
Student's assignment five program stores numerical expressions in infix notation in the Abstract Syntax Tree; OR numerical expressions are nonexistent.		 6 points
Test program 1:
The first benchmark test.		 Proficient
2 points
Student's assignment five program removes all comments from test program one without impacting the line numbering of statements. An Abstract Syntax Tree is created that matches the expected output in the assignment guidelines. All tokens are accounted for and the tree is displayed in breadth-first order.		 Satisfactory
1 point
Students assignment five program generates an Abstract Syntax Tree for test program one. There are fewer than five errors in the resulting tree when compared to the expected output as noted in the assignment guidelines.		 Below Expectation
0 points
Students assignment five program may not generate an Abstract Syntax Tree (AST) for test program one or if an AST is generated it contains six or more errors when compared to the expected output from the assignment guidelines.		 2 points
Test program 2:
The second benchmark test.		 Proficient
2 points
Student's assignment five program removes all comments from test program two without impacting the line numbering of statements. An Abstract Syntax Tree is created that matches the expected output in the assignment guidelines. All tokens are accounted for and the tree is displayed in breadth-first order.		 Satisfactory
1 point
Students assignment five program generates an Abstract Syntax Tree for test program two. There are fewer than five errors in the resulting tree when compared to the expected output as noted in the assignment guidelines.		 Below Expectation
0 points
Students assignment five program may not generate an Abstract Syntax Tree (AST) for test program two or if an AST is generated it contains six or more errors when compared to the expected output from the assignment guidelines.		 2 points
Test program 3:
The third benchmark test.		 Proficient
2 points
Student's assignment five program removes all comments from test program three without impacting the line numbering of statements. An Abstract Syntax Tree is created that matches the expected output in the assignment guidelines. All tokens are accounted for and the tree is displayed in breadth-first order.		 Satisfactory
1 point
Students assignment five program generates an Abstract Syntax Tree for test program three. There are fewer than five errors in the resulting tree when compared to the expected output as noted in the assignment guidelines.		 Below Expectation
0 points
Students assignment five program may not generate an Abstract Syntax Tree (AST) for test program three or if an AST is generated it contains six or more errors when compared to the expected output from the assignment guidelines.		 2 points
Test program 4:
The fourth benchmark test.		 Proficient
2 points
Student's assignment five program removes all comments from test program four without impacting the line numbering of statements. An Abstract Syntax Tree is created that matches the expected output in the assignment guidelines. All tokens are accounted for and the tree is displayed in breadth-first order.		 Satisfactory
1 point
Students assignment five program generates an Abstract Syntax Tree for test program four. There are fewer than five errors in the resulting tree when compared to the expected output as noted in the assignment guidelines.		 Below Expectation
0 points
Students assignment five program may not generate an Abstract Syntax Tree (AST) for test program four or if an AST is generated it contains six or more errors when compared to the expected output from the assignment guidelines.		 2 points
Test program 5:
The fifth benchmark test.		 Proficient
2 points
Student's assignment five program removes all comments from test program five without impacting the line numbering of statements. An Abstract Syntax Tree is created that matches the expected output in the assignment guidelines. All tokens are accounted for and the tree is displayed in breadth-first order.		 Satisfactory
1 point
Students assignment five program generates an Abstract Syntax Tree for test program five. There are fewer than five errors in the resulting tree when compared to the expected output as noted in the assignment guidelines.		 Below Expectation
0 points
Students assignment five program may not generate an Abstract Syntax Tree (AST) for test program five or if an AST is generated it contains six or more errors when compared to the expected output from the assignment guidelines.		 2 points
Total points: 30