¿Por qué no almacenamos el árbol de sintaxis en lugar del código fuente?

108

Tenemos muchos lenguajes de programación. Se analizan todos los idiomas y se comprueba la sintaxis antes de traducirlos al código, por lo que se crea un árbol de sintaxis abstracta (AST).

Tenemos este árbol de sintaxis abstracto, ¿por qué no almacenamos este árbol de sintaxis en lugar del código fuente (o al lado del código fuente)?

Usando un AST en lugar del código fuente. Todos los programadores de un equipo pueden serializar este árbol a cualquier idioma que quieran (con la gramática libre de contexto apropiada) y analizar AST cuando hayan terminado. Así que esto eliminaría el debate sobre las preguntas de estilo de codificación (dónde colocar el {y}, dónde colocar espacios en blanco, sangría, etc.)

¿Cuáles son las ventajas y desventajas de este enfoque?

    
pregunta Calmarius 10.11.2011 - 23:04
fuente

13 respuestas

70

Espacio en blanco y comentarios

En general, un AST no incluye espacios en blanco, terminadores de línea ni comentarios.

Formateo significativo

Usted tiene razón en que, en la mayoría de los casos, esto es positivo (elimina el formateo de las guerras santas), hay muchos casos en los que el formato del código original transmite algún significado, como en los literales de cadenas de varias líneas y los "párrafos de código" ( separando bloques de declaraciones con una línea vacía).

Código que no se puede compilar

Si bien muchos analizadores son muy resistentes a la sintaxis faltante, el código con errores a menudo da como resultado un árbol de sintaxis muy extraño, que está bien y hasta el punto en que el usuario vuelve a cargar el archivo. ¿Alguna vez ha cometido un error en su IDE y, de repente, todo el archivo tiene "garabatos"? Imagina cómo se recargaría en otro idioma.

Tal vez los usuarios no cometan código que no se pueda analizar, pero ciertamente necesitan guardar localmente.

No hay dos idiomas que coincidan perfectamente

Como han señalado otros, casi no hay dos idiomas que tengan una paridad de características perfecta. Lo más cercano que puedo pensar es VB y C #, o JavaScript y CoffeeScript, pero incluso entonces VB tiene características como XML Literals que no tienen equivalentes en C #, y la conversión de JavaScript a CoffeeScript puede resultar en muchos literales de JavaScript.

Experiencia personal:

En una aplicación de software que escribo, en realidad necesitamos hacer esto, ya que se espera que los usuarios ingresen expresiones "simples en inglés" que se convierten a JS en segundo plano. Consideramos solo almacenar la versión JS, pero no encontramos una forma aceptable de hacerlo que se cargue y descargue de manera confiable, por lo que terminamos almacenando tanto el texto del usuario como la versión JS, así como una bandera que indica si el "inglés sencillo" "la versión se analiza perfectamente o no.

    
respondido por el Kevin McCormick 10.11.2011 - 23:27
fuente
42
  

¿Por qué no almacenamos este árbol de sintaxis en lugar del código fuente? Todos los programadores de un equipo pueden serializar este árbol a cualquier idioma, quieren y analizar AST cuando terminen.

De hecho, esa es una idea razonable. Microsoft tenía un proyecto de investigación en la década de 1990 para hacer casi exactamente eso .

Varios escenarios vienen a la mente.

El primero es bastante trivial; como usted dice, podría tener el AST representado en diferentes vistas dependiendo de las preferencias de diferentes programadores para cosas como el espaciado y así sucesivamente. Pero almacenar un AST es una exageración para ese escenario; Sólo escríbete una impresora bonita. Cuando cargue un archivo en su editor, ejecute la bonita impresora para ponerlo en su formato preferido, y vuelva a hacerlo en el formato original cuando lo guarde.

El segundo es más interesante. Si puede almacenar el árbol de sintaxis abstracta, el cambio de código se convierte en no textual sino sintáctico. Las refactorizaciones donde se mueve el código se vuelven mucho más fáciles de entender. El aspecto negativo es, por supuesto, que escribir los algoritmos de diferencia de árbol no es exactamente trivial y, a menudo, tiene que hacerse en una base por idioma. El texto diff funciona para casi cualquier idioma.

El tercero es más parecido a lo que Simonyi imaginó para la Programación intencional: que los conceptos fundamentales comunes a los lenguajes de programación son los que están serializados, y luego tiene diferentes vistas de esos conceptos representados en diferentes lenguajes. Aunque es una idea hermosa, el hecho desagradable es que los idiomas son lo suficientemente diferentes en sus detalles como para que un enfoque del mínimo común denominador no funcione realmente.

