ANTLR4 解析树简化
ANTLR4 parse tree simplification
有没有办法让 ANTLR4 自动删除生成的解析树中的冗余节点?
更具体地说,我一直在试验 GLSL 语法,由于自动处理运算符优先级所需的规则转发,您最终在解析树中得到 "expressions" 的长线性序列.
大多数生成的树节点只是 "forward to the next level of precedence",所以不要提供任何有用的句法信息 - 您只需要每个序列中的最后一个表达式节点(即规则转发停止的点) ), 或者它成为具有多个子节点的实际树节点的点(即在源中遇到实际表达式)...
我希望有一种简单的方法来消除虚拟中间表达式节点 - 这种类型的结构在任何具有运算符优先级的语法中必须是常见的。
语法的基本结构是从语言的 Khronos 规范中提取的相当直接的克隆:
https://www.khronos.org/registry/gles/specs/3.1/es_spec_3.1.pdf
ANTLR v4 能够从处理不同优先级的单个递归规则生成代码,如果您使用这样的语法(基础数学示例):
expr : '(' expr ')'
| '-' expr
| expr ('*'|'/') expr
| expr ('+'|'-') expr
| INT
;
ANTLR v3 无法做到这一点,基本上要求您为每个优先级编写一个规则。所以我建议您重写语法以避免这些样板规则。
那么,我认为您混淆了 parse tree (aka concrete syntax tree) with the AST (abstract syntax tree)。 AST 就像解析树的简化版本,它只保留您的目的所需的内容。例如,使用上面的 expr
规则,AST 不会包含任何括号节点,因为优先级是在树本身中编码的,您通常不需要知道给定表达式的一部分是否是是否加括号。
你的程序应该从解析树构建一个 AST,然后从那里开始。不要直接处理解析树,即使乍一看似乎很方便,因为工具为您生成它们。它很快就会变得很麻烦。构建您自己的树结构 (AST),为手头的任务量身定制。
使用Visitor 实现按顺序访问每个节点。通过在访问父节点时向父节点添加节点来构建您自己的树。在访问节点时决定是否将其添加到新树中。例如:
public T visitExpression(@NotNull AcParser.ExpressionContext ctx) {
// Expressionable parent = getParent(Expressionable.class, ctx);
// Class<? extends AcExpression> expClass = AcExpression.class;
AcExpression obj = null;
String text = ctx.getText();
//do something with text or children
for (int i=0; i<ctx.getChildCount(); i++){
printnl(ctx.getChild(i).getText()+"/");
}
return visitChildren(ctx);
}
有没有办法让 ANTLR4 自动删除生成的解析树中的冗余节点?
更具体地说,我一直在试验 GLSL 语法,由于自动处理运算符优先级所需的规则转发,您最终在解析树中得到 "expressions" 的长线性序列.
大多数生成的树节点只是 "forward to the next level of precedence",所以不要提供任何有用的句法信息 - 您只需要每个序列中的最后一个表达式节点(即规则转发停止的点) ), 或者它成为具有多个子节点的实际树节点的点(即在源中遇到实际表达式)...
我希望有一种简单的方法来消除虚拟中间表达式节点 - 这种类型的结构在任何具有运算符优先级的语法中必须是常见的。
语法的基本结构是从语言的 Khronos 规范中提取的相当直接的克隆:
https://www.khronos.org/registry/gles/specs/3.1/es_spec_3.1.pdf
ANTLR v4 能够从处理不同优先级的单个递归规则生成代码,如果您使用这样的语法(基础数学示例):
expr : '(' expr ')'
| '-' expr
| expr ('*'|'/') expr
| expr ('+'|'-') expr
| INT
;
ANTLR v3 无法做到这一点,基本上要求您为每个优先级编写一个规则。所以我建议您重写语法以避免这些样板规则。
那么,我认为您混淆了 parse tree (aka concrete syntax tree) with the AST (abstract syntax tree)。 AST 就像解析树的简化版本,它只保留您的目的所需的内容。例如,使用上面的 expr
规则,AST 不会包含任何括号节点,因为优先级是在树本身中编码的,您通常不需要知道给定表达式的一部分是否是是否加括号。
你的程序应该从解析树构建一个 AST,然后从那里开始。不要直接处理解析树,即使乍一看似乎很方便,因为工具为您生成它们。它很快就会变得很麻烦。构建您自己的树结构 (AST),为手头的任务量身定制。
使用Visitor 实现按顺序访问每个节点。通过在访问父节点时向父节点添加节点来构建您自己的树。在访问节点时决定是否将其添加到新树中。例如:
public T visitExpression(@NotNull AcParser.ExpressionContext ctx) {
// Expressionable parent = getParent(Expressionable.class, ctx);
// Class<? extends AcExpression> expClass = AcExpression.class;
AcExpression obj = null;
String text = ctx.getText();
//do something with text or children
for (int i=0; i<ctx.getChildCount(); i++){
printnl(ctx.getChild(i).getText()+"/");
}
return visitChildren(ctx);
}