Biorąc pod uwagę ciąg i CFG, jakie znaki mogą podążać za ciągiem (w sentymentalnych formach CFG)?

10

Niech Σ będzie zbiorem terminali, a N zbiorem nieterminalnych symboli gramatyki bez kontekstu G.

Powiedzieć, że posiada ciąg a(ΣN)+ taki, że w którym i są zdaniowymi formy .x , y ( Σ N ) S ( G ) GxayS(G)x,y(ΣN)S(G)G

Biorąc pod uwagę , chciałbym ustalić zestaw .C = { b w a b z S ( G ) , b Σ N }Gdo={bwzabzS.(sol),bΣN.}

Aby wyjaśnić, w tym przypadku są ciągami terminali i nieterminali, a ma długość jeden.bw,x,y,z,za,bb

Widzę, jak to zrobić, jeśli jest również jeden; każdy jest członkiem następującego zestawu a (w tym nie-terminali).bzabza

Jestem jednak ciekawy, czy jest to możliwe dla sekwencji znaków. Na mój wniosek, ciąg nie jest znacznie dłuższy niż prawej strony produkcji w G .zasol

Rozróżnienie między terminalami i nie-terminalami jest nieco nieme w mojej aplikacji, ponieważ używam gramatyki generatywnej; i wierzę, że nie spowoduje to większych kłopotów, ponieważ ma długość jeden.b

Tomasz
źródło
1
Jaka jest twoja aplikacja? Budujesz parser?
Raphael
Czy możemy założyć, że gramatyka ma jakąkolwiek normalną formę, czy też musi działać dla dowolnych?
Raphael
@AlextenBrink - i y są dowolnymi łańcuchy. Patrzę tylko na fragment / podciąg. xy
Thomas
@Raphael - Próbuję zautomatyzować transformacje gramatyki L-System ... więc nie jest w normalnej formie. W rzeczywistości ponownie zmienię to pytanie, aby było bardziej precyzyjne.
Thomas
Mam nadzieję, że nie zmieniłem zbytnio pytania - ma ono teraz nieco inną naturę.
Thomas

Odpowiedzi:

6

Opiszę algorytm, który działa. Czas działania nie powinien być taki zły. Możesz również obliczyć sporo tego.

zaxyzaZAZA

zazax

Używamy adaptacji algorytmu Earleya . Najpierw musisz zrozumieć ten algorytm. Nasz algorytm działa prawie w ten sam sposób, z tym wyjątkiem, że nasze kroki inicjalizacji i zakończenia są różne.

za1za

Teraz wykonujemy algorytm Earley osobno dla każdego możliwego takiego początkowego przedmiotu Earley. Nie możemy po prostu zrobić wszystkich z nich jednocześnie, ponieważ parsowania mogą kolidować ze sobą. Nie widzę tutaj szybszej metody niż cofanie się.

L.ZAL.R(1)L.ZAL.R(1)

L.ZAL.R(1)

za

Edycja: Myślę, że znalazłem metodę, która usuwa większość narzutu wprowadzonego przez powrót. Z każdym elementem Earley kojarzymy zestaw identyfikatorów, które są łańcuchami, ponieważ będziemy musieli używać prefiksów tych identyfikatorów. Podczas inicjalizacji dodajemy wszystkie początkowe elementy do zestawu Earley i kojarzymy unikalny identyfikator z każdym zestawem.

Na etapach skanera i predyktora identyfikatory są przenoszone na nowe elementy. Elementy Earley w tym samym zestawie Earley, które różnią się jedynie identyfikatorami, są łączone ze sobą poprzez łączenie ich identyfikatorów. Pamiętaj, że możemy wykonać kroki skanera i predyktora na tych nowych elementach z identyfikatorami, bez konieczności wykonywania tego kroku dla każdego identyfikatora osobno.

L.ZAL.R(1)

Zasadniczo wykonujemy cofanie za pomocą tych identyfikatorów, aby nie wykonywać podwójnej pracy w krokach skanera i predyktora.

Alex ten Brink
źródło
zaza
@Thomas Nie jest to zbyt trudne: po prostu uważasz, że nieterminal jest terminalem dla tej konkretnej pozycji w analizie: nadal przewidujesz i wypełniasz go normalnie, ale również bierzesz to pod uwagę podczas skanowania.
Alex ten Brink
Tak, w rzeczy samej - teraz, kiedy rozumiem twoje rozwiązanie, nie powinno to mieć znaczenia.
Thomas