En resumen, es una idea encantadora, pero es una enorme cantidad de trabajo extra para un beneficio relativamente pequeño. Es por eso que casi nadie lo hace.

    
respondido por el Eric Lippert 11.11.2011 - 18:45
fuente
19

Podría argumentar que esto es exactamente qué código de byte está en .NET. El programa reflector de infact redgate traduce el código de bytes a una variedad de lenguajes de programación .NET.

Sin embargo, hay problemas. La sintaxis es específica del idioma, ya que hay cosas que puedes representar en un idioma que no tienen representación en otros idiomas. Esto ocurre en .NET, siendo C ++ el único lenguaje .NET que tiene acceso a los 7 niveles de acceso.

Fuera del entorno .NET se vuelve mucho más complicado. Cada idioma comienza a tener su propio conjunto de bibliotecas asociadas. No sería posible reflejar una sintaxis genérica tanto en C como en Java que reflejara la misma ejecución de instrucciones, ya que resuelven problemas simulares de maneras muy diferentes.

    
respondido por el Michael Shaw 10.11.2011 - 23:17
fuente
12

Me gusta algo de tu idea, pero estás sobreestimando significativamente lo fácil que es traducir de un idioma a otro. Si fuera así de fácil, ni siquiera necesitaría almacenar el AST, ya que siempre podría analizar el lenguaje X en el AST y luego pasar del AST al idioma Y.

Sin embargo, me gustaría que las especificaciones del compilador pensaran un poco más acerca de exponer algunos de los AST a través de algún tipo de API. Cosas como la programación orientada a aspectos, la refactorización y el análisis estático de programas podrían implementarse a través de dicha API, sin que el implementador de esas capacidades tenga que rehacer gran parte del trabajo ya implementado por los escritores de compiladores.

Es extraño la frecuencia con la que la estructura de datos del programador para representar un programa es como un conjunto de archivos que contienen cadenas.

    
respondido por el psr 10.11.2011 - 23:45
fuente
11

Creo que los puntos más destacados son aquellos:

  • No hay beneficio. Dijiste que eso significaría que todos podrían usar el lenguaje de su mascota. Pero eso no es cierto : usar una representación de árbol de sintaxis eliminaría las diferencias sintácticas solamente, pero no las semánticas. Funciona en cierta medida para lenguajes muy similares, como VB y C #, o Java y Scala. Pero ni siquiera allí por completo.

  • Es problemático. Has ganado la libertad de lenguaje, pero has perdido la libertad de herramientas. Ya no puede leer y editar el código en un editor de texto, o incluso cualquier IDE; usted depende de una herramienta específica que habla su representación AST para leer y editar el código. No hay nada ganado aquí.

    Para ilustrar este último punto, eche un vistazo a RealBasic, que es una implementación patentada de un potente dialecto BASIC. Durante un tiempo, casi parecía que el idioma podía despegar, pero era completamente dependiente del proveedor, hasta el punto de que solo podía ver el código en su IDE, ya que se guardaba en un formato propietario sin texto. Gran error .

respondido por el Konrad Rudolph 11.11.2011 - 13:26
fuente
6

Creo que, si almacenas tanto el texto como el AST, entonces realmente no has agregado nada útil, ya que el texto ya está allí en un idioma, y el AST se puede reconstruir rápidamente a partir del texto.

Por otro lado, si solo almacenas el AST, pierdes cosas como comentarios que no se pueden recuperar.

    
respondido por el Tesserex 10.11.2011 - 23:16
fuente
4

Creo que la idea es interesante en teoría pero no es muy práctica, ya que diferentes lenguajes de programación son compatibles con diferentes construcciones, algunas de las cuales no tienen equivalentes en otros lenguajes.

Por ejemplo, X ++ tiene una declaración 'while while select' que no se puede escribir en C # sin mucho código adicional (clases adicionales, lógica adicional, etc.). enlace

Lo que estoy diciendo aquí es que muchos idiomas tienen azúcares sintácticos que se traducen en grandes bloques de código del mismo idioma o incluso elementos que no existen en absoluto en otros. Aquí hay un ejemplo de por qué el enfoque AST no funcionará:

El lenguaje X tiene una palabra clave K que se traduce, en AST en 4 declaraciones: S1, S2, S3 y S4. El AST ahora está traducido al lenguaje Y y un programador cambia S2. Ahora, ¿qué pasa con la traducción de nuevo a X? El código se traduce como 4 declaraciones en lugar de una sola palabra clave ...

El último argumento en contra del enfoque AST son las funciones de la plataforma: ¿qué sucede cuando una función está incrustada en la plataforma? Como Environment.GetEnvironmentVariable de .NET. ¿Cómo se traduce?

    
respondido por el Victor Hurdugaci 11.11.2011 - 01:07
fuente
4

