Avantages d'Antlr (par rapport à, disons, lex/yacc/bison)

Question

J'ai utilisé lex et yacc (plus généralement bison) dans le passé pour divers projets, généralement des traducteurs (comme un sous-ensemble d'EDIF diffusé dans une application EDA). De plus, j'ai eu à supporter du code basé sur des grammaires lex/yacc datant de plusieurs décennies. Je sais donc comment utiliser ces outils, même si je ne suis pas un expert.

J'ai vu des commentaires positifs sur Antlr dans divers forums dans le passé, et je suis curieux de savoir ce que je pourrais manquer. Donc, si vous avez utilisé les deux, s'il vous plaît dites-moi ce qui est mieux ou plus avancé dans Antlr. Mes contraintes actuelles sont que je travaille dans un atelier C++, et tout produit que nous expédions n'inclura pas Java, donc les parseurs résultants devront suivre cette règle.

Answer 1

Mise à jour/alerte : Cette réponse peut être périmée !

---

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 LALR. Il s'agit d'une distinction importante pour un certain nombre d'applications, la plus évidente étant les opérateurs :

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

ANTLR est totalement incapable de gérer cette grammaire telle quelle. Pour utiliser ANTLR (ou tout autre générateur d'analyseur syntaxique LL), vous devriez convertir cette grammaire en quelque chose qui n'est pas récursif à gauche. Cependant, Bison n'a aucun problème avec les grammaires de cette forme. Vous auriez besoin de déclarer '+' et '-' comme opérateurs associatifs à gauche, mais ce n'est pas strictement nécessaire pour la récursivité à gauche. Un meilleur exemple pourrait être la répartition :

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

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

Remarquez que les deux expr y el actuals Les règles sont récursives à gauche. Cela produit un AST beaucoup plus efficace au moment de la génération du code, car il évite le besoin de registres multiples et de débordements inutiles (un arbre penchant à gauche peut être effondré alors qu'un arbre penchant à 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 comme shift-reduce et (la redoutable) reduce-reduce. Ces erreurs sont détectées par Bison lors de la génération de l'analyseur, ce qui n'affecte pas l'expérience de l'utilisateur final, mais 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écise.

Answer 2

La différence la plus significative entre YACC/Bison et ANTLR est le type de grammaires que ces outils peuvent traiter. YACC/Bison traite les grammaires LALR, ANTLR traite les grammaires LL.

Souvent, les personnes qui ont travaillé pendant longtemps avec des grammaires LALR trouveront plus difficile de travailler avec des grammaires LL et vice versa. Cela ne signifie pas que les grammaires ou les outils sont intrinsèquement plus difficiles à utiliser. Le choix de l'outil le plus facile à utiliser dépendra essentiellement de la familiarité avec le type de grammaire.

En ce qui concerne les avantages, il y a des aspects où les grammaires LALR ont des avantages sur les grammaires LL et il y a d'autres aspects où les grammaires LL ont des avantages sur les grammaires LALR.

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

ANTLR génère des analyseurs descendants récursifs, ce qui signifie que la "logique de traitement" est contenue dans le code de l'analyseur, puisque chaque règle de production de la grammaire est représentée par une fonction dans le code de l'analyseur. L'avantage est qu'il est plus facile de comprendre ce que fait l'analyseur en lisant son code. De plus, les analyseurs par descente récursive sont généralement plus rapides que les analyseurs par table. Cependant, pour les langages très complexes, l'empreinte du code sera plus importante. C'était un problème dans les années 1960 et 1970. À l'époque, seuls des langages relativement petits, comme le Pascal par exemple, étaient implémentés de cette manière en raison des limitations matérielles.

Les analyseurs générés par ANTLR sont généralement de l'ordre de 10.000 lignes de code et plus. Les analyseurs récursifs descendants écrits à la main sont souvent dans la même fourchette. Le compilateur Oberon de Wirth est peut-être le plus compact avec environ 4000 lignes de code incluant 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 grand plus pour ANTLR est l'outil IDE graphique, appelé ANTLRworks. C'est un laboratoire complet de grammaire et de conception de langage. Il visualise vos règles de grammaire au fur et à mesure que vous les tapez et s'il trouve des conflits, il vous montre graphiquement ce qu'est le conflit et ce qui le cause. Il peut même remanier et résoudre automatiquement des conflits tels que la récursion à gauche. Une fois que vous avez une grammaire sans conflit, vous pouvez laisser ANTLRworks analyser un fichier d'entrée de votre langue et construire un arbre d'analyse et une AST pour vous et montrer l'arbre graphiquement dans l'IDE. C'est un très gros avantage car cela peut vous faire gagner de nombreuses heures de travail : Vous trouverez des erreurs conceptuelles dans la conception de votre langage avant de commencer à coder ! Je n'ai pas trouvé un tel outil pour les grammaires LALR, il semble qu'il n'y en ait pas.

Même pour les personnes qui ne souhaitent pas générer leurs analyseurs syntaxiques mais les coder à la main, ANTLRworks est un outil formidable pour la conception/le prototypage de langues. C'est probablement le meilleur outil de ce type disponible. Malheureusement, cela ne vous aide pas si vous voulez construire des analyseurs LALR. Passer de LALR à LL simplement pour profiter d'ANTLRworks peut être intéressant, mais pour certaines personnes, changer de type de grammaire peut être une expérience très douloureuse. En d'autres termes : YMMV.

Answer 3

Quelques avantages pour ANTLR :

• peut produire des analyseurs en plusieurs langues - Java n'est pas nécessaire pour exécuter l'analyseur généré.
• Une 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, sans outils supplémentaires).
• Le code généré est réellement lisible par l'homme (c'est l'un des objectifs d'ANTLR) et le fait qu'il génère des analyseurs syntaxiques LL aide sûrement à cet égard.
• La définition des terminaux est également libre de contexte (par opposition aux regex dans la (f)lex) - ce qui permet, par exemple, de définir l'expression terminaux contenant des parenthèses correctement fermées

Mon point de vue

Answer 4

Un autre avantage d'ANTRL est que vous pouvez utiliser ANTLRWORKS Je ne peux toutefois pas dire qu'il s'agit d'un avantage strict, car il existe peut-être des outils similaires pour d'autres générateurs.

Answer 5

• Bison et Flex permettent d'obtenir une empreinte mémoire plus faible, mais vous ne disposez pas d'un IDE graphique.
• antlr utilise plus de mémoire, mais vous avez antlrworks, un IDE graphique.

L'utilisation de la mémoire de Bison/Flex est généralement de l'ordre du mbyte. Comparez cela avec antlr - en supposant qu'il utilise 512 octets de mémoire pour chaque token du fichier que vous voulez analyser. 4 millions de tokens et vous êtes à court de mémoire virtuelle sur un système 32 bits.

Si le fichier que vous souhaitez analyser est volumineux, antlr peut manquer de mémoire. Si vous souhaitez simplement analyser un fichier de configuration, c'est une solution viable. Sinon, si vous voulez analyser un fichier contenant beaucoup de données, essayez Bison.