Implement a recursive descent parser for the grammar. Your parser should build a complete parse tree. A binary tree suffices for holding all the nodes of the parse tree of any program derivable from this grammar. After a parse tree has been built, your code will need to print all its nodes using the pre-order traversal. You must use recursion to print the tree.

You may extend the code, but you must not modify the parts that are given to you in the archive; specifically, the main() function in the file main.c should not be changed. The parser code is located in the file parser.c , and the recursive functions to print the parse tree are in the file eval.c. The parser.h file contains declarations relevant to the parser, and the eval.h file holds the prototypes for the printing functions. There is also the ad hoc scanner code included in the files scanner.c and scanner.h.

A struct NODE that will hold parse tree nodes is declared in parser.h. Each node has a type and a union part that is specialized for specific nodes in the tree (e.g., a node for print statement, repeat statement, expressions, and so on). It also has two pointer that should point to the left and right children. Remember to initialize the pointers with NULL, as some nodes may need only one or no children. Note that you will need to use the 'op' field in the NODE structure to record the type of the parsed operator. That includes binary additive operators '+' and '-', multiplicative operators '*', '/', and '%', as well as the unary operator '-' (negation). They will be needed to print the details of the corresponding nodes in the parse tree.

All functions required by the parser are declared in parser.h. The function program() is already implemented in parser.c to show you the pattern that you must follow in the implementation of all remaining functions. You should use the helper function getNextToken() to obtain the next token from the scanner. It should be called from the parser as needed as explained in the lectures. The function getNextToken() calls the scannerAdHoc() function included in scanner_ad_hoc.h. You must not change the code of the scanner, but you will need to use the scanner utility function ungetToken() to return a look-ahead token back to the scanner.

Test your compiler on the following program:

firstvar = 1; secondvar = 2; repeat (10) thirdvar = 2 * (firstvar % secondvar) / (firstvar + 2);; repeat (firstvar + 2 * secondvar) repeat (thirdvar) print -firstvar;;;

The output from your parser should follow the sample provided in the file sample_output.txt. Your printing function printProgram() MUST traverse the parse tree AFTER the parsing is complete (as implemented in the main() function).

Do not print anything else but error messages from the parser. The function error() is a rudimentary vehicle for managing errors: after printing the error message that it is passed, it simple terminates the parser. To test your error handling, make five modifications to the test program that introduce errors and include in the submission the printing transcripts for each of them. You must test one error at any time, since the parser will exit when the error message is printed.

#include "parser.h" TOKEN *getNextToken(TOKEN **token) { freeToken(token); return scannerAdHoc(); } //TOKEN **currToken // *currToken = getNextToken(currToken) //make sure to free token in terminals NODE *program() { NODE *node = malloc(sizeof(NODE)); //same on statement node->type = PROGRAM_NODE; //statement for statement node->leftNode = statement(); // same except its assignstatent for next one if (node->leftNode != NULL) return NULL; else { node->rightNode = program(); } return node; } NODE *statement() { // TODO: implement  TOKEN **currToken; NODE *node = malloc(sizeof(NODE)); //same on statement node->type = STATEMENT_NODE; //statement for statement *currToken = getNextToken(currToken); if((*currToken)->type == IDENT_TOKEN ){ node->leftNode = assignStmt(currToken); } //make a node(malloc) //assign node type //get next token(store in currToken) //if currtoken is ID //set left node to assigment //CODE //if( currentToken = IDENT_TOKEN ){ // node->leftNode = assignStmt(¤tToken) //else if(currentToken = REPEAT_TOKEN) // node->rightNode = assignStmt(¤tToken) //} } NODE *assignStmt(TOKEN **currToken) { // TODO: implement  NODE *node = malloc(sizeof(NODE)); node->type = ASSIGNMENT_TOKEN; *currToken = getNextToken(currToken); node->rightNode = expr(currToken); printf("Parsing error :"); //set left node to id //check for = //set right node to expr //check for ; } NODE *repeatStmt(TOKEN **currToken) { // TODO: implement } NODE *printStmt(TOKEN **currToken) { // TODO: implement } NODE *expr(TOKEN **currToken) { // TODO: implement } NODE *term(TOKEN **currToken) { // TODO: implement } NODE *factor(TOKEN **currToken) { // TODO: implement } NODE *id(TOKEN **currToken) { // TODO: implement } NODE *number(TOKEN **currToken) { // TODO: implement  //get currToken and convert to node // } void error(char *errorMessage) { printf("PARSING ERROR: %s Exiting... ", errorMessage); exit(1); } 