Hay un sistema creado alrededor de esta idea: JetBrains MPS . Un editor es un poco extraño, o simplemente diferente, pero en general no es un gran problema. El mayor problema es, bueno, que ya no es un texto, por lo que no puede usar ninguna de las herramientas normales basadas en texto: otros editores, grep , sed , herramientas de combinación y diferencia, etc.

    
respondido por el SK-logic 11.11.2011 - 14:00
fuente
4

En realidad, hay varios productos, generalmente conocidos como "bancos de trabajo de idiomas" que almacenan AST y presentan, en sus editores, una "proyección" de AST en un idioma particular. Como dijo @ sk-logic, el MPS de JetBrains es uno de esos sistemas. Otro es Intencional Software's Intentional Workbench.

El potencial para los bancos de trabajo de idiomas parece muy alto, especialmente en el área de lenguajes específicos de dominio, ya que puede crear una proyección específica de dominio. Por ejemplo, Intencional muestra un DSL relacionado con la electricidad que se proyecta como un diagrama de circuito, mucho más fácil y más preciso para que un experto en dominios analice y critique que un circuito descrito en un lenguaje de programación basado en texto.

En la práctica, los bancos de trabajo de lenguaje han tardado en ponerse al día porque, aparte del trabajo de DSL, los desarrolladores probablemente preferirían trabajar en un lenguaje de programación general y familiar. Cuando se comparan cara a cara con un editor de texto o IDE de programación, las mesas de trabajo de lenguaje tienen muchos gastos generales y sus ventajas no son tan claras. Ninguno de los bancos de trabajo de idioma que he visto se han atado al arranque hasta el punto en que pueden extender fácilmente sus propios IDE, es decir, si los bancos de trabajo de idioma son excelentes para la productividad, ¿por qué no han mejorado las herramientas del banco de trabajo de idioma? ¿Y mejor a velocidades más rápidas y más rápidas?

    
respondido por el Larry OBrien 11.11.2011 - 20:13
fuente
3

Has estado leyendo mi mente.

Cuando tomé un curso de compiladores, hace unos años, descubrí que si tomas un AST y lo serializas, con la notación de prefijo en lugar de la notación de infijo habitual, y utilizas paréntesis para delimitar declaraciones completas, obtienes Lisp. Mientras aprendía sobre Scheme (un dialecto de Lisp) en mis estudios universitarios, nunca había ganado un aprecio por ello. Definitivamente obtuve un aprecio por Lisp y sus dialectos, como resultado de ese curso.

Problemas con lo que propones:

  1. es difícil / lento componer un AST en un entorno gráfico. Después de todo, la mayoría de nosotros puede escribir más rápido de lo que podemos mover un mouse. Y, sin embargo, una pregunta emergente es "¿cómo se escribe el código del programa en una tableta?" Escribir en una tableta es lento / engorroso, en comparación con un teclado / computadora portátil con un teclado de hardware. Si pudiera crear un AST arrastrando y soltando componentes de una paleta en un lienzo en un dispositivo grande con pantalla táctil, la programación en una tableta podría convertirse en algo real.

  2. pocas / ninguna de nuestras herramientas existentes lo admite. Tenemos décadas de desarrollo envueltas en la creación de IDE cada vez más complejos y editores cada vez más inteligentes. Tenemos todas estas herramientas para reformatear texto, comparar texto, buscar texto. ¿Dónde están las herramientas que pueden hacer el equivalente de una búsqueda de expresiones regulares en un árbol? ¿O una diferencia de dos árboles? Todas estas cosas se hacen fácilmente con texto. Pero solo pueden comparar las palabras. Cambie el nombre de una variable, de manera que las palabras sean diferentes pero el significado semántico sea el mismo, y esas herramientas de diferencias tengan problemas. Estas herramientas, desarrolladas para operar en AST en lugar de texto, le permitirían acercarse más a la comparación del significado semántico. Eso sería algo bueno.

  3. mientras que convertir el código fuente del programa en un AST es relativamente bien comprendido (tenemos compiladores e intérpretes, ¿no?), convertir un AST en código del programa no se entiende tan bien. Multiplicar dos números primos para obtener un número grande y compuesto es relativamente sencillo, pero factorizar un número grande y compuesto de nuevo en números primos es mucho más difícil; Ahí es donde estamos con el análisis de ASTs vs descompilar. Ahí es donde las diferencias entre idiomas se convierten en un problema. Incluso dentro de un idioma en particular, hay varias formas de descompilar un AST. Iterando a través de una colección de objetos y obteniendo algún tipo de resultado, por ejemplo. ¿Utilizar un bucle for, iterar a través de una matriz? Eso sería compacto y rápido, pero hay limitaciones. ¿Utilizar un iterador de algún tipo, operando en una colección? Esa colección podría ser de tamaño variable, lo que agrega flexibilidad a expensas de la velocidad (posible). ¿Mapa reducido? Más complejo, pero implícitamente paralelizable. Y eso es solo para Java, dependiendo de tus preferencias.

