Récupérer une forêt d'analyse d'un analyseur Earley?

25

Je lisais récemment sur l' analyseur Earley et je pense que c'est l'un des algorithmes les plus élégants que j'ai vus à ce jour. Cependant, l'algorithme dans son sens traditionnel est un identificateur et non un analyseur, ce qui signifie qu'il peut détecter si une chaîne correspond à un CFG particulier mais ne pas produire d'arbre d'analyse pour celui-ci. Ma question est de savoir comment récupérer non pas un arbre d' analyse , mais plutôt la forêt d'analyse de toutes les analyses possibles de la chaîne d'entrée donnée.

Dans "Parsing Techniques: A Practical Guide" de Grune et Jacob, ils illustrent un algorithme qui peut être utilisé pour récupérer une forêt d'analyse à partir du résultat de la reconnaissance Earley, mais il est basé sur la méthode d'analyse d'Unger, dont l'exécution est O (n k + 1 ), où k est la longueur de la production la plus longue de la grammaire. Cela signifie que le runtime n'est pas un polynôme de la taille de la grammaire. De plus, l'article original d'Earley sur l'algorithme, qui suggère un algorithme de récupération des forêts d'analyse, est incorrect (voir, par exemple, page 762 de cet article de Tomita), bien que de nombreuses sources le citent toujours comme le moyen approprié pour récupérer la forêt d'analyse .

Ma question est de savoir s'il est possible, en temps polynomial, de récupérer une forêt d'analyse pour une chaîne d'entrée donnée. J'ai trouvé un article ici qui fournit un algorithme pour produire des représentations de forêt d'analyse de taille cubique pour n'importe quelle analyse en utilisant une simulation d'un PDA, donc cela semble être possible, mais je n'ai pas encore trouvé de moyen de le faire. Idéalement, j'aimerais faire cela sans convertir la grammaire d'entrée en CNF (ce qui résoudrait en effet le problème), car la forêt d'analyse résultante serait assez désordonnée.

Merci pour toute aide que vous pouvez offrir!

templatetypedef
la source
Doit-il s'agir d'un algorithme basé sur l'analyse Earley, ou cela ne vous dérangerait-il pas d'utiliser un analyseur CFG général différent?
Alex ten Brink
1
Je préférerais un algorithme basé sur l'analyseur Earley. J'ai enseigné un cours de compilateurs et j'ai passé quelques jours à essayer de trouver une réponse à cette question, et cela me dérange vraiment.
templatetypedef
Les temps d'exécution exponentiels ne sont pas surprenants car les mots peuvent avoir de façon exponentielle de nombreux arbres d'analyse. En fait, ils peuvent même en avoir infiniment si vous autorisez les CFG arbitraires.
Raphael
3
@Raphael Le rôle des forêts d'analyse est précisément d'avoir un mécanisme de partage qui permettra de représenter tous les arbres, même infiniment nombreux, avec une structure finie, avec une petite complexité d'espace. Bien sûr, cela peut laisser du travail aux bûcherons.
babou
Vous voudrez peut-être regarder Marpa . Il s'agit d'un module Perl et d'une bibliothèque C qui implémente un analyseur Earley et prend en charge la forêt d'analyse complète.
hippietrail

Réponses:

14

Cela dépendrait bien sûr de la bonne représentation d'une "forêt dense" qui représente tous les arbres d'analyse pour une phrase donnée.

