Dlaczego Tomita stworzył GLR i nie używał Earleya?


11

Kiedy patrzę na parsowanie Earleya, wygląda to bardzo elegancko i zastanawiam się, dlaczego techniki GLR stały się popularne? Czy ktoś wie, co było nie tak z analizowaniem Earleya przez to, że Tomita stworzyła GLR? Wydajność? Wszelkie publikacje dotyczące tych dyskusji są bardzo mile widziane.


5
GLR pozwala na deterministyczne analizowanie fragmentów gramatyki. Zobacz na przykład Elkhound ( scottmcpeak.com/elkhound ), gdzie przyjęto ten pomysł. Jednak w przypadku języków naturalnych nie jest jasne, czy GLR jest lepszy od Earleya.
Sylvain,

1
@Sylvain: brzmi dla mnie jak odpowiedź ...
Joshua Grochow

Odpowiedzi:


5

Lepiej późno niż wcale.

Jeśli dobrze rozumiem, Earley jest odgórny i poświęci czas i pamięć na tworzenie przedmiotów Earley dla każdej produkcji w danym S (i). Oznacza to, że dla języka naturalnego w S (0) tworzymy i sprawdzamy element Earley dla każdego możliwego słowa, które rozpoczyna zdanie, a jest ich całkiem sporo.

Ale GLR jest oddolny, więc zakładając, że efektywnie zaszyfrowane są tabele / wyszukiwania stanu, pierwszy token wybiera kolejne przejścia w stałym czasie.

Dotyczy to w szczególności języków naturalnych z ogromną liczbą różnych produkcji. Ale niezbyt znaczący dla języków programowania, z bardzo małym zestawem produkcji.

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.