LR(0)和SLR解析有什么区别？
Nit*_*eti 72 compiler-construction algorithm parsing lr-grammar
我正在研究我的编译器概念但是我有点困惑...谷歌搜索让我无处可寻.
SLR和LR(0)解析器是同一个吗？如果没有,那么差异是什么？
tem*_*def 226
LR(0)和SLR(1)解析器都是自下而上的定向解析器.这意味着
- 解析器尝试反向应用产品以将输入句子缩减回起始符号(自下而上)
- 解析器从左到右扫描输入(定向)
- 解析器尝试预测应用的减少量,而不必看到所有输入(预测)
LR(0)和SLR(1)都是移位/缩小解析器,这意味着它们通过将输入流放置在堆栈上来处理输入流的令牌,并且在每个点处通过将令牌推入堆栈或者减少某些令牌来移动令牌堆栈顶部的终端和非终端序列返回到一些非终结符号.可以证明,任何语法都可以使用shift/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)解析器的结构,所以它可以更精确地识别某些冲突何时是虚假的.的Linux实用程序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)("广义LR(0)")的新解析算法已经普及.GLR(0)解析器不是试图解决LR(0)解析器中出现的冲突,而是通过并行尝试所有可能的选项来工作.使用一些聪明的技巧,可以使这种方法非常有效地运行许多语法.此外,GLR(0)可以解析任何无上下文语法,甚至是LR(k)解析器无法为任何k解析的语法.其他解析器也能够执行此操作(例如,Earley解析器或CYK解析器),尽管GLR(0)在实践中往往更快.
如果您有兴趣了解更多信息,那么在今年夏天,我会教授一个入门编译器课程,并花了不到两周的时间讨论解析技术.如果您想对LR(0),SLR(1)以及许多其他强大的解析技术进行更严格的介绍,您可能会喜欢我的讲座幻灯片和有关解析的家庭作业.所有课程资料都可以在我的个人网站上找到.
希望这可以帮助!
- 这是一个很好的答案.以非常明确和教育的方式正确回答问题.我在SO上遇到过的最佳答案之一. (21认同)
- @templatetypedef：我认为您应该详细说明 L(AL)R(1) 和 SLR(1) 之间的区别，这就是为什么 SLR(1) 作为一个有趣的选择而存在的原因。但是+1。 (3认同)
除了上述答案之外，自下而上解析器类中各个解析器之间的区别在于它们在生成解析表时是否会导致移位/归约或归约/归约冲突。冲突越少，语法就越强大（LR(0) < SLR(1) < LALR(1) < CLR(1)）。
\n例如，考虑以下表达式语法：
\nE \xe2\x86\x92 E + T
\nE \xe2\x86\x92 T
\nT \xe2\x86\x92 F
\nT \xe2\x86\x92 T * F
\nF \xe2\x86\x92 ( E )
\nF \xe2\x86\x92 id
\n不是 LR(0) 而是 SLR(1)。使用以下代码，我们可以构建 LR0 自动机并构建解析表（我们需要增强语法，使用闭包计算 DFA，计算操作和 goto 集）：
\nfrom copy import deepcopy\nimport pandas as pd\n\ndef update_items(I, C):\n if len(I) == 0:\n return C\n for nt in C:\n Int = I.get(nt, [])\n for r in C.get(nt, []):\n if not r in Int:\n Int.append(r)\n I[nt] = Int\n return I\n\ndef compute_action_goto(I, I0, sym, NTs): \n #I0 = deepcopy(I0)\n I1 = {}\n for NT in I:\n C = {}\n for r in I[NT]:\n r = r.copy()\n ix = r.index(\'.\')\n #if ix == len(r)-1: # reduce step\n if ix >= len(r)-1 or r[ix+1] != sym:\n continue\n r[ix:ix+2] = r[ix:ix+2][::-1] # read the next symbol sym\n C = compute_closure(r, I0, NTs)\n cnt = C.get(NT, [])\n if not r in cnt:\n cnt.append(r)\n C[NT] = cnt\n I1 = update_items(I1, C)\n return I1\n\ndef construct_LR0_automaton(G, NTs, Ts):\n I0 = get_start_state(G, NTs, Ts)\n I = deepcopy(I0)\n queue = [0]\n states2items = {0: I}\n items2states = {str(to_str(I)):0}\n parse_table = {}\n cur = 0\n while len(queue) > 0:\n id = queue.pop(0)\n I = states[id]\n # compute goto set for non-terminals\n for NT in NTs:\n I1 = compute_action_goto(I, I0, NT, NTs) \n if len(I1) > 0:\n state = str(to_str(I1))\n if not state in statess:\n cur += 1\n queue.append(cur)\n states2items[cur] = I1\n items2states[state] = cur\n parse_table[id, NT] = cur\n else:\n parse_table[id, NT] = items2states[state]\n # compute actions for terminals similarly\n # ... ... ...\n \n return states2items, items2states, parse_table\n \nstates, statess, parse_table = construct_LR0_automaton(G, NTs, Ts)\n其中语法G、非终结符和终结符定义如下
\nG = {}\nNTs = [\'E\', \'T\', \'F\']\nTs = {\'+\', \'*\', \'(\', \')\', \'id\'}\nG[\'E\'] = [[\'E\', \'+\', \'T\'], [\'T\']]\nG[\'T\'] = [[\'T\', \'*\', \'F\'], [\'F\']]\nG[\'F\'] = [[\'(\', \'E\', \')\'], [\'id\']]\n以下是我与上述用于 LR(0) 解析表生成的函数一起实现的一些更有用的函数：
\ndef augment(G, S): # start symbol S\n G[S + \'1\'] = [[S, \'$\']]\n NTs.append(S + \'1\')\n return G, NTs\n\ndef compute_closure(r, G, NTs):\n S = {}\n queue = [r]\n seen = []\n while len(queue) > 0:\n r = queue.pop(0)\n seen.append(r)\n ix = r.index(\'.\') + 1\n if ix < len(r) and r[ix] in NTs:\n S[r[ix]] = G[r[ix]]\n for rr in G[r[ix]]:\n if not rr in seen:\n queue.append(rr)\n return S\n下图（展开查看）显示了使用上述代码为语法构建的 LR0 DFA：
\n
下表显示了作为 pandas 数据帧生成的 LR(0) 解析表，请注意，存在一些移位/归约冲突，表明语法不是 LR(0)。
\n
SLR(1) 解析器仅当下一个输入标记是要归约的非终结符的跟随集的成员时才归约，从而避免上述移位/归约冲突。所以上面的语法不是LR(0)，而是SLR(1)。下面的解析表是由SLR生成的：
\n
以下动画显示了上述 SLR(1) 语法如何解析输入表达式：
\n
a^ncb^n, n >= 1但是，以下接受LR(0)形式的字符串的语法：
A \xe2\x86\x92 a A b
\nA \xe2\x86\x92 c
\nS \xe2\x86\x92 A
\n让我们将语法定义如下：
\n# S --> A \n# A --> a A b | c\nG = {}\nNTs = [\'S\', \'A\']\nTs = {\'a\', \'b\', \'c\'}\nG[\'S\'] = [[\'A\']]\nG[\'A\'] = [[\'a\', \'A\', \'b\'], [\'c\']]\n
从下图可以看出，生成的解析表没有冲突。
\n