Question Choix du générateur d'analyseur [fermé]


OK, je comprends que cette question peut sembler très fondée sur des opinions, mais comme j’ai plusieurs critères de choix, je pense que cela conviendrait bien à SO. Alors je suis là ...

J'ai beaucoup travaillé avec le compilateur / interprète dans le passé (surtout comme passe-temps évidemment) et pour une raison quelconque, je suis resté avec Lex / Yacc (ou Flex / Bison, je suis assez confus sur la façon dont ils les appellent maintenant ... lol).

Cependant, comme je me trouve actuellement en train de jouer avec un autre projet d'interprète amateur, j'ai pensé que je devrais essayer quelque chose de différent peut-être pour éviter ce que je n'aime pas chez Lex / Yacc.

Donc, à savoir:

  • Meilleur C ++ - convivial (que C-friendly)
  • Bonne documentation (de préférence avec certaines grammaires existantes déjà implémentées + des instructions sur la façon de les compiler / utiliser - cela semble assez évident, hein?)
  • Pourrait être LALR, LL (*), descente récursive, je m'en fous (Remarque: une entrée sur le type que vous préférez et pour quel type d’implémentations serait génial; Je n'ai jamais vraiment compris leurs avantages et leurs inconvénients, pour être parfaitement honnête, même si je sais à quoi ils se réfèrent)
  • Combinaison de la partie Lexer et de la grammaire de l'analyseur dans un fichier ne serait pas mauvais du tout; jamais vraiment compris pourquoi il doit être divisé en deux.
  • Last but not least: j'ai toujours eu des problèmes avec ... les problèmes. Je veux dire - au moins dans la mesure où Lex / Yacc va, l'analyse des messages d'erreur est plus ou moins cryptique (Syntax Error... Yuhuu!) Et ils aident rarement à diagnostiquer un problème. (Eh bien, sauf si vous êtes celui qui a développé l'interprète ... lol). Alors, y a-t-il quelque chose de mieux que Lex / Yacc en ce qui concerne rapport d'erreur?

OK, j'espère que ce n'était pas trop verbeux. Je suis tout ouïe! :-)


11
2018-03-01 00:40


origine


Réponses:


Je vais juste répondre à la dernière question, avec une légère modification:

