Analiza Earleya

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 ³ ), gdzie n jest dugoci cigu wejciowego). Dla jednoznacznej gramatyki analiz Earleya przeprowadza si w czasie kwadratowym ( O (n ² )).

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. ${\ styl wywietlania n}$ ${\ styl wywietlania a_ {1} \ ... \ a_ {n}}$

Przedmioty Earley i stoy Earley

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

zasada tworzenia zapisanej gramatyki ; ${\ displaystyle S \ \ rightarrow \ \ alfa}$

indeks pocztkowy w sowie wejciowym, taki jak ;

{\ styl wywietlania i}

{\ displaystyle 0 \ leq i \ leq n}

indeks pozycji po prawej stronie linijki, reprezentowany przez kropk .

Reprezentujemy pozycj w postaci , gdzie . ${\ displaystyle (A \ \ rightarrow \ \ alfa \ bullet \ beta, i)}$ ${\ displaystyle 0 \ leq i \ leq n}$

Zasada algorytmu

Mamy tabel rozmiarów, w której przechowujemy zestawy elementów Earley, gdzie jest dugo cigu wejciowego. ${\ styl wywietlania T}$ ${\ styl wywietlania n + 1}$ ${\ styl wywietlania n}$

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. ${\ styl wywietlania T [0]}$ ${\ displaystyle (S \ \ rightarrow \ \ bullet \ alfa, 0)}$ ${\ styl wywietlania S}$ ${\ displaystyle S \ \ rightarrow \ \ alfa}$ ${\ displaystyle (S \ \ rightarrow \ \ bullet \ alfa, 0)}$

Celem tego kroku jest obliczenie, a nastpnie zapisanie w tabeli zestawu elementów, takich jak rozpoznawany przez . ${\ styl wywietlania j}$ ${\ displaystyle T [j]}$ ${\ displaystyle (A \ \ rightarrow \ \ alfa \ bullet \ beta, i)}$ ${\ displaystyle a_ {i} \ ... \ a_ {j}}$ ${\ styl wywietlania \ alfa}$

W kroku obliczymy z tabel nasycajc kolejno nastpujce trzy operacje: ${\ styl wywietlania j}$ ${\ displaystyle T [j]}$ ${\ styl wywietlania T [0], \ kropki, T [j-1]}$

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 . ${\ styl wywietlania j \ geq 1}$ ${\ displaystyle T [j-1]}$ ${\ displaystyle (A \ \ rightarrow \ \ alfa \ bullet a_ {j} \ \ beta, i)}$ ${\ displaystyle T [j]}$ ${\ displaystyle (A \ \ rightarrow \ \ alfa \ a_ {j} \ bullet \ beta, i)}$ ${\ displaystyle T [j-1]}$ ${\ styl wywietlania a_ {j}}$

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.

{\ displaystyle (A \ \ rightarrow \ \ alfa \ \ bullet B \ beta, i)}

{\ displaystyle T [j]}

{\ styl wywietlania B}

{\ displaystyle B \ \ rightarrow \ \ delta}

{\ styl wywietlania (B \ \ rightarrow \ \ bullet \ delta, j)}

{\ displaystyle T [j]}

{\ styl wywietlania B}

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 .

{\ displaystyle (A \ \ rightarrow \ \ alfa \ \ bullet, i)}

{\ displaystyle T [j]}

{\ displaystyle T [i]}

{\ displaystyle (C \ \ rightarrow \ \ delta \ bullet \ A \ \ gamma, k)}

{\ displaystyle (C \ \ rightarrow \ \ delta \ A \ \ bullet \ gamma, k)}

{\ displaystyle T [j]}

{\ styl wywietlania A}

{\ displaystyle a_ {i} \ ... \ a_ {j}}

{\ styl wywietlania A}

Analiza powiedzie si, jeli w tabeli znajduje si pozycja formularza , gdzie jest produkcja. ${\ styl wywietlania T [n]}$ ${\ displaystyle (S \ \ rightarrow \ \ alfa \ bullet, 0)}$ ${\ displaystyle S \ \ rightarrow \ \ alfa}$

Przykad

Rozwa nastpujc gramatyk wyrae arytmetycznych:

{\ displaystyle S \ rightarrow E}

{\ styl wywietlania E \ strzaka w prawo E + N}

{\ displaystyle E \ rightarrow EN}

{\ displaystyle E \ rightarrow N}

{\ styl wywietlania N \ rightarrow N * F}

{\ styl wywietlania N \ rightarrow N / F}

{\ styl wywietlania N \ strzaka w prawo F}

{\ displaystyle F \ rightarrow a}

