Quel est le type d'analyseur le plus puissant?

28

En parallèle, j'écris un langage en utilisant Python. J'ai commencé par utiliser un clone flex / bison appelé Ply, mais je me heurte aux limites de la puissance de ce que je peux exprimer avec ce style de grammaire, et je ne suis pas intéressé à pirater ma langue en raison d'un décalage d'impédance avec l'outil. Par conséquent, je ne suis pas opposé à écrire le mien.

Alors, quel est le type d'analyseur le plus puissant? Des citations d'articles (ainsi que d'autres articles introductifs) seraient les bienvenues.

(Je sais que «puissant» n'est pas défini avec précision, mais soyons un peu lâches avec lui et voyons où vont les réponses)

Paul Biggar
la source
1
Downvoted: pas au niveau de la recherche.
Warren Schudy
3
@Warren: J'ai vérifié la FAQ avant de demander - cela ne semble pas être une exigence.
Paul Biggar
1
il y a en fait deux FAQ, une pour le site général et une pour CStheory. Le CStheory indique que les questions auxquelles on peut répondre par exemple en lisant Wikipedia sont hors sujet; voir "Quels types de questions sont trop basiques?" dans meta.cstheory.stackexchange.com/questions/225/… .
Warren Schudy
1
@Warren: C'est la FAQ que j'ai lue. J'avais lu wikipedia, mais je sentais que cela nécessitait un aperçu réel.
Paul Biggar
1
Vous voulez dire des analyseurs en production ou théoriques, c'est-à-dire ceux qui couvrent des types de grammaire autres que CFG?
Raphael

Réponses:

33

Une grammaire est généralement définie comme une grammaire sans contexte - une définition précise est donnée sur la page Wikipedia, mais elle fonctionne de la même manière que dans PLY, qui est basé sur Bison , qui est à son tour basé sur yacc .

Il est dit ici que PLY utilise un analyseur LALR . Il s'agit essentiellement d'un analyseur LR où les tables de recherche sont condensées, introduisant éventuellement des conflits d'analyse, réduisant une partie de l'expressivité d'une grammaire LR (c'est-à-dire une grammaire sans contexte qu'un analyseur LR peut analyser). Si vous voulez connaître les limites de cette branche particulière des analyseurs et celles des autres analyseurs, un aperçu de toutes sortes de techniques d'analyse (LL, LR et autres) est donné ici .

Pour répondre à votre question: il existe des algorithmes d'analyse capables d'analyser n'importe quel langage sans contexte, même si le langage est ambigu (c'est-à-dire qu'il y a plus d'une façon d'interpréter l'entrée):

O(n3|g|)n|g|

O(n3)O(n2)

Ici vous pouvez trouver un article discutant d'une implémentation pratique de (une adaptation de) l'algorithme d'Earley. Ils concluent: "Étant donné la généralité de l'analyse de Earley par rapport à l'analyse de LALR (1) ((qui est à peu près ce que fait PLY)), et considérant que même le pire moment de PEP ((leur implémentation de l'algorithme de Earley)) ne serait pas perceptible par un utilisateur, c'est un excellent résultat ".

Le dernier type d'analyseur est l' analyseur GLR . Il s'agit d'une version généralisée de l'analyse LR, capable d'analyser n'importe quel langage sans contexte.

Une implémentation mature de GLR est ASF + SDF . Bison peut également générer un analyseur GLR, bien que ses implémentations soient légèrement différentes de l'algorithme GLR «standard». L' algorithme Elkhound est un algorithme hybride GLR / LALR. Il utilise LALR lorsque cela est possible et GLR lorsque cela est nécessaire, afin d'être à la fois rapide et capable d'analyser n'importe quelle grammaire.

Au-delà des grammaires sans contexte, il existe des grammaires contextuelles , mais elles sont généralement difficiles à analyser et n'ajoutent pas beaucoup d'expressivité: vous pouvez en faire plus, mais pour la plupart des applications, les utilisations supplémentaires ne sont pas pertinentes, sauf si vous analysez une langue naturelle.

Comme dernière étape, il y a des grammaires illimitées . À ce stade, la grammaire est Turing-complete, donc il n'y a pas de limite que l'on puisse donner sur le temps qu'il faudra pour analyser une langue particulière, ce qui n'est pas souhaitable pour la plupart des applications d'analyse. La puissance supplémentaire n'est presque jamais nécessaire. Si vous voulez utiliser toute cette puissance, la machine à langer est disponible.

