ASTが構築されたら、関数を定義して任意の順序で呼び出すことができるように、ツリーウォーカーを実装するための最良の方法は何ですか？
たとえば、これはPHPで有効です。
<?php
f(); // function called before it’s defined
function f() {
print 3;
}
?>
どういうわけか、2回目のパス、つまりツリー変換が必要だと思いますが、このテーマに関して興味深いものは何も見つかりません。問題はおそらくAntlr固有の問題ではありませんが、これがどのように行われるかのAntlrの例を教えていただければ、さらに良いでしょう！
はい、その通りです。これは、ASTの複数のパスで行われます。
最初にソースのASTを構築する文法を作成し、次にツリーを反復処理して定義されたすべての関数を検出するために使用されるツリー文法を作成します。次に、前のツリー文法から検出された関数を取得する別のツリー文法を使用してスクリプトを評価できます。
ソースを取る：
<?php
f(); // function called before it’s defined
function f() {
g();
}
function g() {}
?>
これは、次のASTに解析されます。
（組み合わせた）文法を使用する：
grammar PHPMin;
options {
output=AST;
}
tokens {
SCRIPT; F_CALL; F_DECL; F_BODY;
}
parse
: script EOF -> script
;
script
: '<?php' atom* '?>' -> ^(SCRIPT atom*)
;
atom
: functionCall
| functionDecl
;
functionCall
: Identifier '(' ')' ';' -> ^(F_CALL Identifier)
;
functionDecl
: 'function' Identifier '(' ')' '{' functionBody '}' -> ^(F_DECL Identifier functionBody)
;
functionBody
: functionCall* -> ^(F_BODY functionCall*)
;
Identifier : ('a'..'z' | 'A'..'Z' | '_') ('a'..'z' | 'A'..'Z' | '_' | '0'..'9')* ;
LineComment : '//' ~('\r' | '\n')* ('\r'? '\n' | EOF){skip();} ;
Space : (' ' | '\t' | '\r' | '\n'){skip();} ;
次に、次のツリー文法から生成された「ツリーウォーカー」を使用して、宣言された関数を検出します。
tree grammar PHPMinFunctionWalker;
options {
tokenVocab=PHPMin;
ASTLabelType=CommonTree;
}
@members {
java.util.Set<String> declared = new java.util.HashSet<String>();
}
discover
: script
;
script
: ^(SCRIPT atom*)
;
atom
: functionCall
| functionDecl
;
functionCall
: ^(F_CALL Identifier)
;
functionDecl
: ^(F_DECL Identifier functionBody) {declared.add($Identifier.text);}
;
functionBody
: ^(F_BODY functionCall*)
;
すべてをテストするには、レクサーとパーサーを作成し（A）、「ツリーウォーカー」を生成し（B）、すべてのソースファイルをコンパイルします（C）。
// A
java -cp antlr-3.2.jar org.antlr.Tool PHPMin.g
// B
java -cp antlr-3.2.jar org.antlr.Tool PHPMinFunctionWalker.g
// C
javac -cp antlr-3.2.jar *.java
// D
java -cp .:antlr-3.2.jar Main // *nix
java -cp .;antlr-3.2.jar Main // Windows
次のメインクラス（D）を実行します。
import org.antlr.runtime.*;
import org.antlr.runtime.tree.*;
import org.antlr.stringtemplate.*;
public class Main {
public static void main(String[] args) throws Exception {
String source = "<?php \n" +
"f(); // function called before it’s defined \n" +
"function f() { \n" +
" g(); \n" +
"} \n" +
"function g() {} \n" +
"?> \n";
// create a lexer and parser for the source
ANTLRStringStream in = new ANTLRStringStream(source);
PHPMinLexer lexer = new PHPMinLexer(in);
CommonTokenStream tokens = new CommonTokenStream(lexer);
PHPMinParser parser = new PHPMinParser(tokens);
PHPMinParser.parse_return returnValue = parser.parse();
CommonTree tree = (CommonTree)returnValue.getTree();
// create a tree walker to discover all declared functions
CommonTreeNodeStream nodes = new CommonTreeNodeStream(tree);
nodes.setTokenStream(tokens);
PHPMinFunctionWalker functions = new PHPMinFunctionWalker(nodes);
functions.discover();
System.out.println("Declared functions: "+functions.declared);
}
}
これにより、次の出力が生成されます。
Declared functions: [f, g]
もちろん、これはそれにアプローチする方法の単なる例であり、それが最善の方法であるということではありません。私は想像できます（Javaを使用してスクリプトを解釈する場合）。宣言された関数を単純な文字列Set<String>としてではなくMap<String, CommonTree>、関数のルートを簡単に取得して呼び出されたときに評価するために格納します。
さらに読む：http ：//www.antlr.org/wiki/display/ANTLR3/Simple+tree-based+interpeter
幸運を！
編集
秒の経過により、前のツリーウォーカーを使用して、すべての関数がその前に定義されているかどうかを確認できます。
tree grammar PHPMinValidateWalker;
options {
tokenVocab=PHPMin;
ASTLabelType=CommonTree;
}
@members {
java.util.Set<String> declared = new java.util.HashSet<String>();
}
validate
: script
;
script
: ^(SCRIPT atom*)
;
atom
: functionCall
| functionDecl
;
functionCall
: ^(F_CALL Identifier)
{
if(!declared.contains($Identifier.text)) {
throw new RuntimeException("no such function: " + $Identifier.text);
}
}
;
functionDecl
: ^(F_DECL Identifier functionBody)
;
functionBody
: ^(F_BODY functionCall*)
;
テストの使用：
import org.antlr.runtime.*;
import org.antlr.runtime.tree.*;
import org.antlr.stringtemplate.*;
public class Main {
public static void main(String[] args) throws Exception {
String source = "<?php \n" +
"f(); // function called before it’s defined \n" +
"function f() { \n" +
" g(); \n" +
" x(); \n" +
"} \n" +
"function g() {} \n" +
"?> \n";
// create a lexer and parser for the source
ANTLRStringStream in = new ANTLRStringStream(source);
PHPMinLexer lexer = new PHPMinLexer(in);
CommonTokenStream tokens = new CommonTokenStream(lexer);
PHPMinParser parser = new PHPMinParser(tokens);
PHPMinParser.parse_return returnValue = parser.parse();
CommonTree tree = (CommonTree)returnValue.getTree();
// create a tree walker to discover all declared functions
CommonTreeNodeStream nodes = new CommonTreeNodeStream(tree);
nodes.setTokenStream(tokens);
PHPMinFunctionWalker functions = new PHPMinFunctionWalker(nodes);
functions.discover();
System.out.println("Declared functions: "+functions.declared);
// PHPMinValidateWalker
nodes = new CommonTreeNodeStream(tree);
nodes.setTokenStream(tokens);
PHPMinValidateWalker validator = new PHPMinValidateWalker(nodes);
validator.declared = functions.declared;
validator.validate();
}
}
x()はどこにも定義されていないため、例外が生成されます。ソースから削除すると、ツリーウォーカーは例外を生成しません。