Con el tiempo, el esfuerzo de desarrollo se gastará y se desarrollará utilizando pantallas táctiles y AST. Escribir será cada vez menos necesario. Veo eso como una progresión lógica desde donde estamos, mirando cómo usamos las computadoras, hoy, eso resolverá # 1.

Ya estamos trabajando con árboles. Lisp es meramente ASTs serializados. XML (y HTML, por extensión) es solo un árbol serializado. Para hacer la búsqueda, ya tenemos un par de prototipos: XPath y CSS (para XML y HTML, respectivamente). Cuando se creen herramientas gráficas que nos permitan crear selectores y modificadores de estilo CSS, habremos resuelto parte del # 2. Cuando esos selectores puedan extenderse para soportar expresiones regulares, estaremos más cerca. Sigo buscando una buena herramienta de diferencias gráficas para comparar dos documentos XML o HTML. A medida que las personas desarrollen esas herramientas, el # 2 será resuelto. La gente ya está trabajando en tales cosas; simplemente no están allí, todavía.

La única forma en que puedo ver para poder descompilar esos AST en texto de lenguaje de programación sería buscar objetivos. Si estoy modificando el código existente, el objetivo podría lograrse mediante un algoritmo que haga que mi código modificado sea lo más parecido posible al código de inicio (diferencia textual mínima). Si escribo el código desde cero, el objetivo podría ser el código más pequeño y preciso (probablemente un bucle for). O podría ser un código que se paralice lo más eficientemente posible (probablemente un mapa / reducción o algo que involucre a CSP). Por lo tanto, el mismo AST podría resultar en un código significativamente diferente, incluso en el mismo idioma, en función de cómo se establecieron los objetivos. Desarrollar un sistema así resolvería el # 3. Sería computacionalmente complejo, lo que significa que probablemente necesitaríamos algún tipo de arreglo cliente-servidor, lo que le permitirá a su tableta de mano descargar un montón de trabajo pesado a algún servidor basado en la nube.

    
respondido por el Meower68 19.06.2014 - 16:27
fuente
1

Si su intención es eliminar el debate sobre los estilos de formato, tal vez lo que desea es un editor que lea un archivo de origen, lo formatee según sus preferencias personales para mostrarlo y editarlo, pero cuando lo guarde, lo reformateará. Estilo que usa el equipo.

Es bastante fácil si usas un editor como Emacs . Cambiar el estilo de formato de un archivo completo es un trabajo de tres comandos.

También deberías poder crear los ganchos para transformar automáticamente un archivo a tu propio estilo al cargarlo, y transformarlo en el estilo de equipo al guardar.

    
respondido por el Gustav Bertram 11.11.2011 - 15:23
fuente
1

Es difícil leer y modificar un AST, en lugar del código fuente.

Sin embargo, algunas herramientas relacionadas con el compilador permiten usar el AST. El código de bytes de Java y el código intermedio de .NET funcionan de manera similar a un AST.

    
respondido por el umlcat 11.11.2011 - 00:39
fuente
0

es una buena idea; pero el AST de cada idioma es diferente de los demás.

la única excepción que conozco es para VB.NET y C #, donde Microsoft argumenta que son "exactamente el mismo idioma con diferente sintaxis". Incluso otros lenguajes .NET (IronPython, F #, lo que sea) son diferentes en el nivel AST.

Lo mismo con los idiomas de JVM, todos apuntan al mismo bytecode, pero las construcciones de los idiomas son diferentes, por lo que son diferentes idiomas y diferentes AST.

Incluso los lenguajes de 'capa delgada', como CoffeScript y Xtend, comparten gran parte de la teoría de los lenguajes subyacentes (JavaScript y Java, respectivamente); pero introduzca conceptos de nivel superior que sean (o deberían ser) retenidos en el nivel AST.

si Xtend pudiera reconstruirse a partir de un AST de Java, creo que se habría definido como un "no compilador" de Java a Xtend que mágicamente creará abstracciones de mayor nivel a partir de un código Java existente, ¿no crees?

    
respondido por el Javier 11.11.2011 - 15:05
fuente

Lea otras preguntas en las etiquetas