Pourquoi le C ++ ne peut-il pas être analysé avec un analyseur LR (1)?

153

Je lisais sur les analyseurs et les générateurs d'analyseurs et j'ai trouvé cette déclaration dans l'analyse LR de wikipedia -page:

De nombreux langages de programmation peuvent être analysés en utilisant une variante d'un analyseur LR. Une exception notable est le C ++.

Pourquoi en est-il ainsi? Quelle propriété particulière de C ++ rend impossible l'analyse avec les analyseurs LR?

En utilisant google, j'ai seulement trouvé que C peut être parfaitement analysé avec LR (1) mais C ++ nécessite LR (∞).

Gai
la source
7
Tout comme: vous devez comprendre la récursivité pour apprendre la récursivité ;-).
Toon Krijthe
5
"Vous comprendrez les analyseurs une fois que vous aurez analysé cette phrase."
ilya n.

Réponses:

92

Il existe un fil de discussion intéressant sur Lambda the Ultimate qui traite de la grammaire LALR pour C ++ .

Il comprend un lien vers une thèse de doctorat qui comprend une discussion sur l'analyse C ++, qui stipule que:

"La grammaire C ++ est ambiguë, dépendante du contexte et nécessite potentiellement une recherche infinie pour résoudre certaines ambiguïtés".

Il continue en donnant un certain nombre d'exemples (voir page 147 du pdf).

L'exemple est:

int(x), y, *const z;

sens

int x;
int y;
int *const z;

Comparer aux:

int(x), y, new int;

sens

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

(une expression séparée par des virgules).

Les deux séquences de jetons ont la même sous-séquence initiale mais des arbres d'analyse différents, qui dépendent du dernier élément. Il peut y avoir arbitrairement de nombreux jetons avant celui qui désambiguise.

Rob Walker
la source
29
Ce serait cool d'avoir un résumé de la page 147 sur cette page. Je vais cependant lire cette page. (+1)
Joyeux
11
L'exemple est: int (x), y, * const z; // signification: int x; int y; int * const z; (une séquence de déclarations) int (x), y, new int; // signifiant: (int (x)), (y), (new int)); (une expression séparée par des virgules) Les deux séquences de jetons ont la même sous-séquence initiale mais des arbres d'analyse différents, qui dépendent du dernier élément. Il peut y avoir arbitrairement de nombreux jetons avant celui qui désambiguise.
Blaisorblade
6
Eh bien, dans ce contexte, ∞ signifie «arbitrairement plusieurs» parce que l'anticipation sera toujours limitée par la longueur d'entrée.
MauganRa
1
Je suis assez déconcerté par la citation extraite d'une thèse de doctorat. S'il y a une ambiguïté, alors, par définition, AUCUNE anticipation ne peut jamais "résoudre" l'ambiguïté (c'est-à-dire décider quelle analyse est la bonne, car au moins 2 analyses sont considérées comme correctes par la grammaire). De plus, la citation mentionne l'ambiguïté de C mais l'explication ne montre pas d'ambiguïté, mais seulement un exemple non ambigu où la décision d'analyse ne peut être prise qu'après une longue anticipation arbitraire.
dodecaplex
231

