Qu'est-ce qui rend Java plus facile à analyser que C?

90

Je connais le fait que les grammaires de C et C ++ sont contextuelles , et en particulier il faut un "lexer hack" en C. Par contre, j'ai l'impression qu'on ne peut analyser Java qu'avec 2 jetons d'anticipation, malgré une similitude considérable entre les deux langues.

Que devriez-vous changer à propos de C pour le rendre plus facile à analyser?

Je demande parce que tous les exemples que j'ai vus de la sensibilité au contexte de C sont techniquement acceptables mais terriblement étranges. Par exemple,

foo (a);

pourrait appeler la fonction void fooavec l'argument a. Ou, il pourrait être déclaré aêtre un objet de type foo, mais vous pourriez tout aussi facilement vous débarrasser des paranthèses. En partie, cette bizarrerie se produit parce que la règle de production du "déclarateur direct" pour la grammaire C remplit le double objectif de déclarer à la fois des fonctions et des variables.

D'autre part, la grammaire Java a des règles de production distinctes pour la déclaration de variable et la déclaration de fonction. Si vous écrivez

foo a;

alors vous savez que c'est une déclaration de variable et foopeut être analysée sans ambiguïté comme un nom de type. Ce n'est peut-être pas du code valide si la classe foon'a pas été définie quelque part dans la portée actuelle, mais c'est un travail d'analyse sémantique qui peut être effectué dans une passe ultérieure du compilateur.

J'ai vu que C est difficile à analyser à cause de typedef, mais vous pouvez également déclarer vos propres types en Java. Quelles règles de grammaire C, en plus direct_declarator, sont fautives?

