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!
la source
Réponses:
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.
la source
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.
la source
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
la source
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.
la source
Je voudrais faire écho aux réponses ci-dessus en vous suggérant de lire ce document:
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:
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.
la source