For LR Parsing Algorithm, LR(0) items, SLR Parsing Table Construction

LR Parsing Algorithm

Put the special symbol $ at the end of the input.
Put state 0 at the bottom of the stack.
In each iteration, suppose the current configuration is $< 0 \underset{―}{X_{1} S_{1}} \dots \underset{―}{X_{m} S_{m}} a_{i} \dots a_{n} $ >,$ the current state is $S_{m}$ and the next input token is $a_{i}$
1. If $A C T I O N [S_{m}, a_{i}]$ is " $s h i f t S$ ", then the next configuration is $< 0 \underset{―}{X_{1} S_{1}} \dots \underset{―}{X_{m} S_{m}} a_{i} S \dots a_{n} $ >$
2. If $A C T I O N [S_{m}, a_{i}]$ is " $r e d u c e A \to β$ ", then the next configuration is $< 0 \underset{―}{X_{1} S_{1}} \dots \underset{―}{X_{m - r} S_{m - r}} \underset{―}{A S} \dots a_{n} $ >,$ where $r = | β |$ and $S = G O T O [S_{m - r}, A]$ . At the same time, the parser outputs $A \to β$ $S_{m - r}$ 就是下一个栈顶元素，换句话说就是当前状态的上一个状态首先先判断归约的 Production Rule，可以知道当前的token 会被归约成哪个token 然后根据 $S_{m - r}$ token，去找到下一个状态 $S$
3. If $A C T I O N [S_{m}, a_{i}]$ is "accept" and the current configuration is $< 0 X S_{1} $ >,$ Where $X$ is the start symbol of the grammar, the parser accepts the input.
4. For all other cases, like $A C T I O N [S_{m}, a_{i}]$ is blank, the parser finds a syntax error and switch to error recovery.