Comment mettre en oeuvre un appel de fonction avec Antlr afin qu'il puisse être appelé avant même qu'elle est définie?

Question

Une fois que l'AST est construit, ce qui est la meilleure façon de mettre en œuvre le marcheur arbre afin que les fonctions peuvent être définies et appelées dans l'ordre?

Par exemple, ceci est valable en PHP:

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

Je suppose que d'une certaine manière il doit y avoir un second passage, ou une transformation de l'arbre, mais je ne peux pas trouver quelque chose d'intéressant à ce sujet. Le problème est probablement pas un spécifique-Antlr, mais si vous pouviez me montrer un exemple de la façon dont Antlr cela se fait, encore mieux!

Answer 1

Oui, vous avez raison. Cela se fait dans plus d'une passe au-dessus de l'AST

Vous devez d'abord créer une grammaire qui construit une AST de la source, vous créez une grammaire d'arbre qui est utilisé pour itérer sur l'arbre et découvre la fonction tous définis. Vous pouvez ensuite évaluer le script en utilisant une autre grammaire arbre qui prend les fonctions découvertes de la grammaire de l'arbre précédent.

Une démo.

Prenez la source:

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

qui est analysé dans l'AST suivant:

en utilisant le (combiné) grammaire:

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();} ;

Découvrez ensuite les fonctions déclarées à l'aide d'un « arbre-marcheur » généré à partir de la grammaire de l'arbre suivant:

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*)
  ;

Pour tester tout, créer un analyseur et lexer (A), générer le "arbre-marcheur" (B), compiler tous les fichiers source (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

et exécuter la classe principale suivante (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);
    }
}

qui produit la sortie suivante:

Declared functions: [f, g]

Bien sûr, cela est juste un exemple de la façon d'aborder, non pas de la façon dont il est préférable de faire. Je peux imaginer (lors de l'utilisation de Java pour interpréter le script), vous ne stocker les fonctions déclarées comme des chaînes simples dans un Set<String>, mais plutôt comme un Map<String, CommonTree> facilement obtenir la racine d'une fonction et d'évaluer quand appelé.

Pour en savoir plus: http://www.antlr.org / wiki / affichage / antlr3 / simple arborescente + + interpeter

Bonne chance!

EDIT

Les secondes passent pourrait alors vérifier si toutes les fonctions sont définies à l'avance à l'aide de l'arbre-Walker précédent:

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*)
  ;

En utilisant le test:

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();
    }
}

produit une exception puisque x() est définie nulle part. Retrait de la source provoquera l'arbre-Walker pour produire pas exception.