parsing - 哪些语法可以使用递归下降而不回溯来解析？

Question

根据 "Recursive descent parser" on Wikipedia ，没有回溯的递归下降(又名预测解析)只适用于 LL(k) 文法。

在其他地方，我读到 Lua 的实现使用了这样的解析器。但是，语言不是 LL(k)。实际上，Lua 本质上是模棱两可的: a = f(g)(h)[i] = 1 是指 a = f(g); (h)[i] = 1 还是 a = f; (g)(h)[i] = 1 ？这种歧义是通过解析器中的贪婪来解决的(因此上面的内容被解析为错误的 a = f(g)(h)[i]; = 1 )。

这个例子似乎表明预测解析器可以处理不是 LL(k) 的语法。事实上，他们真的可以处理 LL(k) 的超集吗？如果是这样，有没有办法找出给定的语法是否在这个超集中？

换句话说，如果我正在设计一种我想使用预测解析器来解析的语言，我是否需要将该语言限制为 LL(k)？或者我可以申请更宽松的限制吗？

Answer 1

TL; 博士

对于递归下降解析器的合适定义，只有 LL(k) 语言 可以通过递归下降进行解析是绝对正确的。

Lua 可以用递归下降解析器解析，正是因为 语言 是 LL(k)；也就是说，Lua 存在一个 LL(k) 文法。 [注1]

1. LL(k) 语言可能有非 LL(k) 文法。

如果存在识别该语言的 LL(k) 语法，则该语言是 LL(k)。这并不意味着每个识别语言的语法都是 LL(k)；可能有任意数量的非 LL(k) 语法可以识别该语言。因此，某些语法不是 LL(k) 的事实绝对不能说明语言本身。

2. 许多实用的编程语言都是用歧义的语法来描述的。

在形式语言理论中，只有当语言的每个语法都是二义性时，语言才是 inherently ambiguous。可以肯定地说，没有实用的编程语言本质上是模棱两可的，因为实用的编程语言是确定性解析的(以某种方式)。 [笔记2]。

因为编写严格无歧义的语法可能很乏味，所以语言文档提供歧义语法以及指示如何解决歧义的文本 Material 是很常见的。

例如，许多语言(包括 Lua)都使用不明确包含运算符优先级的语法来记录，从而允许表达式的简单规则:

exp ::= exp Binop exp | Unop exp | term

该规则显然是有歧义的，但是给定一个运算符列表、它们的相对优先级以及每个运算符是左关联还是右关联的指示，该规则可以机械地扩展为一个明确的表达式语法。事实上，许多解析器生成器允许用户单独提供优先级声明，并在生成解析器的过程中进行机械扩展。应该注意的是，生成的解析器是用于消除歧义的语法的解析器，因此原始语法的歧义并不意味着解析算法能够处理歧义语法。

另一个可以机械消除歧义的歧义引用语法的常见例子是 "dangling else" 歧义在像 C 这样的语言中发现(但不是在 Lua 中)。语法:

if-statement ::= "if" '(' exp ')' stmt
               | "if" '(' exp ')' stmt "else" stmt

肯定是模棱两可的；目的是使解析“贪婪”。同样，歧义不是固有的。有一个机械转换可以产生一个明确的语法，如下所示:

matched-statement ::= matched-if-stmt | other-statement
statement         ::= matched-if-stmt | unmatched-if-stmt
matched-if-stmt   ::= "if" '(' exp ')' matched-statement "else" matched-statement 
unmatched-if-stmt ::= "if" '(' exp ')' statement
                    | "if" '(' exp ')' matched-statement "else" unmatched-if-stmt

解析器生成器隐式地执行这种转换是很常见的。 (对于 LR 解析器生成器，转换实际上是通过删除与 shift 操作冲突的 reduce 操作来实现的。这比转换语法更简单，但效果完全相同。)

