algorithm - LR(0) 和 SLR 解析有什么区别？

Question

我正在研究我的编译器概念，但是我有点困惑......谷歌搜索让我无处可寻。

SLR 和 LR(0) 解析器是否相同？如果不是，有什么区别？

score 261 · Accepted Answer

LR(0) 和 SLR(1) 解析器都是自下而上的、定向的、预测性的解析器。这意味着

解析器尝试反向应用产生式以将输入句子还原为开始符号（自下而上）
解析器从左到右（方向）扫描输入
解析器尝试预测要应用哪些缩减，而不必查看所有输入（预测）

LR(0) 和 SLR(1) 都是移位/归约解析器，这意味着它们通过将输入流的令牌放在堆栈上来处理它们，并且在每个点通过将令牌推入堆栈来移动令牌或减少一些堆栈顶部的终端和非终端序列返回到某个非终端符号。可以证明，任何语法都可以使用 shift/reduce 解析器自下而上解析，但该解析器可能不是确定性的。也就是说，解析器可能不得不“猜测”是应用移位还是减少，并且最终可能不得不回溯以意识到它做出了错误的选择。无论您构建的确定性移位/归约解析器多么强大，它都永远无法解析所有语法。

当确定性移位/归约解析器用于解析它无法处理的语法时，会导致移位/归约冲突或归约/归约冲突，其中解析器可能会进入无法判断要采取什么操作的状态。在移位/归约冲突中，它无法判断是否应该向堆栈添加另一个符号或对堆栈的顶部符号执行一些归约。在 reduce/reduce 冲突中，解析器知道它需要用一些非终结符替换堆栈的顶部符号，但它不知道使用什么归约。

如果这是一个冗长的阐述，我深表歉意，但我们需要它来解决 LR(0) 和 SLR(1) 解析之间的差异。LR(0) 解析器是一个移位/归约解析器，它使用前瞻的零标记来确定要采取的操作（因此为 0）。这意味着在解析器的任何配置中，解析器必须有一个明确的动作可供选择——它要么移动特定的符号，要么应用特定的归约。如果有两个或多个选择要做，解析器就会失败，我们说语法不是 LR(0)。

回想一下，两个可能的 LR 冲突是 shift/reduce 和 reduce/reduce。在这两种情况下，LR(0) 自动机至少可以采取两个动作，但它无法判断要使用哪个动作。由于至少有一个冲突动作是归约，因此合理的攻击路线是尝试让解析器在执行特定归约时更加小心。更具体地说，假设允许解析器查看输入的下一个标记以确定它是否应该移位或减少。如果我们只允许解析器在“有意义”时进行归约（对于“有意义”的某些定义），那么我们可以通过让自动机专门选择在具体步骤。

在 SLR(1)（“Simplified LR(1)”）中，允许解析器在决定是否应该移位或减少时查看一个前瞻标记。特别是，当解析器想要尝试减少 A → w 形式的东西（对于非终结符 A 和字符串 w）时，它会查看下一个输入标记。如果该标记可以合法地出现在某个推导中的非终结符 A 之后，则解析器会减少。否则，它不会。这里的直觉是，在某些情况下，尝试减少是没有意义的，因为鉴于我们目前看到的令牌和即将到来的令牌，减少不可能是正确的。

LR(0) 和 SLR(1) 之间的唯一区别是这种额外的能力可以帮助决定在发生冲突时采取什么行动。因此，任何可以被 LR(0) 解析器解析的文法都可以被 SLR(1) 解析器解析。但是，SLR(1) 解析器可以解析比 LR(0) 更多的语法。

但在实践中，SLR(1) 仍然是一种相当弱的解析方法。更常见的是，您会看到正在使用 LALR(1)（“Lookahead LR(1)”）解析器。它们也通过尝试解决 LR(0) 解析器中的冲突来工作，但是它们用于解决冲突的规则比 SLR(1) 中使用的规则要精确得多，因此更多的语法是 LALR(1)比单反（1）。更具体地说，SLR(1) 解析器尝试通过查看语法结构来解决冲突，以了解有关何时移位和何时减少的更多信息。LALR(1) 解析器同时查看语法和 LR(0) 解析器，以获取有关何时移位和何时减少的更具体的信息。因为 LALR(1) 可以查看 LR(0) 解析器的结构，所以它可以更准确地识别某些冲突何时是虚假的。yacc并且bison，默认情况下，生成 LALR(1) 解析器。

