LR Parser in Compiler Design

LR Parser

The most popular type of bottom-up parsing is LR(K) parsing. The LR() parser scans the input from left – to – right, which is the actual abbreviation of L in the LR(K) parser. However, the R in the LR() parser constructs the rightmost derivation in the reverse order. The LR parser uses the lookahead input symbol, which is represented by K in LR(K) parser. The lookahead helps in making parsing decisions.

Why LR Parser

• For any programming language construct, if we are able to write a context-free – grammar, then the LR parser will recognize such kind of programming language. There also exist some non – LR CFG, but in that case, the programming language will avoid the non – LR context-free – grammar.

• The Non–backtracking shift-reduce parser is one of the most preferred LR Parser, which can be implemented in the same way as other primitive shift-reduce parsers.

• LR parser can easily detect any error at the time of scanning the input when required.

• The LR parser, which is parsed by the grammar, is itself the subset of the grammar parsed by LL or Predictive parser.

Difference Between LL and LR Parser

LL Parser	LR Parser
The first L in the LL parser is for scanning the input from left to right, and the second L is for the leftmost derivation.	L in LR parser is for the left to right, and R stands for rightmost derivation in the reverse order.
LL follows the leftmost derivation.	LR follows rightmost derivation in reverse order.
An LL parser amplifies non - terminals.	Terminals are condensed in LR parser.
LL parser constructs a parse tree in a top-down manner.	LR parser constructs a parse tree in a bottom-up manner.
It ends whenever the stack in use becomes empty.	It starts with an empty stack.
It starts with the start symbol.	It ends with the start symbol.
It is easier to write	It is difficult to write
Pre-order traversal of the parse tree.	Post-order traversal of the parse tree.
Reads the terminals when it pops out of the stacks.	Reads the terminals while it pushes them into the stack.

Example LL(0), LL(1)

Example LR(0), SLR(1), LARL(1), CLR(1)

The LR Parser Algorithm

A schematic of an LR parser is shown below fig. This parser contains an input, an output, a stack, a driver program, and a parsing table.  ACTION and GOTO are the two parts of the parsing table. The driver program is not different for all LR parsers; only the parsing table is different from one parser to another parser. The stack stores the chronology of grammar with a $ at the bottom of the stack. The string which has to be parsed stays in the input buffer, which is used to indicate the end of input, followed by a $ Symbol.