Analiza Earleya



Informacje, które udało nam się zgromadzić na temat Analiza Earleya , zostały starannie sprawdzone i uporządkowane, aby były jak najbardziej przydatne. Prawdopodobnie trafiłeś tutaj, aby dowiedzieć się więcej na temat Analiza Earleya . W Internecie łatwo zgubić się w gąszczu stron, które mówią o Analiza Earleya , a jednocześnie nie podają tego, co chcemy wiedzieć o Analiza Earleya . Mamy nadzieję, że dasz nam znać w komentarzach, czy podoba Ci się to, co przeczytałeś o Analiza Earleya poniżej. Jeśli informacje o Analiza Earleya , które podajemy, nie są tym, czego szukałeś, daj nam znać, abyśmy mogli codziennie ulepszać tę stronę.

.

W teorii jzyka The algorytm Earley jest algorytm do analizowania dla gramatyk bezkontekstowych opisany po raz pierwszy przez Jay Earley . Podobnie jak algorytmy CYK i GLR, algorytm Earleya oblicza wszystkie moliwe analizy zdania (a nie tylko jedn z tych analiz). Opiera si na programowaniu dynamicznym .

Moemy zbudowa parser Earleya dla dowolnej gramatyki niekontekstowej. Dziaa w czasie szeciennym ( O (n 3 ), gdzie n jest dugoci cigu wejciowego). Dla jednoznacznej gramatyki analiz Earleya przeprowadza si w czasie kwadratowym ( O (n 2 )).

Algorytm Earleya

Rozwa gramatyk niekontekstow, a take cig wejciowy o oznaczonej dugoci . Celem analizy przez algorytm Earleya jest rozpoznanie cigu, a wic stwierdzenie, czy cig jest czci jzyka generowanego przez gramatyk.

Przedmioty Earley i stoy Earley

Algorytm Earleya manipuluje przedmiotami Earleya , zwanymi prociej przedmiotami . Przedmiotem s dane:

  • zasada tworzenia zapisanej gramatyki  ;
  • indeks pocztkowy w sowie wejciowym, taki jak ;
  • indeks pozycji po prawej stronie linijki, reprezentowany przez kropk .

Reprezentujemy pozycj w postaci , gdzie .

Zasada algorytmu

Mamy tabel rozmiarów, w której przechowujemy zestawy elementów Earley, gdzie jest dugo cigu wejciowego.

Obliczenie rozpoczyna si od uwzgldnienia elementów postaci, gdzie jest aksjomatem gramatyki i jest regu produkcji. Element reprezentuje sytuacj, w której jeszcze niczego nie rozpoznalimy, ale staramy si rozpozna aksjomat od pocztku cigu wejciowego. Nastpnie wykonujemy krok 0, 1, ..., a do kroku n.

Celem tego kroku jest obliczenie, a nastpnie zapisanie w tabeli zestawu elementów, takich jak rozpoznawany przez .

W kroku obliczymy z tabel nasycajc kolejno nastpujce trzy operacje:

  • Czytanie (skaner w jzyku angielskim). Operacja odczytu jest wykonywana dla . Do kadego elementu formularza dodajemy w pozycji . Innymi sowy, zwikszamy punkty w pozycjach, jeli poprzedza ona przeczytan liter .
  • Prognoza. Jeeli element formularza znajduje si w miejscu gdzie jest nieterminalem to dla wszystkich regu dodajemy element do zbioru . Innymi sowy, jeli trzeba rozpozna, testuje si wszystkie reguy, gdzie znajduje si w lewej czci.
  • Zakoczenie . Jeli element formularza jest , to dla wszystkich pozycji w tabeli formularza , dodajemy w . Innymi sowy, jeli rozpoznamy , rozwijamy zasady, które czekay na uznanie .

Analiza powiedzie si, jeli w tabeli znajduje si pozycja formularza , gdzie jest produkcja.

Przykad

Rozwa nastpujc gramatyk wyrae arytmetycznych:

jest aksjomatem gramatyki.

Przeanalizujmy cig wejciowy . Nastpnie otrzymujemy nastpujce tabele: Oznaczymy "P:" operacj przewidywania; "C:" operacja uzupeniania, a "L:" operacja odczytu.

W kroku 0 obliczenia rozpoczynaj si od . Nastpnie nasycamy operacj przewidywania.

P:
P:
P:
P:
P:
P:
P:
P:
P:
P:

W kroku 1 otrzymujemy operacj odczytu. Operacja przewidywania nie daje niczego, poniewa indeks pozycji znajduje si na kocu prawej czci. Element jest uywany przez operacj uzupeniania w celu pobrania , then itd. a do nasycenia operacji zakoczenia.

L:
VS:
VS:
VS:
VS:
VS:
VS:
VS:

W kroku 2 otrzymujemy operacj odczytu. Podobnie jak tu po indeksie pozycji w pierwszym wierszu , dodajemy wszystkie reguy przewidywania , z indeksem 2, który jest indeksem biecej pozycji.

L:
P:
P:
P:
P:
P:
P:
P:

