类似结构的源代码解析和类似宏的处理

Question

TL;DR VERSION：是否有支持以下内容的解析器生成器：当某些规则被缩减时（我假设是 LALR(1) 解析器），则不执行缩减，但解析器会退出并将输入替换为使用此规则中的值的不同代码并解析该代码。如果需要重复。所以如果代码是 "i++" 并且规则是 "expr POST_INCR"，我可以做或多或少：

expr POST_INCR -> "(tmp = expr; expr = expr + 1; tmp)"

所以基本上是使用宏重写代码？

长版：

我编写了另一种简单的解释型语言（为简单起见，在 Java 中）。它工作正常，但它提出了一些问题。简介很长，但很简单，有助于清楚地说明我的问题（我认为）。

我有 "while" 循环。这很简单，给定：

WHILE LPARE boolean_expression RPAREN statement

我或多或少生成了以下内容：

new WhileNode(boolean_expression, statement);

这会创建新节点，稍后访问该节点时，会为我的虚拟机生成代码。但我还有以下内容：

FOR LPAREN for_init_expr SEMICOLON boolean_expression SEMICOLON for_post_expr RPAREN statement

这是从 Java 或 C 中得知的 "for loop"。根据上述规则，我或多或少地创建了以下内容：

new ListNode(
    for_init_expr,
    new WhileNode(
        boolean_expression,
        new ListNode(
            statement,
            new ListNode(for_post_expr, null))))

这当然是简单的改造，来自：

for (for_init ; boolean_expression ; for_post_expr)
    statement

至：

for_init
while (boolean_expression) {
    statement
    for_post_expr;
}

一切都很好，但以下情况变得棘手：

FOR LPAREN var_decl COLON expression RPAREN statement

这个如果广为人知并且喜欢：

for (int x : new int[] { 1, 2 })
    print(x);

我避免使用 post 生成 AST 的代码，因为基本的 for 循环已经有点长了，而且我们得到的结果更糟。此构造等于：

int[] tmp = new int[] { 1, 2 };
for (int it = 0 ; it < tmp.length; it = it + 1) {
    int x = tmp[it];
    print(x);
}

并且因为我没有使用类型，所以我简单地假设 "expression"（右边，在 COLON 之后）是我可以迭代的东西（并且数组不可迭代），我调用一个函数基于这个 "expression" which returns Iterable 实例的结果。所以，其实我重写的代码并没有上面的那么简单，大致是这样的：

Iterator it = makeIterable(new int[] { 1, 2 });
while (it.hasNext()) {
    int x = it.next();
    print(x);
}

看起来还不错，但请注意，AST 会为此生成三个函数调用和 while 循环。为了向您展示它有多乱，我 post 我现在拥有的是：

