Pytania otagowane jako parsers

Pytania o algorytmy decydujące o tym, czy dany ciąg należy do ustalonego języka formalnego.

1
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.
2
Czy istnieje inna rozdzielczość problemu „zwisające inaczej” niż „najbliższy odpowiednik”?
Poniższa gramatyka bezkontekstowa przedstawia dwuznaczność typu „wiszące inne” (wyobraź to sobie zaaaoznacza if expr thenibbboznacza elseidocc oznacza inny rodzaj instrukcji lub bloku): S.→ a S.b S.|a S.|doS→aSbS|aS|c \begin{aligned} S &\rightarrow aSbS \;|\; aS \;|\; c\\ \end{aligned} Na przykład, a a c b caacbcaacbc może być analizowany jako ( ( C …
1
Jak zrekonstruować las drzew składniowych z wektora Earley?
Użycie wektora Earleya jako rozpoznającego jest dość proste: po osiągnięciu końca struny wystarczy sprawdzić, czy produkcja aksjomatyczna została rozpoczęta w pozycji 0. Jeśli masz przynajmniej jeden ciąg, łańcuch jest akceptowany. Użycie wektora Earleya do odtworzenia drzewa przetwarzania jest mniej oczywiste. Właściwie nie jestem w stanie ustalić, jak mogłaby działać procedura …
2
Dwustanowa maszyna Turinga do dopasowywania nawiasów
Na studiach poznawaliśmy ogólnie teorię obliczeń, a dokładniej maszyny Turinga. Jednym z wielkich wyników teoretycznych jest to, że kosztem potencjalnie dużego alfabetu (symboli) można zmniejszyć liczbę stanów do zaledwie 2. Szukałem przykładów różnych maszyn Turinga, a częstym przedstawionym przykładem jest dopasowywanie / sprawdzanie nawiasów. Zasadniczo sprawdza, czy ciąg nawiasów, np. …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.