从历史上看，LALR(1) 解析器通常是通过依赖于功能更强大的 LR(1) 解析器的不同方法构建的，因此您经常会看到以这种方式描述的 LALR(1)。要理解这一点，我们需要谈谈 LR(1) 解析器。在 LR(0) 解析器中，解析器通过跟踪它可能在生产过程中的位置来工作。一旦它发现它已经达到了生产的终点，它就知道要尝试减少。但是，解析器可能无法判断它是在一个生产的末尾还是另一个生产的中间，这会导致移位/归约冲突，或者它已经到达了两个不同生产中的哪一个（归约/减少冲突）。在 LR(0) 中，这会立即导致冲突并且解析器失败。在 SLR(1) 或 LALR(1) 中，

在 LR(1) 解析器中，解析器在运行时跟踪附加信息。除了跟踪解析器认为正在使用的产品之外，它还跟踪该产品完成后可能出现的令牌。因为解析器在每一步都跟踪此信息，而不仅仅是在需要做出决定时，所以 LR(1) 解析器比任何 LR(0)、SLR(1) 或到目前为止，我们已经讨论过 LALR(1) 解析器。LR(1) 是一种非常强大的解析技术，它可以使用一些棘手的数学来证明，任何可以被任何移位/归约解析器确定性解析的语言都有一些可以用 LR(1) 自动机解析的语法。（请注意，这并不意味着所有语法可以确定性解析的是 LR(1)；这只是说可以确定性解析的语言具有一些 LR(1) 语法）。然而，这种能力是有代价的，生成的 LR(1) 解析器可能需要大量信息才能运行，以至于无法在实践中使用。例如，用于真实编程语言的 LR(1) 解析器可能需要数十到数百兆字节的附加信息才能正确运行。出于这个原因，LR(1) 通常不会在实践中使用，而是使用较弱的解析器，如 LALR(1) 或 SLR(1)。

最近，一种称为 GLR(0)（“Generalized LR(0)”）的新解析算法已经流行起来。GLR(0) 解析器不是试图解决出现在 LR(0) 解析器中的冲突，而是通过并行尝试所有可能的选项来工作。使用一些巧妙的技巧，可以使许多语法非常有效地运行。此外，GLR(0) 可以解析任何上下文无关文法，甚至是任何 k 的 LR(k) 解析器都无法解析的文法。其他解析器也能够做到这一点（例如，Earley 解析器或 CYK 解析器），尽管 GLR(0) 在实践中往往更快。

如果您有兴趣了解更多信息，今年夏天我教授了一个编译器入门课程，并花了不到两周的时间讨论解析技术。如果您想对 LR(0)、SLR(1) 和许多其他强大的解析技术有更严格的介绍，您可能会喜欢我关于解析的讲座幻灯片和家庭作业。所有课程材料都可以在我的个人网站上找到。

希望这可以帮助！

score 2 · Accepted Answer

这是我学到的。通常 LR(0) 解析器可能有歧义，即表的一个框（您为创建解析器而派生）可以有多个值（或）更好地说：解析器导致具有相同输入的两个最终状态。因此创建了 SLR 解析器来消除这种歧义。为了构造它，找到所有导致 goto 状态的产生式，在左侧找到产生式符号的 follow 并仅包括出现在 follow 中的那些 goto 状态。这反过来意味着您不包含使用原始语法无法实现的产品（因为该状态不在后续集中）

score 1 · Accepted Answer

在 LR(0) 的解析表中，产生式的归约规则放置在整个行中，跨越所有终端，而在 SLR 解析表中，产生式的归约规则仅放置在左侧非的跟随集合中-减少生产的终端。

parsing-EMU这个工具对解析很有帮助，可以生成first、follow、LR(0)项集、LALR Evaluation等。你可以在这里找到它。

score 0 · Accepted Answer

除了上述答案之外，自下而上解析器类中各个解析器之间的区别在于它们在生成解析表时是否会导致移位/归约或归约/归约冲突。冲突越少，语法就越强大 (LR(0) < SLR(1) < LALR(1) < CLR(1))。

例如，考虑以下表达式语法：

