我正在学习编译器的概念，但是有些困惑......通过谷歌搜索也没有得到明确的答案。
SLR和LR(0)解析器是否相同？如果不同，有什么区别？
LR(0)分析和SLR分析有什么区别？
93
- Nitish Upreti
1
解析算法是相同的。表格是不同的。 - user207421
4个回答
277
LR(0)和SLR(1)解析器均为自底向上、方向性、预测性解析器。这意味着：
- 解析器尝试反向应用产生式，将输入句子还原为起始符号（自底向上）； - 解析器从左到右扫描输入（方向性）； - 解析器试图预测要应用哪些规约，而不一定看到所有的输入（预测性）。
LR(0)和SLR(1)均为移进/归约解析器，这意味着它们通过将输入流的标记放置在栈上来处理标记，并且每次要么通过将标记推送到栈上来移进一个标记，要么通过将栈顶端的一些终结符和非终结符序列归约回某个非终结符号。可以证明，任何文法都可以使用移进/归约解析器自底向上解析，但该解析器可能不是确定性的。也就是说，解析器可能必须“猜测”是否应用移进或归约，并且可能最终不得不回溯以确认其做出了错误的选择。无论您构造多么强大的确定性移进/归约解析器，它永远不能解析所有的文法。
当使用确定性移进/归约解析器来解析它无法处理的文法时，将导致移进/归约冲突或规约/规约冲突，其中解析器可能进入无法确定要执行的操作的状态。在移进/归约冲突中，解析器无法确定是将另一个符号添加到堆栈中，还是对堆栈顶部的符号执行某些规约。在规约/规约冲突中，解析器知道需要用某个非终结符替换堆栈顶部的符号，但无法确定要使用哪个规约。
抱歉如果这篇文章有点冗长，但我们需要了解这一点才能解释LR(0)和SLR(1)解析之间的区别。LR(0)解析器是一个移进/归约解析器，其使用零个标记向前查看来确定要采取的操作（因此为0）。这意味着在解析器的任何配置中，解析器必须具有明确的动作选择-要么移进特定符号，要么应用特定规约。如果有两个或更多选择要做，解析器将失败，我们说该文法不是LR(0)。回想一下，两种可能的LR冲突是shift/reduce和reduce/reduce。在这两种情况下，LR(0)自动机至少可以采取两个行动，它无法确定使用哪一个。由于至少有一个冲突操作是规约，一个合理的攻击方式是尝试让解析器在执行特定规约时更加小心。更具体地说，假设允许解析器查看输入的下一个标记来确定是移进还是规约。如果我们仅允许解析器在“有意义”时进行规约（对于“有意义”的某种定义），那么我们可能可以通过使自动机明确选择在特定步骤中移进或规约来消除冲突。
在SLR(1)（“简化LR(1)”）中，解析器在决定是否应该移进或规约时被允许查看一个标记的展望。特别地，当解析器想要尝试规约形式为A→w（对于非终端A和字符串w）的内容时，它会查看输入的下一个标记。如果该标记可以在某个派生中合法地出现在非终端A之后，则解析器进行规约。否则，它不这样做。这里的直觉是，在某些情况下，试图进行规约是没有意义的，因为鉴于到目前为止我们已经看到的标记和即将出现的标记，规约永远不可能是正确的。
LR(0)和SLR(1)之间唯一的区别在于当存在冲突时帮助决定采取哪个行动的额外能力。由于这个原因，任何可以由LR(0)解析器解析的语法都可以由SLR(1)解析器解析。然而，SLR(1)解析器可以解析比LR(0)更多的语法。
实际上，SLR(1)仍然是一种相对较弱的分析方法。更常见的是使用LALR(1)（“向前看LR(1)”）解析器。它们也通过尝试解决LR(0)解析器中的冲突来工作，但是它们用于解决冲突的规则比SLR(1)使用的规则要精确得多，因此LALR(1)可以解析比SLR(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）通常不在实践中使用，而是改用LALR（1）或SLR（1）等较弱的解析器。
- 解析器尝试反向应用产生式，将输入句子还原为起始符号（自底向上）； - 解析器从左到右扫描输入（方向性）； - 解析器试图预测要应用哪些规约，而不一定看到所有的输入（预测性）。
LR(0)和SLR(1)均为移进/归约解析器，这意味着它们通过将输入流的标记放置在栈上来处理标记，并且每次要么通过将标记推送到栈上来移进一个标记，要么通过将栈顶端的一些终结符和非终结符序列归约回某个非终结符号。可以证明，任何文法都可以使用移进/归约解析器自底向上解析，但该解析器可能不是确定性的。也就是说，解析器可能必须“猜测”是否应用移进或归约，并且可能最终不得不回溯以确认其做出了错误的选择。无论您构造多么强大的确定性移进/归约解析器，它永远不能解析所有的文法。
当使用确定性移进/归约解析器来解析它无法处理的文法时，将导致移进/归约冲突或规约/规约冲突，其中解析器可能进入无法确定要执行的操作的状态。在移进/归约冲突中，解析器无法确定是将另一个符号添加到堆栈中，还是对堆栈顶部的符号执行某些规约。在规约/规约冲突中，解析器知道需要用某个非终结符替换堆栈顶部的符号，但无法确定要使用哪个规约。
抱歉如果这篇文章有点冗长，但我们需要了解这一点才能解释LR(0)和SLR(1)解析之间的区别。LR(0)解析器是一个移进/归约解析器，其使用零个标记向前查看来确定要采取的操作（因此为0）。这意味着在解析器的任何配置中，解析器必须具有明确的动作选择-要么移进特定符号，要么应用特定规约。如果有两个或更多选择要做，解析器将失败，我们说该文法不是LR(0)。回想一下，两种可能的LR冲突是shift/reduce和reduce/reduce。在这两种情况下，LR(0)自动机至少可以采取两个行动，它无法确定使用哪一个。由于至少有一个冲突操作是规约，一个合理的攻击方式是尝试让解析器在执行特定规约时更加小心。更具体地说，假设允许解析器查看输入的下一个标记来确定是移进还是规约。如果我们仅允许解析器在“有意义”时进行规约（对于“有意义”的某种定义），那么我们可能可以通过使自动机明确选择在特定步骤中移进或规约来消除冲突。
在SLR(1)（“简化LR(1)”）中，解析器在决定是否应该移进或规约时被允许查看一个标记的展望。特别地，当解析器想要尝试规约形式为A→w（对于非终端A和字符串w）的内容时，它会查看输入的下一个标记。如果该标记可以在某个派生中合法地出现在非终端A之后，则解析器进行规约。否则，它不这样做。这里的直觉是，在某些情况下，试图进行规约是没有意义的，因为鉴于到目前为止我们已经看到的标记和即将出现的标记，规约永远不可能是正确的。
LR(0)和SLR(1)之间唯一的区别在于当存在冲突时帮助决定采取哪个行动的额外能力。由于这个原因，任何可以由LR(0)解析器解析的语法都可以由SLR(1)解析器解析。然而，SLR(1)解析器可以解析比LR(0)更多的语法。
实际上，SLR(1)仍然是一种相对较弱的分析方法。更常见的是使用LALR(1)（“向前看LR(1)”）解析器。它们也通过尝试解决LR(0)解析器中的冲突来工作，但是它们用于解决冲突的规则比SLR(1)使用的规则要精确得多，因此LALR(1)可以解析比SLR(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）通常不在实践中使用，而是改用LALR（1）或SLR（1）等较弱的解析器。
最近，一种名为GLR(0)（“广义LR(0)”）的新解析算法变得越来越受欢迎。与尝试解决LR(0)解析器中出现的冲突不同，GLR(0)解析器通过并行尝试所有可能的选项来工作。使用一些聪明的技巧，这可以使许多语法非常高效地运行。此外，GLR(0)可以解析任何上下文无关文法，即使是任何k的LR(k)解析器也无法解析的文法。其他解析器也能够做到这一点（例如Earley解析器或CYK解析器），但在实践中GLR(0)往往更快。
如果您有兴趣了解更多信息，去年夏天我教授了一门入门级编译器课程，并花了将近两个星期讨论解析技术。如果您想要更严格的LR(0)、SLR(1)和其他强大的解析技术介绍，您可能会喜欢我的关于解析的演讲幻灯片和作业。所有课程材料都可以在我的个人网站上找到。
- templatetypedef
12
26这是一份出色的回答。非常清晰地并以具有启发性的方式回答了问题。这是我在SO上遇到的最好的答案之一。 - NealB
3我认为你应该详细阐述L(AL)R(1)和SLR(1)之间的区别，这也是为什么SLR(1)成为了一个有趣的选择。但是+1。 - Ira Baxter
非常好的回答。对主题进行了非常清晰的解释。一定会听你的讲座。 - anni
1@新手 LR(0) 解析器确实有一个 ACTION 表，但是动作纯粹取决于状态，而不是状态加上下一个标记。 - templatetypedef
1@新手 你提供的项目是一个reduce项目。这个状态的ACTION条目将被缩减。 - templatetypedef
显示剩余7条评论
5
除了以上的答案之外，自下而上解析器类别中每个单独解析器的区别在于生成解析表时是否会出现移进/规约或规约/规约冲突。冲突越少，语法就越强大（LR(0) < SLR(1) < LALR(1) < CLR(1)）。
例如，考虑以下表达式语法：
E → E + T
E → T
T → F
T → T * F
F → (E)
F → id
它不是LR(0)，但是是SLR(1)。使用以下代码，我们可以构建LR0自动机并构建解析表（我们需要扩充语法，计算具有闭包的DFA，计算操作和转移集合）。
"其中语法G、非终止符和终止符号的定义如下："
这里还有一些我为LR(0)分析表生成实现的有用函数：
下图（展开查看）显示了使用上述代码构建的LR0 DFA用于语法分析：
A → aAb
A → c
S → A
让我们定义这个语法：
例如，考虑以下表达式语法：
E → E + T
E → T
T → F
T → T * F
F → (E)
F → id
它不是LR(0)，但是是SLR(1)。使用以下代码，我们可以构建LR0自动机并构建解析表（我们需要扩充语法，计算具有闭包的DFA，计算操作和转移集合）。
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用于语法分析：
a^ncb^n，n≥1的字符串的以下语法是LR（0）：A → aAb
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']]
- Sandipan Dey
1
1这应该是被接受的答案。 - Sunfline
2
以下是我学到的内容。通常LR(0)分析器可能存在歧义，即表格中的一个框可以有多个值（或者更好地说：该分析器导致具有相同输入的两个最终状态）。因此创建SLR分析器以消除这种歧义。为了构建它，请找出所有导致转移状态的产生式，找出左侧产生式符号的Follow集，并仅包括那些在Follow集中出现过的转移状态。这反过来意味着您不会包括使用原始语法不可能的产生式（因为该状态不在Follow集中）。
- Yeswantth
1
在LR(0)的分析表中，产生式的规约规则被放置在整个行中，跨越所有终端符，而在SLR分析表中，产生式的规约规则仅放置在规约产生式左侧非终结符的Follow集中。
名为parsing-EMU的工具在解析方面非常有用，可以生成first、follow、LR(0)项集、LALR评估等。你可以在这里找到它。
名为parsing-EMU的工具在解析方面非常有用，可以生成first、follow、LR(0)项集、LALR评估等。你可以在这里找到它。
- Srinath M P
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接