Étant donné une chaîne et un CFG, quels caractères peuvent suivre la chaîne (dans les formes sententielles du CFG)?

10

Que l'ensemble des terminaux et N l'ensemble des symboles non-terminaux de la grammaire hors-contexte G .ΣNg

Disons que j'ai une chaîne telle que où et sont les formes phrastiques de .une(ΣN)+x , y ( Σ N ) S ( G ) GXuneyS(g)X,y(ΣN)S(g)g

Étant donné , je voudrais déterminer un ensemble .C = { b w a b z S ( G ) , b Σ N }gC={bwunebzS(g),bΣN}

Pour clarifier, dans ce cas, sont des chaînes de terminaux et de non-terminaux et est de longueur un.bw,x,y,z,a,bb

Je peux voir comment faire si est également de longueur un; chaque est membre de l'ensemble suivant de (y compris les non-terminaux).b aunebune

Cependant, je suis curieux de savoir si c'est possible pour une séquence de caractères. Pour mon application, la chaîne n'est pas beaucoup plus longue que le côté droit des productions en .Guneg

La distinction entre terminaux et non-terminaux est quelque peu muette dans mon application car j'utilise une grammaire générative; et je crois que cela ne causera pas beaucoup de problèmes car est de longueur un.b

Thomas
la source
1
Quelle est votre candidature? Êtes-vous en train de construire un analyseur?
Raphael
Pouvons-nous supposer que la grammaire a une forme normale ou doit-elle fonctionner pour des expressions arbitraires?
Raphael
@AlextenBrink - et y sont des chaînes arbitraires. Je regarde juste un fragment / sous-chaîne. Xy
Thomas
@Raphael - J'essaie d'automatiser les transformations des grammaires du L-System ... donc ce n'est pas sous une forme normale. En fait, je modifierai à nouveau cette question pour la rendre plus précise.
Thomas
J'espère que je n'ai pas trop changé la question - elle a une nature légèrement différente maintenant.
Thomas

Réponses:

6

Je vais décrire un algorithme qui fonctionne. Son temps de course ne devrait pas être trop mauvais. Vous pouvez également précalculer une bonne partie de cela.

Je suppose que ne contient pas de non-terminaux (bien qu'il soit probablement facile de s'adapter à ce cas) et que vous ne connaissez pas x , y ou la dérivation de a . Je suppose également que votre grammaire ne contient pas de productions qui ne sont jamais utilisées dans aucune dérivation ( A A par exemple).uneXyuneUNEUNE

Le problème principal est vraiment d'analyser , car vous voulez savoir dans quel type d'états vous vous retrouvez, afin de savoir ce qui peut suivre un . Ce n'est pas aussi facile que vous ne connaissez pas x .uneuneX

Nous utilisons une adaptation de l'algorithme d' Earley . Vous voudrez d'abord comprendre cet algorithme. Notre algorithme fonctionne presque de la même manière, sauf que nos étapes d'initialisation et d'achèvement sont différentes.

Pour l'initialisation, nous semons notre premier ensemble avec un élément Earley pour chaque occurrence d' (le premier caractère en a ) dans toute production de votre grammaire. Nous avons défini le pointeur arrière de cet élément sur -1, une valeur non valide. Ceci est important dans notre version modifiée. Essentiellement, le -1 signifie «Je n'ai aucune idée de l'endroit où cette production a commencé».une1une

Maintenant, nous effectuons l'algorithme Earley séparément pour chaque élément Earley initial possible. Nous ne pouvons pas simplement les faire tous en même temps, car les analyses peuvent interférer les unes avec les autres. Je ne peux pas facilement voir une méthode plus rapide que de revenir en arrière ici.

Pour l'étape d'achèvement, nous n'avons qu'à apporter une modification pour gérer -1 pointeurs arrière. Comme nous avons terminé une production dont nous ne connaissons pas l'origine, nous sommes en difficulté. Cependant, la méthode utilisée pour calculer les ensemblesLUNELR(1) d' anticipation L A L R ( 1 ) par Pennello et DeRemer nous sauve: ce dont nous avons besoin ici, c'est exactement les ensembles d' anticipation . Chaque élément de ces ensembles d'anticipation a une position correspondante dans la grammaire, ce qui correspond à son tour à une poursuite possible de la production terminée.LUNELR(1)

LUNELR(1)

une

Edit: Je pense que j'ai trouvé la méthode qui supprime la plupart des frais généraux introduits par le retour arrière. Nous associons à chaque élément Earley un ensemble d'identifiants, qui sont des chaînes, car nous devrons utiliser des préfixes de ces identifiants. Lors de l'initialisation, nous ajoutons tous les éléments initiaux à l'ensemble Earley et associons un identifiant unique à chaque ensemble.

Sur les étapes du scanner et du prédicteur, les identifiants sont reportés sur les nouveaux éléments. Les éléments Earley du même ensemble Earley qui ne diffèrent que par leurs identifiants sont fusionnés en fusionnant leurs identifiants ensemble. Notez que nous pouvons effectuer des étapes d'analyse et de prédiction sur ces nouveaux éléments avec des identifiants, sans avoir à effectuer cette étape séparément pour chaque identifiant.

LUNELR(1)

Essentiellement, nous effectuons le retour en arrière en utilisant ces identifiants, afin de ne pas faire de double travail dans les étapes du scanner et du prédicteur.

Alex ten Brink
la source
uneune
@Thomas Ce n'est pas trop difficile: vous considérez simplement que le non-terminal est un terminal pour cette position particulière dans l'analyse: vous le prédisez et le complétez toujours normalement, mais vous le considérez également lors de la numérisation.
Alex ten Brink
Oui, en effet - maintenant que je comprends votre solution, cela ne devrait plus faire de différence.
Thomas