如何使用 Antlr 实现函数调用，以便在定义之前就可以调用它? [英] How to implement a function call with Antlr so that it can be called even before it is defined?
问题描述
一旦构建了 AST，那么实现 tree walker 以便可以以任何顺序定义和调用函数的最佳方法是什么?
Once the AST is built, what is the best way implement the tree walker so that functions can be defined and called in whatever order?
例如，这在 PHP 中是有效的:
For example, this is valid in PHP:
<?php
f(); // function called before it’s defined
function f() {
print 3;
}
?>
我猜测一定有第二遍或树转换，但我找不到关于这个主题的任何有趣的东西.问题可能不是 Antlr 特定的问题，但如果您能指出我如何完成此操作的 Antlr 示例，那就更好了！
I’m guessing that somehow there must be a second pass, or a tree transformation, but I can’t find anything interesting on this subject. The problem is probably not an Antlr-specific one, but if you could point me to an Antlr example of how this is done, even better!
推荐答案
是的，你是对的:这是通过 AST 多次完成的.
Yes, you are right: this is done in more than one pass over the AST.
您首先创建一个语法来构建源的 AST，然后创建一个树语法，用于迭代树并发现所有定义的函数.然后，您可以使用另一个树语法来评估脚本，该树语法从先前的树语法中获取发现的函数.
You first create a grammar that builds a AST of the source, then you create a tree grammar that is used to iterate over the tree and discovers all defined function. You could then evaluate the script using another tree grammar that takes the discovered functions from the previous tree grammar.
取源:
<?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 : '//' ~('
' | '
')* ('
'? '
' | EOF){skip();} ;
Space : (' ' | ' ' | '
' | '
'){skip();} ;
然后使用从以下树语法生成的tree-walker"发现声明的函数:
Then discover the declared functions using a "tree-walker" generated from the following tree grammar:
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):
To test it all, create a lexer and parser (A), generate the "tree-walker" (B), compile all source files (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):
and run the following main class (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
" +
"f(); // function called before it’s defined
" +
"function f() {
" +
" g();
" +
"}
" +
"function g() {}
" +
"?>
";
// 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 中，而是作为 Map 轻松获取函数的根并在调用时对其进行评估.
Of course, this is just an example of how to approach it, not of how it is best done. I can imagine (when using Java to interpret the script), you wouldn't store the declared functions as simple Strings in a Set<String>, but rather as a Map<String, CommonTree> to easily get the root of a function and evaluate it when called.
进一步阅读:http://www.antlr.org/wiki/display/ANTLR3/Simple+tree-based+interpeter
祝你好运！
编辑
然后可以检查是否所有函数都使用之前的 tree-walker 在它之前定义了秒数:
The seconds pass could then check if all functions are defined ahead of it using the previous 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
" +
"f(); // function called before it’s defined
" +
"function f() {
" +
" g();
" +
" x();
" +
"}
" +
"function g() {}
" +
"?>
";
// 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 不会产生任何异常.
produces an exception since x() is not define anywhere. Removing it from the source will cause the tree-walker to produce no exception.
这篇关于如何使用 Antlr 实现函数调用，以便在定义之前就可以调用它?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