Je pense que l'endroit où vous voulez commencer à regarder est la thèse de Joshua Goodman (analyse à l'envers, Harvard, 1999). Fondamentalement, l'idée est que vous pouvez définir un algorithme d'analyse sous un certain semiring. Selon le semiring, vous seriez en mesure de calculer toutes sortes de quantités et de structures au lieu de l'arbre d'analyse nu (en tant que reconnaissance ou en tant qu'analyseur). Un semiring que vous pourriez définir (ce que Goodman fait dans sa thèse) est un semiring où les valeurs sont des ensembles d'analyses. Lorsque vous avez fini d'analyser une phrase, vous obtenez tous les arbres d'analyse dans le nœud d'analyse principal.

Encore une fois, vous devez faire attention à ce que cela soit possible grâce à la bonne représentation.

gmmodeler
la source
Merci pour la référence! Cela ressemble à une excellente ressource et je vais y passer un peu de temps.
templatetypedef
8

Il y a un document qui décrit comment le faire:

Analyse de style SPPF par Earley Recognisers par Elisabeth Scott

Il décrit comment construire une forêt d'analyse binarisée en temps cube.

Angelo Borsotti
la source
2
Ce lien semble désormais rompu. Avez-vous une référence (titre du papier, où publié, liste des auteurs) et / ou un lien mis à jour?
DW
1
Voir web.archive.org/web/20130508170633/http://thor.info.uaic.ro/… : "SPPF-Style Parsing From Earley Recognisers", Elizabeth Scott. Un autre lien: dinhe.net/~aredridel/.notmine/PDFs/… .
a3nm
C'est la bonne réponse à la question «comment obtenir une forêt d'analyse à partir d'un identificateur Earley».
tjvr
Il y a une belle implémentation de ceci dans JS ici: joshuagrams.github.io/pep
tjvr
Qu'entend-on par binarisé dans ce contexte?
Bruce Adams
6

Vous n'avez jamais besoin de CNF. Elle a l'inconvénient de changer la structure grammaticale. Mais vous devez introduire des non-terminaux intermédiaires afin qu'aucun côté droit ne dépasse 2 (forme 2) car la longueur RHS détermine la complexité. La meilleure tentative pour expliquer cela intuitivement est, si ma mémoire est bonne, un article de Beau Shiel, "Observations on Context Free Parsing", publié en 1976 dans une conférence linguistique computationnelle. L'algorithme d'Earley utilise implicitement la forme 2. Il est juste caché dans l'algorithme. En ce qui concerne la récupération et la gestion de la forêt d'analyse, vous devriez consulter le Web à "l'analyse de la forêt d'intersection". C'est en fait très simple. De nombreux articles sont sur le Web, si vous obtenez (à partir de citations ou de tables des matières) les titres ou les auteurs pour les rechercher directement.

En fait, vous pouvez faire beaucoup plus que CF, et toujours obtenir des forêts d'analyse en temps polynomial. La question est parfois: que pouvez-vous en faire une fois que vous l'avez?

L'un des objectifs du dernier article que vous mentionnez est de montrer que les algorithmes complexes (tels que GLR) n'achètent pas nécessairement quoi que ce soit dans le temps ou dans l'espace, et peuvent changer votre forêt d'analyse.

Une remarque sur l'enseignement. Je pense qu'Earley, séminal comme il était, est beaucoup trop compliqué pour l'enseignement et pourrait être remplacé par des algorithmes plus simples avec essentiellement le même contenu éducatif. L'enseignement concerne les concepts ou la technologie. Dans l'algorithme d'Earley, les concepts essentiels sont cachés dans la complexité des détails, et d'un point de vue technologique, ils sont dépassés. C'était un excellent article, mais cela ne veut pas dire que c'est la meilleure approche pédagogique.

Il peut y avoir plus d'informations dans la littérature linguistique informatique que dans les canaux informatiques habituels. Je n'ai pas le livre Ceriel-Grune-Jacobs, mais je serais surpris s'ils n'avaient pas toutes les références appropriées (même si je ne suis pas sûr de leurs critères de sélection).


Complément suite à une demande dans un commentaire (7 juillet 2013)

Ce complément concerne l'existence d'algorithmes plus simples que ceux d'Earley.

Comme je l'ai dit, la recherche sur le Web de "l'analyse de la forêt d'intersection" devrait rapidement vous donner des références, à partir desquelles vous pouvez creuser davantage.

L'idée de base est que tous les chemins analysant la construction d'une forêt partagée ne sont rien d'autre que l'ancienne construction d'intersection de Bar Hillel, Perles et Shamir pour un langage régulier et un langage sans contexte, en utilisant un automate fini et une grammaire sans contexte. Compte tenu de la grammaire CF, vous appliquez la construction à un automate trivial qui ne reconnaît que votre chaîne d'entrée. C'est tout. La forêt partagée n'est que la grammaire de l'intersection. Il est lié à la grammaire d'origine par le biais d'un homomorphisme, ne reconnaît que la chaîne donnée, mais avec tous les arbres d'analyse de la grammaire originale jusqu'à cet homomorphisme (c'est-à-dire un simple changement de nom des non-terminaux).

