yacc/bison LALR（1）算法如何处理“空”规则？

在LALR（1）语法分析器中，语法中的规则被转换为一个分析表，它有效地表示“如果你有这个输入，并且前瞻记号是X，那么转移到状态Y或者按规则减少R”。yacc/bison LALR（1）算法如何处理“空”规则？

我已经成功构建了解释语言（ruby）中的LALR（1）解析器，不使用生成器，但在运行时计算解析表并使用该解析表评估输入。这种方式出人意料地出色，表格生成相当简单（这让我感到很吃惊），支持自我引用规则和左/右关联。

但是，我有一点难以理解的是yacc/bison在概念上如何处理空白规则定义。我的解析器无法处理它们，因为在生成表格时，它会递归地查看每个规则中的每个符号，而“空白”不是来自词法分析器的东西，也不会被规则所减少。那么，LALR（1）解析器如何处理空的规则呢？他们是专门对待它，还是一个有效的算法应该适用的“自然”概念，甚至不需要特别意识到这样的概念？

比方说，一个规则可以与任何中间匹配任意数量成对的括号：

expr: /* empty */ 
     | '(' expr ')' 
     ;

输入类似下面将匹配这条规则：

((((()))))

这意味着在阅读'（'和'看'）'，在分析器选择：解析器选择：

移动'）'（不可能）
根据一些规则（不可能）
别的东西减少输入...

不太适合“移”或“减少”的核心算法。解析器实际上不需要将任何东西移到堆栈上，将“无”减少到expr，然后移动下一个标记')'，给出'(' expr ')'，当然这减少到expr，依此类推。

这是“没有任何变化”，令我困惑。分析表如何传达这样的概念？还要考虑到应该可以调用一些语义操作，该操作返回值为$$以减少空值，因此，从分析表跳过该操作并且在堆栈中指示'('和')'处于前瞻状态的相当简单的视图应该是只是简单地转换为转换，不会真正产生序列'(' expr ')'，但只会产生序列'(' ')'。

来源

2011-11-23 d11wtq

我确信[龙书]（http://en.wikipedia.org/wiki/Compilers:_Principles,_Techniques,_and_Tools）中有关于处理这些规则的部分很长。我不认为Stack Overflow是讨论它的正确场所 - 也许是程序员？ –

感谢您对本书的建议......现在查看该链接。 Stackoverflow似乎是对我来说合适的地方。这是关于算法的直接问题，而不是主观讨论。有人可以很好地寻找这个，如果有人知道答案，快速解决。 – d11wtq

我想我其实只是想到了这一点，当一个基本点出现在我身上时，它是如此明显而直截了当。将回答问题，因为谷歌搜索什么都没有，这是一个相当自然的问题;） – d11wtq

尽管想了很多天，但在写这个问题时以及在接下来的几分钟里思考这个问题，有些事情让我觉得非常明显和简单。

减少所有规则总是：从堆栈中弹出X个输入，其中X是规则中组件的数量，然后将结果移回堆栈并转到该表中给出的任何状态。

在空规则的情况下，您不需要考虑“空”甚至是一个概念。解析表只需要包含一个转换，它表示“在堆栈上给出'('和'在前瞻中不是'('的任何东西，减少'空'规则”。现在由于空规则的大小为零，从堆栈中弹出零意味着堆栈不会改变，那么当没有减少任何东西的结果转移到堆栈上时，您正在查看确实出现在堆栈中的东西语法，一切都变得清晰。

Stack  Lookahead Remaining Input  Action 
-------------------------------------------------------------- 
$   (   ())$     Shift '(' 
$(   (   ))$     Shift '(' 
$((  )   )$     Reduce by /* empty */ 
$((expr )   )$     Shift ')' 
$((expr) )   $     Reduce by '(' expr ')' 
$(expr  )   $     Shift ')' 
$(expr)  $         Reduce by '(' expr ')' 
$expr           Accept

它“正常工作”的原因是因为为了减少空规则，您只需从堆栈中弹出零项。

来源

2011-11-23 13:43:07 d11wtq

它也证明，在我的解析器中对DSL的轻微更改使这项工作...零规则组件和一个空规则组件字符串是两个非常不同的东西。 – d11wtq

另一种观点来也许圆了d11wtq最伟大的回答，如果可能的话：

的可空规则（一个派生ε）下的功能FOLLOW(X)和FIRST(X)解析器建设过程中考虑。例如，如果您有A -> B x，并且B可以导出ε，那么我们必须在由FIRST(A)计算的集合中包含x。并在设置FOLLOW(B)。

此外，空规则很容易在规范LR(1)项目集中表示。

一个有用的事情是想象有一个额外的非终结符号$它代表文件的结尾。

让我们的语法：

S -> X | ϵ 
X -> id

对于第一个规范LR(1)项集，我们可以采取先LR(0)项目设置与符号“$”添加前瞻：

S -> . X , '$' 
S -> .  , '$' 
X -> . id , '$'

然后我们有一个用于预测的是id：

S -> . X , 'id' 
S -> .  , 'id 
X -> . id , 'id'

现在让我们来看看FIRST和FOLLOW集：

S -> . X , '$'

这是不是“最后点”项目，所以这里要调换，但前提是一套FIRST(X)包含我们向前看符号$。这是错误的，所以我们不填写表格条目。

S -> .  , '$'

这是一个 “点最终” 项目，所以想减少。为了验证上下文的缩减，我们看看FOLLOW(S)：我们希望减少的语法符号可以跟在前面的内容之后吗？完全同意。 $始终在FOLLOW(S)之间，因为开始符号在定义之后是输入的结尾。所以是的，我们可以减少。并且由于我们正在减少符号S，因此reduce实际上是一个accept操作：解析结束。我们使用accept操作填写表格条目。

同样，我们可以重复下一个项目集，向前看id。让我们跳到S-获得空规则：

S -> .  , 'id'

可以S跟着id？几乎不。所以这种减少是不合适的。我们不填充解析器表项。

所以你可以看到一个空的规则没有问题。它立即变成点最后的LR(0)或LR(1)项目（取决于解析器构造方法），并且在考虑前瞻性和填充表格方面与其他任何点最终项目相同。

来源

2012-04-24 00:02:09 Kaz

yacc/bison LALR（1）算法如何处理“空”规则？

回答

相关问题