Cómo implementar una llamada de función con Antlr de modo que pueda ser llamado incluso antes de que se define?

Question

Una vez que la AST está construido, ¿cuál es la mejor manera de poner en práctica el árbol andador para que las funciones pueden ser definidos y llamados en el orden?

Por ejemplo, esto es válido en PHP:

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

supongo que de alguna manera tiene que haber una segunda pasada, o una transformación árbol, pero no puedo encontrar nada interesante sobre este tema. El problema no es, probablemente, uno Antlr específica, pero si me podría apuntar a un ejemplo Antlr de cómo se hace esto, aún mejor!

Answer 1

Sí, tiene usted razón:. Esto se hace en más de un pase al centro del AST

En primer lugar, crear una gramática que construye un AST de la fuente, a continuación, crear una gramática de árbol que se utiliza para iterar sobre la función de todos definidos árbol y descubre. A continuación, podría evaluar la secuencia de comandos con otra gramática árbol que lleva las funciones descubiertas de la gramática de árbol anterior.

Una demostración.

Tome la fuente:

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

que se analiza en la siguiente AST:

Uso de la gramática (combinado):

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

A continuación, descubrir las funciones declaradas utilizando un "árbol-walker" generado a partir de la siguiente gramática árbol:

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

Para probar todo, crear un analizador léxico y analizador (A), generar el "árbol-walker" (B), compilar todos los archivos de origen (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

y ejecute el siguiente clase principal (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);
    }
}

que produce el siguiente resultado:

Declared functions: [f, g]

Por supuesto, esto es sólo un ejemplo de cómo acercarse a él, no de la forma en que se hace mejor. Puedo imaginar (cuando se utiliza Java para interpretar el guión), no sería almacenar las funciones declaradas como cadenas simples en un Set<String>, sino más bien como un Map<String, CommonTree> a conseguir fácilmente la raíz de una función y evaluarlo cuando se le llama.

Más información: http://www.antlr.org / wiki / pantalla / ANTLR3 / simple basado en árboles + + interpeter

Buena suerte!

Editar

Los segundos pasan entonces podría comprobar si todas las funciones están definidas por delante de él con el anterior árbol-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*)
  ;

El uso de la prueba:

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 una excepción, ya x() no se definen en cualquier lugar. Extracción de la fuente hará que el árbol-Walker para producir no es una excepción.