如何用递归文法定义递增整数序列列表（McKeeman范式）

先明确基础无约束文法 #

你提到的不含递增约束的递归文法，假设分隔符是X，大概是这样的：

List → Number X | Number X List
Number → Digit | Digit Number
Digit → 0 | 1 | ... | 9

但这个文法允许任意整数序列，无法满足连续递增的要求。

核心问题：递增是上下文相关约束 #

纯上下文无关的McKeeman范式没法直接表达“下一个数必须比前一个大1”这类依赖——上下文无关文法的规则只关注当前符号，无法记录前面的数值信息。所以必须结合语义动作，或者用带属性的文法来传递前一个数的状态。

实用方案：带语义属性的递归文法 #

直接在文法规则中加入数值属性，通过递归调用强制下一个数为前一个数+1，写法如下：

List(n) → Number(n) X | Number(n) X List(n+1)
Number(k) → Digit(d) { k = d } | Digit(d) Number(k') { k = d*10 + k' }
Digit(d) → 0 { d=0 } | 1 { d=1 } | ... | 9 { d=9 }

• List(n)中的n表示当前位置的整数必须等于n
• 递归调用List(n+1)直接约束了下一个整数必须是前一个数加1，实现连续递增
• 大括号内的内容是语义动作，用于计算当前数字的实际数值

避免无效的纯文法枚举 #

如果试图不用语义动作，纯靠上下文无关文法实现，只能枚举所有可能的递增序列：

List → 1 X | 1 X 2 X | 1 X 2 X 3 X | ...

这种方式无法覆盖所有整数范围，完全违背递归定义的初衷，没有实用价值。

实际解析中的落地方式 #

在代码解析时，你可以在递归处理List的每一步，记录上一个整数的值，然后检查当前解析出的整数是否等于上一个数+1，不符合则抛出语法错误。这和带属性文法的逻辑一致，只是把语义检查放到了解析逻辑中。

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