Contexto de análisis de lenguaje sensible

Question

estoy leyendo la referencia antlr definitivo por Terence Parr, donde dice:

predicados semánticos son un poderoso medios de reconocer estructuras lenguaje sensible al contexto permitiendo que la información tiempo de ejecución para conducir reconocimiento

Pero los ejemplos en el libro son muy simples. Lo que necesito saber es: Antlr puede analizar context-sensitive reglas como:

xAy -> XBY

Si antlr no puede analizar estas reglas, es que no hay otra herramienta que se ocupa de las gramáticas sensibles al contexto ?

Answer 1

ANTLR analiza solo las gramáticas que son LL (*). No puede analizar el uso de gramáticas para idiomas completos sensibles al contexto, como el ejemplo que proporcionó. Creo que lo que Parr quería decir es que ANTLR puede analizar algunos idiomas que requieren algunas restricciones de contexto (izquierda).

En particular, se puede usar predicados semánticos en "acciones de reducción" (hacemos esto para analizadores GLR utilizados por nuestro DMS Software Reengineering Toolkit pero la idea es similar para antlr, creo) para inspeccionar los datos recogidos por el analizador hasta el momento , ya sea como efectos secundarios ad hoc de otras acciones semánticas, o en un árbol de análisis sintáctico parcialmente construido.

Para nuestra DMS-based Fortran front end basada en DMS, hay una verificación sensible al contexto para garantizar que los bucles DO estén correctamente alineados. Considere lo siguiente:

DO 20, I= ... 
    DO 10, J = ... 
     ... 
20 CONTINUE 
10 CONTINUE 

Desde el punto de vista del analizador, la corriente léxica se ve así:

DO <number> , <variable> = ... 
    DO <number> , <variable> = ... 
     ... 
<number> CONTINUE 
<number> CONTINUE 

¿Cómo puede entonces el analizador saben cuáles declaración va con cada instrucción continue? (decir que cada DO coincide con su CONTINUACIÓN más cercana no funcionará, porque FORTRAN puede compartir una instrucción CONTINUAR con múltiples encabezados DO).

Utilizamos un predicado semánticas "CheckMatchingNumbers" en la reducción de la siguiente regla:

block = 'DO' <number> rest_of_do_head newline 
     block_of_statements 
     <number> 'CONTINUE' newline ; CheckMatchingNumbers 

para comprobar que el siguiente número de la palabra clave DO, y el número que sigue a la palabra clave de concordancia continuar. Si el predicado semántico dice que coinciden, entonces una reducción para esta regla tiene éxito y hemos alineado el encabezado de DO con CONTINUAR correctamente. Si el predicado falla, entonces no se propone ninguna reducción (y esta regla se elimina de los candidatos para analizar el contexto local); algún otro conjunto de reglas tiene que analizar el texto.

Las reglas reales y los predicados semánticos para manejar el anidamiento de FORTRAN con shared continues son más complejos que esto, pero creo que esto lo demuestra.

Lo que desea es un motor de análisis sensible al contexto completo. Sé que la gente los ha construido, pero no conozco ninguna implementación completa, y no espero que sean rápidos.

Seguí Quinn Taylor Jackson's MetaS grammar system durante un tiempo; sonaba como un intento práctico de acercarse.