Usando ANTLR para analizar y modificar el código fuente; ¿Lo estoy haciendo mal?

Question

Estoy escribiendo un programa donde necesito analizar un archivo fuente JavaScript, extraer algunos datos e insertar/reemplazar partes del código. Una descripción simplificada de los tipos de cosas que había que hacer es, dado este código:

foo(['a', 'b', 'c']); 

Extracto 'a', 'b' y 'c' y volver a escribir el código como:

foo('bar', [0, 1, 2]); 

estoy usando ANTLR para mis necesidades de análisis, produciendo el código C# 3. Alguien más ya había contribuido con una gramática de JavaScript. El análisis del código fuente está funcionando.

El problema que estoy encontrando es averiguar cómo analizar y modificar correctamente el archivo de origen. Cada enfoque que intento tomar en realidad para resolver el problema me lleva a un callejón sin salida. No puedo evitar pensar que no estoy usando la herramienta como estaba previsto o que soy demasiado novato cuando se trata de tratar con AST.

Mi primer enfoque fue analizar utilizando TokenRewriteStream e implementar los métodos parciales EnterRule_* para las reglas que me interesan. Si bien esto parece hacer bastante fácil la modificación de la secuencia de token, no hay suficiente información contextual para mi análisis. Parece que todo lo que tengo acceso es una secuencia plana de tokens, lo que no me dice lo suficiente sobre toda la estructura del código. Por ejemplo, para detectar si la función foo está siendo llamado, simplemente mirando el primer token no funcionaría, ya que coincidiría también falsamente:

a.b.foo(); 

Para permitir que haga el análisis de código más sofisticado, mi segundo enfoque fue modificar la gramática con reglas de reescritura para producir más de un árbol. Ahora, el primer bloque de código de muestra produce esto:

 
Program 
    CallExpression 
     Identifier('foo') 
     ArgumentList 
      ArrayLiteral 
       StringLiteral('a') 
       StringLiteral('b') 
       StringLiteral('c') 

Esto funciona muy bien para analizar el código. Sin embargo, ahora no puedo volver a escribir fácilmente el código. Claro, podría modificar la estructura de árbol para representar el código que quiero, pero no puedo usar esto para dar salida al código fuente. Tenía la esperanza de que el token asociado con cada nodo al menos me diera información suficiente para saber en qué parte del texto original necesitaría hacer las modificaciones, pero todo lo que obtengo son índices simbólicos o números de línea/columna. Para usar los números de línea y columna, tendría que hacer un segundo pase incómodo a través del código fuente.

Sospecho que me falta algo para entender cómo usar ANTLR correctamente para hacer lo que necesito. ¿Hay una forma más adecuada para mí para resolver este problema?

Answer 1

Así que está resultando que realmente puedo usar una gramática de árbol de reescritura e insertar/reemplazar tokens usando un TokenRewriteStream. Además, en realidad es realmente fácil de hacer. Mi código se parece al siguiente:

var charStream = new ANTLRInputStream(stream); 
var lexer = new JavaScriptLexer(charStream); 
var tokenStream = new TokenRewriteStream(lexer); 
var parser = new JavaScriptParser(tokenStream); 
var program = parser.program().Tree as Program; 

var dependencies = new List<IModule>(); 

var functionCall = (
    from callExpression in program.Children.OfType<CallExpression>() 
    where callExpression.Children[0].Text == "foo" 
    select callExpression 
).Single(); 
var argList = functionCall.Children[1] as ArgumentList; 
var array = argList.Children[0] as ArrayLiteral; 

tokenStream.InsertAfter(argList.Token.TokenIndex, "'bar', "); 
for (var i = 0; i < array.Children.Count(); i++) 
{ 
    tokenStream.Replace(
     (array.Children[i] as StringLiteral).Token.TokenIndex, 
     i.ToString()); 
} 

var rewrittenCode = tokenStream.ToString(); 

Answer 2

¿Ha mirado en la biblioteca string template? Es por la misma persona que escribió ANTLR y están destinados a trabajar juntos. Parece que sería adecuado hacer lo que buscas, es decir. el resultado coincide con las reglas de la gramática como texto formateado.

Here is an article on translation via ANTLR

Answer 3

Lo que estamos tratando de hacer es llamado program transformation, es decir, la generación automática de un programa de otro. Lo que estás haciendo "mal" es asumir que el analizador es todo lo que necesitas, y descubrir que no es así y que debes llenar el vacío.