La grammaire résultante contient beaucoup de choses inutiles, non terminales et règles, qui sont soit inaccessibles à partir de l'axiome (ne pas être trouvées dans une chaîne dérivée du symbole initial) ou qui sont non productives (ne peuvent pas être dérivées dans un terminal chaîne).

Ensuite, soit vous devez le nettoyer avec une bonne brosse à la fin (éventuellement longue mais simple sur le plan algorithmique), soit vous pouvez essayer d'améliorer la construction afin qu'il y ait moins de peluches inutiles à brosser à la fin.

Par exemple, la construction CYK est exactement cela, mais organisée de manière à ce que toutes les règles et les non-terminaux créés soient productifs, bien que beaucoup puissent être inaccessibles. Il faut s'y attendre d'une technique ascendante.

Les techniques descendantes (telles que celles basées sur LR (k)) éviteront les règles inaccessibles et les non-terminaux, mais en créeront des improductives.

Une grande partie du brossage peut en fait être réalisée par une utilisation adéquate des pointeurs, je pense, mais je n'ai pas examiné cela depuis longtemps.

Tous les algorithmes existants suivent en fait essentiellement ce modèle. C'est donc vraiment le cœur du problème, et c'est très simple. Alors pourquoi l'enterrer dans la complexité?

De nombreuses "optimisations" sont proposées dans la littérature, souvent basées sur la famille LR (k), LL (k) de construction d'analyseur, éventuellement avec une certaine factorisation statique de ces constructions (Earley n'a pas de factorisation statique). Il pourrait en fait être appliqué à toutes les techniques connues, y compris les anciens analyseurs de priorité. Je mets "optimisation" entre les guillemets car il n'est généralement pas clair ce que vous optimisez, ou même si vous l'optimisez réellement, ou si le bénéfice de l'amélioration vaut la complexité supplémentaire de votre analyseur. Vous trouverez peu de données objectives, formelles ou expérimentales à ce sujet (il y en a), mais bien d'autres affirmations. Je ne dis pas qu'il n'y a rien d'intéressant. Il y a quelques idées intelligentes.

Maintenant, une fois que vous connaissez l'idée de base, les "optimisations" ou améliorations peuvent souvent être introduites statiquement (éventuellement de manière incrémentielle) en construisant un automate déroulant à partir de la grammaire, en suivant le type de technique de construction d'analyseur qui vous intéresse, puis en appliquant la construction de produits croisés pour l'intersection avec cet automate (presque la même chose que le faire avec la grammaire) ou avec une grammaire dérivée de cet automate.

Ensuite, vous pouvez introduire des cloches et des sifflets, mais ce sont principalement des détails technologiques.

Les Philosophiæ Naturalis Principia Mathematica d'Isaac Newton seraient un grand morceau de physique et de mathématiques. Je ne pense pas que ce soit sur la liste de lecture de nombreux étudiants. Toutes choses étant égales par ailleurs, je ne pense pas qu'il soit très utile d'enseigner l'algorithme d'Earley, bien qu'il s'agisse d'un élément historique important. Les élèves ont suffisamment à apprendre tels quels. Au risque d'être abattu par de nombreuses personnes, je pense à peu près la même chose pour le papier Knuth LR (k). C'est un superbe morceau d'analyse théorique, et probablement une lecture importante pour un théoricien. Je doute fortement qu'il soit si essentiel pour la construction d'analyseurs, étant donné l'état actuel de la technologie, à la fois matérielle et logicielle. Les temps sont révolus où l'analyse était une partie importante du temps de compilation, ou lorsque la vitesse des compilateurs était un problème critique (je connaissais une entreprise décédée des coûts de compilation il y a une trentaine d'années). Le spécialiste de l'analyse peut vouloir apprendre ces connaissances spécialisées à un moment donné, mais l'étudiant moyen en informatique, en programmation ou en ingénierie n'en a pas besoin.