E → E + T

E → T

T → F

T → T * F

F → ( E )

F → 身份证

它不是 LR(0) 而是 SLR(1)。使用以下代码，我们可以构建 LR0 自动机并构建解析表（我们需要扩充语法，计算带有闭包的 DFA，计算动作和 goto 集）：

from copy import deepcopy
import pandas as pd

def update_items(I, C):
    if len(I) == 0:
         return C
    for nt in C:
         Int = I.get(nt, [])
         for r in C.get(nt, []):
              if not r in Int:
                  Int.append(r)
          I[nt] = Int
     return I

def compute_action_goto(I, I0, sym, NTs): 
    #I0 = deepcopy(I0)
    I1 = {}
    for NT in I:
        C = {}
        for r in I[NT]:
            r = r.copy()
            ix = r.index('.')
            #if ix == len(r)-1: # reduce step
            if ix >= len(r)-1 or r[ix+1] != sym:
                continue
            r[ix:ix+2] = r[ix:ix+2][::-1]    # read the next symbol sym
            C = compute_closure(r, I0, NTs)
            cnt = C.get(NT, [])
            if not r in cnt:
                cnt.append(r)
            C[NT] = cnt
        I1 = update_items(I1, C)
    return I1

def construct_LR0_automaton(G, NTs, Ts):
    I0 = get_start_state(G, NTs, Ts)
    I = deepcopy(I0)
    queue = [0]
    states2items = {0: I}
    items2states = {str(to_str(I)):0}
    parse_table = {}
    cur = 0
    while len(queue) > 0:
        id = queue.pop(0)
        I = states[id]
        # compute goto set for non-terminals
        for NT in NTs:
            I1 = compute_action_goto(I, I0, NT, NTs) 
            if len(I1) > 0:
                state = str(to_str(I1))
                if not state in statess:
                    cur += 1
                    queue.append(cur)
                    states2items[cur] = I1
                    items2states[state] = cur
                    parse_table[id, NT] = cur
                else:
                    parse_table[id, NT] = items2states[state]
        # compute actions for terminals similarly
        # ... ... ...
                    
    return states2items, items2states, parse_table
        
states, statess, parse_table = construct_LR0_automaton(G, NTs, Ts)

其中语法 G、非终结符号和终结符号定义如下

G = {}
NTs = ['E', 'T', 'F']
Ts = {'+', '*', '(', ')', 'id'}
G['E'] = [['E', '+', 'T'], ['T']]
G['T'] = [['T', '*', 'F'], ['F']]
G['F'] = [['(', 'E', ')'], ['id']]

以下是我为 LR(0) 解析表生成实现的一些更有用的功能：

def augment(G, S): # start symbol S
    G[S + '1'] = [[S, '$']]
    NTs.append(S + '1')
    return G, NTs

def compute_closure(r, G, NTs):
    S = {}
    queue = [r]
    seen = []
    while len(queue) > 0:
        r = queue.pop(0)
        seen.append(r)
        ix = r.index('.') + 1
        if ix < len(r) and r[ix] in NTs:
            S[r[ix]] = G[r[ix]]
            for rr in G[r[ix]]:
                if not rr in seen:
                    queue.append(rr)
    return S

下图（展开查看）显示了使用上述代码为语法构造的 LR0 DFA：

下表显示了作为 pandas 数据帧生成的 LR(0) 解析表，请注意有几个移位/归约冲突，表明语法不是 LR(0)。

SLR(1) 解析器通过仅在下一个输入标记是被归约的非终结符的跟随集的成员时归约来避免上述移位/归约冲突。所以上面的语法不是LR(0)，而是SLR(1)。以下解析表由 SLR 生成：

以下动画展示了上述 SLR(1) 语法如何解析输入表达式：

但是，以下接受形式字符串的文法a^ncb^n, n >= 1是 LR(0)：

A → a A b

A → C

S → A

让我们定义语法如下：

# S --> A 
# A --> a A b | c
G = {}
NTs = ['S', 'A']
Ts = {'a', 'b', 'c'}
G['S'] = [['A']]
G['A'] = [['a', 'A', 'b'], ['c']]

从下图可以看出，生成的解析表没有冲突。

algorithm - LR(0) 和 SLR 解析有什么区别？

4 回答 4

Related

Reference