Avantages de Antlr (versus disons, lex / yacc / bison) [fermé]

Question

J'ai déjà utilisé lex et yacc (plus généralement le bison) dans le cadre de divers projets, généralement des traducteurs (comme un sous-ensemble de fichiers EDIF transmis dans une application EDA). De plus, j'ai dû supporter un code basé sur des grammaires lex / yacc datant de plusieurs décennies. Je connais donc bien les outils, même si je ne suis pas un expert.

J'ai déjà vu des commentaires positifs sur Antlr dans divers forums et je suis curieux de savoir ce qui me manque. Donc, si vous avez utilisé les deux, dites-moi s'il vous plaît ce qui est meilleur ou plus avancé dans Antlr. Mes contraintes actuelles sont que je travaille dans une boutique C ++ et que tout produit que nous expédions n'inclut pas Java. Les analyseurs syntaxiques ainsi créés devraient suivre cette règle.

Answer 1

Mise à jour / avertissement: cette réponse est peut-être obsolète!

Une différence majeure est que ANTLR génère un analyseur syntaxique LL (*), alors que YACC et Bison génèrent tous deux des analyseurs syntaxiques qui sont LALR. C’est une distinction importante pour un certain nombre d’applications, les plus évidentes étant les opérateurs:

expr ::= expr '+' expr
       | expr '-' expr
       | '(' expr ')'
       | NUM ;

ANTLR est tout à fait incapable de gérer cette grammaire telle quelle. Pour utiliser ANTLR (ou tout autre générateur d'analyseur syntaxique LL), vous devez convertir cette grammaire en un élément non récursif de gauche. Cependant, Bison n’a aucun problème avec les grammaires de cette forme. Vous devez déclarer "+" et "-" en tant qu'opérateurs associatifs de gauche, mais cela n'est pas strictement requis pour la récursivité de gauche. Un meilleur exemple pourrait être dispatch:

expr ::= expr '.' ID '(' actuals ')' ;

actuals ::= actuals ',' expr | expr ;

Notez que les règles expr et actual sont récursives à gauche. Cela produit un AST beaucoup plus efficace quand vient le temps de générer du code car cela évite d'avoir à utiliser plusieurs registres et tout renversement inutile (un arbre de gauche peut être effondré alors qu'un arbre de droite ne le peut pas).

En termes de goût personnel, je pense que les grammaires LALR sont beaucoup plus faciles à construire et à déboguer. L'inconvénient est que vous devez faire face à des erreurs quelque peu cryptiques telles que shift-réduire et (redouté) réduire-réduire. Ce sont des erreurs que Bison attrape lors de la génération de l'analyseur. Cela n'affecte donc pas l'expérience de l'utilisateur final, mais cela peut rendre le processus de développement un peu plus intéressant. ANTLR est généralement considéré comme plus facile à utiliser que YACC / Bison pour cette raison précisément.

Answer 2

La différence la plus significative entre YACC / Bison et ANTLR réside dans le type de grammaire que ces outils peuvent traiter. YACC / Bison gère les grammaires LALR, ANTLR gère les grammaires LL.

Souvent, les personnes qui travaillent avec les grammaires LALR depuis longtemps trouveront plus difficile de travailler avec les grammaires LL et vice-versa. Cela ne signifie pas que les grammaires ou les outils sont par nature plus difficiles à travailler. L’outil le plus facile à utiliser dépendra principalement du type de grammaire.

En ce qui concerne les avantages, il existe des aspects pour lesquels les grammaires LALR ont des avantages sur les grammaires LL et il existe d’autres aspects pour lesquels les grammaires LL ont des avantages par rapport aux grammaires LALR.

YACC / Bison génèrent des analyseurs syntaxiques pilotés par table, ce qui signifie la "logique de traitement". est contenu dans les données du programme d'analyse, pas tellement dans le code de l'analyseur. Le résultat est que même un analyseur syntaxique pour un langage très complexe a une empreinte de code relativement petite. C'était plus important dans les années 1960 et 1970, alors que le matériel informatique était très limité. Les générateurs d’analyseurs basés sur les tables remontent à cette époque et la faible empreinte de code était alors une exigence principale.