Korrok
la source
7
Question cool. Probablement beaucoup trop large ou principalement d'opinion.
asteri
37
C'est une question valable sur les analyseurs et la seule chose large ou basée sur l'opinion à ce sujet sont les deux dernières phrases (qui devraient probablement être supprimées ou modifiées). Quittez avec les votes serrés.
R .. GitHub STOP HELPING ICE
1
J'ai édité la question en conséquence, merci pour @R .. pour les commentaires.
korrok
3
Pratiquement tous les langages informatiques (standard) sont sensibles au contexte ; vous ne pouvez pas déclarer une variable d'un type et l'utiliser à mauvais escient dans la plupart des langages . C'est différent du fait que «toutes les grammaires de la langue» sont sensibles au contexte; la plupart des gens qui construisent des analyseurs construisent un analyseur sans contexte (ou même plus restrictif), puis utilisent des hacks en dehors de l'analyseur pour vérifier les propriétés sans contexte.
Ira Baxter
1
@IraBaxter Je n'appellerais pas ça des "hacks". Diviser le problème en deux semble une chose raisonnable à faire, car l'analyse des langages sensibles au contexte ne peut pas être effectuée efficacement (et en fait, même l'analyse des langages sans contexte n'est pas efficace, et c'est pourquoi nous nous limitons généralement à des sous-ensembles de langages sans contexte) . Une analyse sans contexte + une analyse statique pour vérifier uniquement les propriétés contextuelles sur l'AST, c'est une chose raisonnable à faire.
Bakuriu

Réponses:

76

L'analyse C ++ devient difficile. L'analyse de Java devient tout aussi difficile.

Voir cette réponse SO expliquant pourquoi C (et C ++) est "difficile" à analyser . Le bref résumé est que les grammaires C et C ++ sont intrinsèquement ambiguës; ils vous donneront plusieurs analyses et vous devez utiliser le contexte pour résoudre les ambiguïtés. Les gens font alors l'erreur de supposer que vous devez résoudre les ambiguïtés pendant que vous analysez; non, voir ci-dessous. Si vous insistez pour résoudre les ambiguïtés au fur et à mesure que vous analysez, votre analyseur devient plus compliqué et beaucoup plus difficile à construire; mais cette complexité est une blessure auto-infligée.

IIRC, la grammaire "évidente" de LALR (1) de Java 1.4 n'était pas ambiguë, donc c'était "facile" à analyser. Je ne suis pas sûr que Java moderne n'ait pas au moins d'ambiguïtés locales à longue distance; il y a toujours le problème de décider si "... >>" ferme deux modèles ou est un "opérateur de décalage à droite". Je soupçonne que Java moderne n'analyse plus avec LALR (1) .

Mais on peut surmonter le problème d'analyse en utilisant des analyseurs puissants (ou des analyseurs faibles et des hacks de collecte de contexte comme le font généralement les frontaux C et C ++), pour les deux langages. C et C ++ ont la complication supplémentaire d'avoir un préprocesseur; ceux-ci sont plus compliqués en pratique qu'ils n'en ont l'air. Une affirmation est que les analyseurs C et C ++ sont si difficiles qu'ils doivent être écrits à la main. Ce n'est pas vrai; vous pouvez construire des analyseurs Java et C ++ très bien avec les générateurs d'analyseurs GLR.

Mais l'analyse n'est pas vraiment là où se situe le problème.

Une fois que vous avez analysé, vous voudrez faire quelque chose avec l'arborescence AST / parse. En pratique, il faut savoir, pour chaque identifiant, quelle est sa définition et où il est utilisé ("résolution de nom et de type", par négligence, construction de tables de symboles). Cela s'avère être BEAUCOUP plus de travail que d'obtenir le bon analyseur, aggravé par l'héritage, les interfaces, la surcharge et les modèles, et le fait que la sémantique de tout cela est écrite dans un langage naturel informel réparti sur des dizaines à des centaines de pages de la norme de langue. C ++ est vraiment mauvais ici. Java 7 et 8 deviennent assez horribles de ce point de vue. (Et les tableaux de symboles ne sont pas tout ce dont vous avez besoin; voir ma bio pour un essai plus long sur "La vie après l'analyse").

La plupart des gens ont du mal avec la partie d'analyse pure (souvent sans fin; vérifiez SO lui-même pour les nombreuses questions sur la façon de créer des analyseurs fonctionnels pour de vrais langages), de sorte qu'ils ne voient jamais la vie après l'analyse. Et puis nous obtenons des théorèmes populaires sur ce qui est difficile à analyser et aucun signal sur ce qui se passe après cette étape.

La correction de la syntaxe C ++ ne vous mènera nulle part.

En ce qui concerne la modification de la syntaxe C ++: vous constaterez que vous devez patcher de nombreux endroits pour prendre en charge la variété des ambiguïtés locales et réelles dans toute grammaire C ++. Si vous insistez, la liste suivante pourrait être un bon point de départ . Je soutiens que cela ne sert à rien de faire cela si vous n'êtes pas le comité des normes C ++; si vous le faisiez et que vous construisiez un compilateur en utilisant cela, personne ne l'utilisera. Il y a trop d'investissements dans les applications C ++ existantes pour changer pour la commodité des gars qui construisent des analyseurs; de plus, leur douleur est terminée et les analyseurs existants fonctionnent très bien.

Vous voudrez peut-être écrire votre propre analyseur. OK, c'est bon; ne vous attendez pas à ce que le reste de la communauté vous laisse changer la langue qu'il doit utiliser pour vous faciliter la tâche. Ils veulent tous que ce soit plus facile pour eux, et c'est d'utiliser le langage tel que documenté et implémenté.

Ira Baxter
la source
Bonne réponse. Voir également D et C +, qui tentent de résoudre certains de ces problèmes. s / content /
contend
3
J'ai déjà lu Life After Parsing et j'ai trouvé que c'était une véritable révélation; cela m'a fait comprendre qu'il y a beaucoup plus de travail en analyse sémantique (résolution de nom / type, ...) qu'en analyse. Je n'essaye pas de changer la syntaxe d'aucune langue. Je ne veux comprendre ce que les propriétés sont d'une langue dans laquelle vous pouvez faire l'analyse syntaxique d' abord, puis l'analyse sémantique. C n'est pas un tel langage (nécessite le hack lexer); J'ai toujours pensé que Java l'était et je veux savoir pourquoi.
korrok
1
@Korrok: lisez ma réponse sur la construction de Java / C ++ avec des analyseurs GLR. Vous n'avez besoin d'aucun hack lexer . Ainsi, la distinction est dans l'esprit des personnes qui utilisent la mauvaise technologie d'analyse. ... Certes, créer un frontal C ++ complet (en particulier C ++ 14, ce que nous avons fait) est plus difficile que de faire Java8, mais ils sont à la fois difficiles (en termes d'effort et d'attention aux détails) et d'analyse est la pièce la plus simple.
Ira Baxter
1
Je suis d'accord sur votre "vie après l'analyse": par exemple, la résolution de surcharge en C # peut encoder n'importe quel problème 3-SAT et est donc NP-difficile.
Jörg W Mittag