换句话说，我如何在控制递归深度的情况下获得快速树。
。
grammar: Expr
start: expression EOF;
expression
: expression (+|-) expression
| NUMBER
;
NUMBER: [0-9]+;
所有深度= 3的有效输入空间:
深度1:0,10，…
深度2:0 + 2,3 - 4，…
深度3:0 + 2 - 4，....
据我所知，Antlr解析器没有内置功能来完成此操作，一般的解决方案将会很复杂。
即使在你简单的例子中，你的问题也很难解释。解析NUMBER的递归深度是多少?总是1 ?每次迭代一个，就好像重复运算符被扩展成BNF?还是你想忽略词法分析?(请记住，Antlr并不要求将语法分为词汇和句法两部分。)
你的语法不包括任何谓词，但如果不使用谓词，很难为现实世界的问题编写Antlr语法;正是它们赋予了Antlr很大的力量。但是，反转使用谓词的语法可能只能通过生成所有候选项然后测试每个候选项来实现。
如果我们从等式中删除Antlr，只留下BNF，并且不尝试生成超出其标记类型的标记，那么使用广度优先搜索枚举可能的句子就非常简单了，这将自然地按递归深度排序。这个结果很少有用，因为可能性的数量呈指数级增长，但肯定有实现。
更常见的问题是为解析器或语言处理器生成有用的测试用例。经典算法由Paul Purdom在1972年提出;虽然它不是完全令人满意，但它构成了许多语法测试者的基础。开源实现是可用的;如果你想自己写，试着找一本马洛伊的书。Power的对Purdom的自动生成测试用例算法的解释，首次发表于2001年。