递归下降解析适用语言判定：5种{x,y,r}上语言的技术问询

首先明确：无回溯的递归下降解析要求语言可被LL(1)文法生成，LL(1)文法属于上下文无关文法（CFG）的子集；另外，有限语言必然是正则语言（属于CFG），且可构造LL(1)文法，因此天然支持递归下降解析。

以下逐个分析给定语言：

语言A：{ xⁿ yⁿ | n ≤ k } #

这是有限语言（n的取值范围是0到k，k为固定常数），所有有限语言都可通过正则文法描述，且正则文法属于LL(1)文法范畴。例如可构造文法：

S → ε | xSy | xxSyy | ... | xᵏyᵏ

该文法无冲突，可直接用递归下降解析实现。

语言B：{ xⁿ yᵏ | n > k } #

这是上下文无关语言，可构造适配的文法，即使采用带回溯的递归下降解析（非预测型）也能处理该语言。比如可以用如下文法描述：

S → x T
T → x T | x T y | ε

因此B支持递归下降解析。

语言C：{ xᵏ yⁿ | k > n } #

与B对称，同样是上下文无关语言，逻辑和B完全一致：既可以构造适配的文法，也可通过带回溯的递归下降解析实现，因此C也支持递归下降解析。

语言D：{ xⁿ yⁿ rⁿ | n ≤ k } #

和A一样是有限语言，n的取值范围固定（0到k），可枚举所有可能的字符串构造LL(1)文法，例如：

S → ε | xyr | xxYYrr | ... | xᵏyᵏrᵏ

完全符合递归下降解析的要求。

语言E：{ xⁿ yⁿ rⁿ | n ≥ k } #

该语言是上下文相关语言（不属于上下文无关语言范畴），因为它是{xⁿyⁿrⁿ | n≥0}的子集，而后者无法用上下文无关文法描述。递归下降解析的基础是上下文无关文法，因此E无法通过递归下降解析实现。

最终结论 #

可通过递归下降解析实现的语言为：A、B、C、D；无法实现的是E。

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