Les analyseurs GCC et Clang sont-ils vraiment manuscrits?

Il semble que GCC et LLVM-Clang utilisent des analyseurs de descente récursifs manuscrits , et non une analyse ascendante basée sur Bison-Flex, générée par machine.

Quelqu'un ici pourrait-il confirmer que tel est le cas? Et si oui, pourquoi les frameworks de compilateurs traditionnels utilisent-ils des analyseurs manuscrits?

Mise à jour : blog intéressant sur ce sujet ici

Oui:

• GCC a utilisé un parseur yacc (bison) une fois, mais il a été remplacé par un analyseur de descente récursif manuscrit à un moment donné de la série 3.x: voir http://gcc.gnu.org/wiki/New_C_Parser pour des liens vers les soumissions de correctifs pertinents.

• Clang utilise également un analyseur de descente récursif écrit à la main: voir la section "Un seul analyseur unifié pour C, Objective C, C ++ et Objective C ++" vers la fin de http://clang.llvm.org/features.html .

Il existe un théorème populaire qui dit que C est difficile à analyser et C ++ essentiellement impossible.

Ce n'est pas vrai.

Ce qui est vrai, c'est que C et C ++ sont assez difficiles à analyser à l'aide des analyseurs LALR (1) sans pirater la machinerie d'analyse et enchevêtrer les données de la table de symboles. GCC en fait utilisé pour les analyser, en utilisant YACC et d'autres hackers comme celui-ci, et oui, c'était moche. Maintenant, GCC utilise des analyseurs manuscrits, mais toujours avec le piratage de la table des symboles. Les gens de Clang n'ont jamais essayé d'utiliser des générateurs d'analyseurs automatisés; AFAIK l'analyseur de Clang a toujours été une descente récursive codée à la main.

Ce qui est vrai, c'est que C et C ++ sont relativement faciles à analyser avec des analyseurs générés automatiquement plus puissants, par exemple des analyseurs GLR , et vous n'avez pas besoin de hacks. L' analyseur Elsa C ++ en est un exemple. Notre frontal C ++ est un autre (comme le sont tous nos frontaux "compilateurs", GLR est une technologie d'analyse assez merveilleuse).

Notre frontal C ++ n'est pas aussi rapide que celui de GCC, et certainement plus lent qu'Elsa; nous avons mis peu d'énergie à le régler avec soin parce que nous avons d'autres problèmes plus urgents (néanmoins, il a été utilisé sur des millions de lignes de code C ++). Elsa est probablement plus lente que GCC simplement parce qu'elle est plus générale. Compte tenu de la vitesse du processeur de nos jours, ces différences peuvent ne pas avoir beaucoup d'importance dans la pratique.

Mais les «vrais compilateurs» qui sont largement diffusés aujourd'hui ont leurs racines dans des compilateurs d'il y a 10 ou 20 ans ou plus. Les inefficacités importaient alors beaucoup plus, et personne n'avait entendu parler des analyseurs GLR, alors les gens faisaient ce qu'ils savaient faire. Clang est certes plus récent, mais les théorèmes folkloriques conservent leur «force de persuasion» pendant longtemps.

Vous n'avez plus à le faire de cette façon. Vous pouvez très raisonnablement utiliser GLR et d'autres analyseurs de ce type comme frontaux, avec une amélioration de la maintenabilité du compilateur.

Ce qui est vrai, c'est qu'il est difficile d'obtenir une grammaire qui correspond au comportement de votre compilateur de quartier convivial. Alors que pratiquement tous les compilateurs C ++ implémentent (la plupart) du standard d'origine, ils ont également tendance à avoir beaucoup d'extensions de coins sombres, par exemple, les spécifications DLL dans les compilateurs MS, etc. Si vous avez un moteur d'analyse puissant, vous pouvez passer votre temps à essayer d'obtenir la grammaire finale pour correspondre à la réalité, plutôt que d'essayer de plier votre grammaire pour correspondre aux limites de votre générateur d'analyseur.

