He estado programando durante muchos años, pero una tarea que todavía me lleva demasiado tiempo es especificar una gramática para un analizador, e incluso después de este esfuerzo excesivo, nunca estoy seguro de que la gramática que se me ocurrió sea buena ( por cualquier medida razonable de "bueno").
No espero que haya un algoritmo para automatizar el proceso de especificación de una gramática, pero espero que haya formas de estructurar el problema que elimine gran parte de las conjeturas y las pruebas y errores de mi enfoque actual.
Mi primer pensamiento ha sido leer sobre analizadores, y he hecho algo de esto, pero todo lo que he leído sobre este tema toma la gramática como algo dado (o lo suficientemente trivial como para poder especificarlo mediante inspección), y se enfoca en El problema de traducir esta gramática en un analizador sintáctico. Estoy interesado en el problema inmediatamente anterior: cómo especificar la gramática en primer lugar.
Me interesa principalmente el problema de especificar una gramática que represente formalmente una colección de ejemplos concretos (positivos y negativos). Esto es diferente del problema de diseñar una nueva sintaxis . Gracias a Macneil por señalar esta distinción.
Nunca había apreciado realmente la distinción entre una gramática y una sintaxis, pero ahora que estoy empezando a verla, podría agudizar mi primera aclaración al decir que estoy principalmente interesado en el problema de especificar una gramática que imponga un sintaxis predefinida: resulta que, en mi caso, la base de esta sintaxis suele ser una colección de ejemplos positivos y negativos.
¿Cómo se especifica la gramática para un analizador sintáctico? ¿Existe algún libro o referencia que sea el estándar de facto para describir las mejores prácticas, las metodologías de diseño y otra información útil sobre cómo especificar una gramática para un analizador sintáctico? ¿En qué puntos, al leer sobre la gramática del analizador sintáctico, debería centrarme?
Respuestas:
A partir de los archivos de muestra, deberá tomar decisiones basadas en cuánto desea generalizar a partir de esos ejemplos. Supongamos que tiene las siguientes tres muestras: (cada una es un archivo separado)
Podría especificar trivialmente dos gramáticas que aceptarán estas muestras:
Gramática trivial uno:
Gramática trivial dos:
El primero de ellos es trivial ya que acepta sólo las tres muestras. El segundo es trivial porque acepta todo lo que podría usar esos tipos de tokens. [Para esta discusión, voy a suponer que no le preocupa mucho el diseño del tokenizer: es simple asumir identificadores, números y signos de puntuación como sus tokens, y podría tomar prestado cualquier conjunto de tokens de cualquier lenguaje de script que desee como de todos modos.]
Entonces, el procedimiento que deberá seguir es comenzar en el nivel superior y decidir "¿cuántos de cada instancia quiero permitir?" Si una construcción sintáctica puede tener sentido repetir cualquier cantidad de veces, como
method
s en una clase, querrá una regla con esta forma:Lo que se afirma mejor en EBNF como:
Probablemente sea obvio cuando solo desea cero o una instancia (lo que significa que la construcción es opcional, como con la
extends
cláusula para una clase Java), o cuando desea permitir una o más instancias (como con un inicializador variable en una declaración ) Deberá tener en cuenta cuestiones como solicitar un separador entre elementos (como en el caso,
de una lista de argumentos), requerir un terminador después de cada elemento (como con las;
declaraciones para separar) o no requerir separador o terminador (como el caso con métodos en una clase).Si su idioma usa expresiones aritméticas, sería fácil copiar de las reglas de precedencia de un idioma existente. Es mejor atenerse a algo conocido, como las reglas de expresiones de C, que buscar algo exótico, pero solo si todo lo demás es igual.
Además de los problemas de precedencia (lo que se analiza entre sí) y los problemas de repetición (¿cuántos elementos de cada elemento deben ocurrir, cómo se separan?), También tendrá que pensar en el orden: ¿debe aparecer algo siempre antes que otra cosa? Si se incluye una cosa, ¿debería excluirse otra?
En este punto, es posible que sienta la tentación de imponer gramaticalmente algunas reglas, una regla como, por ejemplo, si
Person
se especifica la edad de una persona, no desea permitir que se especifique también su fecha de nacimiento. Si bien puede construir su gramática para hacerlo, puede que le resulte más fácil aplicar esto con un pase de "verificación semántica" después de analizar todo. Esto mantiene la gramática más simple y, en mi opinión, mejora los mensajes de error para cuando se viola la regla.fuente
Para la mayoría de los generadores de analizadores sintácticos, por lo general es una variante de Backus-Naur 's
<nonterminal> ::= expression
formato. Voy a suponer que estás usando algo así y no estás tratando de construir tus analizadores a mano. Si puede producir un analizador sintáctico para un formato en el que se le ha dado la sintaxis (he incluido un problema de muestra a continuación), especificar las gramáticas no es su problema.Creo que te enfrentas a adivinar la sintaxis de un conjunto de muestras, que en realidad es más reconocimiento de patrones que análisis. Si tiene que recurrir a eso, significa que quien proporciona sus datos no puede darle su sintaxis porque no tienen un buen manejo de su formato. Si tiene la opción de retroceder y decirles que le den una definición formal, hágalo. No es justo que le den un problema vago si usted puede ser considerado responsable de las consecuencias de un analizador basado en una sintaxis deducida que acepta una entrada incorrecta o rechaza una buena entrada.
"Bueno" en su situación tendría que significar "analiza los aspectos positivos y rechaza los negativos". Sin ninguna otra especificación formal de la sintaxis de su archivo de entrada, las muestras son sus únicos casos de prueba y no puede hacerlo mejor que eso. Podría poner su pie en el suelo y decir que solo los ejemplos positivos son buenos y rechazar cualquier otra cosa, pero que probablemente no esté en el espíritu de lo que está tratando de lograr.
En circunstancias más sensatas, probar una gramática es como probar cualquier otra cosa: debe encontrar suficientes casos de prueba para ejercer todas las variantes de los no terminales (y terminales, si están siendo generados por un lexer).
Problema de muestra
Escriba una gramática que analizará los archivos de texto que contienen una lista tal como se define en las siguientes reglas:
Ejemplo de entrada (todo válido):
fuente
Las respuestas de Macneil y Blrfl son geniales. Solo quiero agregar algunos comentarios sobre el comienzo del proceso.
Una sintaxis es solo una forma de representar un programa . Entonces, la sintaxis de su idioma debe estar determinada por su respuesta a esta pregunta: ¿Qué es un programa?
Se podría decir que un programa es una colección de clases. Ok, eso nos da
como punto de partida O quizás tengas que escribirlo
Ahora, ¿qué es una clase? Tiene un nombre; una especificación opcional de superclase; y un montón de constructor, método y declaraciones de campo. Además, necesita alguna forma de agrupar una clase en una sola unidad (no ambigua), y eso debe implicar algunas concesiones a la usabilidad (por ejemplo, etiquetarlo con la palabra reservada
class
). Bueno:Esa es una notación ("sintaxis concreta") que podría elegir. O podría decidir fácilmente sobre esto:
o
Probablemente ya haya tomado esta decisión implícitamente, especialmente si tiene ejemplos, pero solo quiero reforzar el punto: la estructura de la sintaxis está determinada por la estructura de los programas que representa. Eso es lo que te hace pasar las "gramáticas triviales" de la respuesta de Macneil. Sin embargo, los programas de ejemplo siguen siendo muy importantes. Sirven para dos propósitos. Primero, te ayudan a descubrir, en el nivel abstracto, qué es un programa. En segundo lugar, le ayudan a decidir qué sintaxis concreta debe usar para representar la estructura de su idioma.
Una vez que haya descifrado la estructura, debe volver atrás y tratar temas como permitir espacios en blanco y comentarios, corregir ambigüedades, etc. Estos son importantes, pero son secundarios al diseño general y dependen en gran medida del tecnología de análisis que está utilizando.
Finalmente, no intentes representar todo sobre tu idioma en la gramática. Por ejemplo, es posible que desee prohibir ciertos tipos de código inalcanzable (por ejemplo, una declaración después de un
return
, como en Java). Probablemente no deberías tratar de incluir eso en la gramática, porque perderás cosas (whoops, ¿quéreturn
pasa si están entre llaves? ¿O si ambas ramas de unif
enunciado regresan?) O harás tu gramática demasiado complicada administrar. Es una restricción sensible al contexto ; escríbalo como un pase separado. Otro ejemplo muy común de una restricción sensible al contexto es un sistema de tipos. Podrías rechazar expresiones como1 + "a"
en la gramática, si trabajaste lo suficiente, pero no pudiste rechazar1 + x
(dondex
tiene cadena de tipo). Entoncesevite las restricciones a medias en la gramática y hágalas correctamente como un pase separado.fuente