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

153

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 (∞).

Alegre
fuente
77
Al igual que: necesita comprender la recursividad para aprender la recursividad ;-).
Toon Krijthe
55
"Entenderás los analizadores una vez que analices esta frase".
ilya n.

Respuestas:

92

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.

Rob Walker
fuente
29
Sería genial tener un resumen sobre la página 147 en esta página. Aunque voy a leer esa página. (+1)
Alegre el
11
El ejemplo es: int (x), y, * const z; // significado: int x; int y; int * const z; (una secuencia de declaraciones) int (x), y, new int; // significado: (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.
Blaisorblade
66
Bueno, en ese contexto ∞ significa "arbitrariamente muchos" porque la búsqueda anticipada siempre estará limitada por la longitud de entrada.
MauganRa
1
Estoy bastante perplejo por la cita extraída de una tesis doctoral. Si existe una ambigüedad, entonces, por definición, NINGUNA anticipación puede "resolver" la ambigüedad (es decir, decidir qué análisis es el correcto, ya que al menos 2 análisis son correctos por la gramática). Además, la cita menciona la ambigüedad de C, pero la explicación no muestra una ambigüedad, sino solo un ejemplo no ambiguo en el que la decisión de análisis solo se puede tomar después de una larga revisión arbitraria.
dodecaplex
231

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 ++ ) .

Ira Baxter
fuente
11
Si bien el ejemplo 'x * y' es interesante, lo mismo puede suceder en C ('y' puede ser un typedef o una variable). Pero C puede ser analizado por un analizador LR (1), entonces, ¿cuál es la diferencia con C ++?
Martin Cote
12
Mi respuesta ya había observado que C tenía el mismo problema, creo que te lo perdiste. No, LR (1) no puede analizarlo por el mismo motivo. Er, ¿qué quieres decir con 'y' puede ser un typedef? ¿Quizás quisiste decir 'x'? Eso no cambia nada.
Ira Baxter
66
Parse 2 no es necesariamente estúpido en C ++, ya que * podría anularse para tener efectos secundarios.
Dour High Arch
8
Lo miré x * yy me reí: es sorprendente lo poco que se piensa en pequeñas ambigüedades ingeniosas como esta.
nuevo123456
51
@altie Seguramente nadie sobrecargaría un operador de desplazamiento de bits para que escriba la mayoría de los tipos de variables en una secuencia, ¿verdad?
Troy Daniels
16

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!

se reúne
fuente
3
C ++ está muy bien arraigado. Nadie lo hará en la práctica. Esas personas (como nosotros) que construyen partes frontales simplemente muerden la bala y hacen la ingeniería para que los analizadores funcionen. Y, mientras existan plantillas en el lenguaje, no obtendrá un analizador puro sin contexto.
Ira Baxter
9

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).

Sam Harwell
fuente
3
La tecnología de análisis que maneja la ambigüedad simplemente produce ambas variantes AST a medida que se analizan, y simplemente elimina la incorrecta según la información de tipo.
Ira Baxter
@Ira: Sí, eso es correcto. La ventaja particular de esto es que le permite mantener la separación del análisis de la primera etapa. Si bien es más comúnmente conocido en el analizador GLR, no hay una razón particular por la que vea que no se puede presionar C ++ con un "GLL". analizador también.
Sam Harwell
"GLL"? Bueno, claro, pero tendrás que descifrar la teoría y escribir un artículo para que el resto lo use. Lo más probable es que pueda utilizar un analizador codificado a mano de arriba hacia abajo, un analizador LALR () de retroceso (pero mantener los analizadores "rechazados") o ejecutar un analizador Earley. GLR tiene la ventaja de ser una solución bastante buena, está bien documentada y por ahora bien probada. Una tecnología GLL tendría que tener algunas ventajas bastante significativas para mostrar GLR.
Ira Baxter
El proyecto Rascal (Países Bajos) afirma que están construyendo un analizador GLL sin escáner. Trabajo en progreso, puede ser difícil encontrar información en línea. en.wikipedia.org/wiki/RascalMPL
Ira Baxter
@IraBaxter Parece que hay nuevos desarrollos en GLL: vea este documento de 2010 sobre GLL dotat.at/tmp/gll.pdf
Sjoerd
6

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.

casademora
fuente
44
Recuerdo de mi clase de compiladores que LR (n) para n> 0 es matemáticamente reducible a LR (1). ¿No es eso cierto para n = infinito?
rmeador
14
No, hay una montaña infranqueable de diferencia entre n e infinito.
Ephemient
44
¿No es la respuesta: sí, dado un tiempo infinito? :)
Steve Fallows
77
En realidad, por mi vago recuerdo de cómo tiene lugar LR (n) -> LR (1), implica crear nuevos estados intermedios, por lo que el tiempo de ejecución es una función no constante de 'n'. Traducir LR (inf) -> LR (1) tomaría un tiempo infinito.
Aaron
55
"¿No es la respuesta: sí, dado un tiempo infinito?" - No: la frase "con una cantidad de tiempo infinita" no es más que una forma breve y no sensorial de decir "no se puede hacer con una cantidad de tiempo finita". Cuando vea "infinito", piense: "no es finito".
ChrisW
4

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).


fuente
Ese es el truco estándar utilizado por GCC con su antiguo analizador LR para manejar la ambigüedad de cosas como "x * y"; Por desgracia, todavía existe el requisito de búsqueda anticipada arbitrariamente grande para analizar otras construcciones, por lo que LR (k) no puede ser una solución k fija. (GCC cambió a descenso recursivo con más publicidad).
Ira Baxter