{\ styl wywietlania F \ rightarrow -F}

{\ styl wywietlania F \ rightarrow + F}

{\ styl wywietlania F \ strzaka w prawo (E)}

${\ styl wywietlania S}$ jest aksjomatem gramatyki.

Przeanalizujmy cig wejciowy . Nastpnie otrzymujemy nastpujce tabele: Oznaczymy "P:" operacj przewidywania; "C:" operacja uzupeniania, a "L:" operacja odczytu. ${\ styl wywietlania a + a}$

W kroku 0 obliczenia rozpoczynaj si od . Nastpnie nasycamy operacj przewidywania. ${\ displaystyle (S \ rightarrow \ bullet E, 0)}$

{\ styl wywietlania T [0]}

	${\ displaystyle S \ rightarrow \ bullet E}$	${\ styl wywietlania, \, 0}$
P:	${\ displaystyle E \ rightarrow \ bullet E + N}$	${\ styl wywietlania, \, 0}$
P:	${\ displaystyle E \ rightarrow \ bullet EN}$	${\ styl wywietlania, \, 0}$
P:	${\ displaystyle E \ rightarrow \ bullet N}$	${\ styl wywietlania, \, 0}$
P:	${\ displaystyle N \ rightarrow \ bullet N * F}$	${\ styl wywietlania, \, 0}$
P:	${\ displaystyle N \ rightarrow \ bullet N / F}$	${\ styl wywietlania, \, 0}$
P:	${\ displaystyle N \ rightarrow \ bullet F}$	${\ styl wywietlania, \, 0}$
P:	${\ displaystyle F \ rightarrow \ bullet a}$	${\ styl wywietlania, \, 0}$
P:	${\ displaystyle F \ rightarrow \ bullet -F}$	${\ styl wywietlania, \, 0}$
P:	${\ displaystyle F \ rightarrow \ bullet + F}$	${\ styl wywietlania, \, 0}$
P:	${\ displaystyle F \ rightarrow \ bullet (E)}$	${\ styl wywietlania, \, 0}$

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. ${\ displaystyle \ color {czerwony} (F \ rightarrow a \ bullet, 0)}$ ${\ displaystyle \ color {czerwony} (F \ rightarrow a \ bullet, 0)}$ ${\ displaystyle \ kolor {czerwony} (N \ rightarrow F \ bullet, 0)}$ ${\ displaystyle \ color {czerwony} (E \ rightarrow N \ bullet, 0)}$

{\ styl wywietlania T [1]}

L:	${\ displaystyle \ color {czerwony} F \ rightarrow a \ bullet}$	${\ styl wywietlania \ kolor {czerwony}, \, 0}$
VS:	${\ displaystyle \ color {czerwony} N \ rightarrow F \ bullet}$	${\ styl wywietlania \ kolor {czerwony}, \, 0}$
VS:	${\ displaystyle \ kolor {czerwony} E \ rightarrow N \ bullet}$	${\ styl wywietlania \ kolor {czerwony}, \, 0}$
VS:	${\ displaystyle N \ rightarrow N \ bullet * F}$	${\ styl wywietlania, \, 0}$
VS:	${\ displaystyle N \ rightarrow N \ bullet / F}$	${\ styl wywietlania, \, 0}$
VS:	${\ displaystyle \ kolor {czerwony} S \ rightarrow E \ bullet}$	${\ styl wywietlania, \, 0}$
VS:	${\ displaystyle E \ rightarrow E \ bullet + N}$	${\ styl wywietlania, \, 0}$
VS:	${\ displaystyle E \ rightarrow E \ bullet -N}$	${\ styl wywietlania, \, 0}$

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. ${\ styl wywietlania (E \ strzaka w prawo E + \ punktor N, 0)}$ ${\ styl wywietlania N}$ ${\ styl wywietlania T [2]}$ ${\ styl wywietlania (N \ rightarrow \ alfa)}$

{\ styl wywietlania T [2]}

L:	${\ displaystyle E \ rightarrow E + \ bullet N}$	${\ styl wywietlania, \, 0}$
P:	${\ displaystyle N \ rightarrow \ bullet N * F}$	${\ styl wywietlania, \, 2}$
P:	${\ displaystyle N \ rightarrow \ bullet N / F}$	${\ styl wywietlania, \, 2}$
P:	${\ displaystyle N \ rightarrow \ bullet F}$	${\ styl wywietlania, \, 2}$
P:	${\ displaystyle F \ rightarrow \ bullet a}$	${\ styl wywietlania, \, 2}$
P:	${\ displaystyle F \ rightarrow \ bullet -F}$	${\ styl wywietlania, \, 2}$
P:	${\ displaystyle F \ rightarrow \ bullet + F}$	${\ styl wywietlania, \, 2}$
P:	${\ displaystyle F \ rightarrow \ bullet (E)}$	${\ styl wywietlania, \, 2}$

