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.