Gramáticas compostables

Question

Hay tantos lenguajes de programación que admiten la inclusión de mini-idiomas. PHP está incrustado en HTML. XML se puede incrustar dentro de JavaScript. Linq se puede incrustar dentro de C#. Las expresiones regulares se pueden incrustar en Perl.

// JavaScript example 
var a = <node><child/></node> 

Pensando en ello, la mayoría de los lenguajes de programación se pueden modelar como mini-idiomas diferentes. Java, por ejemplo, podría ser dividida en unos menos cuatro mini-idiomas distintos:

• Un langauge de declaración de tipo (Directiva paquete, las directivas de importación, declaración de la clase)
• Un lenguaje miembro-declaración (modificadores de acceso, declaraciones de métodos, miembro de vARs)
• Un lenguaje de declaración (flujo de control, ejecución secuencial)
• Un lenguaje de expresión (literales, las tareas, las comparaciones, la aritmética)

Pudiendo implementar esos cuatro lenguajes conceptuales como cuatro gramáticas distintas ciertamente reduciría mucho del espaguetiismo que suelo ver en las complejas implementaciones de compilador y analizador.

He implementado analizadores para diferentes tipos de idiomas antes (usando ANTLR, JavaCC, y analizadores sintácticos de descenso recursivo), y cuando el lenguaje se vuelve realmente grande y complejo, por lo general se termina con una gramática huuuuuuge, y la implementación del analizador se pone muy fea realmente rápido.

Lo ideal sería que, al escribir un analizador para uno de esos idiomas, sería bueno implementarlo como una colección de analizadores sintácticos, pasando el control hacia adelante y hacia atrás entre ellos.

Lo complicado es que, a menudo, el idioma contenedor (por ejemplo, Perl) define su propio término centinela para el lenguaje contenido (por ejemplo, expresiones regulares). He aquí un buen ejemplo:

my $result ~= m|abc.*xyz|i; 

En este código, el código principal del Perl define un terminal no estándar "|" para la expresión regular. Implementar el analizador de expresiones regulares como algo completamente distinto del analizador de perl sería realmente difícil, porque el analizador de expresiones regulares no sabría cómo encontrar el término de expresiones sin consultar el analizador padre.

