非回溯递归下降解析器适配障碍及给定CFG解析性验证

咱先把你提供的文法整理成更易读的格式，方便后续分析：

Prog -> Def^+
Def -> DEF Left == Expr
Left -> MAIN : Type | Ident ([Ident:Type(, Ident:Type)^*]):Type
Type -> NAT | BOOL
Expr -> Num | TRUE | FALSE | Ident[([(Expr(, Expr)^*)])] | IF Expr THEN Expr [ELSE Expr] FI
Ident -> (a|...|z)^+
Num -> (0|...|9)^+

注：大写符号（含==、:，以及Ident和Num的右部）为终结符；()、[]、^+、^*为表示法运算符；其余为非终结符。

接下来逐个解答你的疑问：

假设1：该文法可被非回溯递归下降解析器解析？ #

非回溯递归下降解析器的核心要求是文法必须是LL(1)的——简单说就是，每个非终结符的各个产生式，从第一个输入符号就能唯一确定选哪个，不需要试错回溯。咱们挨个关键非终结符检查：

1. Left的两个产生式：MAIN : Type的首终结符是MAIN，Ident (...)的首符号是小写字母（因为Ident是a-z的组合），这俩集合完全不相交，遇到MAIN就选第一个，遇到小写字母就选第二个，没毛病。
2. Expr的多个产生式：Num的首符号是数字，TRUE/FALSE是大写关键字，Ident开头是小写，IF开头是IF——所有产生式的FIRST集（也就是能触发该产生式的首符号集合）都完全不重叠，而且没有空产生式，所以也能唯一确定选择。
3. 其他非终结符：Prog是Def的重复，Def开头固定是DEF；Type的两个选项NAT/BOOL首符号也不重叠；Ident和Num都是单分支产生式，完全没问题。

所以从LL(1)的标准来看，这个文法的结构是符合非回溯递归下降解析器要求的——当然，前提是词法层面不会把关键字和Ident搞混，这就涉及到你的假设2。

假设2：解析器需遵循“标识符与终结符名称不相似”的定义，扩展Ident规则添加识别终结符可解决问题？ #

这个假设不成立，而且逻辑搞反了。

你提到的“标识符与终结符名称相似”的冲突，本质是词法分析阶段的问题，不是文法的问题。按照你给出的定义，所有关键字终结符（MAIN、DEF、TRUE等）都是大写的，而Ident是小写字母组成的——这种情况下词法分析器完全可以轻松区分：遇到全大写的串就识别为关键字终结符，全小写的就识别为Ident，根本不会有冲突。

如果真出现了关键字和Ident名称重叠的情况（比如关键字是小写的main，而Ident允许是main），正确的解决办法也不是修改Ident的文法规则，而是让词法分析器优先识别关键字：当输入串匹配某个关键字时，优先输出对应的终结符，而不是把它当成Ident。这是词法分析的标准操作，不需要动文法。

假设3：存在除左递归、歧义外的其他语法问题导致无法解析？ #

这个假设不成立。咱们已经确认了文法没有左递归（所有产生式都是右递归或非递归结构），也没有歧义（每个输入串只会对应一种推导路径），而且满足LL(1)的要求，所以不存在其他语法层面的阻碍。

补充：除左递归、歧义外，还有哪些因素会导致非回溯递归下降解析器无法使用？ #

本质上都是文法不满足LL(1)（或你要使用的LL(k)）条件，具体表现包括：

• 需要回溯的产生式选择：比如同一个非终结符的两个产生式FIRST集相交，比如A -> aB | aC，当看到a时，不知道选哪个产生式，必须回溯试错，非回溯解析器做不到。
• ε产生式的FOLLOW集冲突：比如A -> ε | aB，如果FOLLOW(A)（也就是A后面可能出现的符号）和FIRST(aB)（a开头的符号）有交集，那当输入符号在这个交集里时，解析器无法判断是选空产生式还是选aB。
• 间接左递归：比如A -> Bx，B -> Ay，看起来不是直接左递归，但推导起来会无限循环A→Bx→Ay x→...，同样会导致解析器死循环。
• 需要超前看多于1个符号：也就是文法是LL(k)但不是LL(1)的，比如必须看2个甚至更多符号才能确定产生式选择，这时候非回溯的LL(1)解析器就无法处理了。

额外：判断文法是否适配非回溯递归下降解析器的方法 #

除了检查左递归和歧义，最标准的方法是验证文法是否为LL(1)文法，步骤如下：

1. 先消除所有左递归（包括直接和间接的）。
2. 提取左因子：如果同一个非终结符的多个产生式开头相同（比如A -> aB | aC），把公共部分提出来改成A -> a(B | C)，避免FIRST集相交。
3. 计算每个非终结符的FIRST集和FOLLOW集。
4. 检查每个非终结符的所有产生式：
   • 任意两个不同产生式的FIRST集必须互不相交。
   • 如果有产生式是空串（ε），那么这个产生式的FOLLOW集，不能和其他产生式的FIRST集相交。

如果全部满足，那这个文法就是LL(1)的，完全可以用非回溯递归下降解析器。另外，你也可以手工模拟解析过程：给每个非终结符的产生式，看给定第一个输入符号时，能不能立刻确定选哪个，没有模糊的情况——如果都能，那基本就没问题。

内容的提问来源于stack exchange，提问作者user6371852