LR Parsing Cheat Sheet

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

Contents