RSS
Twitter
Facebook
Bottom-up
parsers in general use explicit stack. They are also known as shift reduce
parsers.
Example:
Consider a grammar S ->a S b | c
and a sentence a a c b b. The parser put the sentence to be recognized in the
input buffer appended with end of input symbol $ and bottom of stack has also
$.
The
parser consults a table indexed by two parameters to be discussed later. The
parameters what is on the top of stack and input character pointed by input
buffer pointer. Assume for the time being that the table tells the parser to do
one of the following activities.
The
table formation will be discussed later. From the figure above, after 3 shifts
the table tells the parser to reduce in step-4 that is pop c and replace by
(i.e., push) ‘S’. In the 5th Step again shift is executed. In 6th step the
parser is told to pop 3 symbols and replace it by S, in 7th step again parser
is told to shift. In 8th step the parser pops 3 symbols & replaces it by S
i.e., reduce action takes place. When top of stack is start symbol i.e., S in
this case and input buffer is empty i.e., input buffer is pointing to $ (this indicates
there is no more input available). The parser is told to carryout accept
action. The parser is able to recognize that aacbb is indeed a valid sentence
of the given grammar. We shall see later on how shift reduce and accept actions
are indicated.
Example:
Consider
another example of parsing using the grammar
Recognize abbcde
Rightmost
Derivation
Reduction
done in the shift reduce parses is exactly the reverse order of rightmost
derivation replace statements.
0 comments