Please

modify only the file prog.cpp by adding the methods you need for your parser.

Please use the following grammar:

prog $->$ begin stmt$\_$list end

stmt$\_$list $->$ stmt ; stmt$\_$list

$|$ stmt

$|$ stmt ;

stmt $->$ var $=$ expr

var $->$ A $|$ B $|$ C

expr $->$ var $+$ expr

$|$ var $-$ expr

$|$ var

Implement a recursive descent parser similar to the ones we covered in class.

Note that:

$-$ we have two keywords: begin and end

$-$ we have only three valid identifier: A$,$ B$,$ and C

$-$ the grammar supports three operators: $=,+,$ and $-$

$-$ a semicolon $($;$)$ is a stmt separator within stmt$\_$list

The lexical analyzer in lexan.cpp has already been modified to recognize the tokens listed

above. You may want to compile and run test$-$lexan.cpp with lexan.cpp to verify that this

is the case. Use the input file tp$-01.$txt and create others that you find necessary. It does

not mean that any token that the lexical analyzer recognizes is a valid token for the prog

grammar above. It is the parser's job to flag invalid input due to bad tokens or invalid

statements.

Here are three examples of valid input files $($they appear in parser.zip and they are tp$-$

$01.$txt$,$ tp$-02.$txt$,$ and tp$-03.$txt$)$:

$1)$ begin

A $=$ A

end

$2)$ begin

A $=$ A;

B $=$ C

end

$3)$ begin

B $=$ A $+$ C;

A $=$ B;

C $=$ A $-$ B $+$ C $-$ A;

end

The results appear in the file out$-01.$txt$,$ out$-02.$txt$,$ and out$-03.$txt

Remember, if we can generate a parse tree for an input file, your parser should accept the

input. Anything else should be flagged as an error.

Please see the attached tp$*.$txt files that can be used as input, and the out$*.$txt files that

contain the output produced.

Your code should not be limited to handle only these three examples.

Prog.cpp:

$*$

prog $->$ begin stmt$\_$list end

stmt$\_$list $->$ stmt ; stmt$\_$list

$|$ stmt

$|$ stmt;

stmt $->$ var $=$ expr

var $->$ A $|$ B $|$ C

expr $->$ var $+$ expr

$|$ var $-$ expr

$|$ var

$*/$

#include

#include

#include

#include "token.h$"$

#include "functions.h$"$

using namespace std;

ifstream ifs; $//$ input file stream used by lexan

SymTab symtab; $//$ global symbol table

Token token; $//$ global token

int lookahead $=0$; $//$ no look ahead token yet

int dbg $=1$; $//$ debut is ON

int main$()$

$\{$

ifs $=$ get$\_$ifs$()$; $//$ open an input file stream w$/$ the program

init$\_$kws$()$; $//$ initialize keywords in the symtab

match$($ lookahead $)$; $//$ get the first input token

prog$()$;

return $0$;

$\}$

$//$ your methods...

$//$ utility methods

void emit$($ int t $)$

$\{$

switch$($ t $)$

$\{$

case $\text{'}+\text{'}$: case $\text{'}-\text{'}$: case $\text{'}=\text{'}$:

cout $<<$ char$($ t $)<<\text{'}\text{'}$;

break;

case $\text{'}$;$\text{'}$:

cout $<<"$;

$"$;

break;

case $\text{'}$

$\text{'}$:

cout $<<"$

$"$;

break;

case ID:

case KW:

case UID:

cout $<<$ symtab.tokstr$($ token.tokvalue$())<<\text{'}\text{'}$;

break;

default:

cout $<<"\text{'}$token $"<<$ t $<<",$ tokvalue $"$

$<<$ token.tokvalue$()<<"\text{'}"$;

break;

$\}$

$\}$

void error$($ int t$,$ int expt, const string &str $)$

$\{$

cerr $<<"$

unexpected token $\text{'}"$;

if$($ lookahead $==$ DONE $)$

$\{$

cerr $<<$ "EOF";

$\}$

else

$\{$

cerr $<<$ token.tokstr$()$;

$\}$

cerr $<<"\text{'}$ of type $"<<$ lookahead;

switch$($ expt $)$

$\{$

case $0$: $//$ default value; nothing to do

break;

case ID:

cout $<<"$ while looking for an ID$"$;

break;

case KW:

cout $<<"$ while looking for KW $\text{'}"<<$ str $<<"\text{'}"$;

break;

default:

cout $<<"$ while looking for $\text{'}"<<$ char$($ expt $)<<"\text{'}"$;

break;

$\}$

cerr $<<"$

syntax error.

$"$;

exit$(1)$;

$\}$

void match$($ int t $)$

$\{$

if$($ lookahead $==$ t $)$

$\{$

token $=$ lexan$()$; $//$ get next token

lookahead $=$ token.toktype$()$; $//$ lookahed contains the tok type

$\}$

else

$\{$

error$($ t $)$;

$\}$

$\}$

The lexical analyzer in lexan.cpp has already been modified to recognize the tokens listed above. You may want to compile and run test$-$lexan.cpp with lexan.cpp to verify that this is the case. Use the input file tp$-01.$txt and create others that you find necessary. It does not mean that any token that the lexical analyzer recognizes is a valid token for the prog grammar above. It is the parser's job to flag invalid input due to bad tokens or invalid statements.

Here are three examples of valid input files $($they appear in parser.zip and they are tp$-$

$01.$txt$,$ tp$-02.$txt$,$ and tp$-03.$txt$)$:

$1)$ begin

A $=$ A

end

$2)$ begin

A $=$ A;

B $=$ C

end

$3)$ begin

B $=$ A $+$ C;

A $=$ B;

C $=$ A $-$ B $+$ C $-$ A;

end

The results appear in the file out$-01.$txt$,$ out$-02.$txt$,$ and out$-03.$txt

Remember, if we can generate a parse tree for an input file, your parser should accept the

input. Anything else should be flagged as an error.

Please see the attached tp$*.$txt files that can be used as input, and the out$*.$txt files that

contain the output produced.

Your code should not be limited to handle only these three examples.

Notes to Source Code:

$1.$ test$-$lexan.cpp calls lexan.cpp and tests whether lexan.cpp properly emits tokens

$2.$ prog.cpp calls lexan.cpp to get next token from input