Comment reconstruire la forêt d'arbres syntaxiques à partir du vecteur Earley?

9

L'utilisation du vecteur Earley comme identificateur est assez simple: lorsque la fin de la chaîne est atteinte, il vous suffit de vérifier si la production axiomatique terminée a commencé à la position 0. Si vous en avez au moins une, la chaîne est acceptée.

L'utilisation du vecteur Earley pour reconstruire le ou les arbres d'analyse est moins évidente. En fait, je ne peux pas comprendre comment une procédure algorithmique fonctionnerait, d'ailleurs les seules références que j'ai trouvées étaient soit vagues, soit super-techniques. Quelqu'un pourrait-il nous éclairer?

Stefano Sanfilippo
la source
2
Il serait utile que vous énumériez les références que vous avez trouvées, que vous pensiez vagues et que vous pensiez trop techniques. Sinon, la réponse sera probablement un pointeur vers les références que vous avez déjà trouvées.
Wandering Logic
1
Il se peut que ce que vous appelez vecteur ne soit pas ce que Earley appelle vecteur dans son article d'origine. Ou il se peut qu'elle ne joue pas exactement le même rôle. Les auteurs introduisent des variations dans les algorithmes. Il n'y a aucun moyen de le savoir puisque vous ne faites aucune référence aux documents que vous utilisez ... et nous ne pouvons pas y avoir accès de toute façon. Ce qui peut aider, c'est d'être plus explicite sur les définitions. En répondant, j'ai simplement supposé que vous utilisiez les mêmes définitions que celles d'Earley.
babou
@babou, ce que j'ai appelé "vecteur Earley" est la représentation tabulaire de la structure de données construite par l'analyseur. C'était le terme utilisé par mon professeur de langues officielles en y faisant référence. Il convient de noter que ma langue principale n'est pas l'anglais, donc cela pourrait être juste une mauvaise tentative de traduction de la terminologie. La référence technique que j'ai mentionnée est le document d'Earley lui-même. Je l'ai approché, mais c'était un peu intimidant pour un vrai débutant comme moi.
Stefano Sanfilippo
Vous voudrez peut-être vérifier si «vecteur Earley» est utilisé par votre professeur pour désigner la même structure que ce que Earley appelle «vecteur» dans son article. Peut être utile pour communiquer. Pour le reste, comme vous pouvez le voir, vous devez conserver des informations supplémentaires pour pouvoir récupérer des arbres d'analyse, mais Earley n'entre pas vraiment dans les détails. Il existe maintenant d'autres algorithmes et je crains que la complexité de l'algorithme d'Earley ne cache quelque peu les idées clés de ce type de techniques. Bonne chance.
babou
Mes explications ont-elles été utiles ou avez-vous besoin d'une description plus détaillée de la partie technique?
babou

Réponses:

9

J'utilise la terminologie et les notations du document d' Earley . Il est possible que la description que vous lisez soit différente.

Il semble fréquent que les algorithmes d'analyse générale des CF soient d'abord présentés sous la forme d'un identificateur, puis la gestion des informations nécessaire pour réellement construire des arbres d'analyse et des forêts d'analyse est en quelque sorte ajoutée après coup. Une raison peut être que la conservation des informations nécessaires à la construction de la forêt partagée nécessite un espace cubique n est la longueur de la chaîne d'entrée analysée, mais l'espace requis n'est que le carré O ( n 2 ) pour la reconnaissance, lorsque cette information n'est pas conservée. La raison de cette augmentation de la complexité de l'espace est assez simple: la taille de la forêt d'analyse peut être cubique.O(n3)nO(n2)

Le pire cas de complexité temporelle est , comme cela est bien connu.O(n3)

La meilleure référence pour l'algorithme d' Earley est bien sûr l'article d'Earley , mais il n'est pas très explicite sur la construction de la forêt d'analyse. Cela peut en fait être une affaire désordonnée, bien plus que ce que la discussion rapide de la section 7, page 101 ne laissera apparaître. Pour être vrai, Earley ne parle pas de forêt d'analyse ou de forêt, mais d' une " représentation factorisée de tous les arbres d'analyse possibles ". Et il y a une bonne raison à cela: s'il essayait de produire une forêt en fonction de sa grammaire, sa complexité spatiale (donc temporelle) grimperait jusqu'à sO(ns+1)sest la taille de la règle la plus longue à droite. C'est pourquoi d'autres algorithmes utilisent des grammaires sous forme binaire (pas nécessairement Chomsky Normal Form (CNF)).

En fait, Earley utilise implicitement la forme binaire , car cela est nécessaire pour la complexité du temps cubique. C'est l'un des rôles majeurs du point de règle dans les États. Mais cette forme binaire implicite produit des analyses et des forêts selon la grammaire binarisée, pas selon l'originale, qui, je le crains, est une source majeure d'obscurité. Ceci est détaillé ci-dessous.

