Back Алгоритъм на Ерли Bulgarian Earleyův analyzátor Czech Earley-Algorithmus German Earley parser English Algoritmo de Earley Spanish تجزیه ایرلی Persian Analyse Earley French アーリー法 Japanese Algoritmo Earley Portuguese Алгоритм Эрли Russian

Algorytm Earleya

Algorytm Earleya – algorytm służący do analizy składniowej na podstawie dowolnej gramatyki bezkontekstowej. Stosuje się go między innymi do przetwarzania języków naturalnych[1][2], gdyż inaczej niż większość algorytmów analizy składniowej działa również z gramatykami niejednoznacznymi. Korzysta się też z niego przy tworzeniu interpreterów i kompilatorów języków programowania, zwłaszcza języków specjalizowanych, ponieważ szkielety projektowe oparte na tym algorytmie ułatwiają szybkie tworzenie prototypów (RAD)[3][4].

Górne ograniczenie czasu analizy n symboli terminalnych przez parser oparty na tym algorytmie rośnie proporcjonalnie do n3 w ogólnym przypadku, do n2 dla gramatyk jednoznacznych i do n dla sporej klasy gramatyk bezkontekstowych, w tym większości gramatyk języków programowania.

Algorytm ten opracował w 1968 roku Jay Earley z Carnegie Mellon University w swojej pracy doktorskiej[5] promowanej przez Roberta W. Floyda. W 1970 roku Earley opublikował go w Communications of the ACM w artykule[6], który w 1983 roku zaliczono do 21 najbardziej znaczących publikacji w ćwierćwieczu istnienia tego czasopisma[7].

  1. ↑ Stephen McConnel: PC-PATR Reference Manual. 1995-10-30. [dostęp 2008-12-25]. [zarchiwizowane z tego adresu (2005-09-11)].
  2. ↑ Pierre Boullier, Benoît Sagot: Efficient and robust LFG parsing: SXLFG. W: Proceedings of the Ninth International Workshop on Parsing Technology. Vancouver: 2005, s. 1–10.
  3. ↑ John Aycock, Compiling Little Languages in Python, [w:] Proceedings of the 7th International Python Conference, Houston 1998 [zarchiwizowane z adresu 2006-07-08].
  4. ↑ Laurence Tratt. Domain Specific Language Implementation via Compile-Time Meta-Programming. „ACM Transactions on Programming Languages and Systems (TOPLAS)”. Październik 2008. 30(6). s. 1–40. ISSN 0164-0925. 
  5. ↑ Jay Earley: An Efficient Context-Free Parsing Algorithm. Pittsburgh: Carnegie-Mellon University, Computer Science Department, 1968.
  6. ↑ Jay Earley. An Efficient Context-Free Parsing Algorithm. „Communications of the ACM”. Luty 1970. 13(2). s. 94–102. ISSN 0001-0782. [zarchiwizowane z adresu 2005-12-10]. 
  7. ↑ Jay Earley. An Efficient Context-Free Parsing Algorithm. „Communications of the ACM”. Styczeń 1983. 26(1). s. 57–61. ISSN 0001-0782. 
From Wikipedia, the free encyclopedia · View on Wikipedia

Developed by razib.in