java - 使用ANTLR(或任何其他工具)编写术语重写解析器/表达式评估器

Question

我正在尝试编写仅具有以下功能才能执行基本编程语言指令的软件:

算术表达式评估器(加，减，乘，除，括号，...)

if-else语句

函数定义

并且它应该一次一步显示正在“减少”或“简化”的代码，并让我显示一个示例输出示例:

迭代1:

a=3;
b=2;
c=true;
if(c && (a < 3 * (5 -2) ) || b >= 3 * (5 -2))){
    System.out.println("going through if");
}else{
    System.out.println("going through else");
}

迭代2:

if(true && (a < 3 * (5 -2) ) || b >= 3 * (5 -2))){
    System.out.println("going through if");
}else{
    System.out.println("going through else");
}

迭代3:

if(true && (3 < 3 * (5 -2) ) || 2 >= 3 * (5 -2))){
    System.out.println("going through if");
}else{
    System.out.println("going through else");
}

迭代4:

if(true && (3 < 9 ) || 2 >= 3 * (5 -2))){
    System.out.println("going through if");
}else{
    System.out.println("going through else");
}

迭代5:

if(true && (3 < 9 ) || 2 >= 3 * 3)){
    System.out.println("going through if");
}else{
    System.out.println("going through else");
}

迭代6:

if(true && (3 < 9 ) || 2 >= 9)){
    System.out.println("going through if");
}else{
    System.out.println("going through else");
}

迭代7:

if(true && true || 2 >= 9)){
    System.out.println("going through if");
}else{
    System.out.println("going through else");
}

迭代8:

if(true && (true || false)){
    System.out.println("going through if");
}else{
    System.out.println("going through else");
}

迭代9:

if(true && false){
    System.out.println("going through if");
}else{
    System.out.println("going through else");
}

迭代10:

if(false){
    System.out.println("going through if");
}else{
    System.out.println("going through else");
}

迭代11:

System.out.println("going through else");

因此，它应该解析输入代码并在每次迭代中同时执行它，一次只执行一次基本操作，替换操作结果并在不需要更多简化步骤时完成循环。任何人都知道如何执行此操作，例如使用ANTLR工具？我一直在检查ANTLR的Tree Listener功能，因为这似乎很可行，但是我不清楚如何实现它。

另一个是最佳的是，它可以用Javascript实现，以便能够在Web浏览器中执行，但是Java代码就足够了(即，作为Java小程序执行)。

语法:

program
    :   (variable | function)*
        statement*
    ;


variable
    :   IDENT ('=' expression)? ';'
    ;

type
    :   'int'
    |   'boolean'
    |   'String'
    |   'char'
    ;


statement
    :   assignmentStatement
    |   ifStatement
    ;


ifStatement
    :   'if' '(' expression ')' '{' statement+ '}'
        ('else if' '(' expression ')' '{' statement+)* '}'
        ('else' '{' statement+)? '}'
    ;

assignmentStatement
    :   IDENT '=' expression ';'
    ;


returnStatement
    :   'return' expression ';'
    ;


function
    :   'function' IDENT '(' parameters? ')' '{'
        (statement|returnStatement)*
        '}'
    ;   

parameters
    :   IDENT (',' IDENT)*
    ;

term
    :   IDENT
    |   '(' expression ')'
    |   INTEGER
    ;

negation
    :   '-' -> NEGATION
    ;

unary
    :   ('+'! | negation^)* term
    ;

mult
    :   unary (('*' | '/' | 'mod') unary)*
    ;

add
    :   mult (('+' | '-') mult)*
    ;

relation
    :   add (('=' | '/=' | '<' | '<=' | '>=' | '>') add)*
    ;

expression
    :   relation (('and' | 'or') relation)*
    ;


fragment LETTER : ('a'..'z' | 'A'..'Z') ;
fragment DIGIT : '0'..'9';
INTEGER : DIGIT+ ;
IDENT : LETTER (LETTER | DIGIT)*;
WS : (' ' | '\t' | '\n' | '\r' | '\f')+ {$channel = HIDDEN;};
COMMENT : '//' .* ('\n'|'\r') {$channel = HIDDEN;};

Answer 1

[OP:...(或其他任何工具)]

您使用短语term rewriting，然后显示一个有趣的示例，该示例通过替换值并执行constant folding以产生最终程序答案，来逐步处理程序的源代码。

抽象地讲，您希望从术语重写系统中获得的能力是从一组“术语重写”规则开始，该规则本质上是指定

if you see this, replace it by that

例如

" if (true) then ... "  ==>   " ... "

并以有组织的方式重复应用这些规则，直到达到某种停止条件为止(通常是“不再应用任何规则”)。

有两种方法可以实现术语重写，两种方法均以术语(您的情况下为程序的AST)开头，并产生相同的结果。区别在于重写规则的实际实现方式。

过程树重写

第一种方法按程序指定重写步骤。即，构造一个访问者以遍历AST，然后按程序检查节点类型和感兴趣的节点类型的子树(“匹配”)，并在找到匹配的地方根据期望的效果修改树。规则。

对于上面的“if”示例，访问者将找到“if”语句子树的根，检查左侧/条件子树是否为“true”子树，如果是，则用右侧子树替换“if”子树产生修改后的树。

常量折叠有点特殊:访问者检查一个运算符节点，检查其所有子元素是否为常量值，在这些常量上计算该运算符的结果，然后用包含计算结果的节点替换该运算符。