Une bonne façon de comprendre comment la forêt est obtenue est probablement de la regarder dans un cas plus simple, l'algorithme CYK . Il est également souvent décrit comme un identificateur, et l' aspect analyseur est ajouté à la fin. Vous pouvez consulter la description dans wikipedia. Les informations nécessaires pour construire la forêt sont ce qu'elles stockent dans le tableau des "backpointers". Les backpointers sont essentiellement des pointeurs vers des sous-chaînes (un symbole associé) qui forment les constituants d'une chaîne selon une règle. Ils donnent toutes les manières possibles d'analyser une sous-chaîne. Rappelons que CYK utilise une forme binaire, généralement CNF, pour que les choses soient plus simples. L'analyseur CYK a fondamentalement la même structure de programmation dynamique que Earley, mais est beaucoup plus simple. Il est donc très utile de bien le comprendre.

Pour en revenir à l'algorithme d'Earley, je ne pense pas que vous ayez besoin du vecteur d'Earley pour décider de l'acceptation ou pour construire des arbres et des forêts d'analyse. Ce que Earley appelle vecteur dans son article n'apparaît qu'à la page 97, au troisième paragraphe de la mise en œuvre. Il s'agit uniquement d'un dispositif permettant d'accélérer la recherche d'états pointant vers une position de chaîne donnée k, afin d'obtenir une meilleure complexité. Mais toutes les informations se trouvent dans les ensembles d'états, mis en œuvre sous forme de listes d'états. Cependant, ces informations ne sont pas suffisantes pour construire la forêt d'arbres d'analyse, car l'algorithme ne garde pas la trace de la ou des façons dont un état peut être obtenu. En effet, le vecteur est même utilisé pour éliminer efficacement un état déjà trouvé, indépendamment de la façon dont il a été trouvé.

Dans la section 7 de l'article d'Earley, il explique que pour "faire du reconnaisseur un analyseur", c'est-à-dire pour pouvoir récupérer des arbres d'analyse, il est nécessaire de garder une trace de la façon dont les achèvements sont effectués.

EαD.βgDDγ.fDγEαD.βgγD

fgfDγg

DEαD.βgwf+1gwf+1:gDDγDγ.fD

En supposant que vous ayez conservé tous les pointeurs nécessaires comme indiqué dans le document, vous pouvez obtenir toutes les représentations d'arbre partagées à partir du dernier symbole reconnu par l'analyseur, qui est bien sûr le symbole initial de la grammaire.

UXYZWUV

wf+1:gXwg+1:hYwh+1:iwh+1:jZUXYZwf+1:iwf+1:jU

wi+1:kwj+1:kVWUVwf+1:kW

wf+1:gwg+1:hXYUUXYZUXY.ZfShZWUV.fSk

La forêt d'arbres syntaxiques peut donc être très étrange, avec des sous-arbres jumeaux siamois qui peuvent partager les deux premiers bords d'un nœud, mais pas le troisième. En d'autres termes, il peut s'agir d'une structure très maladroite. Cela peut expliquer pourquoi Earley l'appelle " une représentation factorisée de tous les arbres d'analyse possibles ", sans être plus spécifique.

Toute tentative de séparer chirurgicalement les jumeaux siamois, sans changer la grammaire, entraînera une complexité accrue. La bonne façon de le faire est de binariser la grammaire.

J'espère que cela t'aidera. Faites le moi savoir. Mais j'insiste sur le fait qu'une bonne compréhension de l'analyse syntaxique CYK peut aider. Il existe d'autres algorithmes, plus simples que ceux d'Earley, qui peuvent analyser efficacement tous les langages CF.

Vous pouvez trouver des informations plus générales sur ce problème de forêt d'analyse dans deux autres réponses que j'ai données: /cstheory/7374#18006 et https://linguistics.stackexchange.com/questions/4619#6120 . Mais ils n'entrent pas dans les détails spécifiques de l'algorithme d'Earley.

babou
la source
En plus de l'analyse CYK, il vaut également la peine d'analyser l'analyse GLR.
Pseudonyme
1
@Pseudonym Connaître et comprendre diverses formes d'analyse générale de la mucoviscidose ne fait certainement pas de mal, et je suggère autant avec les deux références à la fin de la réponse. Cependant, mon choix de CYK n'était pas dû au hasard. Il partage avec l'algorithme d'Earley la propriété d'être interprétatif, en utilisant directement la grammaire, plutôt qu'en utilisant des tableaux produits par la compilation de la grammaire dans un automate push-down (comme dans GLR, GLL, GPrec). Par conséquent, la relation entre le processus de reconnaissance et la génération arbre / forêt est plus clairement visible. CKY est également l'algorithme le plus simple, à une exception près.
babou