Need help to complete the C++ parser

Write a parser to parse the input according to the grammar and store the information being parsed by your parser in appropriate data structures to allow your program to execute the program on the inputs. 2.2 Examples The following are examples of input with corresponding outputs. The output will be explained in more details in the next section. 1. MAIN X = 1; Y = X; OUTPUT X; OUTPUT Y; 1 2 3 18 19 This example shows a program with no procedure declarations (PROC) and a MAIN procedure that does not read any input. The output of the program will be 1 1 The sequence of numbers at the end does not affect the output of the program. 2. MAIN INPUT X; INPUT Y; X = X + Y; Y = X+Y; OUTPUT X; OUTPUT Y; 3 7 18 19 This is similar to the previous example, but here we have two input statements. The first input statement reads a value for X from the sequence of numbers and X gets the value 3. The second input statement reads a value for Y which gets the value 7. Here the output will be 10 17 Note that the values 18 and 19 are not read and do not affect the execution of the program. 3. PROC INCX X = X + 1; ENDPROC MAIN INPUT X; INPUT Y; INCX; INCX; Y = X+Y; OUTPUT Y; OUTPUT X; 3 18 19 In this example, we have a procedure called INCX. When the procedure is invoked, the code of the procedure is executed. In this case, X is incremented by 1. The second invocation also increments X again so the final value of X is 5. The output is the following. 23 5 4. PROC INCX X = X + 1; ENDPROC MAIN INPUT X; INPUT Y; Z = 2; 3 DO Z INCX; Y = X+Y; OUTPUT Y; OUTPUT X; 3 18 19

Compile on Ubuntu 18 (Ubuntu). You will need to use the g++ command to compile your code in a terminal window. See section 4 for more details on how to compile using GCC.

Implement the followings: 1. The first step is to write your parser. 2. The second step is to implement functionality for supporting program with only a MAIN function and no PROC declarations. At the end of this step, you will have everything in place to support procedures. This second step has a number of steps 2. 1. Memory Allocation. After writing the parser, you should implement a function to allocate memory for variables, this will be useful for other functionality. 2.2. Storing Inputs. You should implement functionality to store the inputs internally in a data structure that can be accessed later when the program is executed 2.3. Simple Statements. For each of the basic statements (assign, input, output), implement the code that will transform the statements to an intermediate representation that can be executed later 2.4 Statement List. Implement the code that will transform a list of statements into a linked list that can be executed later. 2.5 Execution. implement an execute function that takes the data structure generated in 2.4 as a parameter and accesses the stored inputs to simulate the execution of the program and generate the output of the program 3. Procedures. Add support for procedures. The idea here is to store all the statements of a procedure the same way we did for main and then execute the code of a procedure when a procedure call is made.

// parser.h

#ifndef __PARSER_H__ #define __PARSER_H__

#include #include "lexer.h"

class Parser { private: LexicalAnalyzer lexer;

void syntax_error(); Token expect(TokenType expected_type); Token peek(); };

#endif

// parser.cc

#include #include #include "parser.h"

using namespace std;

void Parser::syntax_error() { cout << "SYNTAX ERROR "; exit(1); }

Token Parser::expect(TokenType expected_type) { Token t = lexer.GetToken(); if (t.token_type != expected_type) syntax_error(); return t; }

Token Parser::peek() { Token t = lexer.GetToken(); lexer.UngetToken(t); return t; }

// Parsing

int main() { LexicalAnalyzer lexer; Token token; token = lexer.GetToken(); token.Print();

while (token.token_type != END_OF_FILE) { token = lexer.GetToken(); token.Print(); } }

#ifndef __PARSER_H__ #define __PARSER_H__

#include #include "lexer.h"

class Parser { private: LexicalAnalyzer lexer;

void syntax_error(); Token expect(TokenType expected_type); Token peek();

};

#endif

// lexer.cc

#include #include #include #include #include

#include "lexer.h" #include "inputbuf.h"

using namespace std;

string reserved[] = { "END_OF_FILE", "MAIN", "PROC", "ENDPROC", "INPUT", "OUTPUT", "DO", "EQUAL", "NUM", "ID", "SEMICOLON", "PLUS", "MINUS", "MULT", "DIV", "ERROR"};

#define KEYWORDS_COUNT 7 string keyword[] = { "MAIN", "PROC", "ENDPROC", "INPUT", "OUTPUT", "DO", "EQUAL" };

