构建 AST 后，实现 tree walker 的最佳方法是什么，以便可以以任何顺序定义和调用函数？
例如，这在 PHP 中是有效的：
<?php
f(); // function called before it’s defined
function f() {
print 3;
}
?>
我猜想一定有第二遍，或者树变换，但我在这个主题上找不到任何有趣的东西。问题可能不是特定于 Antlr 的问题，但如果您能指出一个 Antlr 示例来说明这是如何完成的，那就更好了！
问问题
6172 次
1 回答
9
是的，你是对的：这是通过不止一次 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-walker”发现声明的函数：
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），生成“tree-walker”（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 来解释脚本时），您不会将声明的函数作为简单的字符串存储在 aSet<String>中，而是作为 aMap<String, CommonTree>轻松获取函数的根并在调用时对其进行评估。
进一步阅读：http ://www.antlr.org/wiki/display/ANTLR3/Simple+tree-based+interpeter
祝你好运！
编辑
然后，秒通过可以检查是否所有函数都使用之前的 tree-walker 在它之前定义：
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()没有在任何地方定义。从源中删除它会导致 tree-walker 不会产生异常。
于 2010-11-02T10:22:23.180 回答