#include "eval.h" void printProgram(NODE *node) { if(node == NULL) return; printf("=> START program "); if (node->leftNode != NULL) printStatement(node->leftNode); if (node->rightNode != NULL) printProgram(node->rightNode); printf("=> END program "); } void printStatement(NODE *node) { // TODO: implement  //if(currToken == Iden //node ->leftnode } void printAssignStmt(NODE *node) { // TODO: implement } void printRepeatStmt(NODE *node) { // TODO: implement  //print statement on left and right } void printPrintStmt(NODE *node) { // TODO: implement } void printExpr(NODE *node) { // TODO: implement } void printTerm(NODE *node) { // TODO: implement } void printFactor(NODE *node) { // TODO: implement } void printId(NODE *node) { // TODO: implement } void printNumber(NODE *node) { // TODO: implement } 

#include "eval.h" int main(int argc, char** argv) { freopen(argv[1], "r", stdin); NODE *fullProgram = program(); printf("Done parsing... "); printProgram(fullProgram); exit(0); }

#ifndef __SCANNER_H #define __SCANNER_H #include  #include  #include  #include  typedef enum { INVALID_TOKEN = 0, NUMBER_TOKEN, IDENT_TOKEN, ASSIGNMENT_TOKEN, SEMICOLON_TOKEN, LPAREN_TOKEN, RPAREN_TOKEN, PLUS_TOKEN, MINUS_TOKEN, MULT_TOKEN, DIV_TOKEN, MOD_TOKEN, REPEAT_TOKEN, PRINT_TOKEN, END_OF_INPUT_TOKEN } TOKEN_TYPE; typedef struct token { TOKEN_TYPE type; char *strVal; } TOKEN; TOKEN *scannerAdHoc(); void ungetToken(TOKEN **); void freeToken(TOKEN **); #define BUF_SIZE 128 #define MAX_LINE_LENGTH 256 #endif

#ifndef __EVAL_H #define __EVAL_H #include "parser.h" void printProgram(NODE *node); void printStatement(NODE *node); void printAssignStmt(NODE *node); void printRepeatStmt(NODE *node); void printPrintStmt(NODE *node); void printExpr(NODE *node); void printTerm(NODE *node); void printFactor(NODE *node); void printId(NODE *node); void printNumber(NODE *node); #endif

#ifndef __PARSER_H #define __PARSER_H #include  #include  #include "scanner.h" typedef enum { IDENTIFIER_NODE = 1, NUMBER_NODE, EXPR_NODE, TERM_NODE, ASSIGN_STMT_NODE, REPEAT_STMT_NODE, PRINT_STMT_NODE, FACTOR_NODE, PROGRAM_NODE, STATEMENT_NODE } NODE_TYPE; typedef struct node { NODE_TYPE type; union  { char identifier[128]; double number; char op; //char addOp; //char multOp; } data; struct node *leftNode; struct node *rightNode; } NODE; NODE *program(); NODE *statement(); NODE *assignStmt(TOKEN **currToken); NODE *repeatStmt(TOKEN **currToken); NODE *printStmt(TOKEN **currToken); NODE *expr(TOKEN **currToken); NODE *term(TOKEN **currToken); NODE *factor(TOKEN **currToken); NODE *id(TOKEN **currToken); NODE *number(TOKEN **currToken); TOKEN *getNextToken(TOKEN **currToken); void error(char *errorMsg); #endif

Done parsing... => START program => START statement => START assignment => START identifier  firstvar => END identifier => START expression => START term => START factor => START number  1.000000 => END number => END factor => END term => END expression => END assignment => END statement => START program => START statement => START assignment => START identifier  secondvar => END identifier => START expression => START term => START factor => START number  2.000000 => END number => END factor => END term => END expression => END assignment => END statement => START program => START statement => START repeat => START expression => START term => START factor => START number  10.000000 => END number => END factor => END term => END expression => START statement => START assignment => START identifier  thirdvar => END identifier => START expression => START term => START factor => START number  2.000000 => END number => END factor  => START expression => START term => START factor => START expression => START term => START factor => START identifier  firstvar => END identifier => END factor  => START expression => START term => START factor => START identifier  secondvar => END identifier => END factor => END term => END expression => END term => END expression => END factor  => START expression => START term => START factor => START expression => START term => START factor => START identifier  firstvar => END identifier => END factor => END term  => START expression => START term => START factor => START number  2.000000 => END number => END factor => END term => END expression => END expression => END factor => END term => END expression => END term => END expression => END term => END expression => END assignment => END statement => END repeat => END statement => START program => START statement => START repeat => START expression => START term => START factor => START identifier  firstvar => END identifier => END factor => END term  => START expression => START term => START factor => START number  2.000000 => END number => END factor  => START expression => START term => START factor => START identifier  secondvar => END identifier => END factor => END term => END expression => END term => END expression => END expression => START statement => START repeat => START expression => START term => START factor => START identifier  thirdvar => END identifier => END factor => END term => END expression => START statement => START print => START expression => START term => START factor  => START factor => START identifier  firstvar => END identifier => END factor => END factor => END term => END expression => END print => END statement => END repeat => END statement => END repeat => END statement => START program => END program => END program => END program => END program => END program