LR(1)

Sometimes, SLR(1) Parser is still not capable, then we can try out LR(1).

LR(1) Item

This time, we don’t use $Follow$ set anymore, instead, we directly embed the lookahead into Items, something like below:

$$ \begin{aligned} S’ \to S, $ \ S \to Ab, $ \ A \to xyz, b \ \end{aligned} $$

The lookahead part will propagate during discovery of DFA node.

Consider the following item is in a state:

$$ P \to \cdot A \alpha, x $$

Then we also have the following new item in this state:

$$ A \to \cdot \beta, First(\alpha x) $$

• $\alpha, \beta \in V^*$

Note that the lookahead of the newly discovered item is the first set of the right part of $A$ plus the lookahead of the original item.

Construct Parse Table

Similar to SLR(1), but when facing Reduction operation, only set $Action(S_i, x) = R_j$ when $x = lookahead$