SLR Parsing

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
• $t\in Follow(X)$