### LR Parser

The LR parser is a non-recursive, shift-reduce, bottom-up parser. It uses a wide class of context-free grammar which makes it the most efficient syntax analysis technique. LR parsers are 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 to make decisions.

There are three widely used algorithms available for constructing an LR parser:

- 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

Here we describe a skeleton algorithm of an LR parser:

token = next_token() repeat forever s = top of stack if action[s, token] = “shift si” then PUSH token PUSH si token = next_token() else if action[s, token] = “reduce A::= β“ then POP 2 * |β| symbols s = top of stack PUSH A PUSH goto[s,A] else if action[s, token] = “accept” then return else error()

### LL vs. LR

LL | LR |
---|---|

Does a leftmost derivation. | Does a rightmost derivation in reverse. |

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. |

Uses the stack for designating what is still to be expected. | Uses the stack for designating what is already seen. |

Builds the parse tree top-down. | Builds the parse tree bottom-up. |

Continuously pops a nonterminal off the stack, and pushes the corresponding right hand side. | Tries to recognize a right hand side on the stack, pops it, and pushes the corresponding nonterminal. |

Expands the non-terminals. | Reduces the non-terminals. |

Reads the terminals when it pops one off the stack. | Reads the terminals while it pushes them on the stack. |

Pre-order traversal of the parse tree. | Post-order traversal of the parse tree. |