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

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

Question

J'étais en train de lire sur les analyseurs syntaxiques et les générateurs d'analyseurs syntaxiques et j'ai trouvé cette déclaration dans l'analyse syntaxique LR de wikipedia -page:

  

De nombreux langages de programmation peuvent être analysés en utilisant une variante d’un analyseur syntaxique LR. C ++ constitue une exception notable.

Pourquoi est-ce le cas? Quelle propriété particulière de C ++ rend impossible l’analyse avec les analyseurs syntaxiques LR?

À l’aide de Google, j’ai seulement constaté que C pouvait parfaitement être analysé avec LR (1), mais que C ++ requiert LR (& # 8734;).

Était-ce utile?

La solution

Il existe un fil conducteur 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 inclut une discussion sur l'analyse syntaxique C ++, qui stipule que:

  

& "; La grammaire C ++ est ambiguë,   dépendant du contexte et potentiellement   nécessite une résolution infinie   certaines ambiguïtés & ";

Il donne ensuite un certain nombre d’exemples (voir page 147 du document PDF).

L'exemple est le suivant: 

int(x), y, *const z;

signification 

int x;
int y;
int *const z;

Comparez à: 

int(x), y, new int;

signification 

(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 beaucoup de jetons avant celui qui est en train de lever l’ambiguïté.

Autres conseils

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

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

x * y ;

Il a deux analyses différentes:

  1. Cela peut être la déclaration de y, en tant que pointeur vers x
  2. Il peut s'agir d'une multiplication de x et y, rejetant 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ù il pourrait avoir un effet secondaire (par exemple, si multiplier est surchargé). mais ce n'est pas le point. Le point est qu'il y a deux analyses différentes, et donc un programme peut signifier différentes choses selon la manière dont cela devrait être analysé.

Le compilateur doit accepter celui qui convient dans les circonstances appropriées. En l’absence de toute autre information (par exemple, la connaissance du type de x) doit collecter les deux afin de décider ultérieurement de la marche à suivre. Ainsi, une grammaire doit permettre cela. Et cela rend la grammaire ambiguë.

Ainsi, l'analyse LR pure 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 syntaxiques de type PEG, ne peuvent pas non plus être utilisés dans un & «Pur &»; manière.

Il y a beaucoup de cas plus compliqués (l'analyse syntaxique des modèles nécessite une anticipation arbitraire, alors que LALR (k) peut regarder en avant vers le plus de k jetons), mais il suffit d'un seul contre-exemple pour éliminer pure Analyse de LR (ou des autres).

La plupart des analyseurs syntaxiques C / C ++ réels gèrent cet exemple en utilisant sorte d'analyseur déterministe avec un hack supplémentaire: ils s'entrelacent avec la table des symboles collection ... pour qu'au moment " x " est rencontré, l'analyseur sait si x est un type ou non, et peut donc choisissez entre les deux parses potentielles. Mais un analyseur cela fait ce n'est pas sans contexte, et analyseurs syntaxiques LR (les purs, etc.) sont (au mieux) sans contexte.

On peut tricher et ajouter des contrôles sémantiques de réduction de temps par règle dans la aux analyseurs syntaxiques de LR pour faire cette homonymie. (Ce code n'est souvent pas simple). La plupart des autres types d'analyseurs avoir des moyens d'ajouter des contrôles sémantiques à différents points dans l'analyse, cela peut être utilisé pour le faire.

Et si vous trichez suffisamment, vous pouvez faire en sorte que les analyseurs syntaxiques LR fonctionnent. C et C ++. Les gars de GCC ont fait pendant un certain temps, mais l'ont donné pour l'analyse syntaxique à la main, je pense parce qu'ils voulaient meilleur diagnostic d'erreur.

Il y a une autre approche, cependant, qui est belle et propre et analyse C et C ++ très bien sans aucune table de symboles hackery: analyseurs GLR . Ce sont des analyseurs complets sans contexte (ayant effectivement une infinité regarder en avant). Les analyseurs GLR acceptent simplement les deux analyses, produire un " arbre " (en fait, un graphe acyclique dirigé qui ressemble principalement à un arbre) cela 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 des logiciels DMS (à partir de juin 2017) ceux-ci gèrent complètement C ++ 17 dans les dialectes MS et GNU). Ils ont été utilisés pour traiter des millions de lignes des 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'analyse la plus frustrante d'AST pour C ++. )

Le problème n'est jamais défini comme ceci, 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 & "non-context-free &"; Analyseur Yacc? (en utilisant seulement un 'hack': la désambiguïsation typename / identifier, l’analyseur informant le lexer de chaque typedef / class / struct)

J'en vois quelques unes:

  1. Type Type; est interdit. Un identifiant déclaré en tant que nom_table ne peut pas devenir un identifiant autre que nom_type (notez que struct Type Type n'est pas ambigu et peut être encore autorisé).

    Il existe 3 types de names tokens:

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

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

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

  3. typedef int func_type(); est complètement interdit, il devrait être écrit typedef int (func_type)();

  4. typedef int (*func_ptr_type)(); et int a,b,c[9],*d,(*f)(), (*g)()[9], h(char); sont interdits.

    Un type de fonction doit être un pointeur de fonction type: int a,b,c[9],*d;

  5. La récursion de modèles est limitée à 1024, sinon un maximum accru pourrait être transmis en option au compilateur.

  6. int (*f)(); pourrait également être interdit, remplacé par int (*g)()[9]; int h(char);

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

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

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

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

    (int (MyClass::*)(char*))

    étant resyntaxé comme:

    typedef int type, *type_ptr;

    cela étant cohérent avec l'opérateur de diffusion typedef int type;

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

    sizeof int

    sizeof char

  8. sizeof long long, int, #type int : signed_integer(4) et co. pourrait être déclaré dans chaque fichier source. Ainsi, chaque fichier source utilisant le type unsigned_integer(4) doit commencer par

    #type

    et source.cpp seraient interdits en dehors de cette ambiguous_syntax directive ce serait un grand pas en avant dans la stupide <=> ambiguïté présente dans tant d'en-têtes C ++

Le compilateur implémentant le C ++ resyntaxé déplacerait <=> aussi un dossier <=> et créerait automatiquement une traduction non ambiguë avant de le compiler s'il rencontrait une source C ++ utilisant une syntaxe ambiguë.

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

Comme vous pouvez le voir dans mon répondre 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 une post-analyse) modifiant l’ordre des opérations , et donc de la forme AST (normalement prévu par une analyse de première étape).

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

LR (1) signifie que l'analyse de gauche à droite ne nécessite qu'un seul jeton pour rechercher le contexte, tandis que LR (& # 8734;) signifie une recherche infinie. C'est-à-dire que l'analyseur devrait savoir tout ce qui se passait pour savoir où il se trouve maintenant.

Le " typedef " problème 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 & Quot; modèle & Quot; problème 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 syntaxique LRSTAR lit la notation grammaticale ci-dessus et génère un analyseur syntaxique qui gère le " typedef < !> quot; problème sans ambiguïté dans l'arbre d'analyse ou AST. (Divulgation: je suis le type qui a créé LRSTAR.)

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top