如何使用 antlr4 跨越所有有效输入 space 而不是解析输入？

Question

换句话说，如何在控制递归深度的情况下得到 ast 树。

例如

grammar: Expr

start: expression EOF;

expression
    : expression (+|-) expression
    | NUMBER
    ;

NUMBER: [0-9]+;

深度 = 3 的所有有效输入 space：

深度 1：0、10、...

深度 2：0 + 2、3 - 4、...

深度 3: 0 + 2 - 4, ....

Answer 1

据我所知，Antlr 解析器没有内置功能来执行此操作，一般的解决方案会很复杂。

即使在您的简单示例中，您的问题也很难解释。 NUMBER 的解析的递归深度是多少？总是 1?每次迭代一个，好像重复运算符被扩展为 BNF？还是您打算忽略词法分析？（请记住，Antlr 不要求将语法分为词法和句法部分。）

您的语法不包含任何谓词，但不使用谓词很难为现实世界的问题编写 Antlr 语法；它们赋予了 Antlr 很大的力量。但是反转使用谓词的文法可能只能通过生成所有候选词然后测试每个候选词来实现。

如果我们从等式中删除 Antlr 只留下 BNF，并且不尝试生成超出其标记类型的标记，那么使用广度优先搜索枚举可能的句子非常简单，这自然会按顺序工作通过递归深度。结果很少有用，因为可能性的数量呈指数级增长，但肯定有实现。

一个更常见的问题是为解析器或语言处理器生成有用的测试用例。经典算法由 Paul Purdom 于 1972 年提出；虽然它并不完全令人满意，但它构成了许多语法测试人员的基础。开源实现可用；如果您想自己编写，请尝试查找 Malloy & Power 的 Purdom 自动生成测试用例算法的解释，该书于 2001 年首次出版。

如何使用 antlr4 跨越所有有效输入 space 而不是解析输入？

How can I span all vaild input space using antlr4 instead of parsing a input?

parsing

lexer

antlr4