epsilon 的 LR 解析器

Question

我最近实现了一个 LR(1) 解析器（没有 epsilon），并且一直想知道我将如何在解析算法中实现 epsilon（注意：不是 table 构造算法）。这是我的语法：

start -> A b
b -> B | \epsilon

我已按照 here 列出的步骤进行操作，并从我的解析器 (table) 得到了这个结果：

state 0 on symbol start: 1
state 0 on symbol A: shift and goto state 2
state 1 on symbol $: accept
state 2 on symbol b: 3
state 2 on symbol B: shift and goto state 4
state 2 on symbol $: reduce b → 
state 3 on symbol $: reduce start → A b
state 4 on symbol $: reduce b → B

上面列出的table是正确的，但是当我尝试解析A时，没有转换：

error: no transition in table for (0, 'b')

这是我的堆栈的样子：

[0]
[0, 'A', 2]
[0, 'b'] # stack during the error

现在，我注意到顶部没有状态，这是一个问题，但我不知道在它之后添加什么。我的配对代码基于 here.

上面的代码

Answer 1

那个堆栈肯定是错误的，而且看起来很可能是它导致了错误（尽管没有看到代码很难说）。

这是您所期望的：

            LOOK
STACK       AHEAD   ACTION
[0]         A       shift, goto state 2    pushes A (shift) and new state (2)
[0 A 2]     $       reduce b ->            pops 0 pairs, pushes b (reduce) 
[0 A 2 b]           + goto 3               action for b in state 2
[0 A 2 b 3] $       reduce start -> A b    pops 2 pairs, pushes start (reduce)
[0 start]           + goto 1               action for start in state 0
[0 start 1] $       accept

如果我不得不猜测，我会说您正在为 ε 右侧弹出一个符号。正如我在其他地方提到的（包括您引用的答案），ε 什么都不是。它是零个符号，弹出它什么也不会弹出。

epsilon 的 LR 解析器

LR parser for epsilon

compiler-construction

parsing

dfa

lr