合并的超前集合如何帮助LALR解析比SLR更多的语法? [英] How do merged lookahead sets help LALR parse more grammars than SLR?
问题描述
根据我到目前为止在Google上搜索的内容，LALR(1)和SLR(1)之间的唯一区别是LALR(1)使用带有合并的超前集合的状态.一位消息人士说，LALR(1)不会发生shift-reduce冲突，因为解析器会记住"它从哪个状态到达当前状态.但是，解析算法没有区别，因此我很难看到这些合并的超前集合将如何帮助LALR解析器解决移位减少冲突.而且，如果解析器还记得它从哪个状态到达当前状态，为什么它仍然容易受到减少-减少冲突的影响?
From what I have searched on Google so far, the only difference between LALR(1) and SLR(1) is that LALR(1) uses states with merged lookahead sets. One source says that LALR(1) won't run into shift-reduce conflicts because the parser will "remember" from which state it arrived at the current state. However, there are no differences in the parsing algorithm, so I'm having trouble seeing how these merged lookahead sets would help the LALR parser resolve shift-reduce conflicts. And if the parser remembers from which state it arrived at the current state, why is it still vulnerable to reduce-reduce conflicts?
推荐答案
实际上是SLR，它使用合并的超前集合.或者，更准确地说，将SLR解析表中每个作品的前瞻集近似为作品中最后一个符号的FOLLOW集，从而有效地忽略了上下文.
It is actually SLR which uses merged lookahead sets. Or, more accurately, the lookahead set for each production in an SLR parse table is approximated as the FOLLOW set for the last symbol in the production, effectively ignoring the context.
LALR解析器已针对规范的LR解析器合并了 states .在LR和LALR中，与SLR相比，准确计算了tbe超前集合，但是在LALR解析器的情况下，状态被合并，因此它具有与tbe SLR解析器相同的状态(但不是相同的超前集合).
LALR parsers have merged states with respect to canonical LR parsers. In both LR and LALR, in contrast to SLR, tbe lookahead sets are computed accurately, but in the case of the LALR parser, the states are merged so that it has the same states (but not the same lookahead sets) as tbe SLR parser.
在Wikipedia中有关SLR解析，LALR解析和Canonical LR解析的文章中有一些合理的讨论.有关更多信息，请参见这些文章的参考.
There is a reasonable discussion of the differences in the Wikipedia articles on SLR parsing, LALR parsing and Canonical LR parsing. See the references for those articles for more information.
无论您使用哪种解析器生成技术，如果语法需要更多的前瞻性，都会出现冲突.例如，以下语法需要两个lokahead符号来决定是移位还是减小NAME:
No matter which parser-generation technique you use, there will be conflicts if the grammar requires more lookahead. For example, the following grammar requires two lokahead symbols to decide whether to shift or reduce a NAME:
prog → λ
prog → prog defn
defn → NAME :
defn → defn NAME
在这里，如果defn的一部分，因此要确定是否要转移NAME，您不仅需要NAME(这是一个前瞻性标记)，而且还需要tge在令牌之后，是第二次超前.
Here, a NAME is part of a defn if it is not followed by a colon, so to decide whether or not to shift a NAME, you need not just the NAME, which is the lookahead token, but also tge following token, the second lookahead.
这是一个非常简单的语法，它不是SLR(1)，可能会阐明使用跟随集的问题. (它直接来自《龙书》，经常被用作说明SLR(1)语法不足的示例):
Here is a very simple grammar which is not SLR(1), which might possibly illuminate the problem with using follow sets. (It comes straight out of the Dragon book, and is often used as an example of why SLR(1) grammars are inadequate):
S → L = R
S → R
L → id
L → * R
R → L
在此，R和L的FOLLOW集相同. R和L都包含=，因为* R = ...是有效的，并且将减小为L = ...，并且显然R和L都可以出现在S的末尾，因此，两个FOLLOW集都包括输入的末尾标记.
Here, the FOLLOW sets of R and L are identical. Both R and L include =, since * R = ... is valid, and will reduce to L = ..., and clearly both R and L can appear at the end of an S, so both FOLLOW sets include the end-of-input marker.
然后的问题是决定是否减少R → L.在L = R中，我们应保持L不变，并移动=.但是FOLLOW设置无济于事，因为R后面可以跟随=.因此，在仅使用FOLLOW集的SLR(1)语法中，状态中存在移位/减少冲突:
The problem then is to decide whether or not to reduce R → L. In L = R, we should leave the L as is and shift the =. But the FOLLOW sets don't help, because R can be followed by =. So in an SLR(1) grammar, which only uses FOLLOW sets, there is a shift/reduce conflict in the state:
S → L • = R
R → L •
在LALR(1)语法中不存在此冲突，因为在该状态下
产品R → L的前瞻集不包括=，因为产品来自项目S → • R，其前瞻是输入结束标记.
This conflict doesn't exist in the LALR(1) grammar because in that state
the lookahead set for the production R → L does not include =, because the production was included from the item S → • R, whose lookahead is the end-of-input marker.
这篇关于合并的超前集合如何帮助LALR解析比SLR更多的语法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
