如何忽略不重要的节点？

Question

我正在使用 ANTLR 4.9.2 来解析表示汇编指令的语法。

grammar IrohAsm;
main: line* | EOF;

line: (rangedec | instruction | comment)? EOL;

instruction: MNEMONIC firstoperand COMMA secondoperand;
rangedec : range assignment?;
firstoperand : range | mem | REGISTER;
secondoperand : range | mem | IMM | REGISTER;
range : IDENTIFIER OPENBRACKETS IMM CLOSEDBRACKETS;
assignment : EQUALS OPENCURL IMM (COMMA IMM)* CLOSECURL;
mem : AT IMM;
comment : '#' ~EOL*;

WHITESPACE : (' ') -> skip ;

// remember to append \n to input
EOL : '\n';

OPENCURL : '{';
CLOSECURL : '}';
OPENBRACKETS : '[';
CLOSEDBRACKETS : ']';
COMMA : ',';
EQUALS : '=';
AT : '@';
MNEMONIC : ('jmp' | 'add' | 'sub' | 'jez' | 'mov' | 'wrt' | 'get');
REGISTER: ('ab' | 'bb' | 'cb' | 'db');
IMM : DIGITS RADIX?;
RADIX : ('d' | 'b' | 'h');
DIGITS : [0-9]+;
IDENTIFIER: ([a-zA-Z0-9] | '$' | '_' | '\u00C0'..'\uFFFF')+ ;

语法工作正常，但生成的树如下所示；

当给出以下输入时：

mov ab,ab

如您所见，COMMA 作为指令的子项之一包含在内。它的位置对语言很重要，但解析后我并不真正关心它。有什么办法可以把它完全从最后一棵树上去掉吗？如果是这样，这会是对语法的更改，还是我解析树的代码？

我当前获取树的代码：

CharStream inputStream = CharStreams.fromFileName("src/test/assembly/cool.asm");
IrohAsmLexer lexer = new IrohAsmLexer(inputStream);
IrohAsmParser parser = new IrohAsmParser(new CommonTokenStream(lexer));
ParseTree parseTree = parser.main();

Answer 1

您的问题归结为：“如何将我的解析树转换为抽象语法树？”。对此的简单回答是：“你不能”:)。至少，不使用内置的 ANTLR 机制。您必须遍历解析树（使用 ANTLR 的访问者或侦听器机制）并手动构建您的 AST。

ANTLR 的 Github 存储库中经常会出现从解析树更轻松地创建 AST 的功能：

https://github.com/antlr/antlr4/issues/2428

以及在 Whosebug 上：

Generate AST using ANTLR4 generated visitor

Answer 2

对于ANTLR，就像Bart说的，不自己做是做不到的。本质上，您必须编写自定义代码来遍历 CST 并构建自定义 AST。

不一定非要这样。您可以构建自动构建树的解析器生成器：

省略不带任何值的节点（例如“逗号”、EOL）
删除一元产生式链（例如，“firstoperand”和“secondoperand；在您的示例中这些是短链，但表达式树往往有长链）
每当从表示列表的语法规则生成右倾或左倾树时构造节点列表，用单个列表节点替换“脊椎”节点和列表结束节点（如果有的话）。（您的示例没有这些）。这使得列表更小且更易于操作。

结果给出了非常接近经典 AST 的东西，无需任何手动操作；生成的树通常是它们自动派生的 CST 大小的 30-50%。

这很重要

使用大型语法（您不希望为 3500 条规则手动定义每个节点的映射）
使用瞬息万变的语法（当您尝试正确获得第一份工作草稿时）
构建工具来处理非常大的树（代表非常大的[系统]源代码，比如 Linux 源树），通过避免大量访问，必须接触数十亿个节点来计算答案缓存包含具体节点或列表脊柱的行。

我会提供我设计和构建的执行此操作的工具的名称，但有些 SO 人讨厌我这样做。你可以查看我的个人资料。

Answer 3

对于任何坚持这一点的人来说，Bart Kiers 的回答是一个很好的起点，我发现的一些可以很好地解释 Listener/Visitor 模式的资源是：

This presentation 来自泰勒大学计算机科学系和随附 GitHub example（特别是关于访客模式）
The Definitive ANTLR4 reference's 示例“4.3 构建翻译器听众

如何忽略不重要的节点？

How to leave out unimportant nodes?

java

antlr

antlr4

abstract-syntax-tree