Les analyseurs LR ne peuvent pas gérer les règles de grammaire ambiguës, de par leur conception. (Rendu la théorie plus facile dans les années 1970, lorsque les idées étaient en cours d'élaboration).

C et C ++ autorisent tous les deux l'instruction suivante:

x * y ;

Il a deux analyses différentes:

  1. Cela peut être la déclaration de y, comme pointeur vers le type x
  2. Cela peut être une multiplication de x et y, jetant la réponse.

Maintenant, vous pourriez penser que ce dernier est stupide et devrait être ignoré. La plupart seraient d'accord avec vous; cependant, il y a des cas où cela peut avoir un effet secondaire (par exemple, si la multiplication est surchargée). mais ce n'est pas le but. Le fait est qu'il y a deux analyses différentes, et donc un programme peut signifier des choses différentes selon la façon dont cela aurait dû être analysé.

Le compilateur doit accepter celle qui convient dans les circonstances appropriées, et en l'absence de toute autre information (par exemple, la connaissance du type de x) doit collecter les deux afin de décider plus tard quoi faire. Une grammaire doit donc le permettre. Et cela rend la grammaire ambiguë.

Ainsi, l'analyse pure LR ne peut pas gérer cela. De nombreux autres générateurs d'analyseurs largement disponibles, tels que Antlr, JavaCC, YACC, ou Bison traditionnel, ou même des analyseurs de type PEG, ne peuvent pas non plus être utilisés de manière «pure».

Il y a beaucoup de cas plus compliqués (la syntaxe du modèle d'analyse nécessite une anticipation arbitraire, alors que LALR (k) peut anticiper la plupart des k jetons), mais il suffit d'un seul contre-exemple pour abattre l'analyse LR pure (ou les autres).

La plupart des vrais analyseurs C / C ++ gèrent cet exemple en utilisant une sorte d'analyseur déterministe avec un hack supplémentaire: ils entrelacent l'analyse avec la collection de tables de symboles ... de sorte qu'au moment où "x" est rencontré, l'analyseur sait si x est un type ou pas, et peut ainsi choisir entre les deux analyses potentielles. Mais un analyseur qui fait cela n'est pas sans contexte, et les analyseurs LR (les purs, etc.) sont (au mieux) sans contexte.

On peut tricher et ajouter des vérifications sémantiques par règle de réduction du temps dans les analyseurs de LR pour faire cette désambiguïsation. (Ce code n'est souvent pas simple). La plupart des autres types d'analyseurs ont des moyens pour ajouter des vérifications sémantiques à divers points de l'analyse, qui peuvent être utilisés pour ce faire.

Et si vous trichez suffisamment, vous pouvez faire fonctionner les analyseurs LR pour C et C ++. Les gars de GCC l'ont fait pendant un certain temps, mais l'ont abandonné pour une analyse codée à la main, je pense parce qu'ils voulaient de meilleurs diagnostics d'erreur.

Il existe une autre approche, cependant, qui est agréable et propre et analyse parfaitement C et C ++ sans aucun piratage de table de symboles: les analyseurs GLR . Ce sont des analyseurs sans contexte complets (ayant effectivement une anticipation infinie). Les analyseurs GLR acceptent simplement les deux analyses, produisant un "arbre" (en fait un graphe acyclique dirigé qui ressemble principalement à un arbre) qui représente l'analyse ambiguë. Une passe post-analyse peut résoudre les ambiguïtés.

Nous utilisons cette technique dans les frontaux C et C ++ pour notre Tookit de réingénierie logicielle DMS (à partir de juin 2017, ils gèrent le C ++ 17 complet dans les dialectes MS et GNU). Ils ont été utilisés pour traiter des millions de lignes de grands systèmes C et C ++, avec des analyses complètes et précises produisant des AST avec des détails complets sur le code source. (Voir l'AST pour l'analyse la plus épineuse de C ++. )

Ira Baxter
la source
11
Bien que l'exemple «x * y» soit intéressant, la même chose peut se produire en C («y» peut être un typedef ou une variable). Mais C peut être analysé par un analyseur LR (1), alors quelle est la différence avec C ++?
Martin Cote
12
Mon répondeur avait déjà remarqué que C avait le même problème, je pense que vous l'avez manqué. Non, il ne peut pas être analysé par LR (1), pour la même raison. Euh, que voulez-vous dire «y» peut être un typedef? Peut-être vouliez-vous dire «x»? Cela ne change rien.
Ira Baxter
6
Parse 2 n'est pas nécessairement stupide en C ++, car * pourrait être remplacé pour avoir des effets secondaires.
Dour High Arch
8
J'ai regardé x * yet j'ai ri - c'est incroyable de voir à quel point on pense à de petites ambiguïtés astucieuses comme celle-ci.
nouveau123456
51
@altie Personne ne surchargerait sûrement un opérateur de décalage de bits pour lui faire écrire la plupart des types de variables dans un flux, non?
Troy Daniels
16

Le problème n'est jamais défini comme ça, alors qu'il devrait être intéressant:

quel est le plus petit ensemble de modifications de la grammaire C ++ qui serait nécessaire pour que cette nouvelle grammaire puisse être parfaitement analysée par un analyseur yacc "non-context-free"? (n'utilisant qu'un seul 'hack': l'homonymie du nom de type / identifiant, l'analyseur informant le lexer de chaque typedef / class / struct)

J'en vois quelques-uns:

  1. Type Type;est interdit. Un identifiant déclaré en tant que nom de type ne peut pas devenir un identifiant sans nom de type (note qui struct Type Typen'est pas ambiguë et pourrait être encore autorisée).

    Il existe 3 types de names tokens:

    • types : type intégré ou à cause d'un typedef / class / struct
    • fonctions-modèles
    • identificateurs: fonctions / méthodes et variables / objets

    Considérer les fonctions de modèle comme des jetons différents résout l' func<ambiguïté. Si funcest un nom de fonction de modèle, alors <doit être le début d'une liste de paramètres de modèle, sinon funcest un pointeur de fonction et <est l'opérateur de comparaison.

  2. Type a(2);est une instanciation d'objet. Type a();et Type a(int)sont des prototypes de fonction.

  3. int (k); est totalement interdit, doit être écrit int k;

  4. typedef int func_type(); et typedef int (func_type)();sont interdits.

    Une fonction typedef doit être un pointeur de fonction typedef: typedef int (*func_ptr_type)();

  5. la récursivité du template est limitée à 1024, sinon un maximum augmenté pourrait être passé en option au compilateur.

  6. int a,b,c[9],*d,(*f)(), (*g)()[9], h(char); pourrait être interdit aussi, remplacé par int a,b,c[9],*d; int (*f)();

    int (*g)()[9];

    int h(char);

    une ligne par prototype de fonction ou déclaration de pointeur de fonction.

    Une alternative hautement préférée serait de changer la terrible syntaxe du pointeur de fonction,

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

    en cours de resyntaxe comme:

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

    ceci étant cohérent avec l'opérateur de distribution (int (MyClass::*)(char*))

  7. typedef int type, *type_ptr; pourrait être interdit aussi: une ligne par typedef. Ainsi il deviendrait

    typedef int type;

    typedef int *type_ptr;

  8. sizeof int, sizeof char, sizeof long longEt co. pourrait être déclaré dans chaque fichier source. Ainsi, chaque fichier source utilisant le type intdoit commencer par

    #type int : signed_integer(4)

    et unsigned_integer(4)serait interdit en dehors de cette #type directive ce serait un grand pas dans l' sizeof intambiguïté stupide présente dans tant d'en-têtes C ++

Le compilateur implémentant le C ++ resyntaxé, s'il rencontrait une source C ++ utilisant une syntaxe ambiguë, déplacerait source.cppégalement un ambiguous_syntaxdossier et créerait automatiquement un fichier traduit sans ambiguïté source.cppavant de le compiler.

Veuillez ajouter vos syntaxes C ++ ambiguës si vous en connaissez!

reuns
la source
3
C ++ est trop bien ancré. Personne ne le fera dans la pratique. Ces gens (comme nous) qui construisent des frontaux mordent simplement la balle et font l'ingénierie pour que les analyseurs fonctionnent. Et, tant que des modèles existent dans le langage, vous n'obtiendrez pas un pur analyseur sans contexte.
Ira Baxter
9

Comme vous pouvez le voir dans ma réponse ici , C ++ contient une syntaxe qui ne peut pas être analysée de manière déterministe par un analyseur LL ou LR en raison de l'étape de résolution de type (généralement après l'analyse) modifiant l' ordre des opérations , et donc la forme fondamentale de l'AST ( généralement censé être fourni par une analyse de première étape).

Sam Harwell
la source
3
La technologie d'analyse qui gère l'ambiguïté produit simplement les deux variantes AST lors de l'analyse et élimine simplement la variante incorrecte en fonction des informations de type.
Ira Baxter le
@Ira: Oui, c'est exact. L'avantage particulier de cela est qu'il vous permet de conserver la séparation de l'analyse de première étape. Bien que cela soit le plus connu dans l'analyseur GLR, il n'y a aucune raison particulière pour laquelle je vois que vous ne pouvez pas frapper C ++ avec un "GLL?" parser également.
Sam Harwell le
"GLL"? Eh bien, bien sûr, mais vous devrez aller comprendre la théorie et rédiger un article pour le reste. Plus probablement, vous pouvez utiliser un analyseur codé à la main de haut en bas, ou un analyseur LALR () de retour arrière (mais garder les analyses «rejetées»), ou exécuter un analyseur Earley. GLR a l'avantage d'être une sacrément bonne solution, est bien documentée et désormais bien prouvée. Une technologie GLL devrait avoir des avantages assez importants pour afficher GLR.
Ira Baxter
Le projet Rascal (Pays-Bas) prétend construire un analyseur GLL sans scanner. Travail en cours, il peut être difficile de trouver des informations en ligne. en.wikipedia.org/wiki/RascalMPL
Ira Baxter
@IraBaxter Il semble y avoir de nouveaux développements sur GLL: voir cet article de 2010 sur GLL dotat.at/tmp/gll.pdf
Sjoerd
6

Je pense que vous êtes assez proche de la réponse.

LR (1) signifie que l'analyse de gauche à droite n'a besoin que d'un seul jeton pour anticiper le contexte, alors que LR (∞) signifie une anticipation infinie. Autrement dit, l'analyseur devrait savoir tout ce qui allait arriver pour savoir où il se trouve maintenant.

casademora
la source
4
Je rappelle de ma classe de compilateurs que LR (n) pour n> 0 est mathématiquement réductible à LR (1). N'est-ce pas vrai pour n = infini?
rmeador
14
Non, il y a une montagne infranchissable d'une différence entre n et infini.
éphémère
4
La réponse n'est-elle pas: oui, pour un temps infini? :)
Steve Fallows
7
En fait, d'après mon vague souvenir de la façon dont LR (n) -> LR (1) se déroule, cela implique la création de nouveaux états intermédiaires, donc le runtime est une fonction non constante de «n». Traduire LR (inf) -> LR (1) prendrait un temps infini.
Aaron
5
"N'est-ce pas la réponse: oui, pour un temps infini?" - Non: l'expression «étant donné un laps de temps infini» n'est qu'une manière abrégée et absurde de dire «ne peut être fait dans un laps de temps limité». Quand vous voyez "infini", pensez: "pas n'importe quel fini".
ChrisW
4

Le problème "typedef" en C ++ peut être analysé avec un analyseur LALR (1) qui construit une table de symboles lors de l'analyse (pas un analyseur LALR pur). Le problème du «modèle» ne peut probablement pas être résolu avec cette méthode. L'avantage de ce type d'analyseur LALR (1) est que la grammaire (illustrée ci-dessous) est une grammaire LALR (1) (sans ambiguïté).

/* 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. */

L'entrée suivante peut être analysée sans problème:

 typedef int x;
 x * y;

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

Le générateur d'analyseur LRSTAR lit la notation grammaticale ci-dessus et génère un analyseur qui gère le problème "typedef" sans ambiguïté dans l'arborescence d'analyse ou AST. (Divulgation: je suis le gars qui a créé LRSTAR.)


la source
C'est le hack standard utilisé par GCC avec son ancien analyseur LR pour gérer l'ambiguïté de choses comme "x * y;" Hélas, il y a toujours l'exigence de recherche arbitrairement grande pour analyser d'autres constructions, donc LR (k) ne peut pas être une solution pour tout k fixe. (GCC est passé à la descente récursive avec plus de publicité).
Ira Baxter le