void Token::Print() { cout << "{" << this->lexeme << " , " << reserved[(int) this->token_type] << " , " << this->line_no << "} "; }

LexicalAnalyzer::LexicalAnalyzer() { this->line_no = 1; tmp.lexeme = ""; tmp.line_no = 1; tmp.token_type = ERROR; }

bool LexicalAnalyzer::SkipSpace() { char c; bool space_encountered = false;

input.GetChar(c); line_no += (c == ' ');

while (!input.EndOfInput() && isspace(c)) { space_encountered = true; input.GetChar(c); line_no += (c == ' '); }

if (!input.EndOfInput()) { input.UngetChar(c); } return space_encountered; }

bool LexicalAnalyzer::IsKeyword(string s) { for (int i = 0; i < KEYWORDS_COUNT; i++) { if (s == keyword[i]) { return true; } } return false; }

TokenType LexicalAnalyzer::FindKeywordIndex(string s) { for (int i = 0; i < KEYWORDS_COUNT; i++) { if (s == keyword[i]) { return (TokenType) (i + 1); } } return ERROR; }

Token LexicalAnalyzer::ScanNumber() { char c; input.GetChar(c); if (isdigit(c)) { if (c == '0') { tmp.lexeme = "0"; } else { tmp.lexeme = ""; while (!input.EndOfInput() && isdigit(c)) { tmp.lexeme += c; input.GetChar(c); } if (!input.EndOfInput()) { input.UngetChar(c); } } tmp.token_type = NUM; tmp.line_no = line_no; return tmp; } else { if (!input.EndOfInput()) { input.UngetChar(c); } tmp.lexeme = ""; tmp.token_type = ERROR; tmp.line_no = line_no; return tmp; } }

Token LexicalAnalyzer::ScanIdOrKeyword() { char c; input.GetChar(c); if (isalpha(c)) { tmp.lexeme = ""; while (!input.EndOfInput() && isalnum(c)) { tmp.lexeme += c; input.GetChar(c); } if (!input.EndOfInput()) { input.UngetChar(c); } tmp.line_no = line_no; if (IsKeyword(tmp.lexeme)) tmp.token_type = FindKeywordIndex(tmp.lexeme); else tmp.token_type = ID; } else { if (!input.EndOfInput()) { input.UngetChar(c); } tmp.lexeme = ""; tmp.token_type = ERROR; } return tmp; }

TokenType LexicalAnalyzer::UngetToken(Token tok) { tokens.push_back(tok);; return tok.token_type; }

Token LexicalAnalyzer::GetToken() { char c;

// if there are tokens that were previously // stored due to UngetToken(), pop a token and // return it without reading from input if (!tokens.empty()) { tmp = tokens.back(); tokens.pop_back(); return tmp; }

SkipSpace(); tmp.lexeme = ""; tmp.line_no = line_no; input.GetChar(c); switch (c) { case ';': tmp.token_type = SEMICOLON; return tmp; case '*': tmp.token_type = MULT; return tmp; case '/': tmp.token_type = DIV; return tmp; case '-': tmp.token_type = MINUS; return tmp; case '+': tmp.token_type = PLUS; return tmp; case '=': tmp.token_type = EQUAL; return tmp; default: if (isdigit(c)) { input.UngetChar(c); return ScanNumber(); } else if (isalpha(c)) { input.UngetChar(c); return ScanIdOrKeyword(); } else if (input.EndOfInput()) tmp.token_type = END_OF_FILE; else tmp.token_type = ERROR; return tmp; } }

// lexer.h

// inputbuf.h

#ifndef __INPUT_BUFFER__H__ #define __INPUT_BUFFER__H__

#include

class InputBuffer { public: void GetChar(char&); char UngetChar(char); std::string UngetString(std::string); bool EndOfInput();

private: std::vector input_buffer; };

#endif //__INPUT_BUFFER__H__

// inputbuf.cc

#include #include #include #include #include

#include "inputbuf.h"

using namespace std;

bool InputBuffer::EndOfInput() { if (!input_buffer.empty()) return false; else return cin.eof(); }

char InputBuffer::UngetChar(char c) { if (c != EOF) input_buffer.push_back(c);; return c; }

void InputBuffer::GetChar(char& c) { if (!input_buffer.empty()) { c = input_buffer.back(); input_buffer.pop_back(); } else { cin.get(c); } }

string InputBuffer::UngetString(string s) { for (int i = 0; i < s.size(); i++) input_buffer.push_back(s[s.size()-i-1]); return s; }