Czy parser Earleya można przekształcić w rozmyty parser podobny do Levenshtein Automata Algo dla DFA?

Istnieje sposób wykonywania rozmytego parsowania (akceptuje ciągi nawet w literówkach do określonej odległości edycji), z DFA i skonstruowanymi w czasie wykonywania automatami Levenshtein słowa wejściowego. Czy coś podobnego można zrobić z parserem Earley? Trudno mi zrozumieć algorytm, a co dopiero odpowiedzieć na to pytanie.

Odpowiedź brzmi tak. Nie zrobiłbym tego jednak z parserem Earley, ponieważ są prostsze z tymi samymi możliwościami.

Zasadniczo, parser Earley należy do rodziny ogólnych parserów bezkontekstowych, które produkują wszystkie możliwe analizy dla danego łańcucha, gdy gramatyka jest niejednoznaczna.

Istnieją dwa sposoby (przynajmniej) zrozumienia tych parserów:

• jako dynamiczna interpretacja programowania automatu odpychającego odpowiadającego gramatyce ciągu wejściowego;

• jako konstrukcja przecięcia gramatyki z automatem skończonym.

$w$$|w|+1$$A$$G$$F$$\mathcal L(A)\cap\mathcal L(G)$$F$$G$, aż do zmiany nazw terminali innych niż terminale (z powodu różnych produktów).

$A$$F$$\mathcal L(G)$$\emptyset$$G$

$F$

Ale, jak widzisz, uogólnia to na analizowanie całego regularnego zestawu, jeśli ktoś jest tego zainteresowany.

$w$$w$

$G$$F$

Jeśli jest to pożądane, można to wykorzystać do zachowania tylko łańcuchów przy minimalnej odległości.

Można to jednak nieco poprawić, ponieważ kompozycja za pomocą automatów skończonych jest asocjacyjna.

$G$$w$$\Sigma^*$

Łatwo byłoby przycinać tę konstrukcję, aby uzyskać ten sam wynik jak poprzednio, ale najlepszym sposobem jest bardziej kontrolowana konstrukcja skrzyżowania, taka jak dynamiczna organizacja programowania używana przez większość parserów w literaturze, w tym Earleya, i używaj jej, aby uniknąć generowania niepotrzebna reguła, obliczając odległości i przerywając dowolną ścieżkę obliczeniową, gdy przekroczy ona pożądany próg. Programowania dynamicznego można również użyć do bezpośredniego obliczenia parsowania lasu (lub parsowania drzewa) dla ciągu, który ma najkrótszą odległość od danych wejściowych.