Nigdy nie potrzebujesz CNF. Ma tę wadę, że zmienia strukturę gramatyki. Ale trzeba wprowadzić pośrednie nieterminale, aby żadna prawa strona nie była dłuższa niż 2 (forma 2), ponieważ długość RHS determinuje złożoność. Najlepszą próbą wyjaśnienia tego intuicyjnie jest, jeśli pamięć służy, artykuł Beau Shiel, „Observations on Context Free Parsing”, opublikowany w 1976 r. Na konferencji lingwistyki obliczeniowej. Algorytm Earleya domyślnie używa 2-form. Jest po prostu ukryty w algorytmie. Jeśli chodzi o odzyskiwanie i obsługę parsowania lasu, powinieneś spojrzeć na sieć w „parsowaniu lasu przecięcia”. To jest naprawdę bardzo proste. Wiele artykułów znajduje się w Internecie, jeśli otrzymujesz (z cytatów lub spisów treści) tytuły lub autorów, aby bezpośrednio je przeszukać.
W rzeczywistości możesz zrobić znacznie więcej niż CF i nadal uzyskać parse-lasy w czasie wielomianowym. Czasami pojawia się pytanie: co możesz z tym zrobić, kiedy już go masz?
Jednym z celów ostatniego wspomnianego artykułu jest pokazanie, że złożone algorytmy (takie jak GLR) niekoniecznie kupują cokolwiek w czasie lub w przestrzeni i mogą zmienić parsowany las.
Jedna uwaga na temat nauczania. Myślę, że Earley, choć przełomowy, jest zbyt skomplikowany do nauczania i można go zastąpić prostszymi algorytmami o zasadniczo takich samych treściach edukacyjnych. Nauczanie dotyczy pojęć lub technologii. W algorytmie Earleya podstawowe pojęcia są ukryte w złożoności szczegółów, a z technologicznego punktu widzenia są przestarzałe. To był świetny artykuł, ale to nie znaczy, że jest to najlepsze podejście pedagogiczne.
W literaturze z zakresu językoznawstwa komputerowego może być więcej informacji niż w zwykłych kanałach informatycznych. Nie mam książki Ceriel-Grune-Jacobs, ale byłbym zaskoczony, gdyby nie mieli wszystkich odpowiednich referencji (choć nie jestem pewien co do ich kryteriów wyboru).
Uzupełnienie w następstwie wniosku w komentarzu (7 lipca 2013 r.)
To uzupełnienie dotyczy istnienia prostszych algorytmów niż Earley.
Jak już powiedziałem, wyszukiwanie w Internecie w „parsing intersection forest” powinno szybko dać ci referencje, z których możesz kopać dalej.
Podstawową ideą jest to, że wszystkie ścieżki analizujące z budową wspólnego lasu to nic innego jak stara konstrukcja skrzyżowania Bar Hillel, Perles i Shamir dla zwykłego języka i języka bezkontekstowego, przy użyciu skończonego automatu i gramatyki bezkontekstowej. Biorąc pod uwagę gramatykę CF, zastosujesz konstrukcję do trywialnego automatu, który rozpoznaje tylko twój ciąg wejściowy. To wszystko. Wspólny las to tylko gramatyka skrzyżowania. Jest on związany z oryginalną gramatyką poprzez homomorfizm, rozpoznaje tylko podany ciąg, ale ze wszystkimi parsami oryginalnej gramatyki aż do tego homomorfizmu (tj. Prosta zmiana nazwy nieterminalnych).
Powstała gramatyka zawiera wiele niepotrzebnych rzeczy, nieterminale i reguły, które są albo nieosiągalne z aksjomatu (nie można go znaleźć w ciągu pochodzącym od początkowego symbolu), albo które są nieproduktywne (nie można ich wyprowadzić do terminala strunowy).
Następnie albo musisz go wyczyścić dobrym pędzlem na końcu (być może długim, ale algorytmicznie prostym), albo możesz spróbować ulepszyć konstrukcję, aby na końcu było mniej bezużytecznego puchu.
Na przykład konstrukcja CYK jest dokładnie taka, ale zorganizowana w taki sposób, że wszystkie utworzone reguły i nieterminale są produktywne, chociaż wiele może być nieosiągalnych. Tego należy się spodziewać po technice oddolnej.
Techniki odgórne (takie jak oparte na LR (k)) pozwolą uniknąć nieosiągalnych reguł i terminali, ale stworzą nieproduktywne.
Myślę, że dużo szczotkowania można osiągnąć poprzez odpowiednie użycie wskaźników, ale nie patrzyłem na to przez długi czas.
Wszystkie istniejące algorytmy są zgodne z tym modelem. To jest naprawdę sedno sprawy i jest bardzo proste. Dlaczego więc pogrzebać to w złożoności?
W literaturze zaproponowano wiele „optymalizacji” często opartych na rodzinie parserów LR (k), LL (k), być może z pewnym statycznym faktoringiem tych konstrukcji (Earley nie ma faktorowania statycznego). Można go faktycznie zastosować do wszystkich znanych technik, w tym do starych analizatorów pierwszeństwa. Umieszczam „optymalizację” między cudzysłowami, ponieważ zwykle nie jest jasne, co optymalizujesz, ani nawet czy tak naprawdę optymalizujesz, czy też korzyść z ulepszenia jest warta większej złożoności twojego parsera. Na ten temat znajdziesz niewiele obiektywnych danych, formalnych lub eksperymentalnych (jest ich kilka), ale wiele innych twierdzeń. Nie twierdzę, że nie ma nic interesującego. Istnieje kilka inteligentnych pomysłów.
Teraz, gdy poznasz podstawowy pomysł, „optymalizacje” lub ulepszenia mogą być często wprowadzane statycznie (być może przyrostowo) poprzez zbudowanie automatyki przesuwającej z gramatyki, zgodnie z interesującą Cię techniką budowy parsera, a następnie zastosowanie konstrukcja krzyżowa produktu dla skrzyżowania z tym automatem (prawie to samo, co robienie tego z gramatyką) lub gramatyki wyprowadzonej z tego automatu.
Następnie możesz wprowadzić dzwonki i gwizdki, ale są to głównie szczegóły technologiczne.
Philosophiæ Naturalis Principia Mathematica Izaaka Newtona jest podobno wielkim dziełem fizyki i matematyki. Nie sądzę, że jest na liście czytelniczej wielu studentów. Ponieważ wszystkie inne rzeczy są równe, nie sądzę, aby nauczanie algorytmu Earleya było bardzo przydatne, chociaż jest to ważny kawałek historyczny. Studenci mają wystarczająco dużo do nauczenia się. Ryzykując, że zostanie zestrzelony przez wiele osób, myślę tak samo w przypadku artykułu Knuth LR (k). Jest to znakomity fragment analizy teoretycznej i prawdopodobnie ważna lektura dla teoretyka. Głęboko wątpię, czy jest to tak istotne dla budowy parserów, biorąc pod uwagę obecny stan technologii, zarówno sprzętu, jak i oprogramowania. Minęły czasy, kiedy parsowanie było znaczącą częścią czasu kompilacji, lub gdy szybkość kompilatorów była krytycznym problemem (znałem jedną korporację, która zmarła z powodu kompilacji kosztów jakieś 30 lat temu). Specjalista od analizy może chcieć nauczyć się tej wiedzy specjalistycznej w pewnym momencie, ale przeciętny student informatyki, programowania lub inżynierii jej nie potrzebuje.
Jeśli uczniowie muszą spędzać więcej czasu na analizie, istnieją inne rozszerzenia, które mogą być bardziej przydatne i bardziej kształtujące, takie jak te używane w językoznawstwie komputerowym. Pierwszą rolą nauczania jest wydobycie prostych pomysłów, które kształtują wiedzę naukową, a nie zmuszanie studentów do cierpienia tego, co musieli ponieść naukowcy (z wyjątkiem doktorantów: jest to rytuał przejścia :-).
Licencja CC BY-SA 3.0 od autora