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

Estaba leyendo sobre analizadores y generadores de analizadores y encontré esta declaración en la página de análisis de LR de 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?

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

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

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

"La gramática de C ++ es ambigua, depende del contexto y potencialmente requiere una anticipación infinita para resolver algunas ambigüedades".

Continúa para dar una serie de ejemplos (vea la 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 tokens tienen la misma subsecuencia inicial pero diferentes árboles de análisis, que dependen del último elemento. Puede haber arbitrariamente muchos tokens antes del desambiguado.

Los analizadores LR no pueden manejar reglas gramaticales ambiguas, por diseño. (Facilitó la teoría en la década de 1970, cuando las ideas se estaban elaborando).

C y C ++ 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 x e y, tirando la respuesta.

Ahora, podrías pensar que este último es estúpido y debería ser ignorado. La mayoría estaría de acuerdo contigo; sin embargo, hay casos en los que podría tener un efecto secundario (por ejemplo, si la multiplicación está sobrecargada). Pero ese no es el punto. El punto es que hay son dos análisis sintácticos diferentes, y por lo tanto un programa puede significar cosas diferentes dependiendo de cómo esto debería haber sido analizado.

El compilador debe aceptar el apropiado bajo las circunstancias apropiadas, y en ausencia de cualquier otra información (por ejemplo, conocimiento del tipo de x) debe recopilar ambos para decidir más adelante 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 utilizarse de manera "pura" muchos otros generadores de analizadores disponibles, como Antlr, JavaCC, YACC o Bison tradicional, o incluso analizadores de estilo PEG.

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

La mayoría de los analizadores reales de C / C ++ manejan este ejemplo utilizando algún tipo de analizador determinista con un truco adicional: 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 posibles análisis. Pero un analizador 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 trampa y agregar controles semánticos 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 analizadores tienen algunos medios para agregar comprobaciones semánticas en varios puntos del análisis, que pueden usarse para hacer esto.

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

Sin embargo, hay otro enfoque, que es agradable y limpio y analiza C y C ++ muy bien sin ninguna piratería de la tabla de símbolos: analizadores GLR . Estos son analizadores completos sin contexto (que tienen efectivamente anticipación infinita). Los analizadores GLR simplemente aceptan ambos analizadores , produciendo un "árbol" (en realidad, un gráfico acíclico dirigido que es principalmente un árbol) que representa el análisis ambiguo. Un pase posterior al análisis puede resolver las ambigüedades.

Utilizamos esta técnica en las interfaces C y C ++ para nuestro token de reingeniería de software DMS (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. (Vea el AST para el análisis más irritante de C ++ ) .

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 de C ++ que sería necesario para que esta nueva gramática pudiera ser perfectamente analizada por un analizador yacc "sin contexto"? (haciendo uso de un solo 'hack': la desambiguación del nombre de tipo / identificador, el analizador informa al lexer de cada typedef / class / struct)

Veo algunas:

1. Type Type;está prohibido. Un identificador declarado como typename no puede convertirse en un identificador que no sea typename (tenga en cuenta questruct Type Type no sea no es ambiguo y aún podría permitirse).

   Hay 3 tipos de names tokens:

   • types : tipo incorporado o debido a un typedef / class / struct
   • funciones de plantilla
   • identificadores: funciones / métodos y variables / objetos

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

2. Type a(2);Es una instanciación de objeto. 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 recursividad de la plantilla está limitada a 1024, de lo contrario, se podría pasar un máximo aumentado como una opción al compilador.

6. int a,b,c[9],*d,(*f)(), (*g)()[9], h(char); podría estar prohibido también, 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 horrible sintaxis del puntero de función,

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

   siendo resintaxis como:

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

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

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

   typedef int type;

   typedef int *type_ptr;

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

   #type int : signed_integer(4)

   y unsigned_integer(4)estaría prohibido fuera de esa #type directiva, esto sería un gran paso hacia la estúpida sizeof intambigüedad presente en tantos encabezados de C ++

El compilador que implementa el C ++ resyntaxed, si encuentra una fuente C ++ haciendo uso de una sintaxis ambigua, movería source.cpptambién una ambiguous_syntaxcarpeta y crearía automáticamente una traducción no ambiguasource.cpp antes de compilarla.

¡Agregue sus sintaxis ambiguas de C ++ si conoce algunas!

Como puede ver en mi respuesta aquí , C ++ contiene una sintaxis que un analizador LL o LR no puede analizar de manera determinista debido a que la etapa de resolución de tipo (generalmente posterior al análisis) cambia el orden de las operaciones y, por lo tanto, la forma fundamental del AST ( normalmente se espera que sea proporcionado por un análisis de primera etapa).

Creo que estás bastante cerca de la respuesta.

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

El problema "typedef" en C ++ se puede analizar con un analizador LALR (1) que crea una tabla de símbolos durante el análisis (no un analizador LALR puro). El problema de la "plantilla" probablemente no puede resolverse con este método. La ventaja de este tipo de analizador LALR (1) es que la gramática (que se muestra a continuación) es una gramática LALR (1) (sin ambigüedad).

/* C Typedef Solution. */

/* Terminal Declarations. */

   <identifier> => lookup();  /* Symbol table lookup. */

/* Rules. */

   Goal        -> [Declaration]... <eof>               +> goal_

   Declaration -> Type... VarList ';'                  +> decl_
               -> typedef Type... TypeVarList ';'      +> typedecl_

   VarList     -> Var /','...     
   TypeVarList -> TypeVar /','...

   Var         -> [Ptr]... Identifier 
   TypeVar     -> [Ptr]... TypeIdentifier                               

   Identifier     -> <identifier>       +> identifier_(1)      
   TypeIdentifier -> <identifier>      =+> typedefidentifier_(1,{typedef})

// The above line will assign {typedef} to the <identifier>,  
// because {typedef} is the second argument of the action typeidentifier_(). 
// This handles the context-sensitive feature of the C++ language.

   Ptr          -> '*'                  +> ptr_

   Type         -> char                 +> type_(1)
                -> int                  +> type_(1)
                -> short                +> type_(1)
                -> unsigned             +> type_(1)
                -> {typedef}            +> type_(1)

/* End Of Grammar. */

La siguiente entrada se puede analizar sin problemas:

 typedef int x;
 x * y;

 typedef unsigned int uint, *uintptr;
 uint    a, b, c;
 uintptr p, q, r;

El generador de analizador LRSTAR lee la notación gramatical anterior y genera un analizador que maneja el problema "typedef" sin ambigüedad en el árbol de análisis o AST. (Divulgación: soy el tipo que creó LRSTAR).