LR(0)

parses without using any lookahead at all

LR(0) Item

E→E+·T T→·F T→·T*F

Steps to Build LR(0) DFA

  1. Initialization:
    • Start by creating the initial state. The initial state contains the closure of the start symbol of the grammar. Typically, a new start symbol is added to the grammar which produces the original start symbol.
  2. Closure of Initial State:
    • Compute the closure of the initial state. This includes all the LR(0) items that can be derived from the initial item.
  3. Iterative State Expansion:
    • For each state, and for each symbol (terminal and non-terminal) in the grammar, compute the GOTO of the state on that symbol. The GOTO of a state on a symbol X is the closure of all items that can be obtained by advancing the dot over an X in the items of the state.
    • If the GOTO result is not empty and is not already a state in the DFA, add it as a new state.
  4. Transitions:
    • For each state and symbol that you used to compute GOTO, if the GOTO result is a valid state, add a transition from the original state to the new state on that symbol.
  5. Repeat Until No New States Are Added:
    • Continue the process until no new states can be added to the DFA.
  6. Finalization:
    • Once all states and transitions are determined, the DFA is complete.

SLR

Heuristics that will refine when we shift or reduce
Idea: Assume

  • stack contains a
  • next input is t
  • DFA on input a terminates in state s

Then reduce by X -> B if

  • s contains item X -> B

image.png