¿Cómo debo especificar una gramática para un analizador?

A partir de los archivos de muestra, deberá tomar decisiones basadas en cuánto desea generalizar a partir de esos ejemplos. Supongamos que tiene los siguientes tres ejemplos: (cada uno es un archivo separado)

f() {}
f(a,b) {b+a}
int x = 5;

Podrías especificar trivialmente dos gramáticas que aceptarán estas muestras:

Gramática trivial uno:

start ::= f() {} | f(a,b) {b+a} | int x = 5;

Gramática trivial dos:

start ::= tokens
tokens ::= token tokens | <empty>
token ::= identifier | literal | { | } | ( | ) | , | + | = | ;

El primero es trivial porque acepta solo las tres muestras. El segundo es trivial porque acepta todo que posiblemente podría usar esos tipos de token. [Para esta discusión, voy a suponer que no te preocupa mucho el diseño del tokenizador: es fácil asumir los identificadores, los números y la puntuación como tus tokens, y puedes tomar prestado cualquier conjunto de tokens de cualquier lenguaje de scripting como de todos modos.]

Por lo tanto, el procedimiento que deberá seguir es comenzar en el nivel alto y decidir "¿cuántos de cada instancia quiero permitir?" Si una construcción sintáctica puede tener sentido repetir cualquier número de veces, como method s en una clase, querrá una regla con este formulario:

methods ::= method methods | empty

Lo que se indica mejor en EBNF como:

methods ::= {method}

Probablemente será obvio cuando solo desee cero o una instancia (lo que significa que la construcción es opcional, como con la cláusula extends para una clase Java), o cuando desea permitir una o más instancias (como con un inicializador variable en una declaración). Tendrá que tener en cuenta cuestiones como requerir un separador entre elementos (como con , en una lista de argumentos), requerir un terminador después de cada elemento (como con ; para declaraciones separadas), o no requerir separador o terminador (como el caso con los 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 ceñirse a algo conocido, como las reglas de las expresiones de C, que buscar algo exótico, pero siempre que todo lo demás sea igual.

Además de los problemas de precedencia (lo que se analiza entre sí) y los problemas de repetición (¿cuántos de cada elemento deben aparecer, cómo se separan?), también deberá pensar en el orden: ¿Debe aparecer algo siempre antes que otro? ¿cosa? Si se incluye una cosa, ¿debería excluirse otra?

En este punto, puede verse tentado a imponer algunas reglas gramaticalmente, una regla tal como si se especifica la edad de Person , no quiere permitir que también se especifique 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 que se analiza todo. Esto mantiene la gramática más simple y, en mi opinión, proporciona mejores mensajes de error para cuando se viola la regla.

  

¿Dónde puedo aprender cómo especificar la gramática para un analizador?

Para la mayoría de los generadores de analizadores, suele ser una variante de Backus-Naur 's <nonterminal> ::= expression formato. Voy a suponer que estás usando algo así y que no intentas construir tus analizadores a mano. Si puede producir un analizador para un formato en el que se le ha dado la sintaxis (he incluido un problema de muestra a continuación), la especificación de las gramáticas no es su problema.

A lo que creo que te enfrentas es a la sintaxis de adivinación de un conjunto de muestras, que en realidad es más un reconocimiento de patrones que un análisis. Si tiene que recurrir a eso, significa que quienquiera que proporcione sus datos no puede proporcionarle su sintaxis porque no tiene un buen control sobre su formato. Si tiene la opción de rechazar y decirles que le den una definición formal, hágalo. No es justo que te den un problema vago si puedes ser responsable de las consecuencias de un analizador basado en una sintaxis deducida que acepta una entrada incorrecta o rechaza una buena entrada.

  

... Nunca estoy seguro de que la gramática haya subido, lo cual es bueno (por cualquier   medida razonable de "bueno").

"Bien" 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 hacer nada mejor que eso. Podrías poner tu pie abajo y decir que solo los ejemplos positivos son buenos y rechazar cualquier otra cosa, pero probablemente no esté en el espíritu de lo que estás tratando de lograr.

En circunstancias más sanas, probar una gramática es como probar cualquier otra cosa: tienes que presentar suficientes casos de prueba para ejercitar 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 analice los archivos de texto que contienen una lista como se define en las reglas a continuación:

• Una lista consta de cero o más cosas .
• Una cosa consiste en un identificador , una llave abierta, una lista de elementos y una llave de cierre.
• Una _item_list_ consta de cero o más elementos .
• Un elemento consiste en un identificador , un signo igual, otro identificador y un punto y coma.
• Un identificador es una secuencia de uno o más de los caracteres A-Z, a-z, 0-9 o el subrayado.
• Se omite el espacio en blanco.

Ejemplo de entrada (todo válido):

clank { foo = bar; baz = bear; }
clunk {
    quux =bletch;
    281_apple = OU812;
    He_Eats=Asparagus ; }

Las respuestas de Macneil y Blrfl son excelentes. Solo quiero agregar algunos comentarios sobre el inicio del proceso.

Una sintaxis es solo una forma de representar un programa . Por lo tanto, la sintaxis de su idioma debe estar determinada por su respuesta a esta pregunta: ¿Qué es un programa?

Podrías decir que un programa es una colección de clases. Está bien, eso nos da

program ::= class*

como punto de partida. O puede que tengas que escribirlo

program ::= ε
         |  class program

Ahora, ¿qué es una clase? Tiene un nombre; una especificación de superclase opcional; y un montón de declaraciones de constructores, métodos y campos. Además, necesita alguna forma de agrupar una clase en una sola unidad (no ambigua), y eso debería implicar algunas concesiones a la usabilidad (por ejemplo, etiquétela con la palabra reservada class ). Bien:

class ::= "class" identifier extends-clause? "{" class-member-decl * "}"

Esa es una notación ("sintaxis concreta") que puedes elegir. O simplemente puedes decidir sobre esto:

class ::= "(" "class" identifier extends-clause "(" class-member-decl* ")" ")"

o

class ::= "class" identifier "=" "CLASS" extends-clause? class-member-decl* "END"

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 dos propósitos. Primero, te ayudan a descubrir, en el nivel abstracto, qué es un programa. En segundo lugar, te ayudan a decidir qué sintaxis concreta debes usar para representar la estructura de tu idioma.

Una vez que haya reducido la estructura, debería regresar y lidiar con problemas como permitir espacios en blanco y comentarios, corregir ambigüedades, etc. Estos son importantes, pero son secundarios al diseño general, y son altamente depende de la tecnología de análisis que esté utilizando.

Finalmente, no trates de representar todo lo relacionado con 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 intentar meter eso en la gramática, ya sea porque extrañarás cosas (gritos, ¿qué pasaría si return está entre llaves o si ambas ramas de una declaración if regresan?) Haz tu gramática demasiado complicada de manejar. Es una restricción sensible al contexto ; Escríbelo como un pase separado. Otro ejemplo muy común de una restricción sensible al contexto es un sistema de tipos. Podría rechazar expresiones como 1 + "a" en la gramática, si trabajó lo suficientemente duro, pero no pudo rechazar 1 + x (donde x tiene una cadena de tipo). Así que evita las restricciones semicocidas en la gramática y hazlas correctamente como un pase aparte.