Enfin, l'implémentation de votre propre générateur d'analyseur n'est pas une mince affaire, en particulier pour qu'il soit rapide. Personnellement, je viens de terminer ma propre version de flex (le générateur de lexer), et même si cela semblait être un exercice de problèmes algorithmiques relativement simples, il est devenu assez complexe de bien faire les choses, en particulier lorsque j'ai essayé de prendre en charge Unicode. Pensez à utiliser une implémentation déjà existante au lieu d'écrire la vôtre.

Alex ten Brink
la source
1
Excellente réponse !! Avez-vous des réflexions sur la manière dont les PEG s'intègrent?
Paul Biggar
2
Les PEG sont «différents» des CFG: il existe des CFG qui ne sont pas des PEG et vice versa. Je vous renvoie ici: stackoverflow.com/questions/1857022/… .
Alex ten Brink
Cela pourrait également être intéressant: blogs.ethz.ch/copton/2009/07/08/parsing-expression-grammars .
Alex ten Brink
1
En fait, les générateurs d'analyseurs les plus courants (yacc, Antlr, bison) autorisent les concepts non CF par des prédicats ou du code arbitraire qui vérifie si une règle peut être appliquée resp. décider de la priorité. Cela peut être utilisé pour implémenter une sémantique statique principalement car la syntaxe de base reste essentiellement sans contexte.
Raphael
1
Les langages récursifs sont précisément les langages décidables en arrêtant toujours les machines de Turing. Tout langage contextuel est donc également récursif, mais comme les langages contextuels sont décidables en temps exponentiel, il existe des langages récursifs qui ne sont pas contextuels. Les grammaires illimitées sont encore plus puissantes: le problème d'arrêt peut être décrit par une grammaire illimitée, mais ce n'est pas un langage récursif.
Alex ten Brink
15

Un article à ICFP 2010 cette année, Total Parser Combinators , décrit une bibliothèque de combinateurs d'analyseurs à terminaison prouvée et établit également que dans cette bibliothèque "les combinateurs d'analyseurs sont aussi expressifs que possible" étant donné que l'analyseur est garanti de se terminer. Malheureusement, je ne me souviens pas de l'explication donnée par l'auteur sur ce que signifie «aussi expressif que possible», mais cela semble certainement pertinent pour votre question sur le «pouvoir».

Rob Simmons
la source
1
J'ai une voiture qui ne pollue pas, en fait elle ne bouge pas non plus ... Alors la question est: quel genre de langage est analysé par cette bibliothèque? Cela ne veut pas dire que ce travail n'est pas intéressant, bien sûr.
babou
2

Si vous voulez aller au-delà des grammaires hors contexte pour analyser les langages de programmation, mais toujours en syntaxe polynomiale, vous pouvez recourir à l' analyse des grammaires d'expression ou des grammaires booléennes - ces dernières sont également disponibles en versions LL et LR (voir ici ). Dans la théorie du langage formel, les langages Church-Rosser puissants mais reconnaissables en temps linéaire sont également étudiés, mais je ne connais aucun générateur d'analyseur implémenté pour ceux-ci.

Dans le traitement du langage naturel, les goûts sont différents, par exemple, le traitement de l'ambiguïté (également: l'ambiguïté inhérente) et l'ordre des mots libres joue un rôle très important. Ici, les mots-clés des langues légèrement contextuelles et le redémarrage des automates peuvent vous aider à commencer la lecture.

Hermann Gruber
la source
1
Compte tenu de la façon dont la question a été posée et de la plainte selon laquelle les FC sont trop contraignantes, votre réponse est clairement la meilleure. Alors ça va ...
babou
0

Outils du générateur d'analyseur:

ANTLR est très bon. Alternativement, vous pouvez jeter un œil à JavaCC


la source
Je ne suis pas un informaticien (malgré ce que dit mon diplôme;), donc mes mots pourraient peser légèrement ici. Je suis d'accord avec Sazzad - ANTLR est un outil très puissant. Il est très complet et je n'ai pas encore trouvé de problème avec le générateur d'analyseur (LL (k) si je me souviens bien). D'un autre côté, je n'ai pas encore implémenté un compilateur de pour une grammaire quelque peu complexe ...
Jörgen Sigvardsson
5
Je pense que vous manquez le point de la question, et peut-être l'ensemble du site. Il s'agit d'analyser la théorie, pas d'implémentations et d'outils.
Paul Biggar