所以 Lua(和其他编程语言)本质上并不是模棱两可的；因此它们可以用需要明确确定性解析器的解析算法来解析。事实上，有些语言的每一种可能的语法都是模棱两可的，这甚至可能有点令人惊讶。正如上面引用的维基百科文章所指出的，1961 年 Rohit Parikh 证明了这种语言的存在；固有歧义的上下文无关语言的一个简单示例是
{anbmcmdn|n,m≥0} ∪ {anbncmdm|n,m≥0}。

3. Lua赋值和函数调用语句的贪婪LL(1)解析

与上面的悬空 else 构造一样，Lua 语句序列的消歧是通过只允许贪婪解析来执行的。直观地说，这个过程很简单；它基于禁止两个连续的语句(不插入分号)，其中第二个语句以可能继续第一个的标记开头。

在实践中，实际上并没有必要执行这种转换；它可以在解析器的构建过程中隐式完成。所以我不会在这里费心生成一个完整的 Lua 语法。但我相信这里 Lua 语法的一小部分足以说明转换是如何工作的。

以下子集(主要基于引用语法)准确地展示了 OP 中指出的歧义:

program        ::= statement-list
statement-list ::= Ø
                 | statement-list statement
statement      ::= assignment | function-call | block | ';'
block          ::= "do" statement-list "end"
assignment     ::= var '=' exp
exp            ::= prefixexp                          [Note 3]
prefixexp      ::= var | '(' exp ')' | function-call
var            ::= Name | prefixexp '[' exp ']'
function-call  ::= prefixexp '(' exp ')'

