Reglas de análisis: cómo hacer que funcionen bien juntas

Question

Así que estoy haciendo un analizador, donde prefiero la flexibilidad a la velocidad, y quiero que sea fácil escribir gramáticas para, por ejemplo.no hay reglas de solución complicadas (reglas falsas para resolver conflictos, etc., como tienes que hacer en yacc/bison, etc.)

Hay un Lexer codificado a mano con un conjunto fijo de tokens (p. ej.PLUS, DECIMAL, STRING_LIT, NAME, etc.) ahora mismo existen tres tipos de reglas:

• Regla de token:coincide con un token en particular
• Regla de secuencia:coincide con una lista ordenada de reglas
• Regla de grupo:coincide con cualquier regla de una lista

Por ejemplo, digamos que tenemos TokenRule 'varAccess', que coincide con el NOMBRE del token (aproximadamente /[A-Za-z][A-Za-z0-9_]*/), y SequenceRule 'assignment', que coincide con [ expresión, TokenRule(PLUS), expresión].

La expresión es una GroupRule que coincide con 'asignación' o 'varAccess' (el conjunto de reglas real con el que estoy probando es un poco más completo, pero eso servirá para el ejemplo)

Pero ahora digamos que quiero analizar

var1 = var2

Y digamos que el analizador comienza con la expresión de regla (el orden en el que se definen no debería importar; las prioridades se resolverán más adelante).Y digamos que la expresión GroupRule primero intentará 'asignación'.Luego, dado que 'expresión' es la primera regla que coincide en 'asignación', intentará analizar una expresión nuevamente, y así sucesivamente hasta que la pila se llene y la computadora, como se esperaba, simplemente se dé por vencida en un brillante error de segmento.

Entonces, lo que hice fue: SequenceRules se agregan como 'hojas' a su primera regla y se convierten en reglas no raíz.Las reglas raíz son reglas que el analizador probará primero.Cuando uno de ellos se aplica y coincide, intenta subaplicar cada una de sus hojas, una por una, hasta que una coincida.Luego prueba las hojas de la hoja correspondiente, y así sucesivamente, hasta que ya no hay nada que coincida.

Para que pueda analizar expresiones como

var1 = var2 = var3 = var4

Justo =) Ahora lo interesante.Este código:

var1 = (var2 + var3)

No analizará.Lo que sucede es que var1 se analiza (varAccess), se subaplica la asignación, busca una expresión, intenta 'paréntesis', comienza, busca una expresión después de '(', encuentra var2 y luego se ahoga con '+ ' porque esperaba un ')'.

¿Por qué no coincide con 'var2 + var3'?(y sí, hay una SequenceRule para "agregar", antes de preguntar).Porque 'agregar' no es una regla raíz (para evitar la recursividad infinita con la expresión de análisis que comienza con la expresión, etc.) y que las hojas no se prueban en SequenceRules, de lo contrario, analizaría cosas como

reader readLine() println()

como

reader (readLine() println())

(p.ej.'1 = 3' es la expresión esperada por add, la hoja de varAccess a)

mientras que nos gustaría que fuera asociativo de izquierda, p.analizando como

(reader readLine()) println()

De todos modos, ahora tenemos el problema de que deberíamos poder analizar expresiones como '1 + 2' dentro de SequenceRules.¿Qué hacer?¿Agregar un caso especial en el que cuando las SequenceRules comienzan con una TokenRule, las GroupRules que contiene se prueban en busca de hojas?¿Tendría eso sentido fuera de ese ejemplo en particular?¿O debería poder especificarse en cada elemento de una SequenceRule si se debe probar si hay hojas o no?Dígame lo que piensa (aparte de desechar todo el sistema; de todos modos, eso probablemente sucederá en unos meses)

PD:Por favor, por favor, no respondas algo como "ve a leer este libro de 400 páginas o ni siquiera mereces nuestro tiempo". Si sientes la necesidad, simplemente abstente y visita reddit.¿Bueno?Gracias de antemano.

Answer 1

LL (k) analizadores (de arriba hacia abajo recursiva, ya sea automatizado o escrita a mano) requieren refactorización de su gramática para evitar recursión por la izquierda, y con frecuencia requieren especificaciones especiales de búsqueda hacia delante (por ejemplo antlr) para ser capaz de manejar lookahead k-token . Desde las gramáticas son complejos, se llega a descubrir k mediante la experimentación, que es exactamente lo que desea evitar.

YACC / LALR (1) gramáticas aviod el problema de la recursión por la izquierda, que es un gran paso adelante. La mala noticia es que no hay langauges de programación real (excepto PASCAL original del Wirth) que sean LALR (1). Por lo tanto se llega a cortar su gramática para cambiarlo desde LR (k) a LALR (1), una vez más lo que obligó a sufrir los experimentos que se exponen los casos extraños, y la piratería la lógica de reducción de la gramática a tratar de manejar K símbolos de anticipación cuando el analizador generadores (YACC, bisonte, ... lo que sea) producen analizadores 1-búsqueda hacia delante.

GLR analizadores ( http://en.wikipedia.org/wiki/GLR_parser ) le permiten evitar casi todo este disparate. Si usted puede escribir un programa de análisis independiente del contexto, en circunstancias más prácticas, un analizador GLR analizará sin más esfuerzo. Eso es un enorme alivio cuando intenta escribir gramáticas arbitrarias. Y un muy buen analizador GLR producirá directamente un árbol.

BISON se ha mejorado para hacer el análisis sintáctico GLR, más o menos. Usted todavía tiene que escribir la lógica compleja para producir su AST deseada, y usted tiene que preocuparse acerca de cómo manejar los analizadores fallidos y limpiar / borrar sus árboles correspondientes (fallidos). El software DMS Reingeniería Tookit proporciona analizadores GLR estándar para cualquier gramática independiente del contexto y AST construye automáticamente sin ningún esfuerzo adicional de su parte; árboles ambiguas se construyen de forma automática y se pueden limpiar por analyis semántica post-análisis. Hemos utilizado esto que ver 30 + definir gramáticas de las lenguas, incluyendo C, incluyendo C ++ (que es ampliamente cree que es difícil de analizar [y es casi imposible analizar con YACC] pero es sencillo con el Real GLR); ver C +++ analizador extremo delantero y AST constructor basado en DMS.

En pocas palabras: si usted quiere escribir reglas gramaticales de una manera directa, y conseguir un analizador para procesarlos, utilizar la tecnología de análisis GLR. Bisontes casi funciona. Los DM realmente funciona.

Answer 2

Mi técnica favorita es el análisis sintáctico para crear analizador sintáctico descendente recursivo (RD) a partir de una especificación de la gramática PEG. Por lo general son muy rápida, sencilla y flexible. Una buena ventaja es que usted no tiene que preocuparse acerca de los pases de tokenización separadas, y preocuparse por apretar la gramática en alguna forma LALR es inexistente. Algunas bibliotecas de PEG se enumeran [aquí] [1].

Lo siento, sé que esto cae en un tiro de distancia del sistema, pero usted es apenas fuera de la puerta con su problema y el cambio a un programa de análisis de PEG RD, que acaba de eliminar sus dolores de cabeza ahora.