简介
对于递归下降解析器的合适定义而言，只有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. 许多实用的编程语言采用模棱两可的文法描述。
在形式语言理论中，仅当语言的每个文法都是模棱两可的时，该语言才是固有模棱两可的。由于实用的编程语言可以被确定地解析（以某种方式），因此可以大胆地说，没有一种实用的编程语言是固有模棱两可的。[注2]
因为编写一个严格的非模棱两可文法可能很繁琐，所以语言文档通常会提供一个模棱两可的文法，以及说明如何解决歧义的文本材料。
例如，许多语言（包括Lua）都使用不明确包含运算符优先级的文法进行文档记录，从而允许对表达式进行简单规则：
exp ::= exp Binop exp | Unop exp | term
那个规则显然是含糊不清的，但是如果给出运算符列表、它们相对优先级以及每个运算符是左结合还是右结合的指示，该规则可以被机械地扩展为一个明确的表达式语法。实际上，许多解析器生成器允许用户单独提供优先级声明，并在生成解析器的过程中执行机械扩展。需要注意的是，结果解析器是用于已消除歧义的语法的解析器，因此原始语法的歧义并不意味着解析算法能够处理有歧义的语法。
另一个常见的例子是在像C这样的语言中发现的
"悬挂else"歧义，这种歧义也可以被机械地消除。语法如下：
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解析器生成器，该转换实际上是通过删除规约操作（如果它们与移位操作冲突）来实现的。这比转换语法更简单，但效果完全相同。）
因此，Lua（和其他编程语言）并不是本质上模棱两可的；因此，它们可以使用需要无歧义确定性解析器的解析算法进行解析。事实上，甚至可能有点令人惊讶的是，存在一些语言，其中每个可能的语法都是模棱两可的。正如上面引用的维基百科文章中所指出的那样，这种语言的存在是由Rohit Parikh在1961年证明的；一个本质上模棱两可的无上下文语言的简单示例是
{a
n b
m c
m d
n | n，m≥0} ∪ {a
n b
n c
m d
m | 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 ')'
(Note:（我使用
Ø代表空字符串，而不是
ε，
λ或
%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
为了使贪婪解析变得明确，我们需要禁止（从语法上）任何出现
S1 S2的情况，其中
S1以
exp结尾，
S2以'('开头。实际上，我们需要根据语句是否以
(开头以及语句是否以
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的表来决定该非终端要使用哪个替代产生式，然后简单地通过符号逐个“执行”产生式：如果终端符号匹配，则丢弃下一个输入符号，如果不匹配，则报告错误；如果是非终端符号，则调用非终端过程。
前瞻序列的表可以使用FIRSTk和FOLLOWk集合构建。（如果产生式A→ω映射到一个序列α的终端，则α ∈ FIRSTk(ω FOLLOWk(A))。）[注5]
根据这种递归下降解析的定义，递归下降解析器可以精确地处理LL(k)语言。[注6]
然而，LL(k)和递归下降解析器的对齐忽略了递归下降解析器的一个重要方面，即它首先是一个程序，通常是用某种图灵完备的编程语言编写的。如果允许该程序稍微偏离上述严格结构，它可以解析更大范围的语言，甚至是非上下文无关的语言。（例如，参见注2中引用的C上下文敏感性。）
特别是，将一个“默认”规则添加到将前瞻映射到产生式的表中非常容易。这是一种非常诱人的优化，因为它大大减小了前瞻表的大小。通常，默认规则用于其替代项包括空右侧的非终结符，在LL（1）语法的情况下，该替代项将被映射到非终结符的FOLLOW集中的任何符号。在该实现中，前瞻表仅包括来自FIRST集的前瞻，并且对于任何其他符号，解析器会自动产生一个空的右侧，对应于立即返回。（与LR（k）解析器中类似的优化一样，此优化可以延迟错误的识别，但在读取其他标记之前仍然识别它们。）
LL（1）解析器不能包含具有FIRST和FOLLOW集包含公共元素的可空非终结符。但是，如果递归下降解析器使用“默认规则”优化，则在构建解析器期间永远不会注意到该冲突。实际上，忽略冲突允许从（某些）非确定性语法构造出“贪婪”的解析器。
这非常方便，因为正如我们在上面看到的，生成无歧义的贪婪语法需要大量工作，而且不会导致任何类似于语言的清晰表述。但是修改后的递归解析算法并不更强大；它只是解析等效的SLL（k）语法（而无需实际构造该语法）。
我不打算提供对上述断言的完整证明，但第一步是观察到任何非终端符号都可以重写为新的非终端符号的析取形式，每个符号只有一个独特的FIRST令牌，并且可能有一个右侧为空的新的非终端符号。然后，通过创建新的析取式来从可空非终端符号的FOLLOW集中删除非终端符号即可。
笔记
这里，我谈论的是在分词流上运行的语法，在其中已删除注释和其他构造物（例如由“长括号”界定的字符串）被简化为单个标记。如果没有这种转换，该语言将不是LL(k)（因为注释 - 可以是任意长 - 干扰了前瞻标记的可见性）。这也使我能够回避如何使用LL(k)语法识别长括号的问题，这与此问题不是特别相关。
有些编程语言无法通过上下文无关文法进行确定性解析。最臭名昭著的例子可能是Perl，但也有众所周知的C构造(x)*y，只能使用有关符号x的信息进行确定性解析-它是变量名称还是类型别名-以及正确解析涉及模板的C ++表达式的困难。（例如，请参阅为什么不能使用LR(1)解析器解析C ++？和C ++是上下文自由还是上下文相关的？）
为简单起见，我删除了各种文字常量（字符串，数字，布尔值等），以及表构造函数和定义。这些标记不能成为函数调用的目标，这意味着以这些标记结尾的表达式不能使用带括号的表达式进行扩展。删除它们简化了消歧过程；使用完整语法仍然是可能的，但更加繁琐。
在完整语法中，我们还需要考虑无法使用(扩展的表达式，因此将有四个不同的选项。
有些确定性LL(k)文法无法使用此算法生成一致的解析表，Sippu＆Soisalon-Soininen称之为强LL(k)算法。可以使用附加解析状态增强算法，类似于LR(k)解析器中的状态。这可能对特定语法很方便，但不会改变LL(k)语言的定义。正如Sippu＆Soisalon-Soininen所证明的那样，可以从任何LL(k)语法机械地推导出产生完全相同语言的SLL(k)语法。（请参阅第2卷中的定理8.47）。
递归定义算法是规范栈式LL(k)解析器的精确实现，在解析器执行期间使用当前续集和激活记录栈的组合隐式构建解析器堆栈。
x = y，因为你需要查看x后面是否有一个=。 - user5066707