LR(1) Parsing

• LR(1) parsing refines the notion of state. A state is now a set of LR(1) itemize, where each item is of the form [X = A _ B ; c] and c is a terminal.
  • X=AB. is a production, which is currently possible.
  • A is on the stack.
  • B c is in the input.
  • the _ describes the border between stack and input.
• The rest of the construction is similar to LR(0), except that we reduce in a state with item [X = A _ ; c] only if the next input token is c.
• The result is called LR(1) parsing, because now we use one token lookahead to make our decision.
• LR(1) parsers are slightly more powerful than LALR(1) parsers.
• But, there are many more LR(1) states than LR(0) states. Often we have a state explosion