herramientas que hacer que este bien tiene programas de análisis (para construir AST), medios para modificar las AST (tanto de procedimiento como patrón dirigido), y prettyprinters que convierten la AST (modificada) de nuevo en código fuente legal.Pareces estar luchando con el hecho de que ANTLR no viene con lindas impresoras; eso no es parte de su filosofía; ANTLR es un (muy) analizador sintáctico. Otras respuestas han sugerido el uso de "plantillas de cadena" de ANTLR, que no son, por sí solas, lindas impresoras, pero pueden utilizarse para implementar una, al precio de implementar una. Esto es más difícil de lo que parece; ver mi respuesta SO en compiling an AST back to source code.

El verdadero problema aquí es la suposición , , pero falso que dice "si tengo un analizador, estoy en camino de construir herramientas complejas de análisis y transformación de programas". Vea mi ensayo en Life After Parsing para una discusión larga de esto; Básicamente, necesita muchas más herramientas que "solo" un analizador para hacer esto, a menos que desee reconstruir una fracción significativa de la infraestructura usted mismo en lugar de continuar con su tarea. Otras características útiles de los sistemas prácticos de transformación de programas incluyen típicamente transformaciones de fuente a fuente, que simplifican considerablemente el problema de encontrar y reemplazar patrones complejos en árboles.

Por ejemplo, si usted tenía capacidades de transformación de código-fuente (de nuestra herramienta, el DMS Software Reengineering Toolkit, que sería capaz de escribir partes de su código de ejemplo se cambia el uso de estos DMS transforma:

 domain ECMAScript. 

     tag replace; -- says this is a special kind of temporary tree 


     rule barize(function_name:IDENTIFIER,list:expression_list,b:body): 
      expression->expression 
     = " \function_name ('[' \list ']') " 
     -> "\function_name(\firstarg\(\function_name\), \replace\(\list\))"; 


     rule replace_unit_list(s:character_literal): 
      expression_list -> expression_list 
      replace(s) -> compute_index_for(s); 

     rule replace_long_list(s:character_list, list:expression_list): 
      expression_list -> expression_list 
      "\replace\(\s\,\list)-> "compute_index_for\(\s\),\list"; 

con procedimientos de "meta" de regla externa "first_arg" (que sabe cómo calcular "bar" dado el identificador "foo" [supongo que quieres hacer esto), y "compute_index_for" que, dada una cadena de literales, sabe qué entero para reemplazarlo con.

Las reglas de reescritura individuales tienen listas de parámetros "(...)" en las que los espacios que representan los subárboles son named, un lado izquierdo que actúa como un patrón para hacer coincidir y un lado derecho que actúa como reemplazo, ambos generalmente citados en las metacotas " que separa el texto del lenguaje de reescritura del idioma meta (p. ej. JavaScript) texto. Hay muchos meta-escapes ** encontrados dentro de las metacitas que indican un elemento especial rewrite-rule-language. Normalmente, estos son nombres de parámetros, y representan cualquier tipo de árbol de nombre que el parámetro represente, o representan una llamada a un procedimiento de metadatos externo (como first_arg, notará que su lista de argumentos (,) está metacuentada!), O finalmente, un " etiqueta "como" reemplazar ", que es un tipo peculiar de árbol que representa la intención futura de hacer más transformaciones.

Este conjunto particular de reglas funciona reemplazando una llamada de función candidata por la versión barizada, con la intención adicional de "reemplazar" para transformar la lista. Las otras dos transformaciones se dan cuenta de la intención al transformar "reemplazar" procesando elementos de la lista de uno en uno, y empujando el reemplazo más abajo en la lista hasta que finalmente se cae del extremo y se realiza el reemplazo. (Este es el equivalente transformacional de un bucle).

Su ejemplo específico puede variar un poco ya que realmente no era preciso acerca de los detalles.

Después de aplicar estas reglas para modificar el árbol analizado, DMS puede entonces imprimir trivialmente el resultado (el comportamiento predeterminado en algunas configuraciones es "analizar AST, aplicar reglas hasta el agotamiento, AST bastante) porque es útil).

Puede ver un proceso completo de "definir el idioma", "definir las reglas de reescritura", "aplicar las reglas y la impresión bonita" en (High School) Algebra as a DMS domain.

Otros sistemas de transformación de programa incluyen TXL y Stratego. Imaginamos a DMS como la versión industrial de estos, en la que hemos construido toda esa infraestructura, incluyendo many standard language parsers and prettyprinters.