semantico - ¿Por qué no se puede analizar C++ con un analizador LR(1)?

como hacer un compilador

Question

Estaba leyendo acerca de los analizadores sintácticos y analizadores sintácticos y encontré esta afirmación en la página de análisis LR de la wikipedia:

Muchos lenguajes de programación se pueden analizar utilizando alguna variación de un analizador LR. Una excepción notable es C ++.

¿Por que es esto entonces? ¿Qué propiedad particular de C ++ hace que sea imposible analizar con analizadores LR?

Al usar google, solo encontré que C se puede analizar perfectamente con LR (1) pero C ++ requiere LR (∞).

Answer 1

Como puede ver en mi respuesta aquí , C ++ contiene sintaxis que no puede ser analizada determinísticamente por un analizador LL o LR debido a la etapa de resolución de tipo (típicamente post-análisis) cambiando el orden de las operaciones , y por lo tanto la forma fundamental de la AST ( típicamente se espera que sea provisto por un análisis de primera etapa).

Answer 2

Creo que estás muy cerca de la respuesta.

LR (1) significa que el análisis de izquierda a derecha necesita solo un token para mirar hacia adelante para el contexto, mientras que LR (∞) significa una mirada infinita. Es decir, el analizador tendría que saber todo lo que venía para descubrir dónde está ahora.

Answer 3

El problema nunca se define así, mientras que debería ser interesante:

¿Cuál es el conjunto más pequeño de modificaciones a la gramática C ++ que sería necesario para que esta nueva gramática pueda ser perfectamente analizada por un analizador yacc "sin contexto"? (haciendo uso solo de un ''hack'': la desambiguación typename / identifier, el analizador que informa al lexer de cada typedef / class / struct)

Veo algunos:

1. Type Type; está prohibido. Un identificador declarado como un nombre de tipo no puede convertirse en un identificador de tipo no de tipo (tenga en cuenta que el struct Type Type no es ambiguo y podría seguir permitiéndose).

   Hay 3 tipos de names tokens de names tokens :

   • types : types integrado o debido a un typedef / class / struct
   • plantillas-funciones
   • identificadores: funciones / métodos y variables / objetos

   Considerar funciones de plantilla como tokens diferentes resuelve la ambigüedad de la func< . Si func es un nombre de función de plantilla, entonces < debe ser el comienzo de una lista de parámetros de plantilla; de lo contrario, func es un puntero de función y < es el operador de comparación.

2. Type a(2); es una instanciación de objetos. Type a(); y Type a(int) son prototipos de funciones.

3. int (k); está completamente prohibido, debe escribirse int k;

4. typedef int func_type(); y typedef int (func_type)(); están prohibidos

   Una función typedef debe ser un puntero de función typedef: typedef int (*func_ptr_type)();

5. la recursión de la plantilla está limitada a 1024; de lo contrario, se podría pasar un máximo incrementado como una opción para el compilador.

6. int a,b,c[9],*d,(*f)(), (*g)()[9], h(char); también podría estar prohibido, reemplazado por int a,b,c[9],*d; int (*f)();

   int (*g)()[9];

   int h(char);

   una línea por prototipo de función o declaración de puntero de función.

   Una alternativa muy preferida sería cambiar la sintaxis del puntero de función horrible,

   int (MyClass::*MethodPtr)(char*);

   siendo resintantado como:

   int (MyClass::*)(char*) MethodPtr;

   siendo esto coherente con el operador de reparto (int (MyClass::*)(char*))

7. typedef int type, *type_ptr; podría estar prohibido también: una línea por tipodef. Por lo tanto, se convertiría

   typedef int type;

   typedef int *type_ptr;

8. sizeof int , sizeof char , sizeof long long y co. podría declararse en cada archivo fuente. Por lo tanto, cada archivo fuente que haga uso del tipo int debe comenzar con

   #type int : signed_integer(4)

   y unsigned_integer(4) estaría prohibido fuera de esa directiva #type esto sería un gran paso en el tamaño estúpido de la ambigüedad sizeof int presente en tantos encabezados de C ++

El compilador que implementa C ++ resintado podría, si encuentra una fuente de C ++ haciendo uso de la sintaxis ambigua, mover source.cpp también una carpeta ambiguous_syntax , y crearía automáticamente un source.cpp traducido source.cpp antes de compilarlo.

¡Por favor, agregue sus sintaxis ambiguas de C ++ si sabe algo!

Answer 4

Hay un hilo interesante en Lambda the Ultimate que discute la gramática LALR para C ++ .

