Bottom-up Parsing: Shift Reduce Parser — LR Parse
Background information:
Shift Reduce parser:
« Reduce is the action of replacing the handle on the top of the parse stack with its
co
esponding 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. E
or:
o Thisis the situation in which the parser can neither perform shift action no
educe 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 co
ect 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 co
ect 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.