Buttom Up Parsing or Shift-reduce parsing

Buttom Up Parsing or Shift-reduce parsing

Buttom Up Parsing  is also known as Shift-reduce parsing. Buttom Up Parsing  or shift reducing parsing attempts to construct a parse tree for an input string beginning at the leaves and working up towards the root. In other words, it is a
process of “reducing” (opposite of deriving a symbol using a production rule) a string w to the start symbol of a grammar. At every (reduction) step, a
particular substring matching the RHS of a production rule is replaced by the symbol on the LHS of the production.

A general form of shift-reduce parsing is LR (scanning from Left to right and using Right-most derivation in reverse) parsing, which is used in a number of
automatic parser generators like Yacc, Bison, etc.

Here are the definitions of some commonly used terminologies in this context.

Implementation of Shift-Reduce Parsing

A convenient way to implement a shift-reduce parser is to use a stack to hold grammar symbols and an input buffer to hold the string w to be parsed. The
symbol $ is used to mark the bottom of the stack and also the right-end of the input.

Notationally, the top of the stack is identified through a separator symbol |, and the input string to be parsed appears on the right side of |. The stack content
appears on the left of |.

For example, an intermediate stage of parsing can be shown as follows:
$id1 | + id2 * id3$ .... (1)

Here “$id1” is in the stack, while the input yet to be seen is “+ id2 * id3$*
In shift-reduce parser, there are two fundamental operations: shift and reduce.
Shift operation: The next input symbol is shifted onto the top of the stack.

After shifting + into the stack, the above state captured in (1) would change into:
$id1 + | id2 * id3$

Reduce operation: Replaces a set of grammar symbols on the top of the stack with the LHS of a production rule.

After reducing id1 using E → id, the state (1) would change into:
$E | + id2 * id3$

Viable Prefixes

The set of prefixes of right sentential forms that can appear on the stack of a shift-reduce parser are called viable prefixes. It is always possible to add
terminal symbols to the end of a viable prefix to obtain a right-sentential form.

Item

An item X → β.γ is valid for a viable prefix αβ if
S’ →* αXw → αβγw
is obtainable by a rightmost derivation. After parsing αβ, the valid items are the possible tops of the stack of items.

Notations for Possible Actions in LR Parsing Table

sn: Shift into state n
gn: Goto state n
rk: Reduce by rule k
a: Accept
<Nothing> : Error