113     | FOR LPAREN var_decl_name.v PIPE simple_value_field_or_call.o RPAREN statement.s
114                                         {: Symbol sv = ext(_symbol_v, _symbol_o);
115                                            String autoVarName = generateAutoVariableName();
116                                            Node iter = new StatementEndNode(sv, "",
117                                                new BinNode(sv, CMD.SET, "=",
118                                                    new VarDeclNode(sv, autoVarName),
119                                                    new CallNode(sv, "()",
120                                                        new BinNode(sv, CMD.DOT, ".",
121                                                            new MkIterNode(sv, o),
122                                                            new PushConstNode(sv, "iterator")))));
123                                            Node varinit = new StatementEndNode(sv, "",
124                                                new BinNode(sv, CMD.SET, "=",
125                                                    v,
126                                                    new PushConstNode(sv, "null")));
127                                            Node hasnext = new CallNode(sv, "()",
128                                                new BinNode(sv, CMD.DOT, ".",
129                                                    new VarNode(sv, autoVarName),
130                                                    new PushConstNode(sv, "hasNext")));
131                                            Node vargennext = new StatementEndNode(sv, "",
132                                                new BinNode(sv, CMD.SET, "=",
133                                                    new VarNode(sv, v.name),
134                                                    new CallNode(sv, "()",
135                                                        new BinNode(sv, CMD.DOT, ".",
136                                                            new VarNode(sv, autoVarName),
137                                                            new PushConstNode(sv, "next")))));
138                                            return new ListNode(sv, "",
139                                                new ListNode(sv, "",
140                                                    new ListNode(sv, "",
141                                                        iter
142                                                    ),
143                                                    varinit
144                                                ),
145                                                new WhileNode(sv, "while",
146                                                    hasnext,
147                                                    new ListNode(sv, "",
148                                                        new ListNode(sv, "",
149                                                            vargennext
150                                                        ),
151                                                        s)));

回答你的问题：是的，我为这段代码感到羞耻。

问题：是否有解析器生成器让我做一些事情，即给定规则：

FOR LPAREN var_decl COLON expr RPAREN statement

告诉解析器重写它，就好像它是别的东西一样。我想这将需要某种 LISP 的宏机制（由于基本上缺乏语法，这在 lisp 中很容易），可能与此类似：

FOR LPAREN var_decl COLON expr RPAREN statement =
    {   with [ x = generateAutoName(); ]
        emit [ "Iterator $x = makeIterable($expr).iterator();"
               "while (${x}.hasNext()) {"
               "$var_decl = ${x}.next();"
               "$statement"
               "}"
        ]
    }

我不知道这是否是一个众所周知的问题，我什至不知道要寻找什么 - 我发现的最相似的问题是这个问题：Any software for pattern-matching and -rewriting source code? 但它与我的需要相去甚远，因为它应该作为一个单独的步骤而不是在编译期间工作，所以它不符合条件。

任何帮助将不胜感激。

Answer 1

也许您正在寻找类似 ANTLR 的树重写规则之类的东西。

您可以通过定义一些辅助函数来使您的 AST 构造语法更具可读性。在我看来，有很多冗余（为什么运算符既需要枚举又需要字符串？）但我不是 Java 程序员。

您可能采取的一种方法：

从您的解析器开始，它已经生成了 AST。添加一两个词法语法来处理模板参数和 gensyms。然后编写一个 AST walker，它将 AST 序列化为重新生成 AST 所需的代码（Java 或字节码）。使用它，您可以使用自己的解析器生成宏模板函数，这意味着它将自动与您可能对 AST 所做的任何更改保持同步。

Answer 2

我认为您试图过度弯曲解析器。你可以简单地构建包含宏的树，然后 post- 处理树以用您想要的任何替换替换宏。

您可以通过遍历生成的树、检测宏节点（或您想要进行替换的地方）并使用程序树黑客简单地拼接替换来实现这一点。不漂亮但可行。您应该能够使用任何解析器 generator/AST 构建机器的结果来执行此操作。

如果您想要一种更结构化的方法，您可以构建您的 AST，然后使用源到源转换将宏"rewrite" 转换为它们的内容。 Out DMS Software Reengineering Toolkit 可以做到这一点，你可以阅读更多细节关于 transforms look like.

使用 DMS 方法，您的概念：

expr POST_INCR -> "(tmp = expr; expr = expr + 1; tmp)"

要求您以常规方式解析原文语法规则的方式：

 term = expr POST_INCR ;

你会把所有这些语法规则都交给DMS，让它解析源代码并根据语法构建你的 AST。

然后您将 DMS 重写应用于生成的树：

domain MyToyLanguage; -- tells DMS to use your grammar to process the rule below

rule replace_POST_INCR(e: expr): term->term
  = "\e POST_INCR" -> " (tmp = \e; \e = \e + 1; tmp) ";

这里的引号是"domain meta quotes"而不是字符串文字引号。双引号外的文本是 DMS 规则语法。引号内的文本是来自您的语言 (MyToyLangauge) 的语法，并使用您提供的解析器进行解析，一些模式变量的特殊转义，如 \e。（您无需对语法进行任何操作即可获得此模式解析功能；DMS 会负责）。

根据 DMS 的约定，我们通常将文字标记命名为 POST_INCR 在词法分析器中使用带引号的等效“++”，而不是使用这样的名称。而不是

#token POST_INCR "\+\+"

词法分析器规则如下所示：

#token '++'  "\+\+"

如果你这样做，那么你的语法规则如下：

term = expr '++' ;

您的重写规则现在如下所示：

rule replace_POST_INCR(e: expr): term->term
  = "\e++" -> " (tmp = \e; \e = \e + 1; tmp) ";

遵循这个约定，语法（词法分析器和 BNF）是（恕我直言）更具可读性，并且重写规则也更具可读性，因为它们保留非常接近实际的语言语法。

类似结构的源代码解析和类似宏的处理

Source code parsing and macro-like handling of similar constructions

java

parsing

lalr