下载掌阅APP，畅读海量书库
立即打开
在本节中，我们讨论Earley解析算法（1970），这是Lark使用的默认算法。该算法的强大之处在于可以处理任何上下文无关文法，这使得它易于使用，但它不是一种特别高效的解析算法。对于二义性文法，Earley算法的时间复杂度是 O （ n 3 ），对于无二义性文法是 O （ n 2 ），其中 n 是输入字符串中的记号个数（Hopcroft，Motwani，and Ullman 2006）。在3.6节中，我们将学习LALR（1）算法，它更高效，但不能处理所有的上下文无关文法。
可以将Earley算法看作一个解释器：它将文法视为被解释的程序，并将要解析的程序的具体语法视为其输入。Earley算法使用一种称为 图表 的数据结构来跟踪其进展并存储结果。图表是一个数组，对于输入字符串中的每个位置都有一个槽，其中位置0在第一个字符之前，位置 n 紧接在最后一个字符之后。因此，对于长度为 n 的输入字符串，数组的长度为 n +1。图表中的每个槽都包含一组 带点规则 。带点规则即在右部有句点的文法规则，句点用来标识规则的右部有多少已经被解析。例如，带点规则
表示已完成部分解析，即后跟"+"的exp部分已得到匹配，但尚未解析exp式中"+"右边的部分。Earley算法从初始化阶段开始，然后只要机会出现就重复三个动作——预测、扫描和完成。我们在一个运行示例上演示Earley算法，解析下面的程序：
算法的初始化阶段为左侧是起始符号的所有文法规则创建带点规则，并将它们放置在图表的槽0中，我们还将带点规则的起始位置记录在右侧的括号中。例如，对于图3.3中的文法，我们将
放置在图表的槽0中。然后，该算法继续进行预测操作，根据句点后立即出现的非终结符，在图表中添加更多的带点规则。在上面的带点规则中，非终结符stmt_list出现在句点之后，因此我们将stmt_list的所有规则添加到槽0中，在这些规则的右部的开头有一个句点，如下所示：
随着更多机会的出现，我们继续预测行动。例如，现在非终结符stmt出现在句点之后，因此stmt的所有带点规则会被添加进来。
这揭示了更多的预测机会，因此，我们又将exp和exp_hi的文法规则添加到槽0中。
我们已经完成了当前的预测，因此算法继续扫描。在扫描过程中，检查下一个输入记号，并在当前位置寻找一个带点规则，该规则在句点之后跟随有一个与当前输入记号匹配的终结符。在我们的运行示例中，第一个输入记号是"print"，因此我们在图表的槽0中识别句点后立即跟随"print"的规则：
我们将句点向前移动到"print"之后，并将结果规则添加到槽1中：
如果新的带点规则在句点之后是一个非终结符，我们将需要执行预测操作，在槽1中添加更多的带点规则。事实并非如此，所以我们继续扫描。下一个输入记号是"（"，因此我们将以下内容添加到图表的槽2中。
现在，在句点后面紧跟着一个非终结符，所以需要执行几个预测操作，将exp和exp_hi的带点规则添加到槽2中，句点在规则的开头，规则的起始位置为2。
完成此预测后，继续扫描，注意下一个输入记号是"1"，lexer将其解析为INT。在槽2中有一个匹配规则：
因此，我们向前移动句点，并将下面的规则加入槽3中。
此时，我们将采取“完成”动作。当句点到达带点规则的末尾时，已经识别出子字符串与规则左侧的非终结符匹配，在本例中为exp_hi。因此，对于槽2（2是已完成规则的起始位置）中存在的任何句点之后紧接着exp_hi的带点规则，我们需要将该句点向前移动。因此，我们发现：
并将下面的带点规则加入槽3中：
这将触发对于非终结符exp的另一个“完成”动作，然后再向槽3中添加下面的两条带点规则。
然后，继续扫描，下一个输入记号是"+"，因此，我们将下面的规则添加到槽4中。
句点位于非终结符exp_hi之前，因此预测的结果是将以下带点规则添加到图表的槽4中。
下一个输入记号是"3"，lexer将其归类为INT，因此，对于槽4中句点之后是INT的规则（只有一个），将句点向前移动到INT之后，并将以下内容放入槽5中。
句点在规则末尾，将触发槽4中的规则采取“完成”动作，在槽4中，有一个句点出现在exp_hi之前的规则。因此，我们将句点向前移动，并将以下内容放入槽5中。
这将触发另一个对于槽2中exp的“完成”动作，对于槽2中句点在exp之前的规则，将句点向前移动到exp之后。
扫描下一个输入记号"）"，将下面的带点规则放入槽6中。
这触发对于槽0中stmt的“完成”动作。
最后一个输入记号是换行符（NEWLINE），因此我们向前移动句点，并将新的带点规则放入槽7中。
我们即将结束对输入的解析！句点出现在非终结符stmt_list之前，因此我们可先后对stmt_list和stmt应用预测。
有机会立即“完成”stmt_list，因此我们将以下内容添加到插槽7中。
这触发对于槽0中stmt_list的另一个“完成”动作。
这又进一步“完成”了文法的起始符号lang_int，从而完成了对输入的解析。
作为参考，下面给出Earley算法的一般描述。
1.算法首先使用起始符号的文法规则初始化图表的槽0，在右侧的开始处放置一个句点，并将其起始位置记录为0。
2.只要有机会，算法就会重复应用以下三种动作。
●预测：如果槽 k 中有一条规则的句点在非终结符之前，则将该非终结符的规则添加到槽 k 中，在其右侧的开头放置一个句点，并将其起始位置记录为 k 。
●扫描：如果输入字符串的位置 k 处的记号与图表槽 k 中带点规则中句点后的符号匹配，则将带点规则中的句点向前移动，将结果添加到槽 k +1。
●完成：如果槽 k 中的带点规则的句点在末尾（已完成规则），则检查与该已完成规则的起始位置对应的槽中的规则。如果这些规则中的任何一个在其句点后面有一个与已完成规则的左侧相匹配的非终结符，则将其句点向前移动，并将新的带点规则放在槽 k 中。
在重复这三个操作时，请注意不要在图表中添加重复的带点规则。
我们已经描述了Earley算法如何识别输入字符串与文法的匹配，但我们还没有描述它如何构建解析树。基本思想很简单，但以有效的方式构建解析树更为复杂，需要一种称为 共享压缩解析林 的数据结构（Tomita 1985）。简单的想法是为图表中的每个带点规则附加一个部分解析树。最初，与带点规则关联的节点没有子节点。随着句点向右移动，解析过程中产生的节点将作为子节点添加到节点中。
如本节开头所述，Earley算法对于无二义性文法的时间复杂度是 O （ n 2 ），这意味着它可以在合理的时间内解析包含数千个记号的输入文件，但不能解析数百万个记号的。下一节，我们讨将论LALR（1）解析算法，该算法即使对于最大的输入文件也足够有效。