O, digamos que tenía un lenguaje que permitió la inclusión de expresiones LINQ, pero en lugar de terminar con un punto y coma (como C# hace), que quería obligar aparecen las expresiones LINQ entre corchetes:

var linq_expression = [from n in numbers where n < 5 select n] 

Si definí la gramática de Linq dentro de la gramática del lenguaje parental, podría escribir fácilmente una producción no ambigua para un "LinqExpression" utilizando la búsqueda sintáctica para encontrar los cercados del bracket. Pero entonces la gramática de mi padre tendría que absorber toda la especificación de Linq. Y eso es un lastre Por otro lado, un analizador de Linq secundario aislado tendría dificultades para determinar dónde detenerse, ya que tendría que implementar la búsqueda anticipada de tipos de tokens extranjeros.

Y eso descartaría casi por completo el uso de fases lexing/analíticas separadas, ya que el analizador de Linq definiría un conjunto completamente diferente de reglas de tokenización que el analizador padre. Si está escaneando un token a la vez, ¿cómo sabe cuándo pasar el control nuevamente al analizador léxico del idioma principal?

¿Qué piensan?¿Cuáles son las mejores técnicas disponibles en la actualidad para implementar gramáticas distintas, desacopladas y compostables para la inclusión de mini-idiomas dentro de lenguajes padres más grandes?

Answer 1

El análisis es un aspecto del problema, pero sospecho que la interoperación entre los diversos intérpretes ejecutables que se relacionan con cada mini-lenguaje probablemente sea mucho más difícil de resolver. Para que sea útil, cada bloque de sintaxis independiente debe funcionar de manera coherente con el contexto general (o el comportamiento final será impredecible y, por lo tanto, inutilizable).

No entiendo lo que realmente están haciendo, pero un lugar muy interesante para buscar más inspiración es FoNC. Parecen (estoy adivinando) dirigirse hacia una dirección que permita que todo tipo de diferentes motores computacionales interactúen sin problemas.

Answer 2

Estoy trabajando en este problema exacto. Compartiré mis pensamientos:

Las gramáticas son difíciles de depurar. He depurado algunos en Bison y ANTLR y no era bonito. Si desea que el usuario inserte DSL como gramática en su analizador, entonces debe encontrar la forma de hacerlo para que no explote. Mi enfoque es no permitir DSL arbitrarias, sino para permitir que sólo los que siguen dos reglas:

• Los tipos de tokens (identificadores, cuerdas, números) son los mismos entre todos los DSL en un archivo.
• desequilibradas paréntesis, llaves o corchetes no se permiten

El motivo de la primera restricción se debe a que los analizadores modernos dividen analizar en una etapa de léxico y luego aplicar las reglas de la gramática tradicional. Afortunadamente, creo que un único tokenizador universal es lo suficientemente bueno para el 90% de las DSL que desea crear, incluso si no se adapta a las DSL que ya creó y que desea incorporar.

La segunda restricción permite que las gramáticas estén más separadas unas de otras. Puede analizar en dos etapas agrupando paréntesis (llaves, corchetes) y luego analizando recursivamente cada grupo. La gramática de su DSL incorporado no puede escapar a través de los corchetes en los que está contenida.

Otra parte de la solución es permitir macros. Por ejemplo, regex("abc*/[^.]") me parece bien. De esta forma, la macro "regex" puede analizar la expresión regular en lugar de compilar una gramática de expresiones regulares en el idioma principal. No puedes usar diferentes delimitadores para tu expresión regular, claro, pero sí ganas una medida de consistencia en mi mente.

Answer 3

Si lo piensas bien, así es como funciona el análisis descendente recursivo. Cada regla y todas las reglas de las que depende forman una mini gramática. Cualquier cosa más arriba no importa. Podría, por ejemplo, escribir una gramática Java con ANTLR y separar todos los diferentes "mini-idiomas" en diferentes partes del archivo.

Esto no es muy común simplemente por el hecho de que estos "mini-idiomas" a menudo comparten muchas reglas. Sin embargo, definitivamente sería bueno si herramientas como ANTLR le permitieran incluir gramáticas separadas de diferentes archivos. Esto te permitiría separarlos lógicamente. Probablemente la razón por la que probablemente no se implemente es porque se trata de un problema "cosmético", está puramente relacionado con los propios archivos de gramática y no se analiza automáticamente. Tampoco hará que su código sea más corto (aunque puede ser un poco más fácil de seguir). El único problema técnico que esto resolvería son colisiones de nombres.

Answer 4

Es posible que desee escuchar this podcast.El análisis sin escaneo fue "inventado" para ayudar a resolver el problema de componer diferentes gramáticas (el problema es que rápidamente descubres que no puedes escribir un tokenizador/escáner "universal").

Answer 5

Eche un vistazo a SGLR, Analizador LR generalizado sin escáner. Aquí hay algunas referencias y URL. Estas técnicas de análisis hacen que la composición de tablas de análisis sea muy simple. Especialmente en combinación con SDF.

Martin Bravenboer y Eelco Visser. Diseño de incrustaciones y asimilaciones de sintaxis para bibliotecas de idiomas. En Modelos en Ingeniería de Software: Los talleres y simposios en los modelos de 2007, el volumen de LNCS 5002, 2008.

MetaBorg y MetaBorg in action

Answer 6

Perl 6 puede verse como un conjunto de DSL hechos específicamente para escribir programas.

De hecho, la implementación de Rakudo está construida exactamente de esta manera.

Las cadenas pares son una DSL con opciones que puede habilitar o deshabilitar.

Q 
:closure 
:backslash 
:scalar 
:array 
:hash 
"{ 1 + 3 } \n $a @a<> %a<>" 

qq"{1+2}" eq ｢3｣ 

qq:!closure"{1+2}" eq ｢{1+2}｣ 

Básicamente tiene que hacerse a partir de gramáticas componibles para que esto funcione:

sub circumfix:«:-) :-)» (@_) { say @_ } 

:-) 1,2,3 :-) 

---

En Perl 6 gramáticas son sólo un tipo de clase, y los símbolos son un tipo de método.

role General-tokens { 
    token start-of-line { ^^ } 
    token end-of-line { $$ } 
} 
grammar Example does General-tokens { 
    token TOP { 
    <start-of-line> <stuff> <end-of-line> 
    } 
    token stuff { \N+ } 
} 

role Other { 
    token start-of-line { <alpha> ** 5 } 
} 
grammar Composed-in is Example does Other { 
    token alpha { .. } 
} 

say Composed-in.parse: 'abcdefghijklmnopqrstuvwxyz'; 

｢abcdefghijklmnopqrstuvwxyz｣ 
start-of-line => ｢abcdefghij｣ 
    alpha => ｢ab｣ 
    alpha => ｢cd｣ 
    alpha => ｢ef｣ 
    alpha => ｢gh｣ 
    alpha => ｢ij｣ 
stuff => ｢klmnopqrstuvwxyz｣ 
end-of-line => ｢｣ 

Tenga en cuenta que yo no les haya mostrado una clase de acciones, que es útil para transformar el árbol de análisis sintáctico ya que está construido.