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

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?

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 où 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(n^3)$$n$$O(n^2)$

Le pire cas de complexité temporelle est , comme cela est bien connu.$O(n^3)$

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'à où $O(n^{s+1})$$s$est 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\rightarrow \alpha D.\beta \; g$$D$$D\rightarrow \gamma. \; f$$D$$\gamma$$E\rightarrow \alpha D.\beta \; g$$\gamma$$D$

$f$$g$$f$$D\rightarrow \gamma$$g$

$D$$E\rightarrow \alpha D.\beta \; g$$w$$f+1$$g$$w_{f+1:g}$$D$$D\rightarrow \gamma$$D\rightarrow \gamma. \; f$$D$

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.

$U\rightarrow XYZ$$W\rightarrow UV$

$w_{f+1:g}$$X$$w_{g+1:h}$$Y$$w_{h+1:i}$$w_{h+1:j}$$Z$$U\rightarrow XYZ$$w_{f+1:i}$$w_{f+1:j}$$U$

$w_{i+1:k}$$w_{j+1:k}$$V$$W\rightarrow UV$$w_{f+1:k}$$W$

$w_{f+1:g}$$w_{g+1:h}$$X$$Y$$U$$U\rightarrow XYZ$$U\rightarrow XY.Z \; f$$S_h$$Z$$W\rightarrow UV. \; f$$S_k$

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.