如何判断一门语言能否通过递归下降分析法解析？

一、递归下降分析法的核心要求 #

递归下降分析通常分为两种实用场景，适用条件差异明显：

1. 无回溯的预测递归下降（主流实用方案） #

这种分析方式要求对应的文法是LL(1)文法，判断LL(1)文法的核心规则：

• 文法不存在左递归（包括直接左递归和间接左递归）；
• 对于每个非终结符的所有产生式：
  • 各产生式的FIRST集互不相交；
  • 如果某产生式可推导出空串ε，则该非终结符的FOLLOW集与其他产生式的FIRST集也不能相交。

只要能为目标语言构造或改写出满足LL(1)条件的文法，就可以用这种高效的无回溯递归下降分析。

2. 带回溯的递归下降（几乎不实用） #

只要语言是上下文无关语言，理论上都可以用这种方式解析，但它会反复尝试不同的产生式选择（失败则回溯），效率极低且容易陷入无限循环，实际开发中基本不使用。

二、实例分析：语言{ s^p r^q | p > q } #

1. 构造合法的上下文无关文法 #

先为该语言构造符合规则的上下文无关文法：

S → s S | s R
R → s R r | ε

验证逻辑：

• 多次选择S → s S后选S → s R，R最终推导出s^k r^k（k≥0），总s数为(n+1)+k，r数为k，满足(n+1)+k > k；
• 直接选S → s R时，s数为1+k，r数为k，同样满足p>q。

2. 检查LL(1)条件是否满足 #

计算关键集合：

• FIRST(S) = {s}（两个产生式均以s开头）；
• FIRST(R) = {s, ε}；
• FOLLOW(S) = {$}（输入结束符）；
• FOLLOW(R) = {$, r}。

观察非终结符S的两个产生式：S→sS和S→sR的FIRST集完全相同（都是{s}），存在选择冲突——当解析器看到当前输入是s时，无法确定应该选择哪个产生式，因此这个文法不是LL(1)文法。

3. 能否改写为LL(1)文法？ #

无法改写。该语言的核心特性是s的数量必须多于r，解析时仅通过当前输入符号s，无法预判后续r的数量，也就无法确定是继续添加s还是开始匹配r。这种冲突无法通过提取左因子、消除左递归等LL(1)改写技巧解决。

4. 最终结论 #

该语言不能用无回溯的预测递归下降分析法解析；由于它属于上下文无关语言，理论上可以用带回溯的递归下降分析，但实际开发中不建议采用这种低效方案。

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