Niech będzie zbiorem terminali, a zbiorem nieterminalnych symboli gramatyki bez kontekstu .
Powiedzieć, że posiada ciąg taki, że w którym i są zdaniowymi formy .x , y ∈ ( Σ ∪ N ) ∗ S ( G ) G
Biorąc pod uwagę , chciałbym ustalić zestaw .C = { b ∣ w a b z ∈ S ( G ) , b ∈ Σ ∪ N }
Aby wyjaśnić, w tym przypadku są ciągami terminali i nieterminali, a ma długość jeden.b
Widzę, jak to zrobić, jeśli jest również jeden; każdy jest członkiem następującego zestawu a (w tym nie-terminali).b
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 .
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.
Odpowiedzi:
Opiszę algorytm, który działa. Czas działania nie powinien być taki zły. Możesz również obliczyć sporo tego.
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.
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ę.
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.
Zasadniczo wykonujemy cofanie za pomocą tych identyfikatorów, aby nie wykonywać podwójnej pracy w krokach skanera i predyktora.
źródło