Incluye un enlace a una tesis de doctorado que incluye una discusión sobre el análisis C ++, que establece que:

"La gramática de C ++ es ambigua, depende del contexto y posiblemente requiera una búsqueda infinita para resolver algunas ambigüedades".

Continúa para dar una serie de ejemplos (ver página 147 del pdf).

El ejemplo es:

int(x), y, *const z;

sentido

int x;
int y;
int *const z;

Comparar con:

int(x), y, new int;

sentido

(int(x)), (y), (new int));

(una expresión separada por comas).

Las dos secuencias de token tienen la misma subsecuencia inicial pero diferentes árboles de análisis, que dependen del último elemento. Puede haber arbitrariamente muchos tokens antes de la desambiguación.

Answer 5

Los analizadores LR no pueden manejar reglas gramaticales ambiguas, por diseño. (Hizo la teoría más fácil en la década de 1970 cuando las ideas se estaban resolviendo).

C y C ++ ambos permiten la siguiente declaración:

x * y ;

Tiene dos análisis diferentes:

1. Puede ser la declaración de y, como puntero para escribir x
2. Puede ser una multiplicación de xey, descartando la respuesta.

Ahora, puedes pensar que este último es estúpido y debe ser ignorado. La mayoría estaría de acuerdo con usted; sin embargo, hay casos en los que podría tener un efecto secundario (por ej., si Multiplicado está sobrecargado). pero ese no es el punto. El punto es que hay dos análisis diferentes, y por lo tanto un programa puede significar cosas diferentes dependiendo de cómo debería haberse analizado.

El compilador debe aceptar el apropiado en las circunstancias apropiadas, y en ausencia de cualquier otra información (p. Ej., Conocimiento del tipo de x) debe recopilar ambos para decidir luego qué hacer. Por lo tanto, una gramática debe permitir esto. Y eso hace que la gramática sea ambigua.

Por lo tanto, el análisis LR puro no puede manejar esto. Tampoco pueden usarse muchos otros generadores de analizadores ampliamente disponibles, como Antlr, JavaCC, YACC o Bison tradicional, o incluso analizadores de estilo PEG, de una manera "pura".

Hay muchos casos más complicados (la sintaxis de la plantilla de análisis requiere una búsqueda anticipada arbitraria, mientras que LALR (k) puede mirar hacia delante en la mayoría de los k tokens), pero solo se necesita un contraejemplo para derribar el análisis LR puro (o los demás).

La mayoría de los analizadores de C / C ++ reales manejan este ejemplo usando algún tipo de analizador determinístico con un hack extra: entrelazan el análisis con la colección de tablas de símbolos ... de modo que cuando se encuentra "x", el analizador sabe si x es un tipo o no, y así puede elegir entre los dos análisis potenciales. Pero un analizador sintáctico que hace esto no está libre de contexto, y los analizadores LR (los puros, etc.) están (en el mejor de los casos) libres de contexto.

Uno puede hacer trampas y agregar comprobaciones semánticas de tiempo de reducción por regla en los analizadores LR para hacer esta desambiguación. (Este código a menudo no es simple). La mayoría de los otros tipos de analizador tienen algunos medios para agregar comprobaciones semánticas en varios puntos del análisis sintáctico, que se pueden usar para hacer esto.

Y si hace trampa suficiente, puede hacer que los analizadores de LR funcionen para C y C ++. Los chicos de GCC lo hicieron por un tiempo, pero lo abandonaron por un análisis codificado a mano, creo que porque querían un mejor diagnóstico de errores.

Sin embargo, hay otro enfoque, que es bueno y limpio, y analiza C y C ++ sin ningún tipo de hacking de tabla de símbolos: analizadores GLR . Estos son analizadores sintácticos sin contexto completo (que tienen una búsqueda infinita y efectiva). Los analizadores de GLR simplemente aceptan ambos análisis, produciendo un "árbol" (en realidad, un gráfico acíclico dirigido que es casi como un árbol) que representa el análisis ambiguo. Un pase posterior al análisis puede resolver las ambigüedades.

Usamos esta técnica en los frontales C y C ++ para nuestro DMS Software Reengineering Tookit (a partir de junio de 2017, estos manejan C ++ 17 completo en dialectos MS y GNU). Se han utilizado para procesar millones de líneas de grandes sistemas C y C ++, con análisis completos y precisos que producen AST con detalles completos del código fuente. (Ver el AST para el análisis más irritante de C ++ ) .