EDIT Novembre 2012: Depuis l'écriture de cette réponse, nous avons amélioré notre frontal C ++ pour gérer le C ++ 11 complet, y compris les dialectes de variantes ANSI, GNU et MS. Bien qu'il y ait eu beaucoup de choses supplémentaires, nous n'avons pas à changer notre moteur d'analyse; nous venons de réviser les règles de grammaire. Nous ne devons changer l'analyse sémantique; C ++ 11 est sémantiquement très compliqué, et ce travail submerge l'effort pour faire fonctionner l'analyseur.

EDIT Février 2015: ... gère désormais le C ++ 14 complet. (Voir obtenir un AST lisible par l'homme à partir du code c ++ pour des analyses GLR d'un simple bout de code et la tristement célèbre "analyse la plus vexante" de C ++).

EDIT avril 2017: gère maintenant (brouillon) C ++ 17.

L'analyseur de Clang est un analyseur de descendance récursive écrit à la main, tout comme plusieurs autres frontaux C et C ++ open source et commerciaux.

Clang utilise un analyseur de descente récursive pour plusieurs raisons:

• Performances : un analyseur manuscrit nous permet d'écrire un analyseur rapide, en optimisant les chemins d'accès au besoin, et nous contrôlons toujours ces performances. Avoir un analyseur rapide a permis à Clang d'être utilisé dans d'autres outils de développement où les analyseurs "réels" ne sont généralement pas utilisés, par exemple, la coloration syntaxique et la complétion de code dans un IDE.
• Diagnostics et récupération d'erreurs : parce que vous avez le contrôle total avec un analyseur de descente récursive écrit à la main, il est facile d'ajouter des cas spéciaux qui détectent les problèmes courants et fournissent d'excellents diagnostics et récupération d'erreurs (par exemple, voir http: //clang.llvm .org / features.html # expressivediags ) Avec les analyseurs générés automatiquement, vous êtes limité aux capacités du générateur.
• Simplicité : les analyseurs de descendance récursive sont faciles à écrire, à comprendre et à déboguer. Vous n'avez pas besoin d'être un expert en analyse ou d'apprendre un nouvel outil pour étendre / améliorer l'analyseur (ce qui est particulièrement important pour un projet open source), mais vous pouvez toujours obtenir d'excellents résultats.

Dans l'ensemble, pour un compilateur C ++, cela n'a pas beaucoup d'importance: la partie analyse de C ++ n'est pas triviale, mais c'est toujours l'une des parties les plus faciles, il est donc avantageux de rester simple. L'analyse sémantique - en particulier la recherche de nom, l'initialisation, la résolution de surcharge et l'instanciation de modèle - est des ordres de grandeur plus compliqués que l'analyse. Si vous voulez une preuve, allez vérifier la distribution du code et des commits dans le composant "Sema" de Clang (pour l'analyse sémantique) par rapport à son composant "Parse" (pour l'analyse).

L'analyseur de gcc est écrit à la main. . Je soupçonne la même chose pour clang. C'est probablement pour plusieurs raisons:

• Performance : quelque chose que vous avez optimisé manuellement pour votre tâche particulière fonctionnera presque toujours mieux qu'une solution générale. L'abstraction a généralement un impact sur les performances
• Timing : au moins dans le cas de GCC, GCC est antérieur à de nombreux outils de développement gratuits (sortis en 1987). Il n'y avait pas de version gratuite de yacc, etc. à l'époque, ce qui, j'imagine, aurait été une priorité pour les gens de la FSF.

Ce n'est probablement pas un cas de syndrome du "non inventé ici", mais plutôt du genre "il n'y avait rien d'optimisé spécifiquement pour ce dont nous avions besoin, alors nous avons écrit le nôtre".

Des réponses étranges là-bas!

Les grammaires C / C ++ ne sont pas sans contexte. Ils sont sensibles au contexte à cause de la barre Foo *; ambiguïté. Nous devons construire une liste de typedefs pour savoir si Foo est un type ou non.

Ira Baxter: Je ne vois pas l'intérêt de votre truc GLR. Pourquoi construire un arbre d'analyse qui comporte des ambiguïtés. L'analyse signifie résoudre les ambiguïtés, construire l'arbre syntaxique. Vous résolvez ces ambiguïtés dans une seconde passe, donc ce n'est pas moins moche. Pour moi, c'est beaucoup plus moche ...

Yacc est un générateur d'analyseur LR (1) (ou LALR (1)), mais il peut être facilement modifié pour être sensible au contexte. Et il n'y a rien de laid dedans. Yacc / Bison a été créé pour aider à analyser le langage C, donc ce n'est probablement pas l'outil le plus laid pour générer un analyseur C ...

Jusqu'à GCC 3.x, l'analyseur C est généré par yacc / bison, avec une table typedefs construite pendant l'analyse. Avec la construction de table de typedefs "in parse", la grammaire C devient localement sans contexte et de plus "localement LR (1)".

Maintenant, dans Gcc 4.x, c'est un analyseur de descente récursif. C'est exactement le même analyseur que dans Gcc 3.x, c'est toujours LR (1), et a les mêmes règles de grammaire. La différence est que l'analyseur yacc a été réécrit à la main, que les décalages / réductions sont maintenant cachés dans la pile d'appels, et il n'y a pas de "state454: if (nextsym == '(') goto state398" comme dans gcc 3.x yacc's parser, il est donc plus facile de patcher, de gérer les erreurs et d’imprimer des messages plus agréables, et d’effectuer certaines des étapes de compilation suivantes lors de l’analyse.

Pourquoi sont-ils passés du yacc à la descente récursive? Parce qu'il faut bien éviter yacc pour analyser le C ++, et parce que GCC rêve d'être un compilateur multi langage, c'est à dire de partager un maximum de code entre les différents langages qu'il peut compiler. C'est pourquoi l'analyseur C ++ et C sont écrits de la même manière.

C ++ est plus difficile à analyser que C car ce n'est pas "localement" LR (1) comme C, ce n'est même pas LR (k). Regardez func<4 > 2>quelle est une fonction de modèle instanciée avec 4> 2, c'est- func<4 > 2> à- dire qu'elle doit être lue comme func<1>. Ce n'est certainement pas LR (1). Considérons maintenant, func<4 > 2 > 1 > 3 > 3 > 8 > 9 > 8 > 7 > 8>. C'est là qu'une descente récursive peut facilement résoudre l'ambiguïté, au prix de quelques appels de fonction supplémentaires (parse_template_parameter est la fonction d'analyseur ambiguë. Si parse_template_parameter (17tokens) a échoué, réessayez parse_template_parameter (15tokens), parse_template_parameter (13tokens) ... Ça marche).

Je ne sais pas pourquoi il ne serait pas possible d'ajouter des sous-grammaires récursives yacc / bison, peut-être que ce sera la prochaine étape du développement de l'analyseur gcc / GNU?

Il semble que GCC et LLVM-Clang utilisent des analyseurs de descente récursifs manuscrits, et non une analyse ascendante basée sur Bison-Flex, générée par machine.

Bison en particulier, je ne pense pas pouvoir gérer la grammaire sans analyser certaines choses de manière ambiguë et faire une deuxième passe plus tard.

Je sais que Happy de Haskell permet des analyseurs monadiques (c'est-à-dire dépendant de l'état) qui peuvent résoudre le problème particulier avec la syntaxe C, mais je ne connais pas de générateurs d'analyseurs C qui permettent une monade d'état fournie par l'utilisateur.

En théorie, la récupération d'erreur serait un point en faveur d'un analyseur manuscrit, mais mon expérience avec GCC / Clang a été que les messages d'erreur ne sont pas particulièrement bons.

En ce qui concerne la performance, certaines affirmations ne semblent pas fondées. La génération d'une grosse machine à états à l'aide d'un générateur d'analyseur devrait aboutir à quelque chose qui est O(n)et je doute que l'analyse soit le goulot d'étranglement dans de nombreux outils.