W kroku 3 czytamy , wic uzupeniamy de en . Jest wic regua, wic regua jest zakoczona w .

Nasycamy przez dopenienie.

L:
VS:
VS:
VS:
VS:
VS:
VS:
VS:

Tak jak w , sowo wejciowe jest rozpoznawane.

Zoono

Zoono przestrzeni

Niech bdzie liczb odrbnych elementów z wyjtkiem pocztkowego indeksu. Mona to zwikszy za pomoc rozmiaru gramatyki: dla kadego elementu gramatyki indeks pozycji moe mie skoczon liczb miejsc, a dla kadej z tych pozycji otrzymujemy inny element. Otrzymujemy , liczc te przedmioty. W praktyce sprowadza si to do policzenia liczby moliwych lokalizacji symbolu w reguach produkcji gramatyki. W poprzednim przykadzie mamy zatem .

W tabeli kady z elementów moe pojawi si z indeksem pocztkowym midzy a . W zwizku z tym istnieje co najwyej elementy w tabeli ograniczone gdzie jest rozmiar sowa wejciowego. Dodajc do od do , otrzymujemy co najwyej elementy w tabelach. Zoono w przestrzeni jest zatem w O (n²).

Zoono czasowa (przypadek ogólny)

Przestudiujmy zoono operacji odczytu, przewidywania i uzupeniania na tablicy :

Czytanie analizuje elementy kadego w staym czasie. Biorc pod uwag rozmiar , operacja odczytu jest wykonywana w . Przewidywanie dziaa na kadym z elementów ju obecnych w staym czasie. Po przeczytaniu liczba obecnych elementów jest w , wic przewidywanie jest w . Uzupenianie dziaa na kadym elemencie obecnym w czasie w zalenoci od rozmiaru tablicy, do której odnosi si jego indeks pocztkowy. W najgorszym przypadku moemy ograniczy si do pojedynczego skanowania kadej z poprzednich tabel, co daje zoono w O (j²).

Sumujc te zoonoci na tablicach, otrzymujemy ostateczn zoono czasow w O (n 3 ).

Zoono czasowa (jednoznaczna gramatyka)

Tym, co umiecio zoono w O (n 3 ), bya czynno dopenienia. Jeli jednak gramatyka jest jednoznaczna, istnieje tylko jeden sposób uzyskania kadego elementu, a rozmiar tablicy po zakoczeniu wynosi . Tak wic kady z tych elementów mona byo uzyska tylko w czasie . Nastpnie otrzymujemy sumujc zoono czasow w O (n²).

Wariant

Analiz Earleya mona przeprowadzi za pomoc ukierunkowanego wykresu acyklicznego jako danych wejciowych, a nie cigu. Umoliwia to wprowadzanie kilku sów w bardziej zwizy sposób, a take analizowanie kilku sów jednoczenie, dziki czemu jest bardziej wydajne. Indeksy tabel s wic indeksami odpowiadajcymi topologicznemu sortowaniu grafu. Co wicej, dla wza o indeksie j, operacja odczytu ju nie uywa, ale gdzie k jest indeksem wza rodzica badanego wza.

Uwagi i referencje

  1. Jay Earley, Wydajny algorytm analizy bezkontekstowej , Communication of the ACM, 13 (2), 1970
  2.   Techniki analizowania praktyczny przewodnik Dick Grune  
  3.   Wydajny, bezkontekstowy algorytm analizy Carnegie Mellon University  
  4. Tak jest w przypadku parsera Earleya systemu SYNTAX , uywanego w parserze SxLFG dla formalizmu LFG , którego pierwsza wersja jest opisana w tym artykule

Mamy nadzieję, że informacje, które zgromadziliśmy na temat Analiza Earleya , były dla Ciebie przydatne. Jeśli tak, nie zapomnij polecić nas swoim przyjaciołom i rodzinie oraz pamiętaj, że zawsze możesz się z nami skontaktować, jeśli będziesz nas potrzebować. Jeśli mimo naszych starań uznasz, że informacje podane na temat _title nie są całkowicie poprawne lub że powinniśmy coś dodać lub poprawić, będziemy wdzięczni za poinformowanie nas o tym. Dostarczanie najlepszych i najbardziej wyczerpujących informacji na temat Analiza Earleya i każdego innego tematu jest istotą tej strony internetowej; kierujemy się tym samym duchem, który inspirował twórców Encyclopedia Project, i z tego powodu mamy nadzieję, że to, co znalazłeś o Analiza Earleya na tej stronie pomogło Ci poszerzyć swoją wiedzę.

Opiniones de nuestros usuarios

Violetta Michalski

Wspaniałe odkrycie tego artykułu na Analiza Earleya i całej stronie. Przechodzi prosto do ulubionych.

Bernard Kaczmarczyk

To dobry artykuł dotyczący Analiza Earleya . Podaje niezbędne informacje, bez ekscesów.

Patrycja Kacprzak

Minęło trochę czasu odkąd widziałem artykuł o zmiennej napisany w tak dydaktyczny sposób. Podoba mi się.