要使用一组规则实现重写，您必须首先写下所有抽象规则，然后对该访问者进行编码，并结合所有规则中的所有测试。这会产生非常困惑的代码，它正在检查节点类型并在子树中上下移动以进行进一步的检查。 (您还可以将每个规则的访问者实现为一个访问者，这使得它们更易于编写，但是现在您有大量的访问者，因此必须在树上反复运行它们……结果非常慢)。

访问者有点聪明:您不希望它在“子时间到来之前”处理子树。请考虑以下由重写器处理的代码:

  if (x) then y = 3/ 0; else y = 3;

您不希望在评估x之前将其常数折叠为“3/0”。

您可以从任何解析器生成器(包括ANTLR)的AST开始实现过程重写。写访客只是汗水。也许很多。

由于将所有规则匹配都组合到访问者中，因此程序重写很难实现。如果您有许多规则，那么这将变得难以管理，快速。 (如果要使用规则来处理一种完整的计算机语言，则每位语法至少要有一个规则；在这种情况下，很容易获得几十个规则(如果不是数百个)。

为了获得OP所需的“增量”显示方式，您必须在每个匹配/替换步骤之后停止，然后漂亮地打印AST，例如，从AST重新生成表面语法文本。每次修改树后，修改访问者以调用prettyprint并不难。

但是，产生AST的解析器生成器通常不能为完成 pretty-print 步骤提供良好的帮助。这比看起来漂亮更难。细节太复杂了，不能放在这里。有关如何执行此操作的详细信息，请参见我的 SO answer on how to prettyprint。

下一个复杂性:当遇到要评估的程序中的变量时，应在树中替换哪个值？为此，需要一种用于语言的符号表，并且必须使该符号表保持最新状态，才能将值分配给变量。

如果程序格式错误，会发生什么情况，这里没有讨论。它们将是:-{rwrites可能需要进行大量“错误检查”以防止无意义的计算(例如，“x / y”，其中y是字符串)。

直接树重写

理想情况下，您想要的是一种引擎，该引擎直接接受显式术语重写规则，并可以应用它们。

Program Transformation Systems (PTS)执行此操作。特定系统包括Mathematica(现在称为“Wolfram语言”？)，DMS，TXL，Stratego / XT。
(OP一直在寻找一种用Java实现的工具:我认为Stratego有Java版本，而其他人肯定没有)。

这些工具接受使用目标语言的表面语法编写的重写规则，将规则本质上转换为模式树对(具有可变占位符的“匹配”树)和具有(相同)变量占位符的“替换”树。这些工具中的重写引擎将采用指定规则的任意子集，并将其应用于树，通过将“匹配”树与目标树进行比较来检查所有匹配项，然后替换替换树，并在其中替换占位符找到匹配项时的匹配项。这是编写复杂的重写集的主要便利。 (如果您考虑一下，这仍然是过程重写……只是引擎在做它，而不是您在做规则说明者。尽管如此，还是很方便的)。

这样的PTS包括用于生成AST的解析器生成器(Mathematica不提供)和完整的prettyprinter(或至少允许您方便地定义一个)。

对于DMS，您可以编写如下规则:

 rule fold_true_ifTE(s: statement, t:statement): statement->statement =
 "  if (true) then \s else \t " ->  " \s ";

 rule fold_false_ifTE(s: statement, t:statement): statement->statement =
 "  if (false) then \s else \t " ->  " \t ";

 rule fold_constants_add(x:NUMBER,y:NUMBER):sum -> sum =
 " \x + \y " -> " \Add\(\x\,\y\)";

前两个规则实现了我们之前概述的“if”语句重写；您还需要仅用于“if-then”语句的规则。引号是元引号；它们将规则规范语言(RSL)的文本与规则所操纵的语言的文本分开。元转义字母(s，t，x，y)是元变量，表示规则匹配的子树。这些元变量必须具有规则参数列表指定的AST类型(例如s:语句意味着s是“任何语句节点”)。

第三条规则实现了“加法”的恒定折叠。该模式寻找“+”运算符；只有找到两个 child 都是数字常数的 child ，它才会匹配。它通过在其运算符上调用外部过程“\ Add”来工作； Add返回包含总和的树，重写引擎将其合并到位。

对于DMS，在每次重写尝试(失败和成功)之后都会调用重写机制，以跟踪重写结果。该挂钩将是OP调用prettyprinter的地方，以显示树在每一步之后如何发生变化。

有关如何编写规则以评估代数表达式的详细示例，请参见 how to implement Algebra with rewrite rules。

有关DMS重写规则如何工作的更详细描述，以及将其应用于“简化”(评估)Nikolas Wirth的编程语言Oberon的示例，请参见 DMS Rewrite Rules。

在两种情况下均未显示控制规则应用顺序的方法。由于排序约束可以是任意的，因此必须介入并指导重写引擎。如果需要，DMS可提供规则排序的完整程序控制。通常，人们可以将规则划分为不同的集合:可以随意应用的规则和需要排序的规则(例如，if-then简化规则)。

PTS不会使符号表问题消失。 OP仍然需要一个。大多数PTS对此均不提供任何支持。 DMS为此提供了明确的支持(需要花费一些精力进行配置，但要比没有任何方法少得多!)，并构建静态类型检查器以帮助在程序开始执行之前验证程序是否格式正确。实际上，准备要执行的程序需要解决许多问题(例如，可能需要构建标签到源代码点的映射，以实现有效的GOTO仿真)。参见 Life After Parsing。