哪些文法可以在不回溯的情况下使用递归下降来解析？
Which grammars can be parsed using recursive descent without backtracking?
根据 "Recursive descent parser" on Wikipedia，没有回溯的递归下降（a.k.a。预测分析）仅适用于 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)？还是我可以申请更宽松的限制？
TL;DR
对于什么是递归下降解析器的suitable定义，只有LL(k)languages可以被递归下降解析是绝对正确的。
Lua 可以用递归下降解析器解析，正是因为 language 是 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
肯定是模棱两可的；目的是解析为 "greedy"。同样，歧义不是固有的。有一个产生明确语法的机械转换，如下所示：
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 parser generator，转换实际上是通过删除与shift动作冲突的reduce动作来实现的。这比转换语法更简单，但效果完全一样。）
所以Lua（和其他编程语言）本质上不是模棱两可的；因此，可以使用需要明确的确定性解析器的解析算法来解析它们。事实上，有些语言的 所有可能的语法 都是模棱两可的，这甚至有点令人惊讶。正如上面引用的维基百科文章中指出的那样，Rohit Parikh 在 1961 年证明了此类语言的存在；一个本质上模棱两可的上下文无关语言的简单例子是
{a<sup>n</sup>b<sup>m</sup>c<sup>m</sup>d<sup>n</sup>|n,m≥0}∪{a<sup>n</sup>b<sup>n</sup>c<sup>m</sup>d<sup>m</sup>|n,m≥0}.
3。贪心 LL(1) 解析 Lua 赋值和函数调用语句
与上面的悬挂 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 文法是左递归的，所以它显然不是 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
为了使贪心解析明确无误，我们需要禁止（从语法中）出现任何 S<sub>1</sub> S<sub>2 </sub> 其中 S<sub>1</sub> 以 exp 和 S<sub>2</sub>以'('开头。实际上，我们需要根据语句是否以(开头来区分不同类型的语句，以及独立地，语句是否以 exp 结尾。（实际上，只有三种类型，因为没有以 ( 开头且不以 exp 结尾的语句.[注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) 算法的一种实现，其中每个非终结符都映射到一个过程。每个非终端过程首先使用长度为 k 的可能前瞻序列的 table 来决定该非终端使用哪个替代产生式，然后简单地 "executes" 产生式符号symbol: 终结符号如果匹配则丢弃下一个输入符号，如果不匹配则报错；非终端符号导致调用非终端过程。
前瞻序列的table可以使用FIRSTk和FOLLOW[=构造186=]k套。 （如果 α ∈ <i>FIRST</i><sub>k</sub>，则产生式 <code>A→ω 映射到终端序列 α (ωFOLLOWk(A)).) [注5]
有了这个递归下降解析的定义，递归下降解析器就可以精确地处理 LL(k) 语言。 [注6]
然而，LL(k) 和递归下降解析器的对齐忽略了递归下降解析器的一个重要方面，即它首先是一个 程序通常用某种图灵完备的编程语言编写。如果允许该程序稍微偏离上述严格的结构，它就可以解析更多的语言，甚至是非上下文无关的语言。 （例如，参见注释 2 中引用的 C 上下文敏感性。）
特别是，很容易将 "default" 规则添加到 table 映射前瞻到产品。这是一个非常诱人的优化，因为它大大减少了前瞻 table 的大小。通常，默认规则用于非终结符，其替代项包括一个空的右侧，在 LL(1) 文法的情况下，它将映射到 FOLLOW[=166= 中的任何符号] 设置为非终端。在该实现中，前瞻 table 仅包括来自 FIRST 集合的前瞻，并且解析器自动生成一个空的右侧，对应于立即 return , 对于任何其他符号。 （与 LR(k) 解析器中的类似优化一样，这种优化可以延迟错误的识别，但在读取额外的标记之前它们仍然被识别。）
LL(1) 解析器不能包含可空非终结符，其 FIRST 和 FOLLOW 集合包含公共元素。但是，如果递归下降解析器使用 "default rule" 优化，那么在构造解析器期间永远不会注意到该冲突。实际上，忽略冲突允许从（某些）非确定性语法构建 "greedy" 解析器。
这非常方便，因为正如我们在上面看到的那样，生成明确的贪婪语法需要大量工作，并且不会产生任何东西，即使是模糊地类似于对语言的清晰阐述。但是修改后的递归解析算法并没有更强大；它只是解析一个等价的 SLL(k) 文法（而不实际构造该文法）。
我不打算提供上述断言的完整证明，但第一步是观察任何非终结符都可以重写为新非终结符的析取，每个非终结符都有一个不同的 FIRST 标记，可能还有一个右侧为空的新非终结符。然后 "only" 有必要通过创建新的析取从 FOLLOW 组可空非终结符中删除非终结符。
备注
在这里，我谈论的是在标记化流上运行的语法，其中注释已被删除，其他结构（例如由 "long brackets" 分隔的字符串）减少为单个令牌。如果没有这种转换，语言就不会是 LL(k)（因为注释——可以任意长——会干扰前瞻标记的可见性）。这让我也回避了用 LL(k) 语法可以识别多长括号的问题，这与这个问题没有特别的关系。
有些编程语言无法通过上下文无关文法进行确定性解析。最臭名昭著的例子可能是 Perl，但也有著名的 C 构造 (x)*y，它只能使用有关符号 x 的信息进行确定性解析——无论它是变量名还是类型别名——以及正确解析涉及模板的 C++ 表达式的困难。 （例如，参见问题 Why can't C++ be parsed with a LR(1) parser? and Is C++ context-free or context-sensitive?）
为简单起见，我删除了各种文字常量（字符串、数字、布尔值等）以及 table 构造函数和函数定义。这些标记不能成为函数调用的目标，这意味着以这些标记之一结尾的表达式不能用带括号的表达式扩展。删除它们简化了消歧的说明；该过程仍然可以使用完整的语法，但它更加乏味。
有了完整的语法，我们还需要考虑不能用 ( 扩展的表达式，所以会有四个不同的选项。
有确定性的 LL(k) 文法无法使用此算法产生明确的解析 tables，Sippu 和 Soisalon-Soininen 将其称为强 LL(k) 算法。可以使用额外的解析状态来扩充算法，类似于 LR(k) 解析器中的状态。这对于特定语法可能很方便，但它不会改变 LL(k) 语言的定义。正如 Sippu 和 Soisalon-Soininen 所证明的，可以从任何 LL(k) 文法中机械地派生出产生完全相同语言的 SLL(k) 文法。 （参见第 2 卷中的定理 8.47）。
递归定义算法是规范的基于堆栈的LL(k)解析器的精确实现，其中解析器堆栈是在解析器执行期间使用当前延续的组合隐式构造的和激活记录的堆栈。
根据 "Recursive descent parser" on Wikipedia，没有回溯的递归下降（a.k.a。预测分析）仅适用于 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)？还是我可以申请更宽松的限制？
TL;DR
对于什么是递归下降解析器的suitable定义，只有LL(k)languages可以被递归下降解析是绝对正确的。
Lua 可以用递归下降解析器解析，正是因为 language 是 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
肯定是模棱两可的；目的是解析为 "greedy"。同样，歧义不是固有的。有一个产生明确语法的机械转换，如下所示：
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 parser generator，转换实际上是通过删除与shift动作冲突的reduce动作来实现的。这比转换语法更简单，但效果完全一样。）
所以Lua（和其他编程语言）本质上不是模棱两可的；因此，可以使用需要明确的确定性解析器的解析算法来解析它们。事实上，有些语言的 所有可能的语法 都是模棱两可的，这甚至有点令人惊讶。正如上面引用的维基百科文章中指出的那样，Rohit Parikh 在 1961 年证明了此类语言的存在；一个本质上模棱两可的上下文无关语言的简单例子是
{a<sup>n</sup>b<sup>m</sup>c<sup>m</sup>d<sup>n</sup>|n,m≥0}∪{a<sup>n</sup>b<sup>n</sup>c<sup>m</sup>d<sup>m</sup>|n,m≥0}.
3。贪心 LL(1) 解析 Lua 赋值和函数调用语句
与上面的悬挂 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 文法是左递归的，所以它显然不是 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
为了使贪心解析明确无误，我们需要禁止（从语法中）出现任何 S<sub>1</sub> S<sub>2 </sub> 其中 S<sub>1</sub> 以 exp 和 S<sub>2</sub>以'('开头。实际上，我们需要根据语句是否以(开头来区分不同类型的语句，以及独立地，语句是否以 exp 结尾。（实际上，只有三种类型，因为没有以 ( 开头且不以 exp 结尾的语句.[注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) 算法的一种实现，其中每个非终结符都映射到一个过程。每个非终端过程首先使用长度为 k 的可能前瞻序列的 table 来决定该非终端使用哪个替代产生式，然后简单地 "executes" 产生式符号symbol: 终结符号如果匹配则丢弃下一个输入符号，如果不匹配则报错；非终端符号导致调用非终端过程。
前瞻序列的table可以使用FIRSTk和FOLLOW[=构造186=]k套。 （如果 α ∈ <i>FIRST</i><sub>k</sub>，则产生式 <code>A→ω 映射到终端序列 α (ωFOLLOWk(A)).) [注5]
有了这个递归下降解析的定义，递归下降解析器就可以精确地处理 LL(k) 语言。 [注6]
然而，LL(k) 和递归下降解析器的对齐忽略了递归下降解析器的一个重要方面，即它首先是一个 程序通常用某种图灵完备的编程语言编写。如果允许该程序稍微偏离上述严格的结构，它就可以解析更多的语言，甚至是非上下文无关的语言。 （例如，参见注释 2 中引用的 C 上下文敏感性。）
特别是，很容易将 "default" 规则添加到 table 映射前瞻到产品。这是一个非常诱人的优化，因为它大大减少了前瞻 table 的大小。通常，默认规则用于非终结符，其替代项包括一个空的右侧，在 LL(1) 文法的情况下，它将映射到 FOLLOW[=166= 中的任何符号] 设置为非终端。在该实现中，前瞻 table 仅包括来自 FIRST 集合的前瞻，并且解析器自动生成一个空的右侧，对应于立即 return , 对于任何其他符号。 （与 LR(k) 解析器中的类似优化一样，这种优化可以延迟错误的识别，但在读取额外的标记之前它们仍然被识别。）
LL(1) 解析器不能包含可空非终结符，其 FIRST 和 FOLLOW 集合包含公共元素。但是，如果递归下降解析器使用 "default rule" 优化，那么在构造解析器期间永远不会注意到该冲突。实际上，忽略冲突允许从（某些）非确定性语法构建 "greedy" 解析器。
这非常方便，因为正如我们在上面看到的那样，生成明确的贪婪语法需要大量工作，并且不会产生任何东西，即使是模糊地类似于对语言的清晰阐述。但是修改后的递归解析算法并没有更强大；它只是解析一个等价的 SLL(k) 文法（而不实际构造该文法）。
我不打算提供上述断言的完整证明，但第一步是观察任何非终结符都可以重写为新非终结符的析取，每个非终结符都有一个不同的 FIRST 标记，可能还有一个右侧为空的新非终结符。然后 "only" 有必要通过创建新的析取从 FOLLOW 组可空非终结符中删除非终结符。
备注
在这里，我谈论的是在标记化流上运行的语法，其中注释已被删除，其他结构（例如由 "long brackets" 分隔的字符串）减少为单个令牌。如果没有这种转换，语言就不会是 LL(k)（因为注释——可以任意长——会干扰前瞻标记的可见性）。这让我也回避了用 LL(k) 语法可以识别多长括号的问题，这与这个问题没有特别的关系。
有些编程语言无法通过上下文无关文法进行确定性解析。最臭名昭著的例子可能是 Perl，但也有著名的 C 构造
(x)*y，它只能使用有关符号x的信息进行确定性解析——无论它是变量名还是类型别名——以及正确解析涉及模板的 C++ 表达式的困难。 （例如，参见问题 Why can't C++ be parsed with a LR(1) parser? and Is C++ context-free or context-sensitive?）为简单起见，我删除了各种文字常量（字符串、数字、布尔值等）以及 table 构造函数和函数定义。这些标记不能成为函数调用的目标，这意味着以这些标记之一结尾的表达式不能用带括号的表达式扩展。删除它们简化了消歧的说明；该过程仍然可以使用完整的语法，但它更加乏味。
有了完整的语法，我们还需要考虑不能用
(扩展的表达式，所以会有四个不同的选项。有确定性的 LL(k) 文法无法使用此算法产生明确的解析 tables，Sippu 和 Soisalon-Soininen 将其称为强 LL(k) 算法。可以使用额外的解析状态来扩充算法，类似于 LR(k) 解析器中的状态。这对于特定语法可能很方便，但它不会改变 LL(k) 语言的定义。正如 Sippu 和 Soisalon-Soininen 所证明的，可以从任何 LL(k) 文法中机械地派生出产生完全相同语言的 SLL(k) 文法。 （参见第 2 卷中的定理 8.47）。
递归定义算法是规范的基于堆栈的LL(k)解析器的精确实现，其中解析器堆栈是在解析器执行期间使用当前延续的组合隐式构造的和激活记录的堆栈。