LR(0) Parsing

• Idea: Use a DFA applied to the stack to decide whether to shift or to reduce.
• The states of the DFA are sets of LR(0) itemize.
• An LR(0) item is of the form [X = A _ B ], where X is a non-terminal and A,B are strings of terminals and non-terminals (possibly empty).
• An LR(0) item describes a possible situation during parsing, where
  • X=AB. is a production, which is currently possible.
  • A is on the stack.
  • B is in the input.
  • the _ describes the border between stack and input.
• Example: [ E = T _ "+" E ]