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 能够从处理不同优先级的单个递归规则生成代码，如果您使用这样的语法(例如基本数学):

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屋！