Next: LR(0) Parsing (2)
Up: No Title
Previous: Algorithm for first(X), follow(X)
- 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
- An LR(0) item describes a possible situation during parsing,
- 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 ]