scanner and parser and tree generated from parserno de parser
CSCI 4355 Programming Language Concepts Fall 2021 Term Project Final Due Date: 11/30/2021 In this project you are to implement a scanner and a recursive descent parser, and a de-parser for a small programming language (let’s call it Hawk). Your program will take as input a program written in the provided language and produce a parse tree in the form of a table. In addition to generating the parse tree, your program must generate the proper errors when encountered. After generating the tree, you need to write a program that de-parses the tree into the original code that generated it. The following is the grammar that you will use: Rule 01: PROGRAM program DECL_SEC begin STMT_SEC end; Rule 02: DECL_SEC DECL | DECL DECL_SEC Rule 03: DECL ID_LIST : int ; Rule 04: ID_LIST ID | ID , ID_LIST Rule 05: ID a|b|c|...| z | A | ... | Z Rule 06: STMT_SEC STMT | STMT STMT_SEC Rule 07: STMT ASSIGN | IFSTMT | WHILESTMT | INPUT | OUTPUT Rule 08: ASSIGN ID := EXPR ; Rule 09: IFSTMT if COMP then STMT_SEC end if ; | if COMP then STMT_SEC else STMT_SEC end if ; Rule 10: WHILESTMT while COMP loop STMT_SEC end loop ; Rule 11: INPUT input ID; Rule 12: OUTPUT output ID_LIST ; Rule 13: EXPR FACTOR | FACTOR + EXPR | FACTOR - EXPR Rule 14: FACTOR OPERAND | OPERAND * FACTOR Rule 15: OPERAND INT | ID | ( EXPR ) Rule 16: INT 0 | 1 | ... | 9 Rule 17: COMP ( OPERAND = OPERAND ) | ( OPERAND <> OPERAND ) | ( OPERAND > OPERAND ) | ( OPERAND < operand="" )="" this="" grammar="" has="" 17="" rules.="" it="" also="" has="" reserved="" words="" in="" it="" indicating="" that="" they="" cannot="" be="" used="" for="" identifiers.="" non-terminal="" symbols="" are="" those="" that="" are="" capitalized,="" and="" terminal="" symbols="" are="" those="" that="" are="" lowercase.="" some="" rules="" have="" alternative="" choices,="" for="" example="" rule="" 09="" has="" two="" alternatives,="" one="" without="" an="" else,="" and="" one="" with="" and="" else.="" you="" do="" not="" need="" to="" worry="" about="" the="" alternatives="" for="" rules="" 05="" and="" 16="" when="" generating="" the="" parse="" tree.="" however,="" which="" alternative="" for="" a="" rule="" that="" you="" produce="" (choose)="" should="" be="" indicated="" in="" the="" parse="" tree.="" the="" following="" are="" the="" lexemes="" for="" the="" language:="" ·="" reserved="" words:="" program,="" begin,="" end,="" if,="" then,="" else,="" input,="" output,="" int,="" while,="" loop.="" ·="" operators:="" assignment="" (:=")," less="" than=""><), greater="" than="" (="">), equals (=), not equals (<>), plus (+), minus (-) , multiply (*), and parentheses. · The ‘;’ is also used to terminate statements and the ‘,’ and the ‘:’ are used when declaring variables. · Identifiers: only one-character identifiers a-z or A-Z and they are case insensitive. · Integers: only one-digit integers 0-9. · Note: The only types to be declared in the language are integers. Upon encountering a variable in a declaration section, you must add it to the symbol table. This means that a redeclaration of a variable should produce an error and exit the program. The use of a variable before it is declared should also produce an error an exit the program. Errors that could be generated upon scanning and parsing a program: · Illegal symbol · Illegal identifier · Illegal number · Parse errors encountered by expecting a symbol and not getting that symbol. All errors must indicate the line number in the file. All error message must be descriptive as well indicating what happened precisely. Upon encountering an error, you must exit the program immediately after reporting the error and its location. You will be provided with some test cases to use to test your program. However, your implementation should work with other test cases. So, you are encouraged to generate your own test cases to make them work with your parser. In the assignment, you will be turning it in incremental. The first part should be only a scanner to print out the tokens and lexemes. The second part should be just a parser without the tree. The third should be a parser with the tree. The fourth is going to be a de-parser that accepts the tree and produces the program that generated it. While the de-parser is a separate application than the parser (the parser by the way includes the scanner and the building of the tree), it will use a lot of the constructs in the parser. So, you will see a description of it after the parsing example. The following is an example program and its expected output: program x, y: int; begin input x,y; y:=x+y; output y; end; This happens to be a correct program, so the resulting output for it looks like this: Node # Rule # Branch 1 Branch 2 Branch 3 Alternative # Id/Int Value ------ ------ -------- -------- -------- ------------- ----------- 1 1 2 8 0 1 2 2 3 0 0 1 3 3 4 0 0 1 4 4 5 6 0 2 5 5 0 0 0 0 24 6 4 7 0 0 1 7 5 0 0 0 0 25 8 6 9 15 0 2 9 7 10 0 0 4 10 11 11 0 0 1 11 4 12 13 0 2 12 5 0 0 0 0 24 13 4 14 0 0 1 14 5 0 0 0 0 25 15 6 16 27 0 2 16 7 17 0 0 1 17 8 18 19 0 1 18 5 0 0 0 0 25 19 13 20 23 0 2 20 14 21 0 0 1 21 15 22 0 0 1 22 5 0 0 0 0 24 23 13 24 0 0 1 24 14 25 0 0 1 25 15 26 0 0 1 26 5 0 0 0 0 25 27 6 28 0 0 1 28 7 29 0 0 5 29 12 30 0 0 1 30 4 31 0 0 1 31 5