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

StackOverflow https://stackoverflow.com/questions/243383

Pregunta

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

Usando Google, solo descubrí que C se puede analizar perfectamente con LR(1) pero C++ requiere LR(∞).

¿Fue útil?

Solución

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

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

  

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

Continúa dando una serie de ejemplos (vea la página 147 del pdf).

El ejemplo es: 

int(x), y, *const z;

significado 

int x;
int y;
int *const z;

Comparar con: 

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 muchas fichas antes de la desambiguación.

Otros consejos

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 xey, desechando 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 (p. ej., si la multiplicación está sobrecargada). Pero ese no es el punto. El punto es que hay dos análisis diferentes y, por lo tanto, un programa puede significar diferentes cosas dependiendo de cómo este 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 usarse muchos otros generadores de analizadores disponibles ampliamente, como Antlr, JavaCC, YACC o Bison tradicional, o incluso analizadores de estilo PEG, en un & "; Puro &"; manera.

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 puro Análisis LR (o los otros).

La mayoría de los analizadores C / C ++ reales manejan este ejemplo usando algunos tipo de analizador determinista con un truco adicional: entrelazan el análisis con la tabla de símbolos colección ... de modo que para el momento " x " se encuentra el analizador sabe si x es un tipo o no, y puede elige entre los dos posibles análisis. Pero un analizador eso hace que esto no esté libre de contexto, y 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 el analizadores LR para hacer esta desambiguación. (Este código a menudo no es simple). La mayoría de los otros tipos de analizadores tener algunos medios para agregar controles semánticos en varios puntos en el análisis, eso se puede usar para hacer esto.

Y si haces trampa lo suficiente, puedes hacer que los analizadores LR funcionen para C y C ++. Los muchachos del CCG lo hicieron por un tiempo, pero lo dieron para el análisis codificado a mano, creo que porque querían mejor diagnóstico de errores.

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

Utilizamos esta técnica en los extremos 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. (Consulte el AST para el análisis más irritante de C ++. )

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

¿Cuál es el conjunto más pequeño de modificaciones a la gramática de C++ que serían necesarias para que esta nueva gramática pueda ser analizada perfectamente por un analizador yacc "no libre de contexto"?(haciendo uso sólo de un 'truco':la desambiguación de nombre de tipo/identificador, el analizador informa al lexer de cada definición de tipo/clase/estructura)

Veo algunos:

  1. Type Type; está prohibido.Un identificador declarado como nombre de tipo no puede convertirse en un identificador que no sea nombre de tipo (tenga en cuenta que struct Type Type 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 tokens diferentes resuelve el problema func< ambigüedad.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 objeto.Type a(); y Type a(int) son prototipos de funciones.

  3. int (k); Está completamente prohibido, debería escribirse. int k;

  4. typedef int func_type(); ytypedef 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 opción al compilador.

  6. int a,b,c[9],*d,(*f)(), (*g)()[9], h(char); También podría prohibirse, sustituirse 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 siendo 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 long y compañía.podría declararse en cada archivo fuente.Por lo tanto, cada archivo fuente que utilice el tipo int debería comenzar con

    #type int : signed_integer(4)

    y unsigned_integer(4) estaría prohibido fuera de eso #type Directiva, este sería un gran paso en el estúpido sizeof int ambigüedad presente en tantos encabezados de C++

El compilador que implementa el C++ resintaxis, si encuentra una fuente de C++ que utiliza una sintaxis ambigua, movería source.cpp también un ambiguous_syntax carpeta, y crearía automáticamente una traducción inequívoca source.cpp antes de compilarlo.

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

Como puede ver en mi responda 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 (normalmente posterior al análisis) cambia el orden de 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 una ficha para mirar hacia delante para el contexto, mientras que LR (& # 8734;) 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 " typedef " El problema 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). La & Quot; plantilla & Quot; El problema 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 " typedef < !> quot; problema sin ambigüedad en el árbol de análisis o AST. (Divulgación: soy el tipo que creó LRSTAR.)

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top