(注意:(我使用 Ø 来表示空字符串，而不是 ε 、 λ 或 %empty 。)

Lua 语法 as 是左递归的，所以它显然不是 LL(k)(与歧义无关)。去除左递归可以机械地完成；为了证明子集是 LL(1)，我在这里已经做了足够多的工作。不幸的是，转换后的文法没有保留解析树的结构，这是 LL(k) 文法的经典问题。在递归下降解析过程中重建正确的解析树通常很简单，我不打算详细介绍。

提供 exp 的 LL(1) 版本很简单，但结果消除了 var(可以分配给)和 function-call(不能)之间的区别:

exp          ::= term exp-postfix
exp-postfix  ::= Ø
               | '[' exp ']' exp-postfix
               | '(' exp ')' exp-postfix 
term         ::= Name | '(' exp ')' 

但是现在我们需要重新创建区别，以便能够解析赋值语句和函数调用。这是直截了当的(但不会促进对语法的理解，恕我直言):

a-or-fc-statement ::= term a-postfix
a-postfix         ::= '=' exp 
                    | ac-postfix
c-postfix         ::= Ø
                    | ac-postfix
ac-postfix        ::= '(' exp ')' c-postfix
                    | '[' exp ']' a-postfix

为了使贪婪解析没有歧义，我们需要禁止(从语法上)任何 S1 S2 的出现，其中 S1 以 exp 和 S2 结尾，我们需要区分不同类型的 ',关于语句是否以 ( 开头，以及独立地，语句是否以 exp 结尾。(实际上只有三种类型，因为没有以 0x2518122313 do43141 和 an1331313313131331331331341 开头的语句. [注4])

statement-list ::= Ø
                 | s1 statement-list
                 | s2 s2-postfix
                 | s3 s2-postfix
s2-postfix     ::= Ø
                 | s1 statement-list
                 | s2 s2-postfix
s1             ::= block | ';'
s2             ::= Name a-postfix
s3             ::= '(' exp ')' a-postfix

4. 什么是递归下降解析，如何修改它以包含消歧？

在最常见的用法中，预测递归下降解析器是 LL(k) 算法的一种实现，其中每个非终结符都映射到一个过程。每个非终结符过程首先使用一个长度为 ( 的可能的前瞻序列表来决定该非终结符使用哪个替代产生式，然后简单地一个符号“执行”产生式:终结符导致下一个输入符号匹配则丢弃，不匹配则报错；非终端符号导致非终端过程被调用。

可以使用 FIRSTk 和 FOLLOWk 集构建先行序列表。 (产生式 exp 映射到终端序列 k 如果 A→ω 。) [注 5]

有了递归下降解析的这个定义，递归下降解析器可以精确地处理 LL(k) 语言。 [注6]

然而，LL(k) 和递归下降解析器的对齐忽略了递归下降解析器的一个重要方面，即它首先是一个通常用某种图灵完备编程语言编写的程序。如果允许该程序稍微偏离上述严格结构，它可以解析更大的语言集，甚至是非上下文无关的语言。 (例如，参见注释 2 中引用的 C 上下文敏感性。)

特别是，将“默认”规则添加到映射前瞻到产生式的表中非常容易。这是一个非常诱人的优化，因为它大大减少了前瞻表的大小。通常，默认规则用于非终结符，其替代项包括一个空的右侧，在 LL(1) 语法的情况下，它将映射到非终结符的 FOLLOW 集中的任何符号。在该实现中，前瞻表仅包括来自第一个集合的前瞻，并且解析器自动为任何其他符号生成一个空的右侧，对应于立即返回。 (与 LR(k) 解析器中的类似优化一样，这种优化可以延迟错误的识别，但在读取额外的标记之前仍然可以识别它们。)

LL(1) 解析器不能包含其 FIRST 和 FOLLOW 集包含公共(public)元素的可空非终结符。但是，如果递归下降解析器使用“默认规则”优化，那么在解析器的构建过程中将永远不会注意到该冲突。实际上，忽略冲突允许从(某些)非确定性文法构建“贪婪”解析器。

这是非常方便的，因为正如我们在上面看到的，产生明确的贪婪语法需要大量的工作，并且不会导致任何甚至模糊地类似于语言的清晰阐述的东西。但是修改后的递归解析算法并没有更强大；它只是解析等效的 SLL(k) 语法(没有实际构建该语法)。

我不打算提供上述断言的完整证明，但第一步是观察任何非终结符都可以重写为新非终结符的析取，每个非终结符都有一个单独的 FIRST 标记，可能还有一个新的右侧为空的非终结符。然后“仅”需要通过创建新的析取从 FOLLOW 可空非终结符集合中删除非终结符。

笔记

在这里，我谈论的是在标记化流上运行的语法，其中删除了注释，并将其他结构(例如由“长括号”分隔的字符串)简化为单个标记。如果没有这种转换，语言就不会是 LL(k)(因为注释——可以任意长——会干扰前瞻标记的可见性)。这让我也可以回避使用 LL(k) 语法可以识别多长时间括号的问题，这与这个问题并不特别相关。

有些编程语言无法通过上下文无关文法进行确定性解析。最臭名昭著的例子可能是 Perl，但也有著名的 C 构造 α，它只能使用有关符号 α ∈ FIRSTk(ω FOLLOWk(A)) 的信息进行确定性解析——无论是变量名还是类型别名——以及正确解析的困难解析涉及模板的 C++ 表达式。 (例如，参见问题 Why can't C++ be parsed with a LR(1) parser? 和 Is C++ context-free or context-sensitive?)

为简单起见，我删除了各种文字常量(字符串、数字、 bool 值等)以及表构造函数和函数定义。这些标记不能作为函数调用的目标，这意味着以这些标记之一结尾的表达式不能用带括号的表达式进行扩展。删除它们可以简化消除歧义的说明；该过程仍然可以使用完整的语法，但更加乏味。

对于完整的语法，我们还需要考虑不能用 (x)*y 扩展的表达式，因此将有四个不同的选项。

存在确定性 LL(k) 语法无法使用该算法生成明确的解析表，Sippu & Soisalon-Soininen 将其称为 Strong LL(k) 算法。可以使用额外的解析状态来扩充算法，类似于 LR(k) 解析器中的状态。这对于特定的语法可能很方便，但它不会改变 LL(k) 语言的定义。正如 Sippu & Soisalon-Soininen 所证明的那样，可以从任何 LL(k) 文法机械地推导出 SLL(k) 文法，它产生完全相同的语言。 (参见第 2 卷中的定理 8.47)。

递归定义算法是基于规范堆栈的LL(k)解析器的精确实现，其中解析器堆栈是在解析器执行期间使用当前延续和事件记录堆栈的组合隐式构造的。