ANTLR4解析树简化 [英] ANTLR4 parse tree simplification

问题描述

有没有办法让ANTLR4自动删除生成的分析树中的冗余节点?

Is there any means to get ANTLR4 to automatically remove redundant nodes in generated parse trees?

更具体地说，我一直在尝试GLSL的语法，由于需要自动进行运算符优先级处理的规则转发，最终您会在解析树中得到长长的线性表达式"序列.

More specifically, I've been experimenting with a grammar for GLSL and you end up with long linear sequences of "expressions" in the parse tree due to the rule forwarding needed to give the automatic handling of operator precedence.

大多数生成的树节点只是前进到下一个优先级"，因此不提供任何有用的语法信息-您只真正需要每个序列中的最后一个表达式节点(即规则所在的点)转发已停止)，或者它成为具有多个子代的实际树节点的点(即，在源中遇到了实际表达式)...

Most of the generated tree nodes are simply "forward to the next level of precedence", so don't provide any useful syntactic information - you only really need the last expression node in each sequence (i.e. the point at which the rule forwarding stopped), or the point where it becomes an actual tree node with more than one child (i.e. an actual expression was encountered in the source) ...

我希望有一种简单的方法可以消除虚拟的中间表达节点-这种类型的结构在任何具有运算符优先级的语法中都必须是常见的.

I was hoping there would be an easy way to kill off the dummy intermediate expression nodes - this type of structure must be common in any grammar with operator precedence.

语法的基本结构是从Khronos规范中获得的一种相当直接的克隆:

The basic structure of the grammar is a fairly direct clone taken from the Khronos specification for the language:

https://www.khronos.org/registry/gles/specs/3.1/es_spec_3.1.pdf

推荐答案

如果您使用这样的语法(例如基本数学示例)，则ANTLR v4可以从处理不同优先级的单个递归规则生成代码./p>

ANTLR v4 is able to generate code from a single recursive rule dealing with different precedence levels, if you use a grammar like this (example for basic math):

expr : '(' expr ')'
     | '-' expr
     | expr ('*'|'/') expr
     | expr ('+'|'-') expr
     | INT
     ;

ANTLR v3无法执行此操作，并且基本上要求您为每个优先级编写一个规则.因此，建议您重写语法以避免这些重复的规则.

ANTLR v3 was unable to do so and basically required you to write one rule per precedence level. So I'd advise you to rewrite your grammar to avoid these boilerplate rules.

然后，我认为您混淆了解析树(又名具体语法树)与 AST(抽象语法树) . AST就像解析树的简化版本，仅保留您所需的内容.例如，使用上述expr规则，AST将不包含任何括号节点，因为优先级是在树本身中编码的，并且您通常不需要知道给定表达式的一部分是否被括号括起来或不是.

Then, I think you're confusing the parse tree (aka concrete syntax tree) with the AST (abstract syntax tree). The AST is like a simplified version of the parse tree, which keeps only what's needed for your purpose. For instance, with the expr rule above, the AST wouldn't contain any node for parentheses, since the precedence is encoded in the tree itself and you usually don't need to know whether a part of a given expression was parenthesized or not.

您的程序应从解析树构建AST，然后从那里开始.即使乍一看似乎很方便，也不要直接处理解析树，因为该工具会为您生成它们.它将很快变得麻烦.建立适合自己任务的树形结构(AST).

Your program should build an AST from the parse tree and then go from there. Don't deal with parse trees directly, even if it seems convenient at first sight because the tool generates them for you. It'll quickly become cumbersome. Build your own tree structure (AST), tailored for the task at hand.

这篇关于ANTLR4解析树简化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！