Pourquoi ne ' t C++ analysé avec un analyseur LR(1) ?

Question

Je lisais les analyseurs et générateurs d’analyseur et trouvé cet énoncé dans wikipedia de LR l’analyse - page :

Plusieurs langages de programmation peuvent être analysées à l’aide de certaines variations d’un analyseur LR. Une exception notable est le C++.

Pourquoi est-il ainsi ? Quelle propriété particulière de C++ les causes qu’il est impossible d’analyser avec les analyseurs LR ?

À l’aide de google, je n’ai trouvé que C puisse être parfaitement analysé avec LR(1) mais le code C++ nécessite LR(∞).

Answer 1

Les analyseurs LR ne peut pas gérer ambigu des règles de grammaire, de par leur conception. (En fait de la théorie de la plus facile de retour dans les années 1970, quand les idées sont en cours d'élaboration).

Le C et le C++ permet la déclaration suivante:

x * y ;

Il dispose de deux différents analyse:

1. Il peut être la déclaration de y, comme pointeur de type x
2. Il peut être une multiplication de x et y, de jeter la réponse.

Maintenant, vous pourriez penser que le dernier est stupide et doit être ignorée. La plupart seraient d'accord avec vous; cependant, il y a des cas où il pourrait d'effet secondaire (par exemple, si multipliez est surchargé). mais ce n'est pas le point. Le point est, il sont deux différentes traite, et, par conséquent, un programme de peut signifier différentes choses en fonction de la façon dont cela devrait ont été analysés.

Le compilateur doit accepter le plus approprié dans les circonstances appropriées, et en l'absence de toute autre information (par exemple, la connaissance du type de x) doit recueillir à la fois, afin de décider par la suite quoi faire. Ainsi, une grammaire doit permettre cela. Et qui fait de la grammaire ambiguë.

Donc un pur LR analyse ne peut pas gérer cela. Ni beaucoup d'autres largement disponibles analyseur de générateurs, comme Antlr, JavaCC, YACC, traditionnels ou de Bison, ou même PEG-style analyseurs utilisés dans une "pure".

Il y a beaucoup de cas les plus complexes (analyse de la syntaxe du modèle nécessite arbitraire d'anticipation, alors que LALR(k) permettent d'envisager au plus k jetons), mais seulement il ne prend contre-exemple à abattre pur LR (ou les autres) de l'analyse.

De plus réel C/C++ analyseurs de gérer cet exemple par l'utilisation de certaines type d'analyseur déterministe avec un supplément de hack: ils se mêlent l'analyse avec la table des symboles une collection... de sorte que par le temps "x" est rencontré, l'analyseur sait si x est un type ou pas, et peut donc choisir entre les deux possibilités d'analyse. Mais un analyseur que ne ce n'est pas sans contexte, et les analyseurs LR (le pur, etc.) sont (au mieux) sans contexte.

On peut tricher et ajouter des contrôles dans la proposition de réduction de pour les analyseurs LR pour ce faire, la désambiguïsation. La plupart des autres types d'analyseur avoir des moyens pour ajouter de la sémantique des contrôles divers points dans l'analyse, qui peut être utilisé pour ce faire.

Et si vous trichez, vous pouvez faire des analyseurs LR travail pour Le C et le C++. La GCC gars ont fait pendant un certain temps, mais il l'a donné pour codée à la main de l'analyse, je pense que parce qu'ils voulaient mieux erreur de diagnostic.

Il y a une autre approche, cependant, ce qui est agréable et propre et l'analyse de C et de C++, il suffit d'amende, sans la table des symboles hackery: GLR analyseurs. Ce sont sans contexte les analyseurs (ayant réellement infini d'anticipation). GLR des analyseurs de simplement accepter à la foisanalyse, la production d'un "arbre" (en fait un graphe dirigé acyclique qui est principalement arborescente) que représente l'ambiguïté de l'analyser. Une post-analyse passe peut résoudre les ambiguïtés.

Nous utilisons cette technique dans le C et le C++ avant se termine pour notre DMS de la Réingénierie du Logiciel boîte à outils. Ils ont été utilisés pour traiter des millions de lignes de grand C et C++ de systèmes, complète, précise, analyse la production de ASTs avec tous les détails du code source.

Answer 2

Il y a un fil intéressant sur Lambda Ultime qui traite de la grammaire LALR pour le C++.

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

"C++ grammaire est ambiguë, en fonction du contexte et potentiellement nécessite infini d'anticipation pour résoudre certaines ambiguïtés".

Il se poursuit par un certain nombre d'exemples (voir page 147 du pdf).

Answer 3

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

quel est le plus petit ensemble de modifications à C++ grammaire qui serait nécessaire pour faire de cette nouvelle grammaire, peuvent parfaitement être analysé par un "non-libre de tout contexte" yacc analyseur ? (utiliser uniquement d'un "hack": le nom/identificateur de désambiguïsation, l'analyseur d'informer l'analyseur lexical de chaque typedef/class/struct)

Je vois quelques unes:

1. Type Type; est fordidden. Un identificateur déclaré comme un typename ne peut pas devenir un non-typename (identificateur de noter que strut Type Type n'est pas ambigu et pourrait être encore autorisés).

   Il existe 3 types de names tokens :

   • types : builtin-type, ou d'un typedef/class/struct
   • modèle-fonctions
   • identifiants : fonctions/méthodes et des variables/objets

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

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

3. int (k); est complètement interdit, doivent être écrits en int k;

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

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

5. modèle de la récursivité est limité à 1024, sinon une augmentation maximale peut être adopté comme une option pour le compilateur.

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

   int (*g)()[9];

   int h(char);

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

   Un très préféré une autre solution serait de changer le terrible pointeur de fonction de la syntaxe,

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

   beeing resyntaxed:

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

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

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

   typedef int type;

   typedef int *type_ptr;

8. sizeof int, sizeof char, sizeof long long et co. pourrait être déclarée dans chaque fichier source. Ainsi, chaque fichier source, faisant usage de la type int devrait commencer avec

   #type int : signed_integer(4)

   et unsigned_integer(4) serait interdit en dehors de l' #typedirective ce serait un grand pas dans la stupide sizeof int ambiguïté présente dans de nombreux C++ en-têtes

Le compilateur de la mise en œuvre de la resyntaxed C++, si la rencontre d'un source C++ en faisant usage de l'ambigu, de la syntaxe, de déplacer source.cpp une ambiguous_syntax le dossier, et créer automatiquement un unamiguous traduit source.cpp avant de le compiler.

S'il vous plaît ajouter votre ambigu C++ syntaxes si vous connaissez déjà un peu !

Answer 4

Comme vous pouvez le voir dans ma réponse ici, C++ contient une syntaxe qui ne peut pas être analysée de façon déterministe par un analyseur LL ou LR en raison de la phase de résolution de type (généralement après l’analyse), changer l' ordre des opérationset donc la forme fondamentale de l’AST (en général devraient être fournis par une analyse du premier étage).

Answer 5

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

LR(1) signifie que l’analyse de gauche à droite besoins qu’un seul jeton à regarder en avant pour le contexte, tandis que LR(∞) désigne une infinie à venir. Autrement dit, l’analyseur devra connaître tout ce qui allait arriver afin de comprendre où il est maintenant.