Sonoma State University
Department of Computer Science
CS-460: Programming Languages
Programming Assignment 3: Recursive Descent Parser

Objective:

  • Write a program in C or C++ that creates a concrete syntax tree (CST) using a recursive descent parsing technique. I expect all parsing to be done using procedurally-driven deterministic finite state automotons (DFA). No table-driven DFAs should be implemented for this assignment. Furthermore, your program should utilize an LCRS binary tree (Left-Child, Right-Sibling) to store your CST. Your program should also display the resulting CST in breadth-first order. You may output your CST 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 three solution:

The output from your programming assignment three 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 3 Rubric

CRITERIA RATINGS POINTS
Compilation:
Will the program compile with GNU compiler?		 Proficient
2 points
Makefile provided. Student's assignment three 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 three 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 three program fails to compile with gcc or g++ on GNU/Linux.		 2 points
Parsing Implementation:
How was the parsing technique implemented?		 Proficient
4 points
Student's assignment three program features a procedurally-driven deterministic finite-state automaton (DFA) to identify and parse comments.		 Below Expectation
0 points
Student's assignment three program implements a table-driven DFA; OR student's assignment three program implements a combination of procedurally-driven and table-driven DFA; OR student's assignment three program fails to use a DFA (table or procedural).		 4 points
Concrete Syntax Tree Implementation:
How was the the Concrete Syntax Tree implemented?		 Proficient
4 points
Student's assignment three program utilizes a Left-Child, Right-Sibling binary tree representation to store a Concrete Syntax Tree.		 Below Expectation
0 points
Student's assignment three program fails to properly create a Concrete Syntax Tree (CST) using a binary tree. There may be structural flaws with the CST.		 4 points
Recursive Descent technique
How was the Concrete Syntax Tree created?		 Proficient
4 points
Student's assignment three program utilizes a recursive descent technique to build a Concrete Syntax Tree from the top-down.		 Below Expectation
0 points
Recursive descent technique is not implemented; OR there may be flaws in how the recursive descent technique is implemented; OR another technique is utilized instead.		 4 points
Test program 1:
The first benchmark test.		 Proficient
1 point
Student's assignment three program removes all comments from test program one without impacting the line numbering of statements. Proper syntax tree is created that exactly matches the expected output in the assignment guidelines. All tokens are accounted for and the tree is displayed in breadth-first order.		 Satisfactory
0.75 points
Student's assignment three program removes all comments. A syntax tree is generated that nearly matches the expected output as outlined in the assignment guidelines (above) with three (inclusive) or fewer tokens that are improperly ordered in the tree and/or do not match.		 Below Expectation
0 points
Student's assignment three program may not remove comments. Student's assignment three program has four or more errors in the Concrete Syntax Tree output that do not match the expected Concrete Syntax Tree output from the assignment guidelines; OR students assignment three program generates no output for a Concrete Syntax Tree.		 1 point
Test program 2:
The second benchmark test.		 Proficient
1 point
Student's assignment three program removes all comments from test program two without impacting the line numbering of statements. Proper syntax tree is created that exactly matches the expected output in the assignment guidelines. All tokens are accounted for and the tree is displayed in breadth-first order.		 Satisfactory
0.75 points
Student's assignment three program removes all comments. A syntax tree is generated that nearly matches the expected output as outlined in the assignment guidelines (above) with three (inclusive) or fewer tokens that are improperly ordered in the tree and/or do not match.		 Below Expectation
0 points
Student's assignment three program may not remove comments. Student's assignment three program has four or more errors in the Concrete Syntax Tree output that do not match the expected Concrete Syntax Tree output from the assignment guidelines; OR students assignment three program generates no output for a Concrete Syntax Tree.		 1 point
Test program 3:
The third benchmark test.		 Proficient
1 point
Student's assignment three program removes all comments from test program three without impacting the line numbering of statements. Proper syntax tree is created that exactly matches the expected output in the assignment guidelines. All tokens are accounted for and the tree is displayed in breadth-first order.		 Satisfactory
0.75 points
Student's assignment three program removes all comments. A syntax tree is generated that nearly matches the expected output as outlined in the assignment guidelines (above) with three (inclusive) or fewer tokens that are improperly ordered in the tree and/or do not match.		 Below Expectation
0 points
Student's assignment three program may not remove comments. Student's assignment three program has four or more errors in the Concrete Syntax Tree output that do not match the expected Concrete Syntax Tree output from the assignment guidelines; OR students assignment three program generates no output for a Concrete Syntax Tree.		 1 point
Test program 4:
The fourth benchmark test.		 Proficient
1 point
Student's assignment three program removes all comments from test program four without impacting the line numbering of statements. Proper syntax tree is created that exactly matches the expected output in the assignment guidelines. All tokens are accounted for and the tree is displayed in breadth-first order.		 Satisfactory
0.75 points
Student's assignment three program removes all comments. A syntax tree is generated that nearly matches the expected output as outlined in the assignment guidelines (above) with three (inclusive) or fewer tokens that are improperly ordered in the tree and/or do not match.		 Below Expectation
0 points
Student's assignment three program may not remove comments. Student's assignment three program has four or more errors in the Concrete Syntax Tree output that do not match the expected Concrete Syntax Tree output from the assignment guidelines; OR students assignment three program generates no output for a Concrete Syntax Tree.		 1 point
Test program 5:
The fifth benchmark test.		 Proficient
2 points
Student's assignment three program detects a syntax error from an unterminated string on line eight of test program five then outputs the error message "Syntax error on line 8: unterminated string quote.". No token list is displayed since a syntax error occurred.		 Satisfactory
1 point
Student's assignment three program detects a syntax error from an unterminated string on line eight of test program five then outputs an error message but the line number where the error occurred is incorrect or missing; OR a token list is displayed with the error message.		 Below Expectation
0 points
Student's assignment three program displays no error message; OR an error message unrelated to an unterminated string is displayed instead. A token list may be displayed.		 2 points
Test program 6
The sixth benchmark test.		 Proficient
2 points
Student's assignment three program detects a syntax error from a negative integer being used to define an array on line six of test program six then outputs the error message "Syntax error on line 6: array declaration size must be a positive integer". No token list is displayed since a syntax error occurred.		 Satisfactory
1 point
Student's assignment three program outputs a syntax error message indicating an array is defined with a negative integer and displays a relevant syntax error message but the line number where the error occurred is incorrect or missing; OR a token list is displayed with the error message.		 Below Expectation
0 points
Student's assignment three program displays no error message; OR an error message is displayed that is unrelated to a negative integer used to define array size. A token list may be displayed.		 2 points
Test program 7:
The seventh benchmark test.		 Proficient
2 points
Student's assignment three program detects a syntax error from using a reserved word as a variable name on line six of test program seven then outputs the error message "Syntax error on line 6: reserved word 'char' cannot be used for the name of a variable". No token list is displayed since a syntax error occurred.		 Satisfactory
1 point
Student's assignment three program displays a syntax error message that a reserved word is used as a variable name but the line number where the error occurred is incorrect or missing; OR a token list is displayed with the error message.		 Below Expectation
0 points
Student's assignment three program displays no error message; OR an error message is displayed that is unrelated to using reserved words for variable names. A token list may be displayed.		 2 points
Test program 8
The eight benchmark test.		 Proficient
2 points
Student's assignment three program detects a syntax error from using a reserved word as a variable name on line six of test program eight then outputs the error message "Syntax error on line 6: reserved word 'void' cannot be used for the name of a variable". No token list is displayed since a syntax error occurred.		 Satisfactory
1 point
Student's assignment three program displays a syntax error message that a reserved word is used as a variable name but the line number where the error occurred is incorrect or missing; OR a token list is displayed with the error message.		 Below Expectation
0 points
Student's assignment three program displays no error message; OR an error message is displayed that is unrelated to using reserved words for variable names. A token list may be displayed.		 2 points
Test program 9:
The ninth benchmark test.		 Proficient
2 points
Student's assignment three program detects a syntax error from using a reserved word as a variable name on line twelve of test program nine then outputs the error message "Syntax error on line 12: reserved word 'int' cannot be used for the name of a variable". No token list is displayed since a syntax error occurred.		 Satisfactory
1 point
Student's assignment three program displays a syntax error message that a reserved word is used as a variable name but the line number where the error occurred is incorrect or missing; OR a token list is displayed with the error message.		 Below Expectation
0 points
Student's assignment three program displays no error message; OR an error message is displayed that is unrelated to using reserved words for variable names. A token list may be displayed.		 2 points
Test program 10
The tenth benchmark test.		 Proficient
2 points
Student's assignment three program detects a syntax error from using a reserved word as a function name on line twelve of test program ten then outputs the error message "Syntax error on line 12: reserved word 'printf' cannot be used for the name of a function". No token list is displayed since a syntax error occurred.		 Satisfactory
1 point
Student's assignment three program displays a syntax error message that a reserved word is used as a function name but the line number where the error occurred is incorrect or missing; OR a token list is displayed with the error message.		 Below Expectation
0 points
Student's assignment three program displays no error message; OR an error message is displayed that is unrelated to using reserved words for function names. A token list may be displayed.		 2 points
Total points: 30