Analyser des grammaires arbitraires sans contexte, principalement de courts extraits

Je souhaite analyser les langues spécifiques au domaine défini par l'utilisateur. Ces langages sont généralement proches des notations mathématiques (je n'analyse pas un langage naturel). Les utilisateurs définissent leur DSL dans une notation BNF, comme ceci:

expr ::= LiteralInteger
       | ( expr )
       | expr + expr
       | expr * expr

L'entrée comme 1 + ( 2 * 3 )doit être acceptée, tandis que l'entrée comme 1 +doit être rejetée comme incorrecte, et l'entrée comme 1 + 2 * 3doit être rejetée comme ambiguë.

Une difficulté centrale ici est de faire face aux grammaires ambiguës de manière conviviale. Limiter la grammaire pour qu'elle ne soit pas ambiguë n'est pas une option: c'est ainsi que la langue est - l'idée est que les écrivains préfèrent omettre les parenthèses lorsqu'elles ne sont pas nécessaires pour éviter toute ambiguïté. Tant qu'une expression n'est pas ambiguë, je dois l'analyser, et si elle ne l'est pas, je dois la rejeter.

Mon analyseur doit fonctionner sur n'importe quelle grammaire sans contexte, même ambiguë, et doit accepter toutes les entrées sans ambiguïté. J'ai besoin de l'arbre d'analyse pour toutes les entrées acceptées. Pour une entrée invalide ou ambiguë, je souhaite idéalement de bons messages d'erreur, mais pour commencer, je prendrai ce que je peux obtenir.

J'invoquerai généralement l'analyseur sur des entrées relativement courtes, avec une entrée plus longue occasionnelle. Ainsi, l'algorithme asymptotiquement plus rapide n'est peut-être pas le meilleur choix. Je voudrais optimiser pour une distribution d'environ 80% d'entrées de moins de 20 symboles de long, 19% entre 20 et 50 symboles et 1% d'entrées plus longues rares. La vitesse des entrées invalides n'est pas une préoccupation majeure. De plus, je m'attends à une modification de la DSL toutes les 1000 à 100 000 entrées; Je peux passer quelques secondes à prétraiter ma grammaire, pas quelques minutes.

Quel (s) algorithme (s) d'analyse dois-je étudier, compte tenu de mes tailles d'entrée typiques? Le rapport d'erreurs doit-il être un facteur dans ma sélection, ou dois-je me concentrer sur l'analyse des entrées sans ambiguïté et éventuellement exécuter un analyseur complètement distinct et plus lent pour fournir un retour d'erreur?

