Как реализовать вызов функции с помощью Antlr, чтобы ее можно было вызывать еще до того, как она была определена? - PullRequest
Новая
       24

Как реализовать вызов функции с помощью Antlr, чтобы ее можно было вызывать еще до того, как она была определена?

6 голосов
/ 02 ноября 2010

Как только AST построен, каков наилучший способ реализовать обходчик дерева, чтобы функции могли быть определены и вызваны в любом порядке?

Например, это действительно в PHP: 

<?php
f(); // function called before it’s defined
function f() {
  print 3;
}
?>

Я предполагаю, что каким-то образом должен быть второй проход или преобразование дерева, но я не могу найти ничего интересного по этому вопросу.Вероятно, проблема не в Antlr-специфичной проблеме, но, если бы вы могли указать мне на пример Antlr того, как это делается, еще лучше!

1 Ответ

8 голосов
/ 02 ноября 2010

Да, вы правы: это делается более чем за один проход по AST.

Сначала вы создаете грамматику, которая строит AST источника, затем вы создаете древовидную грамматику, которая используется дляперебирать дерево и обнаруживает все определенные функции.Затем вы можете оценить скрипт, используя другую древовидную грамматику, которая берет обнаруженные функции из предыдущей древовидной грамматики.

Демонстрация.

Возьмите источник: 

<?php
f(); // function called before it’s defined
function f() {
  g();
}
function g() {}
?>

, который разбирается в следующее AST:

alt text

используя (комбинированную) грамматику: 

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() нигде не определен.Удаление его из источника приведет к тому, что обходчик деревьев не выдаст исключений.

...