W kroku 3 czytamy , wic uzupeniamy de en . Jest wic regua, wic regua jest zakoczona w . ${\ styl wywietlania F}$ ${\ displaystyle (N \ rightarrow \ bullet F, 2)}$ ${\ styl wywietlania T [2]}$ ${\ displaystyle (N \ rightarrow F \ bullet, 2)}$ ${\ displaystyle (N \ rightarrow F \ bullet, 2)}$ ${\ styl wywietlania (E \ strzaka w prawo E + \ punktor N, 0)}$ ${\ styl wywietlania (E \ strzaka w prawo E + N \ punktor, 0)}$

Nasycamy przez dopenienie.

{\ displaystyle T [3]}

L:	${\ displaystyle \ color {czerwony} F \ rightarrow a \ bullet}$	${\ styl wywietlania \ kolor {czerwony}, \, 2}$
VS:	${\ displaystyle \ color {czerwony} N \ rightarrow F \ bullet}$	${\ styl wywietlania \ kolor {czerwony}, \, 2}$
VS:	${\ displaystyle \ color {czerwony} E \ rightarrow E + N \ bullet}$	${\ styl wywietlania \ kolor {czerwony}, \, 0}$
VS:	${\ displaystyle N \ rightarrow N \ bullet * F}$	${\ styl wywietlania, \, 2}$
VS:	${\ displaystyle N \ rightarrow N \ bullet / F}$	${\ styl wywietlania, \, 2}$
VS:	${\ displaystyle \ kolor {czerwony} S \ rightarrow E \ bullet}$	${\ styl wywietlania \ kolor {czerwony}, \, 0}$
VS:	${\ displaystyle E \ rightarrow E \ bullet + N}$	${\ styl wywietlania, \, 0}$
VS:	${\ displaystyle E \ rightarrow E \ bullet -N}$	${\ styl wywietlania, \, 0}$

Tak jak w , sowo wejciowe jest rozpoznawane. ${\ displaystyle \ kolor {czerwony} (S \ rightarrow E \ bullet, 0)}$ ${\ displaystyle T [3]}$

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 . ${\ styl wywietlania I}$ ${\ styl wywietlania I}$ ${\ styl wywietlania \ punktor}$ ${\ styl wywietlania I = 34}$

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²). ${\ displaystyle T [j]}$ ${\ styl wywietlania I}$ ${\ styl wywietlania 0}$ ${\ styl wywietlania j}$ ${\ styl wywietlania I. (j + 1)}$ ${\ displaystyle T [j] .j}$ ${\ styl wywietlania n}$ ${\ styl wywietlania n}$ ${\ styl wywietlania I. (j + 1)}$ ${\ styl wywietlania j}$ ${\ styl wywietlania 0}$ ${\ styl wywietlania n}$ ${\ styl wywietlania I. (n + 1). (n + 2) / 2}$

Zoono czasowa (przypadek ogólny)

Przestudiujmy zoono operacji odczytu, przewidywania i uzupeniania na tablicy : ${\ displaystyle T [j]}$

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²). ${\ displaystyle T [j-1]}$ ${\ displaystyle T [j-1]}$ ${\ styl wywietlania O (j)}$ ${\ styl wywietlania O (j)}$ ${\ styl wywietlania O (j)}$

Sumujc te zoonoci na tablicach, otrzymujemy ostateczn zoono czasow w O (n ³ ). ${\ styl wywietlania n}$

Zoono czasowa (jednoznaczna gramatyka)

Tym, co umiecio zoono w O (n ³ ), 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²). ${\ displaystyle T [j]}$ ${\ styl wywietlania O (j)}$ ${\ styl wywietlania O (j)}$

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. ${\ displaystyle T [j-1]}$ ${\ styl wywietlania T [k]}$

Uwagi i referencje

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

[:0-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

Analiza Earleya

streszczenie

Algorytm Earleya

Przedmioty Earley i stoy Earley

Zasada algorytmu

Przykad

Zoono

Zoono przestrzeni

Zoono czasowa (przypadek ogólny)

Zoono czasowa (jednoznaczna gramatyka)

Wariant

Uwagi i referencje

Opiniones de nuestros usuarios

Violetta Michalski

Bernard Kaczmarczyk

Patrycja Kacprzak

Enciclo

Sapientia

Scientia

Boobota