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

LR Parsing Algorithm

  1. Put the special symbol $ at the end of the input.
  2. Put state 0 at the bottom of the stack.
  3. In each iteration, suppose the current configuration is
    the current state is and the next input token is
    1. If is "", then the next configuration is
    2. If is "", then the next configuration is
      where and . At the same time, the parser outputs
      就是下一个栈顶元素，换句话说就是当前状态的上一个状态
      首先先判断归约的 Production Rule，可以知道当前的token 会被归约成哪个token
      然后根据 token，去找到下一个状态
    3. If is "accept" and the current configuration is
      Where is the start symbol of the grammar, the parser accepts the input.
    4. For all other cases, like is blank, the parser finds a syntax error and switch to error recovery.

Example

State id + * ( ) $ E T F
0 s5 s4 1 2 3
1 s6 acc
2 r2 s7 r2 r2
3 r4 r4 r4 r4
4 s5 s4 8 2 3
5 r6 r6 r6 r6
6 s5 s4 9 3
7 s5 s4 10
8 s6 s11
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
Stack Input Output
0 id + id * id$
0id 5 + id * id$ shift 5
0F 3 + id * id$ reduce F → id
0T 2 + id * id$ reduce T → F
0E 1 + id * id$ reduce E → T
0E 1 + 6 id * id$ shift 6
0E 1 + 6 id 5 * id$ shift 5
0E 1 + 6 F 3 * id$ reduce F → id
0E 1 + 6 T 9 * id$ reduce T → F
0E 1 + 6 T 9 * 7 id$ shift 7
0E 1 + 6 T 9 * 7 id 5 $ shift 5
0E 1 + 6 T 9 * 7 F 10 $ reduce F → id
0E 1 + 6 T 9 $ reduce T → T * F
0E 1 $ reduce E → E + T
0E 1 $ accept
Table Of Contents
Compiler-Solution For LR Parsing Algorithm, LR(0) items, SLR Parsing Table Construction
LR Parsing Algorithm
Example