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:

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?