文法を見ずに何を提案すればよいかを正確に知ることは困難です。私はあなたが書いたものについてここでいくつかの仮定をしましたが、それは正しくないかもしれません。しかし、私があなたの問題に厳密に固執していなくても、あなたが抱えている問題はそれ自体で対処するのに十分一般的だと思います。他に何もないとしても、提供されている例で必要なものが得られることを願っています。
算術演算子は左から右に評価されます。あなたが抱えていると思われる問題は、ノードがASTに表示される順序であり、ノードにアクセスする順序であるため、の=演算子が左から右に評価されていることです。a = b = 1 + 2
ただし、=オペランド式は右から左に評価されます。ノードの順序を変更することで、ツリーにこれを表すことができます。しかし、私がより理にかなっていると思うのは、ASTでの入力の自然な順序を維持しながら、目的の評価順序に対応するようにツリーウォーカーを変更することです。
たとえば、ASTが次のように表示されるとします。
=
/ \
a =
/ \
b +
/ \
1 2
演算子を正しい順序で評価することは、次の手順で機能します。
- ツリーウォーカーが最初にヒットし
=ます。右側が最初に評価されることがわかっているため、処理をスキップしますa。2番目の子に続き=ます。
- 2番目にヒットし
=ます。+今のところスキップして、2番目の子（）を評価しbます。
+が評価されます。今3はスタックにあり、スタックにあるのはそれだけです。- 最後の子（ ）が評価された後、保留中の
=ロジックが引き継ぎます。と呼ばれ、と呼ばれます。スタック上にあります。+dupistoreb3
- 最後の子（ ）が評価された後、保留中の
=ロジックが引き継ぎます。と呼ばれ、と呼ばれます。スタック上にあります。=dupistorea3
- ステートメントが終了するので、
popと呼ばれます。スタックは空になりました。
注意：このプロセスでは、すべてのステートメント（割り当てを実行するかどうかに関係なく）は、スタック上の唯一の値で終了することが期待されます。ステートメントの終わりだけがそれをポップします。プッシュする自然な値がない式（たとえば、への呼び出し）は、、、、または予約済みオブジェクトであっても、void foo()何かをプッシュすることが期待されます。これらの式が割り当てられていないことを確認するのは、コンパイラの初期段階の仕事です。null0void
以下は、トークンパーサーとツリーパーサーの短い例と、テストの入力と出力であり、ANTLR（v3）でこれを行う方法を示しています。簡単にするために疑似命令を使用し、出力を最適化しようとはしませんでした。
Ordered.g
grammar Ordered;
options
{
output = AST;
}
tokens {
COMPUNIT;
STAT;
REFID;
}
compilationUnit : statement* EOF -> ^(COMPUNIT statement*);
statement: assign_expr SEMI -> ^(STAT assign_expr)
| expr SEMI -> ^(STAT expr)
;
assign_expr: ID EQ^ (assign_expr | expr); //call recursively to keep the tree simple.
expr : add_expr;
add_expr : primary_expr (PLUS^ primary_expr)*;
primary_expr
: NUM
| (ID -> REFID[$ID.text]) //An ID expr is a reference to the thing named in ID.
| LPAR! expr RPAR!
;
SEMI: ';';
EQ : '=';
LPAR : '(';
RPAR : ')';
PLUS : '+';
ID : ('a'..'z'|'A'..'Z')+;
NUM: ('0'..'9')+;
WS : (' '|'\t'|'\f'|'\r'|'\n')+ {skip();};
OrderedTreeParser.g
tree grammar OrderedTreeParser;
options {
output = AST;
tokenVocab = Ordered;
ASTLabelType = CommonTree;
filter = true;
}
@members {
private java.util.LinkedList<String> assigningIds = new java.util.LinkedList<String>();
}
topdown
: enter_assign
;
enter_assign
: ^(EQ ID {assigningIds.push($ID.getText());} .+) //Push our ID and handle assignment during bottomup.
;
bottomup
: NUM {System.out.println("lcd " + $NUM.getText());}
| EQ
{
System.out.println("dup");
System.out.println("istore " + assigningIds.pop());
}
| PLUS {System.out.println("iadd");}
| REFID {System.out.println("iload " + $REFID.getText());}
| STAT {System.out.println("pop");}
;
OrderedTest.java
import java.io.IOException;
import org.antlr.runtime.ANTLRStringStream;
import org.antlr.runtime.CharStream;
import org.antlr.runtime.CommonTokenStream;
import org.antlr.runtime.RecognitionException;
import org.antlr.runtime.tree.CommonTreeNodeStream;
import org.antlr.runtime.tree.Tree;
public class OrderedTest {
public static void main(String[] args) throws Exception {
test("a = 1;");
test("a = 1 + 2;");
test("a = b = 1 + 2;");
test("a = b = 1 + c;");
test("x = y = z = 1 + 2;");
test("1 + 2;"); //no assignment
}
private static void test(String str) throws RecognitionException, Exception, IOException {
CharStream input = new ANTLRStringStream(str);
OrderedLexer lexer = new OrderedLexer(input);
CommonTokenStream tokens = new CommonTokenStream(lexer);
OrderedParser parser = new OrderedParser(tokens);
OrderedParser.compilationUnit_return result = parser.compilationUnit();
if (lexer.getNumberOfSyntaxErrors() > 0 || parser.getNumberOfSyntaxErrors() > 0){
throw new Exception("Syntax Errors encountered!");
}
OrderedTreeParser tparser = new OrderedTreeParser(new CommonTreeNodeStream(result.getTree()));
tparser.downup(result.getTree());
System.out.println("---------");
}
}
テストケース
入力
a = 1;
出力
lcd 1
dup
istore a
pop
入力
a = 1 + 2;
出力
lcd 1
lcd 2
iadd
dup
istore a
pop
入力
a = b = 1 + 2;
出力
lcd 1
lcd 2
iadd
dup
istore b
dup
istore a
pop
入力
a = b = 1 + c;
出力
lcd 1
iload c
iadd
dup
istore b
dup
istore a
pop
入力
x = y = z = 1 + 2;
出力
lcd 1
lcd 2
iadd
dup
istore z
dup
istore y
dup
istore x
pop
入力
1 + 2;
出力
lcd 1
lcd 2
iadd
pop