ANTLR génère des analyseurs syntaxiques à descente récursive, ce qui signifie que la "logique de traitement" est contenu dans le code de l'analyseur, chaque règle de production de la grammaire étant représentée par une fonction dans le code de l'analyseur. Le résultat est qu'il est plus facile de comprendre ce que l'analyseur fait en lisant son code. En outre, les analyseurs récursifs de descente sont généralement plus rapides que ceux pilotés par des tables. Cependant, pour les langages très complexes, l'encombrement du code sera plus grand. C'était un problème dans les années 1960 et 1970. À l’époque, seules des langues relativement petites comme Pascal par exemple étaient implémentées de cette manière en raison de limitations matérielles.

Les analyseurs générés par ANTLR se situent généralement autour de 10 000 lignes de code et plus. Les analyseurs syntaxiques de descente récursifs manuscrits sont souvent dans le même stade. Le compilateur Oberon de Wirth est peut-être le plus compact avec environ 4000 lignes de code, y compris la génération de code, mais Oberon est un langage très compact avec seulement environ 40 règles de production.

Comme quelqu'un l'a déjà souligné, un gros avantage pour ANTLR est l'outil graphique IDE, appelé ANTLRworks. C'est un laboratoire complet de grammaire et de conception linguistique. Il visualise vos règles de grammaire au fur et à mesure que vous les tapez et, s'il détecte des conflits, il vous montrera graphiquement ce qu'il est et ce qui le cause. Il peut même automatiquement refactoriser et résoudre des conflits tels que la récursivité à gauche. Une fois que vous avez une grammaire sans conflit, vous pouvez laisser ANTLRworks analyser un fichier d’entrée de votre langue, créer un arbre d’analyse et AST pour vous, puis l’afficher sous forme graphique dans l’EDI. Ceci est un très gros avantage car cela peut vous épargner de nombreuses heures de travail: vous constaterez des erreurs conceptuelles dans la conception de votre langage avant de commencer à coder! Je n’ai trouvé aucun outil de ce type pour les grammaires LALR, il semble qu’il n’en existe pas.

Même pour les personnes qui ne souhaitent pas générer leurs parseurs mais les coder à la main, ANTLRworks est un excellent outil pour la conception / prototypage de langage. Très probablement le meilleur outil disponible. Malheureusement, cela ne vous aide pas si vous voulez construire des analyseurs syntaxiques LALR. Passer de LALR à LL simplement pour tirer parti d'ANTLRworks peut en valoir la peine, mais pour certaines personnes, changer de type de grammaire peut s'avérer une expérience très pénible. En d'autres termes: YMMV.

Answer 3

Quelques avantages pour ANTLR:

• peut générer des analyseurs syntaxiques dans différentes langues - Java n'est pas nécessaire pour exécuter l'analyseur généré.
• L’interface graphique impressionnante facilite le débogage de la grammaire (par exemple, vous pouvez voir les AST générés directement dans l’interface graphique, aucun outil supplémentaire n'est requis)
• Le code généré est réellement lisible par l'homme (c'est l'un des objectifs de ANTLR) et le fait qu'il génère des analyseurs syntaxiques LL est certainement utile à cet égard.
• la définition des terminaux est également dépourvue de contexte (par opposition à regex dans (f) lex) - permettant ainsi, par exemple, la définition de terminaux contenant des parenthèses correctement fermées

Mon .02 $

Answer 4

Un autre avantage de ANTRL est que vous pouvez utiliser ANTLRWORKS , bien que je ne puisse pas Dites que c'est un avantage strict, car il peut y avoir des outils similaires pour d'autres générateurs.

Answer 5

• Bison et Flex réduisent l’empreinte mémoire, mais vous n’avez pas d’IDE graphique.
• antlr utilise plus de mémoire, mais vous avez antlrworks, un IDE graphique.

L'utilisation de la mémoire Bison / Flex est généralement de l'ordre de quelques octets. Comparez cela avec antlr - en supposant qu'il utilise 512 octets de mémoire pour chaque jeton du fichier que vous souhaitez analyser. 4 millions de jetons et vous n’avez plus de mémoire virtuelle sur un système 32 bits.

Si le fichier que vous souhaitez analyser est volumineux, antlr risque de manquer de mémoire. Si vous souhaitez uniquement analyser un fichier de configuration, ce sera une solution viable. Sinon, si vous souhaitez analyser un fichier contenant beaucoup de données, essayez Bison.