Come implementare una chiamata di funzione con Antlr in modo che possa essere chiamato anche prima che si definisce?

Question

Una volta che l'AST è costruito, qual è il modo migliore implementare l'albero camminatore in modo che le funzioni possono essere definite e chiamati in qualsiasi ordine?

Ad esempio, questo è valido in PHP:

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

Sto indovinando che in qualche modo ci deve essere un secondo passaggio, o una trasformazione albero, ma non riesco a trovare nulla di interessante su questo argomento. Il problema non è probabilmente un uno Antlr specifico, ma se mi potesse indicare un esempio Antlr di come questo è fatto, ancora meglio!

Answer 1

Sì, hai ragione. Questo è fatto in più di un passaggio sulla AST

Per prima cosa creare una grammatica che costruisce un AST della fonte, quindi si crea una grammatica albero che viene utilizzato per scorrere la funzione di tutti definiti albero e scopre. Si potrebbe quindi valutare lo script utilizzando un altro grammatica albero che prende le funzioni scoperti dal precedente grammatica albero.

Una demo.

Prendere la fonte:

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

che viene analizzato nel seguente AST:

utilizzando la grammatica (combinato):

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

Poi scoprire le funzioni dichiarate utilizzando un "albero-walker" generato dalla seguente grammatica albero:

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

Per testare il tutto, creare un lexer e parser (A), genera l ' "albero-walker" (B), compilare tutti i file sorgente (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

ed eseguire la seguente classe principale (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);
    }
}

che produce il seguente output:

Declared functions: [f, g]

Naturalmente, questo è solo un esempio di come affrontarla, non di come è meglio farlo. Posso immaginare (quando si utilizza Java per interpretare lo script), non si memorizzare le funzioni dichiarate come semplici stringhe in un Set<String>, ma piuttosto come un Map<String, CommonTree> per ottenere facilmente la radice di una funzione e valutare quando viene chiamato.

Per ulteriori approfondimenti: http://www.antlr.org / wiki / display / ANTLR3 / semplice a base di albero + + interpeter

In bocca al lupo!

Modifica

I secondi passano potrebbe quindi verificare se tutte le funzioni sono definite in anticipo utilizzando il precedente albero-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*)
  ;

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

produce un'eccezione poiché x() non è definire da nessuna parte. La rimozione dalla fonte causerà l'albero-walker per produrre non fa eccezione.