(Dans le projet où j'avais besoin de cela (il y a quelque temps), j'ai utilisé CYK , qui n'était pas trop difficile à implémenter et fonctionnait correctement pour mes tailles d'entrée, mais n'a pas produit de très belles erreurs.)

L'algorithme idéal pour vos besoins est probablement l' analyse LL généralisée , ou GLL. Il s'agit d'un tout nouvel algorithme (l'article a été publié en 2010). D'une certaine manière, c'est l'algorithme d'Earley augmenté d'une pile structurée de graphes (GSS), et utilisant l'anticipation LL (1).

L'algorithme est assez similaire à l'ancien LL (1), sauf qu'il ne rejette pas les grammaires si elles ne sont pas LL (1): il essaie simplement toutes les analyses LL (1) possibles. Il utilise un graphe orienté pour chaque point de l'analyse, ce qui signifie que si un état d'analyse est rencontré et traité auparavant, il fusionne simplement ces deux sommets. Cela le rend approprié même pour les grammaires récursives à gauche, contrairement à LL. Pour des détails exacts sur son fonctionnement interne, lisez le papier (c'est un papier assez lisible, bien que l'étiquette de soupe nécessite une certaine persévérance).

L'algorithme présente un certain nombre d'avantages clairs correspondant à vos besoins par rapport aux autres algorithmes d'analyse généraux (que je connaisse). Premièrement, la mise en œuvre est très facile: je pense que seule Earley est plus facile à mettre en œuvre. Deuxièmement, les performances sont assez bonnes: en fait, elles deviennent tout aussi rapides que LL (1) sur des grammaires LL (1). Troisièmement, la récupération de l'analyse est assez facile, et il est également possible de vérifier s'il existe plusieurs analyses.

Le principal avantage de GLL est qu'il est basé sur LL (1) et est donc très facile à comprendre et à déboguer, lors de l'implémentation, lors de la conception des grammaires ainsi que lors de l'analyse des entrées. En outre, cela facilite également la gestion des erreurs: vous savez exactement où les analyses possibles ont échoué et comment elles ont pu continuer. Vous pouvez facilement donner les analyses possibles au point de l'erreur et, par exemple, les 3 derniers points où les analyses se sont échouées. Vous pouvez plutôt choisir d'essayer de récupérer de l'erreur et de marquer la production sur laquelle l'analyse la plus éloignée travaillait comme `` terminée '' pour cette analyse, et de voir si l'analyse peut continuer après cela (par exemple, quelqu'un a oublié une parenthèse). Vous pourriez même faire cela pour, disons, les 5 analyses qui ont été les plus éloignées.

Le seul inconvénient de l'algorithme est qu'il est nouveau, ce qui signifie qu'aucune implémentation bien établie n'est facilement disponible. Ce n'est peut-être pas un problème pour vous - j'ai implémenté l'algorithme moi-même, et c'était assez facile à faire.

Mon entreprise (Semantic Designs) a utilisé les analyseurs GLR avec beaucoup de succès pour faire exactement ce que OP suggère en analysant les deux langages spécifiques au domaine et en analysant les langages de programmation "classiques", avec notre DMS Software Reengineering Toolkit. Cela prend en charge les transformations de programme de source à source utilisées pour la restructuration de programmes à grande échelle / l'ingénierie inverse / la génération de code vers l'avant. Cela inclut la réparation automatique des erreurs de syntaxe d'une manière assez pratique. En utilisant GLR comme base et quelques autres changements (prédicats sémantiques, entrée de jeu de jetons plutôt que juste entrée de jeton, ...), nous avons réussi à construire des analyseurs pour environ 40 langues.

Aussi important que la capacité d'analyser des instances de langues complètes, GLR s'est également révélé extrêmement utile pour analyser les règles de réécriture de source à source . Ce sont des fragments de programme avec beaucoup moins de contexte qu'un programme complet, et ont donc généralement plus d'ambiguïté. Nous utilisons des annotations spéciales (par exemple, insistant pour qu'une phrase corresponde à une grammaire spécifique non terminale) pour aider à résoudre ces ambiguïtés pendant / après l'analyse des règles. En organisant le mécanisme d'analyse GLR et les outils qui l'entourent, nous obtenons des analyseurs pour réécrire les règles "gratuitement" une fois que nous avons un analyseur pour sa langue. Le moteur DMS possède un applicateur de règles de réécriture intégré qui peut ensuite être utilisé pour appliquer ces règles afin d'effectuer les modifications de code souhaitées.

Notre résultat le plus spectaculaire est probablement la capacité d' analyser le C ++ 14 complet , malgré toutes les ambiguïtés, en utilisant une grammaire sans contexte comme base. Je note que tous les compilateurs C ++ classiques (GCC, Clang) ont abandonné la possibilité de le faire et d'utiliser des analyseurs manuscrits (ce qui à mon humble avis les rend beaucoup plus difficiles à maintenir, mais ce n'est pas mon problème). Nous avons utilisé cette machinerie pour effectuer des changements massifs dans l'architecture des grands systèmes C ++.

Côté performances, nos analyseurs GLR sont relativement rapides: des dizaines de milliers de lignes par seconde. C'est bien en deçà de l'état de l'art, mais nous n'avons fait aucune tentative sérieuse pour l'optimiser, et certains des goulots d'étranglement sont dans le traitement du flux de caractères (Unicode complet). Pour construire de tels analyseurs, nous pré-traitons les grammaires sans contexte en utilisant quelque chose d'assez proche d'un générateur d'analyseur LR (1); cela fonctionne normalement sur un poste de travail moderne en dix secondes sur de grandes grammaires de la taille de C ++. Étonnamment, pour les langages très complexes comme le COBOL moderne et le C ++, la génération de lexers s'avère prendre environ une minute; certains des DFA définis sur Unicode deviennent assez poilus. Je viens de faire Ruby (avec un sous-programme complet pour ses regexps incroyables) comme exercice au doigt; DMS peut traiter son lexer et sa grammaire ensemble en environ 8 secondes.

Il existe de nombreux analyseurs généraux sans contexte qui peuvent analyser des phrases ambiguës (selon une grammaire ambiguë). Ils se présentent sous différents noms, notamment par programmation dynamique ou parseurs graphiques. Le plus connu et le plus simple est probablement l'analyseur CYK que vous avez utilisé. Cette généralité est nécessaire car vous devez gérer plusieurs analyses et ne savez pas jusqu'à la fin si vous avez affaire à une ambiguïté ou non.

D'après ce que vous dites, je pense que CYK n'est pas un si mauvais choix. Vous n'avez probablement pas grand-chose à gagner en ajoutant de la prédictivité (LL ou LR), et cela peut en fait avoir un coût en discriminant les calculs qui devraient être fusionnés plutôt que discriminés (en particulier dans le cas LR). Ils peuvent également avoir un coût correspondant à la taille de la forêt d'analyse qui est produite (ce qui peut avoir un rôle dans les erreurs d'ambiguïté). En fait, même si je ne sais pas comment comparer formellement l'adéquation des algorithmes plus sophistiqués, je sais que CYK offre un bon partage de calcul.

Maintenant, je ne crois pas qu'il existe beaucoup de littérature sur les analyseurs syntaxiques généraux des FC pour les grammaires ambiguës qui ne devraient accepter que des entrées sans ambiguïté. Je ne me souviens pas en avoir vu, probablement parce que même pour les documents techniques, ou même les langages de programmation, l'ambiguïté syntaxique est acceptable tant qu'elle peut être résolue par d'autres moyens (par exemple l'ambiguïté dans les expressions ADA).

Je me demande en fait pourquoi vous voulez changer votre algorithme, plutôt que de vous en tenir à ce que vous avez. Cela pourrait m'aider à comprendre quel type de changement pourrait le mieux vous aider. Est-ce un problème de vitesse, est-ce la représentation des analyses, ou est-ce la détection et la récupération des erreurs?

La meilleure façon de représenter plusieurs analyses est d'utiliser une forêt partagée, qui est simplement une grammaire sans contexte qui génère uniquement votre entrée, mais avec exactement toutes les mêmes arborescences d'analyse que la grammaire DSL. Cela le rend très facile à comprendre et à traiter. Pour plus de détails, je vous propose de regarder cette réponse que j'ai donnée sur le site linguistique. Je comprends que vous n'êtes pas intéressé à obtenir une forêt d'analyse, mais une représentation appropriée de la forêt d'analyse peut vous aider à donner de meilleurs messages sur le problème d'ambiguïté. Cela pourrait également vous aider à décider que l'ambiguïté n'a pas d'importance dans certains cas (associativité) si vous le souhaitez.

Vous mentionnez les contraintes de temps de traitement de votre grammaire DSL, mais ne donnez aucune indication quant à sa taille (ce qui ne veut pas dire que je pourrais y répondre avec des chiffres).

Certains traitements d'erreurs peuvent être intégrés dans ces algorithmes CF généraux de manière simple. Mais j'aurais besoin de comprendre quel type de traitement d'erreur vous attendez à être plus affirmatif. Auriez-vous des exemples.

Je suis un peu mal à l'aise pour en dire plus, car je ne comprends pas vraiment quelles sont vos motivations et contraintes. Sur la base de ce que vous dites, je m'en tiendrai à CYK (et je connais les autres algorithmes et certaines de leurs propriétés).