Hors de curiosité, je me demandais quels étaient des résultats "théoriques" sur l'analyse C ++.
Soit n la taille de mon projet (dans LOC, par exemple, mais depuis que nous traiterons de Big-o ce n'est pas très important)
Les références seraient grandement appréciées!
3 Réponses :
difficile à dire si C ++ peut être "juste analysé", conformément à la plupart des langues - il ne peut pas être analysé de manière syntaxée sans effectuer une analyse sémantique en même temps.
Ce n'est pas vrai. Voir ma réponse.
dépend de ce que vous entendez par "analysé", mais si votre analyse est censée inclure une instanciation de gabarits, alors non en général:
[Raccourci si vous souhaitez éviter de lire l'exemple - les modèles de calcul fournissent un modèle de calcul suffisamment riche. les instancier est, en général, un problème de style d'arrêt] évidemment, dans ce cas, le compilateur pourrait repérer théoriquement que les numéros de triangle ont une fonction de générateur simple et calculer le Valeur de retour en utilisant cela. Mais sinon, instanciateur [fin du raccourci] maintenant, afin de savoir si Les implémentations réelles chantent arbitrairement la profondeur de l'instanciation de gabarit, faisant une analyse Big-O sans pertinence, mais j'ignore que, étant donné que, dans toutes cas, des implémentations réelles ont des limites de ressources naturelles, ce qui rend également grand -O analyse sans importance ... Je pense que vous pouvez produire des programmes similaires-difficiles en C avec recrutement Mis à part cela, C, en commun avec beaucoup d'autres langues, peut avoir une analyse (pas beaucoup). Vous aurez peut-être besoin de la recherche de symboles et ainsi de suite, que David dit dans sa réponse ne peut généralement avoir un strict o (1) le pire des cas liés, de sorte que O (n) pourrait être un peu optimiste. Même un assembleur peut rechercher des symboles pour les étiquettes. Mais par exemple, des langues dynamiques ne nécessitent pas nécessairement une recherche de symboles pour analyser, car cela pourrait être fait à l'exécution. Si vous choisissez une langue dans laquelle tout l'analyseur doit faire, c'est établir quels symboles sont des mots-clés et faire une sorte de correspondance de support, alors l'algorithme de cour de la courage est O (n), donc il y a de l'espoir. triangle k peut aller assez rapidement avec la taille de ce programme, en ce qui concerne La limite du type int . triangle <127> :: valeur est un objet ou un type, le compilateur en vigueur doit instancier triangle <127> (à nouveau, dans ce cas, il pourrait s'agir d'un raccourci car valeur est défini comme un objet dans chaque spécialisation de gabarit, mais pas en général). Si un symbole représente un objet ou un type est pertinent pour la grammaire de C ++, donc je dirais probablement que "analysant" C ++ fait nécessite une instanciation de modèle. D'autres définitions peuvent varier, cependant. #include , bien que je ne sois pas sûr si vous avez l'intention d'inclure le préprocesseur Dans le cadre de l'étape d'analyse.
Je pense que le terme "analyse" est interprété par différentes personnes de différentes manières aux fins de la question.
Dans un sens technique étroit, l'analyse est simplement vérifiant que le code source correspond à la grammaire (ou peut-être même de la construction d'un arbre).
Il y a un théorème folklorique plutôt répandu qui dit que vous ne pouvez pas analyser C ++ (en ce sens), car vous devez résoudre le sens de certains symboles à analyser. Ce théorème folklorique est tout simplement faux.
Il découle de l'utilisation des analyseurs "Faible" (Lalr ou de descendance récursive de l'arrière-marche), qui, s'ils s'engagent dans le mauvais choix de plusieurs sous-varers possibles d'une partie de texte ambiguë localement (ce SO thread aborde un exemple ), échoue complètement en vertu de la vertu de faire ce choix. La façon dont ceux qui utilisent un tel analyseur résolvent le dilemme sont de collecter des données de la table des symboles, car l'analyse se produit et écrase une vérification supplémentaire dans le processus d'analyse pour forcer l'analyseur à faire le bon choix lorsqu'il est rencontré. Cela fonctionne au coût de nom et de résolution de type d'tangage de manière significative avec l'analyse, ce qui rend la création de tels analyseurs vraiment difficiles. Mais au moins pour legacy GCC, ils ont utilisé Lalr, qui est un temps linéaire à l'analyse et je ne pense pas que beaucoup plus cher si vous incluez le nom / type capture que l'analyseur le fait (il y a plus à faire après l'analyse parce que je ne fais pas t penser qu'ils font tout cela).
Il y a au moins deux implémentations d'analyseurs C ++ effectués à l'aide de "pur" PARSING GLR Technologie , qui admet simplement que l'analyse peut être ambiguë localement et capture les multiples analyses sans commentaire ni des frais généraux importants. Les analyseurs de GLR sont du temps linéaire où il n'y a pas d'ambiguïté locale. Ils sont plus chers dans la région de l'ambiguïté, mais comme une question pratique, la plupart du texte source dans un programme standard C ++ entrent dans la partie "Durée linéaire". Donc, le taux effectif est linéaire, même capturer les ambiguïtés. Les deux analyseurs mis en œuvre font le nom et la résolution de type après analyses et utilisent des incohérences pour éliminer les analyses ambiguës incorrects.
(Les deux implémentations sont Elsa et Notre extrémité frontale (SD) C ++ . Je ne peux pas parler de la capacité actuelle d'Elsa (je ne pense pas qu'il ait été mis à jour dans années), mais la nôtre fait tout de C ++ 11 [Modifier Jan 2015: maintenant Full C ++ 14 Edit oct 2017: Maintenant Full C ++ 17] comprenant GCC et des variantes Microsoft).
Si vous prenez la définition de la science informatique dure qu'une langue est définie de manière prolongée en tant qu'ensemble arbitraire de chaînes (grammaires sont censés être des moyens succincts d'encoder cette intensité) et de traiter l'analyse comme «Vérifiez que la syntaxe du programme est correcte «Ensuite, pour C ++, vous avez élargi les modèles pour vérifier que chacun se développe complètement. Il existe une machine de dissimulation de la machine dans les modèles, donc en théorie vérifiant qu'un programme C ++ est valide est impossible (pas de délai). Les compilateurs réels (honorant la norme) Placez des contraintes fixes sur la quantité de modèle qu'ils vont faire, de même que la mémoire réelle, donc en pratique les compilateurs C ++ terminés. Mais ils peuvent prendre arbitrairement long pour "analyser" un programme en ce sens. Et je pense que c'est la réponse la plupart des gens se soucient de.
Dans la pratique, je suppose que la plupart des modèles sont en fait assez simples, de sorte que les compilateurs C ++ peuvent se terminer aussi vite que les autres compilateurs en moyenne. Seules les personnes assez folles pour écrire des machines de Turing dans les modèles paient un prix grave. (Opinion: Le prix est vraiment le coût conceptuel des choses compliquées sur les modèles, et non le coût d'exécution du compilateur.)
C'est exactement ce que je voulais savoir. Merci.
bool b = (A :: c ==
@BCS: GLR reprend les deux interprétrations lors de l'analyse. Lequel à garder est résolu après l'analyse. Je suis d'accord, vous avez besoin d'informations taisées pour décider. Cette information sémantique est plus facile à collecter sur l'arbre d'analyse complet, même avec les ambiguïtés.
Amusant. À ce moment-là, vous pouvez discuter lorsque vous avez fini d'analyser: avant ou après l'étape de résolution. Cette résolution est presque sûre d'être NP (SAT?).
Re C ++ 1x: définitivement. Certaines des caractéristiques de la bibliothèque utilisent une forte utilisation de la programmation méta-méta, qui est bien connue pour provoquer de longues périodes de compilation.
Je pense qu'il y a des analyseurs O (N) (N) (ou presque O (N), de toute façon) pour C, mais certainement pas pour C ++. Je ne pense pas que la vitesse d'analyse C ++ puisse être approximée de la notation / gig-o, sauf peut-être o (n ^ frandes ()), où 'frand' est un point flottant de valeur aléatoire imprégnée.
@SBI: Je ne sais pas qu'il est "défini". Les compilateurs ne sont nécessaires que pour soutenir le modèle de modèle / ConstExpr jusqu'à une certaine valeur définie par la mise en œuvre, ce qui signifie que peu importe le modèle que vous invoquez, il ne peut qu'ajouter au plus grand nombre d'expressions et de déclarations délimitées.
O (n + 1000) n'est toujours queO (n) .@Damon: lisez à nouveau. J'ai écrit "re C ++ 1x: définitivement." C'était à partir de novembre 2010, donc C ++ 1x fait référence à ce qui est devenu C ++ 11, qui introduisait des fonctions Lambda,
>> pour la fermeture des templates imbriquées des listes d'arguments et d'autres choses qui ont définitivement fabriqué C ++ encore plus fort. analyser.