如何使用Antlr实现函数调用，以便甚至在定义之前就可以调用它？ [英] How to implement a function call with Antlr so that it can be called even before it is defined?
问题描述
一旦构建了AST，实现树遍历器的最佳方法是什么，以便可以按任何顺序定义和调用函数？
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：
which is parsed into the following 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发现声明的函数：
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 \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> 即可轻松获取函数的根并在调用时对其求值。
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.
进一步阅读：< a href = http://www.antlr.org/wiki/display/ANTLR3/Simple+tree-based+interpeter rel = noreferrer> http://www.antlr.org/wiki/display/ANTLR3/简单+基于树的+干扰程序
祝你好运！
编辑
然后，秒传递可以检查是否使用先前的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 \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 （）不在任何地方定义。从源代码中删除它会导致树行者不会产生异常。
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屋！
