# LR Parsing Cheat Sheet

LR($k$): Parsing from Left to right producing the Rightmost derivation by looking ahead $k$ tokens on the input

## LR(0) Parsing Concepts:
- Item: a hypothesis about the sub-derivation: $N \to \alpha.\beta$
  + $N$: the hypothesis
  + $\alpha$: the confirmed part
  + $\beta$: the expectation
  + the item is reducible if $\beta$ is empty
- Item set: a collection of items
- Closure of an item set:
  + for any item $N \to \alpha.A\beta$ in the item set (note that the dot appears immediately before the _non-terminal_ $A$), add new hypotheses for parsing $A$, _i.e._, for each rule $A \to \gamma$ in the grammar, add the item $A \to .\gamma$ to the item set
  + repeat until we reach a fixed point

## LR(0) Parsing and LR(0) Automaton
- We start parsing in the state that is the closure of hypotheses corresponding to the start symbol; this is the initial state of the automaton
- Complete the automaton by exploring the space:
  Given a state $s$, we go to state $s'$ from $s$ by seeing a (non-)terminal $x$, if
  + $x$ appears before a dot in $s$
  + $s'$ is the closure of the set consisting of all the items of the form $A \to \alpha x.\beta$ where $A \to \alpha.x\beta$ was in $s$

## LR(0) General Ideas
- Based on a stack of alternating components: item sets and derivations
- Shifting: updating hypotheses
- Reducing: popping from the stack and replacing by the new (larger) sub derivation
- Conflicts: shift/reduce and reduce/reduce

## LR(1) Parsing Concepts
- Item: a hypothesis together with a lookahead set: $N \to \alpha.\beta, L$
  + $N$: the hypothesis
  + $\alpha$: the confirmed part
  + $\beta$: the expectation
  + $L$ is the set of symbols that expect _after parsing an $N$ using this rule_
  + the item is reducible if $\beta$ is empty and the next symbol on the input is in $L$
- Closure on an item set:
  + for any item $N \to \alpha .A \beta, L$ in the item set (note that the dot appears immediately before the _non-terminal_ $A$) add new hypotheses for parsing $A$, _i.e._, for each rule $A \to \gamma$ in the grammar, add the item $A \to .\gamma, \mathit{first}(\beta L)$ to the item set

  + repeat until we reach a fixed point

## LR(1) Parsing and LR(1) Automaton
- We start parsing in the state that is the closure of hypotheses corresponding to the start symbol with $\emptyset$ as lookahead; this is the initial state of the automaton
- Complete the automaton by exploring the space:
  Given a state $s$, we go to state $s'$ from $s$ by seeing a (non-)terminal $x$, if
  + $x$ appears before a dot in $s$
  + $s'$ is the closure of the set consisting of all the items of the form $A \to \alpha x.\beta, L$ where $A \to \alpha.x\beta, L$ was in $s$

## LR(1) General Ideas
- The same as LR(0) with the following key idea to reduce conflicts
- __Key Idea__: since we only reduce if the next symbol on the input is in the lookahead set, there are fewer reduces possible in each state and therefore some shift-reduce or reduce-reduce conflicts are eliminated