au moins pour ce qui est de Lex / Yacc, les messages d'erreur d'analyse sont plus ou moins cryptiques (erreur de syntaxe ... Yuhuu!) et aident rarement à diagnostiquer un problème. (Eh bien, sauf si vous êtes celui qui a développé l'interprète ... lol). Donc, est-ce qu'il y a rien de mieux que  une meilleure façon d'utiliser Lex / Yacc concernant les rapports d'erreurs?

Eh bien, commencez par utiliser une version moderne du bison, qui a un Manuel en ligne (et très probablement installé avec l'exécutable, selon la façon dont vous installez bison). En particulier, commencez par ces déclarations:

%define parse.error verbose
%define parse.lac full

Cela remplacera au moins l'erreur mystérieuse d'erreur de syntaxe par une liste de types de jetons "attendus".

Ensuite, assurez-vous que vos types de jetons ont des noms significatifs, car ils seront présentés à l'utilisateur dans le cadre du message d'erreur. Si vous avez l'habitude d'utiliser IDENTIFIER en tant que terminal, alors vous êtes probablement ok, mais le message "TOK_YY_ID attendu" est un peu geek. Vous pouvez déclarer une lisible pour un terminal dans le type déclaration:

%type TOK_YY_ID "identifier"

Cela ne vous mènera que si loin. Dans de nombreux cas, savoir ce qui est "attendu" est suffisant pour comprendre une erreur de syntaxe, mais parfois il est utile d'être plus explicite. Dans de tels cas, il est utile de définir réellement errorrègles. Obtenir ces droits est plus un art qu'une science, mais cela vaut pour toutes les approches en matière de signalement des erreurs et de récupération. L'essentiel est d'essayer d'être aussi précis que possible à propos de la syntaxe erronée et non plus spécifique que nécessaire.

Une approche intéressante du signalement d'erreurs consiste à utiliser l'état actuel du parseur et le jeton d'analyse (tous deux visibles au moment du signalement des erreurs) pour rechercher un message d'erreur personnalisé, s'il en existe un. Je pense que cette approche fait partie du folklore du compilateur depuis longtemps, et je suis sûr que j'ai vu plusieurs articles à ce sujet au cours des décennies. Voici un article relativement récent de Russ Cox.


7
2018-03-01 19:28



Je construis des générateurs et des analyseurs syntaxiques depuis 1969.

La descente récursive, YACC et JavaCC sont les réponses typiques que vous entendez.

Ce sont les générateurs d'analyseurs de votre grand-père qui souffrent de limitations dans les grammaires qu'ils accepteront. Invariablement (en particulier sur Stack Overflow), une pauvre âme demande "comment résoudre ce problème / réduire" (pour les générateurs d’analyseurs LR tels que YACC) ou "comment éliminer la récursivité gauche" JavaCC). Pire, ils ne peuvent pas gérer les grammaires qui ont vraiment une ambiguïté syntaxique, comme cela se produit dans la plupart des langages complexes.

GLR Les analyseurs (et GLL) vous permettent d'écrire des grammaires sans contexte ... et de les analyser sans problème. C'est un réal amélioration de la productivité. Il y a un prix: vous pouvez vous retrouver avec des analyses ambiguës, mais il y a des façons de gérer cela. (regarde ça discussion des problèmes d'analyse C ++ que ni YACC ni JavaCC ne peuvent gérer eux-mêmes).

Bison (largement disponible) a un Option GLR; utilise le! Les outils de manipulation de programmes multilingues récents semblent tous utiliser GLL ou GLR. Notre outil de réingénierie logicielle DMS utilise GLR et analyse C ++ (C ++ 14 complet dans les variantes MS et GNU!), Java, COBOL et de nombreux autres langages complexes. GLR a été l'un des meilleurs choix techniques que j'ai faits dans ma carrière. Stratego utilise GLR. Je pense que RascalMPL utilise GLL. Le générateur d’analyseurs Elkhound GLR de Scott McPeak est basé sur C ++ et génère, je suis sûr, du code C ++ (OP a demandé une réponse basée sur C ++).

Les sujets d'actualité sont PEG et ANTLR4. Ce sont mieux que les analyseurs syntaxiques LL ou LR mais donnent quand même un chagrin en essayant de façonner la grammaire. (Avec PEG, vous devez commander les productions, en supposant que vous puissiez trouver un tel ordre, gérer des règles ambiguës avec des priorités. Avec ANTLR4, vous devez toujours spécifier des règles de recherche pour résoudre les ambiguïtés; AFAIK, personne n’a construit d’analyseurs C ++ pratiques avec l’une ou l’autre de ces technologies, de sorte qu’elles ne sont pas à la hauteur de leur réputation.

Je pense que les réponses GLR et GLL sont beaucoup, beaucoup mieux.


21
2018-03-04 00:42



Question intéressante - je ne suis pas sûr d'avoir une bonne réponse à votre question, mais mon "commentaire" est un peu long pour un commentaire ...

Je travaille dans un compilateur Pascal, et j'ai écrit un fichier Lexer, Tokenizer et Parser (y compris la production d'AST pour générer un code pour LLVM) dans environ 1100 lignes, si je puis dire, plutôt "joli ", de code C ++ - tout à la main. Il est beaucoup plus convivial de générer de bons messages d'erreur, et cela aide. Il manque plusieurs bits, et il me reste encore beaucoup de travail à faire avant que mon compilateur ne soit complet, mais je peux compiler un code assez complexe.

J'avoue que je n'ai jamais utilisé Lex / Yacc ou Flex / Bison pour rien de réel. Je l'ai parfois regardé, mais j'ai du mal à utiliser ces outils, et vous finissez par prendre le code généré et le modifier (mauvaise idée avec du code généré automatiquement), ou avec une mauvaise gestion des erreurs et du code de débogage difficile. de ça. Mais alors, je passe juste environ deux heures à essayer de trouver une erreur causée par le fait de "manger" un point-virgule trop tôt, ce qui entraîne la perte de l'analyseur dans le flux de jetons ...


2
2018-03-01 01:02