Compiler Design Bottom Up Parser - Compiler Design

How Bottom-Up parser works in Compiler Design?

The parsing is started from the leaf nodes of the tree and works upward till it reaches the root node in Bottom-Up parsing. Parsing starts from a sentence and the production rules are applied in the reverse manner and reach the start symbol. The bottom-up parser is depicted below:

Bottom Up Parsing

Shift-Reduce Parsing

For bottom-up parsing two techniques are used by shift-reducing parsing. These techniques are known as shift-step and reduce-step.

  • Shift step: The input pointer advances to the next input symbol by the shift step and the next input symbol is known as shifted symbol and the symbol is pushed upon stack. The shifted symbol is considered as a single node of the parse tree.
  • Reduce step : When a complete grammar rule RHS is replaced by LHS it is termed as reduce-step. The stack performs a pop function which facilitates in popping off the handle and replacing with the LHS non-terminal symbol.

LR Parser

A bottom-up parser which is non-recursive and shift-reduce is LR parser. A context-free grammar is used which facilitates the efficient syntax analysis technique. LR parser is also known as LR(k) parsers, where L stands for left-to-right scanning of the input stream; R stands for the construction of right-most derivation in reverse, and k denotes the number of lookahead symbols for making decisions.

An LR Parser can be constructed by using algorithms such as:

  • SLR(1) – Simple LR Parser:
    • Works on smallest class of grammar
    • Few number of states, hence very small table
    • Simple and fast construction
  • LR(1) – LR Parser:
    • Works on complete set of LR(1) Grammar
    • Generates large table and large number of states
    • Slow construction
  • LALR(1) – Look-Ahead LR Parser:
    • Works on intermediate size of grammar
    • Number of states are same as in SLR(1)

LR Parsing Algorithm

The algorithm of an LR parser is as follows:

What are the differences between LL and LR?

Leftmost derivation is done.
Rightmost derivation is done.
Starts with the root nonterminal on the stack.
Ends with the root nonterminal on the stack.
Ends when the stack is empty.
Starts with an empty stack.
Stack is used for designating the expected.
Stack is used for designating the already seen.
Parse tree is built top-down.
Parse tree is built bottom-up.
A nonterminal that is off the stack pops up continuously and the corresponding right hand side is pushed.
The right hand side of the stack is recognized, is popped and the corresponding nonterminal is pushed.
Non-terminals are expanded.
Non-terminals are reduced.
When one of the stacks is popped, the terminal is read.
When the terminals are pushed on the stack, they are read.
Pre-order traversal of the parse tree.
Post-order traversal of the parse tree.

All rights reserved © 2020 Wisdom IT Services India Pvt. Ltd Protection Status

Compiler Design Topics