使用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 applet执行).

语法:

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:...(或任何其他工具)]

您使用短语术语重写,然后显示一个有趣的例子,通过替换值并进行常量折叠来生成最终的程序答案,从而逐步处理程序的源代码.

抽象地说,你想从术语重写系统中得到的是从一组"术语重写"规则开始的能力,这些规则本质上是指定的

if you see this, replace it by that

例如

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

并重复地以有组织的方式应用这些规则,直到达到一些停止条件(通常是"不再适用规则").

有两种方法可以实现术语重写,既可以从术语开始(在你的情况下是程序的AST),也可以产生相同的结果.不同之处在于重写规则的实际实施方式.

程序树重写

第一种方式在程序上指定重写步骤.也就是说,构建一个访问者来遍历AST,它在程序上检查节点类型,以及有趣节点类型的子树("匹配"),并找到匹配的位置,根据所需的效果修改树.规则.

对于上面的"if"示例,访问者会找到"if"语句子树根,检查左/条件子树以查看它是否是"真实"子树,如果是,则用右子树替换"if"子树生产一棵改良的树.

常量折叠有点特殊:访问者检查操作员节点,检查其所有子节点是否为常量值,在这些常量上计算运算符的结果,然后用包含计算结果的节点替换运算符.

要使用一组规则实现重写,您必须首先记下所有抽象规则,然后对此访问者进行编码,并结合所有规则中的所有测试.这可能会产生一个非常混乱的代码,它会检查节点类型并在子树上上下走动以进行进一步检查.(你也可以按规则实现这一个访问者,这使得它们更容易编写,但是现在你有大量的访问者,你必须在树上重复运行它们......这最终会非常慢).

访问者有点聪明:你不希望它"在他们的时间之前"处理子树"考虑这个代码,由重写器处理:

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

在评估x 之前,您不希望常量折叠"3/0" .

您可以从任何解析器生成器(包括ANTLR)开始执行ASTs的过程重写; 写访客只是汗流.背.也许很多.

由于将所有规则匹配组合到访问者中的问题,程序重写很难实现.如果你有几十个规则,这就变得难以管理,速度很快.(如果您要使用规则来处理完整的计算机语言,那么每个语法位置至少会有一条规则;在这种情况下很容易获得数十条规则,如果不是数百条规则的话.

要获得OP所需的"增量"显示方面,您必须在每个匹配/替换步骤之后停止,然后重新打印AST,例如,从AST重新生成表面语法文本.修改访问者在每次树修改后调用prettyprint并不是很难.

但是,生成AST的解析器生成器通常不能为执行漂亮的打印步骤提供很好的帮助.它比看起来漂亮印刷更难.细节太复杂了,不能放在这里; 请参阅我的答案,了解如何详细说明如何执行此操作的详细信息.

下一个复杂问题:当遇到正在评估的程序中的变量时,应该在树中替换什么值？为此,需要一个符号表用于语言,并且必须使该符号表保持最新的变量值分配.

如果程序格式不正确,将不会讨论会发生什么.它们将是: - {很可能rwrites需要大量的"错误检查"来防止无意义的计算(例如,"x/y",其中y是一个字符串).

直接树重写

理想情况下,您想要的是直接接受明确的术语重写规则的引擎,并且可以应用它们.

程序转换系统(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"语句的规则.引号是metaquotes ; 它们将规则规范语言(RSL)的文本与规则操纵的语言文本分开.所述metaescaped字母(S,T,X,Y)是元变量,并且表示规则匹配的子树.这些元变量必须具有规则参数列表指定的AST类型(例如, s:statement表示s是"任何语句节点").

第三条规则实现了"加法"的恒定折叠.该模式寻找"+"运算符; 只有当找到一个同时具有数字常量的子项时才会获得匹配.它通过在其运算符上调用外部过程"\ Add"来工作; 添加返回包含总和的树,重写引擎将其拼接到位.

在DMS的情况下,在每次重写尝试(失败和成功)之后调用重写机制的钩子来跟踪重写结果.这个钩子将是OP称为prettyprinter的地方,以显示每个步骤后树的变化情况.

有关如何编写规则以评估代数表达式的详细示例,请参阅如何使用重写规则实现代数.

有关DMS重写规则如何工作的更详细说明,以及将它们应用于"简化"(评估)Nikolas Wirth的编程语言Oberon的示例,请参阅DMS重写规则.

在任何一种情况下都没有显示控制规则应用顺序的方法.因为排序约束可以是任意的,所以必须介入并引导重写引擎.如果需要,DMS提供规则排序的完整程序控制.通常,人们可以将规则划分为不同的集合:可以不加选择地应用的集合,以及需要排序的集合(例如,if-then简化规则).

PTS不会使符号表问题消失; OP仍然需要一个.大多数PTS不提供任何支持.DMS为此提供了明确的支持(配置需要一些努力,但比没有任何时候要少得多!)以及构建静态类型检查器以帮助在开始执行之前验证程序是否良好.实际上,有许多问题需要解决以准备执行程序(例如,可能想要构建标签的映射到源代码点以实现有效的GOTO模拟).见解析后的生活.