Si les élèves doivent consacrer plus de temps à l'analyse, il existe d'autres extensions qui pourraient être plus utiles et plus formatrices, comme celles utilisées en linguistique computationnelle. Le premier rôle de l'enseignement est d'extraire les idées simples qui structurent les connaissances scientifiques, et non de forcer les étudiants à subir les souffrances des chercheurs (doctorants exceptés: c'est un rite de passage :-).

Licence CC BY-SA 3.0 de l'auteur

babou
la source
2
"Earley ... est beaucoup trop compliqué pour l'enseignement et pourrait être remplacé par des algorithmes plus simples ...". Pourriez-vous fournir un exemple d'un algorithme aussi simple?
wjl
@wjl Je vous réponds dans un addendum à la réponse ci-dessus. Je ne pointe pas vers un algorithme spécifique bien que vous puissiez en trouver dans la littérature si vous effectuez une recherche comme je le recommande. J'ai plutôt essayé d'expliquer pourquoi il est très facile de créer des algorithmes plus simples mais efficaces. Earley's est probablement le plus complexe de tous. Expliquant le Bar Hillel et al. la construction est d'environ une demi-page de manuel, disons une page avec la preuve.
babou
@wjl Répondre à votre demande m'a pris du temps. Cela vous a-t-il aidé? . . . . . Si vous vouliez un algorithme réel, il y en a un dans le dernier lien de la question initiale.
babou
Oui merci; J'apprécie le détail supplémentaire. Je travaille sur une bibliothèque d'analyseurs généralisés pour certains travaux que je fais et j'ai fait une tonne de recherches sur différents algorithmes. Je penche actuellement vers une implémentation de style précoce car, pour moi, il semblait être un algorithme très facile à comprendre, et il est facile de l'étendre aux grammaires conjonctives et aux terminaux "boîte noire" (éventuellement sensibles au contexte). J'ai parcouru et imprimé certains des documents que vous avez mentionnés; mais je ne les ai pas encore sérieusement lues.
wjl
@wjl Si c'est ce que vous faites, vous devriez examiner les sujets suivants: langages légèrement sensibles au contexte, systèmes de réécriture sans contexte linéaire (LCFRS) et grammaires de concaténation de plages. Je ne suis pas sûr de comprendre ce qu'est un terminal "boîte noire". - - email: babou sur email.com. - -
babou
5

L'article qui décrit comment construire une forêt d'analyse binarisée en temps cubique (mentionné dans l'article de Angelo Borsotti) est: "Analyse de style SPPF à partir de Earley Recognizers" par Elizabeth Scott. Vous pouvez le trouver ici: http://dx.doi.org/10.1016/j.entcs.2008.03.044

Dans cet article, la construction d'une forêt d'analyse partagée (SPPF) partagée est décrite, qui représente tous les arbres d'analyse possibles. Les sous-arbres sont partagés chaque fois que possible, et les nœuds correspondant à différentes dérivations de la même sous-chaîne à partir du même non-terminal sont combinés.

eider
la source
Merci pour le pointeur. La construction de forêts d'analyse binarisées en temps cube est standard. La binarisation est le seul moyen d'obtenir le temps cubique, de sorte que la remarque du PO sur la complexité par rapport à la taille de la grammaire n'est pas pertinente. Un autre problème est de comprendre de quelle manière la forêt d'analyse est binarisée. Cela peut dépendre de l'algorithme. D'autres problèmes sont la quantité de partage dans la forêt partagée et l'efficacité pratique de la stratégie d'analyse (Earley peut être une mauvaise idée). Tout cela est développé dans la dernière référence du PO. Une vue formelle générale de la question est esquissée dans ma réponse.
babou
1

Je voudrais faire écho aux réponses ci-dessus en vous suggérant de lire ce document:

http://dx.doi.org/10.1016/j.entcs.2008.03.044

Je voudrais cependant nuancer en disant que j'ai implémenté l'algorithme dans cet article et je pense qu'il y a une erreur. En particulier, la première phrase du deuxième paragraphe de la section 4. Les étiquettes de prédécesseur que vous faites pour ce qu'Earley appellerait la phase de "numérisation" devraient pointer de p à q et non l'inverse.

En particulier, la ligne suivante:

Réglez E0 pour être les éléments (S :: = · α, 0). Pour i> 0 initialiser Ei en ajoutant l'item p = (A :: = αai · β, j) pour chaque q = (A :: = α · aiβ, j) ∈ Ei − 1 et, si α =, créer un pointeur prédécesseur nommé i - 1 de q à p

Devrait lire "de p à q" et non "de q à p"

J'ai implémenté l'algorithme comme il est indiqué à l'origine, ce qui m'a donné des erreurs sur certains cas de test fabriqués à la main, qui ont été corrigés une fois que j'ai changé la direction du pointeur ici.

Jeremy Dohmann
la source