Bottom-up Parsing: Shift Reduce Parser — LR ParserBackground information:Shift Reduce parser:« Reduce is the action of replacing the handle on the top of the parse stack with itscorresponding...

The assignment instructions are provided in the .cpp file!


Bottom-up Parsing: Shift Reduce Parser — LR Parser Background information: Shift Reduce parser: « Reduce is the action of replacing the handle on the top of the parse stack with its corresponding LHS ® Shift is the action of moving the next token to the top of the parse stack The parse tree is constructed from leaves (bottom) to the root (up). This parser requires some data structures: An input buffer for storing the input string. A stack for storing and accessing the production rules. Basic Operations — 1. Shift: «This involves moving of symbols from input buffer onto the stack. 2. Reduce: o Ifthe handle appears on top of the stack then, its reduction by using appropriate production rule is done i.e. RHS of production rule is popped out of stack and LHS of production rule is pushed onto the stack. 3. Accept: o If only start symbol is present in the stack and the input buffer is empty then, the parsing action is called accept. When accept action is obtained, it is means successful parsing is done. 4. Error: o Thisis the situation in which the parser can neither perform shift action nor reduce action and not even accept action. Your task: 1. Write a C++ program to perform the actions of a shift reduce parser for the following grammar. E>T+T|T T>T*F|F Fo i To make it simple, the input string will be: i*i+ The output of your program will look like the following: ck Input Action STII) *i+i$ REDUCE eat Ved SCI ia EEC) +i$ REDUCE SCI 12) Te 3 STIG) FCI $ REDUCE FIV: $ REDUCE [a There is a sample program for this lab — “LR_parser_sample_for_hw3.cpp”. The sample program has a portion of the logic for this homework. It will process the input string and produce the following output. The output is not correct because the code is incomplete. Input string is: i®ii Stack Input Action FEET) *i+i$ REDUCE TO F -> Ett) Feta +i$ REDUCE TO F REDUCE TO F aa You need to modify the sample program or you can rewrite the program from scratch to produce the correct output for this homework. Note: Take a screen shot of your output and put it in a word doc. Do not zip the word doc. Submit it and the program file separately to Canvas.