Earleyův analyzátor: Porovnání verzí

← Přejít na předchozí porovnání Přejít na další porovnání →

Smazaný obsah Přidaný obsah

V textu

Verze z 17. 1. 2016, 16:42

Earleyův algoritmus je algoritmus syntaktické analýzy, který vytvořil a v roce 1968 popsal Jay Earley ve své disertační práci^[1] vedené Robertem W. Floydem z Carnegie Mellon University. Algoritmus byl v roce 1970 publikován ve zkrácené a čitelnější podobě v časopise Communications of the ACM^[2] v článku zařazeném v roce 1983 mezi 21 nejvýznamnějších článků za čtvrtstoletí existence tohoto časopisu.^[3]

Původní algoritmus pouze zjišťuje, zda zadaný textový řetězec patří do jazyka popsaného bezkontextovou gramatikou – jedná se tedy o rozpoznávač (anglicky recogniser). Lze jej však snadno rozšířit, aby v průběhu analýzy vytvářel derivační strom, čímž vznikne kompletní syntaktický analyzátor (anglicky parser).

Algoritmus je vhodný i pro nejednoznačné bezkontextové jazyky používané pro zpracování přirozeného jazyka^[4]^[5], díky čemuž má v matematické lingvistice podobnou úlohu jako LR parsery a LL parsery používané v matematické informatice v překladačích programovacích jazyků.

Asymptotická složitost Earleyova algoritmu pro obecný bezkontextový jazyk je O(n³), kde n je délka analyzovaného řetězce; pro jednoznačné gramatiky pracuje v kvadratickém čase O(n²), a pro téměř všechny LR(k) gramatiky v lineárním čase. Funguje obzvlášť dobře, když pravidla používají levou rekurzi. Některé varianty mohou trpět problémy s určitými vypouštějícími gramatikami^[6].

Earleyův analyzátor (anglicky Earley parser) je syntaktický analyzátor založený na Earleyově algoritmu. Často jej používají projektové frameworky podporující Rapid Application Development (RAD)^[7]^[8] využívané při konstrukci interpretů a kompilátorů především doménově specifických jazyků.

Princip fungování

Earleyův algoritmus patří stejně jako algoritmus CYK, do třídy tabulkových metod syntaktické analýzy (anglicky chart parsers). Při načítání řetězce zleva doprava provádí syntaktickou analýzu zdola nahoru na základě predikcí shora dolů. Výsledky jsou z dříve získaných částečných výsledků konstruovány technikou dynamického programování.

Aby se vyhnul backtrackingu, pracuje Earleyův algoritmus s množinou Earleyových položek (anglicky Earley items) nebo krátce položek, což jsou pravidla gramatiky, do jejichž pravé strany je vložena tečka, která identifikuje aktuální pozici v pravidle. Každá položka navíc obsahuje informaci, od které pozice ve vstupním řetězci se uplatní. Během práce algoritmu Earleyovy položky odrážejí dosud použitá pravidla a slouží pro predikci dalších pravidel. Analýzou vstupního řetězce, který patří do jazyka, vznikne položka, která odráží odvození řetězce z počátečního symbolu gramatiky.

Podrobný popis

V následujícím popisu se použivá toto značení:

velká písmena ze začátku abecedy A, B, atd. a symbol S reprezentují jeden neterminální symbol (S je počáteční symbol),
X_k je jeden terminální nebo neterminální symbol,
malá písmena t_n reprezentují jeden terminální symbol,
malá řecká písmena α, β, γ reprezentují libovolný řetězec složený z terminálních a neterminálních symbolů (včetně prázdného řetězce označovaného ε).

Earleyovy položky

Earleyův analyzátor vytváří během analýzy každé vstupní věty tvořené symboly t₁ … t_n (n je délka vstupní věty) specifickou množinu Earleyových položek.

Vstupní pozice i je pozice za i-tým symbolem vstupního věty; před načtením prvního symbolu je vstupní pozice 0.

Earleyova položka pro pravidlo gramatiky A → X₁ … X_q je výraz tvaru [A →_hX₁ … X_p •_i X_{p + 1} … X_q], přičemž tečka může být v libovolném místě počínaje pozicí bezprostředně před X₁ až po pozici bezprostředně za X_q, tj. 0 ≤ p ≤ q, index h u šipky udává, na které vstupní pozici začíná část vstupní věty vygenerovaná pravidlem odpovídajícím právě probírané položce, index i u tečky je pozice za posledním dosud načteným terminálním symbolem; platí tedy 0 ≤ h ≤ i ≤ n.

Algoritmus

Před analýzou každé věty se množina Earleyových položek vždy inicializuje jedinou položkou [S’ →₀ •₀ S], kde S je počáteční symbol dané gramatiky, a S’ je přidaný pomocný počáteční symbol.

Analyzátor opakovaně provádí tři operace: predikci, načtení a kompletaci, které do množiny Earleyových položek přidávají nové položky na základě existujících položek a vstupního řetězce:

Predikce (anglicky prediction) přidává položky, odpovídající dalším očekáváním analyzátoru shora dolů: pro každou položku [A →_hX₁ … X_p •_i X_p+1 … X_q], která má za tečkou neterminální smybol, tj. X_p+1 je neterminál B, a pro každé pravidlo B → β, které má tento neterminál na levé straně, se do množiny pravidel přidá položka [B →_i •_i β].

Načtení (anglicky scanning) je načtení terminálního symbolu shodného s očekáváním analyzátoru shora dolů: Jestliže t_i je první dosud nenačtený symbol ve vstupním řetězci, pak pro každou položku [A →_h α •_i-1 t_iη], která má tento symbol bezpostředně za tečkou, přidáme položku [A →_h αt_i •_i η].

Kompletace (anglicky completion) realizuje část analýzy zdola nahoru: Pro každou položku, která má tečku na konci, tj. tvaru [A →_h α •_i], a položku, která má neterminál z levé strany této položky bezprostředně za tečkou [B →_g β •_h Aγ], přidáme položku [B →_g βA •_i γ], v níž je tečka přesunuta za neterminál A a index u ní je změnen na i.

Uvedené operace se opakují tak dlouho, dokud přibývají nové položky. Pokud nově utvořená položka v množině již je, nebudeme ji přidávat. Množina je zpravidla implementována jako fronta položek, které se mají zpracovat, s operacemi, které se mají provádět podle toho, o jaký druh položky se jedná.

Původní Earleyův algoritmus zahrnoval do položky i náhled; pozdější výzkum ukázal, že náhled má malý praktický vliv na efektivitu analýzy a proto jej většina implementací nepoužívá.

Příklad

Analýza anglických vět

Pro „mikrogramatiku” angličtiny

S → NP VP

NP → Det N

NP → Det Adj N

VP → V

VP → V NP

a vstupní řetězec The_Det black_Adj cat_N ate_V a_Det white_Adj mouse_N vytváří algoritmus následující množiny Earleyových položek:

Earleyova položka	Zdroj přidání do množiny položek
S(0)
[S’ →₀ •₀ S]	inicializace
[S →₀ •₀ NP VP]	predikce S z položky [S’ →₀ •₀ S]
[NP →₀ •₀ Det N]	predikce NP z položky [S →₀ •₀ NP VP]
[NP →₀ •₀ Det Adj N]	predikce NP z položky [S →₀ •₀ NP VP]
S(1)
[NP →₀ Det •₁ N]	načtení Det z položky [NP →₀ •₀ Det N]
[NP →₀ Det •₁ Adj N]	načtení Det z položky [NP →₀ •₀ Det Adj N]
S(2)
[NP →₀ Det Adj •₂ N]	načtení Adj z položky [NP →₀ Det •₁ Adj N]
S(3)
[NP →₀ Det Adj N •₃]	načtení N z položky [NP →₀ Det Adj •₂ N]
[S →₀ NP •₃ VP]	kompletace NP z položky [S₀ → •₀ NP VP]
[VP →₃ •₃ V]	predikce VP z položky [S →₀ NP •₃ VP]
[VP →₃ •₃ V NP]	predikce VP z položky [S →₀ NP •₃ VP]
S(4)
[VP →₃ V •₄]	načtení V z položky [VP →₃ •₃ V]
[VP →₃ V •₄ NP]	načtení V z položky [VP →₃ •₃ V NP]
[S →₀ NP VP •₄]	kompletace VP z položky [S →₀ NP •₃ VP]
[NP →₄ •₄ Det N]	predikce NP z položky [VP →₃ V •₄ NP]
[NP →₄ •₄ Det Adj N]	predikce NP z položky [VP →₃ V •₄ NP]
[S’ →₀ S •₄]	kompletace S z položky [S’ →₀ •₀ S]
S(5)
[NP →₄ Det •₅ N]	načtení Det z položky [NP →₄ •₄ Det N]
[NP →₄ Det •₅ Adj N]	načtení Det z položky [NP →₄ •₄ Det Adj N]
S(6)
[NP →₄ Det Adj •₆ N]	načtení Adj z položky [NP →₄ Det •₅ Adj N]
S(7)
[NP →₄ Det Adj N •₇]	načtení N z položky [NP →₄ Det Adj •₆ N]
[VP →₃ V NP •₇]	kompletace NP z položky [VP →₃ V •₄ NP]
[S →₀ NP VP •₇]	kompletace VP z položky [S →₀ NP •₃ VP]
[S’ →₀ S •₇]	kompletace S z položky [S’ →₀ •₀ S]

Poslední Earleyova položka [S’ →₀ S •₇] odpovídá úplnému odvození celého vstupního řetězce. Earleyova položka [S’ →₀ S •₄] ukazuje, že první čtyři symboly tohoto řetězce také tvoří správnou větu dané gramatiky.

Alternativní zápis

Earleyovy položky se někdy rozdělují do různých množin podle vstupní pozice (tj. index za tečkou) označovaných S(i), kde i je vstupní pozice. Počáteční pozice položky (h) se pak obvykle nepíše jako index u šipky, ale do závorek, ve kterých je položka zapsána: (A → X₁ … X_p • X_{p + 1} … X_q, h).

Analyzátor začíná s množinou položek S(0) obsahující jedinou položku (S’ → • S, 0), kde S je vlastní počáteční symbol dané gramatiky, a S’ je přidaný pomocný počáteční symbol. Operace predikci, načtení a kompletaci lze pak popsat takto:

Predikce (anglicky prediction): pokud v S(i) existuje položka tvaru (X → α • B β, h) (kde h je počáteční pozice definovaná výše) s terminálním symbolem bezprostředně za tečkou, pak projdeme všechna pravidla, která mají tento symbol B na levé straně a do S(i) přidáme pro každé pravidlo tvaru (B → β) položku (B → • β, i).

Načtení (anglicky scanning): jestliže a je další symbol ve vstupním řetězci, pro každou položku v S(i-1) tvaru (X → α • a β, h), přidáme (X → α a • β, h) do S(i).

Kompletace (anglicky completion): pro každou položku v S(i) tvaru (A → α •, h), najdeme v S(h) položky tvaru (B → β • A γ, g), a přidáme (B → β A • γ, i) do S(i).

Pseudokód

Pseudokód je převzatý z publikace^[9], kterou napsal Daniel Jurafsky a James H. Martin

function EARLEY_PARSE(words, grammar)
    ENQUEUE((γ → •S, 0), chart[0])
    for i ← from 0 to LENGTH(words) do
        for each state in chart[i] do
            if INCOMPLETE?(state) then
                if NEXT_CAT(state) is a nonterminal then
                    PREDICTOR(state, i, grammar)         { neterminál }
                else do
                    SCANNER(state, i)                    { terminál }
            else do
                COMPLETER(state, i)
        end
    end
    return chart

procedure PREDICTOR((A → α•B, i), j, grammar)
    for each (B → γ) in GRAMMAR_RULES_FOR(B, grammar) do
        ADD_TO_SET((B → •γ, j), chart[j])
    end

procedure SCANNER((A → α•B, i), j)
    if B ⊂ PARTS_OF_SPEECH(word[j]) then
        ADD_TO_SET((B → word[j], j), chart[j + 1])
    end

procedure COMPLETER((B → γ•, j), k)
    for each (A → α•Bβ, i) in chart[j] do
        ADD_TO_SET((A → αB•β, i), chart[k])
    end

Příklady

Analýza aritmetických výrazů

Uvažujme následující jednoduchou gramatiku pro aritmetické výrazy:

<P> ::= <S>      # počáteční pravidlo
<S> ::= <S> "+" <M> | <M>
<M> ::= <M> "*" <T> | <T>
<T> ::= "1" | "2" | "3" | "4"

Při analýze vstupního řetězce:

2 + 3 * 4

dostáváme následující posloupnost množin položek (i je číslo položky a p je počáteční pozice):

(i) Pravidlo         (p)    # Komentář
--------------------------------------------------------

S(0): • 2 + 3 * 4

(1)  P → • S         (0)    # počáteční pravidlo
(2)  S → • S + M     (0)    # predikce z (1)
(3)  S → • M         (0)    # predikce z (1)
(4)  M → • M * T     (0)    # predikce z (3)
(5)  M → • T         (0)    # predikce z (3)
(6)  T → • číslo     (0)    # predikce z (5)

S(1): 2 • + 3 * 4

(1)  T → číslo •     (0)    # načtení z S(0)(6)
(2)  M → T •         (0)    # kompletace z (1) a S(0)(5)
(3)  M → M • * T     (0)    # kompletace z (2) a S(0)(4)
(4)  S → M •         (0)    # kompletace z (2) a S(0)(3)
(5)  S → S • + M     (0)    # kompletace z (4) a S(0)(2)
(6)  P → S •         (0)    # kompletace z (4) a S(0)(1)

S(2): 2 + • 3 * 4

(1)  S → S + • M     (0)    # načtení z S(1)(5)
(2)  M → • M * T     (2)    # predikce z (1)
(3)  M → • T         (2)    # predikce z (1)
(4)  T → • číslo     (2)    # predikce z (3)

S(3): 2 + 3 • * 4

(1)  T → číslo •     (2)    # načtení z S(2)(4)
(2)  M → T •         (2)    # kompletace z (1) a S(2)(3)
(3)  M → M • * T     (2)    # kompletace z (2) a S(2)(2)
(4)  S → S + M •     (0)    # kompletace z (2) a S(2)(1)
(5)  S → S • + M     (0)    # kompletace z (4) a S(0)(2)
(6)  P → S •         (0)    # kompletace z (4) a S(0)(1)

S(4): 2 + 3 * • 4

(1)  M → M * • T     (2)    # načtení z S(3)(3)
(2)  T → • číslo     (4)    # predikce z (1)

S(5): 2 + 3 * 4 •

(1)  T → číslo •     (4)    # načtení z S(4)(2)
(2)  M → M * T •     (2)    # kompletace z (1) a S(4)(1)
(3)  M → M • * T     (2)    # kompletace z (2) a S(2)(2)
(4)  S → S + M •     (0)    # kompletace z (2) a S(2)(1)
(5)  S → S • + M     (0)    # kompletace z (4) a S(0)(2)
(6)  P → S •         (0)    # kompletace z (4) a S(0)(1)

Výskyt položky (P → S •, 0) v množině znamená, že načtený řetězec patří do jazyka. Tato položka se také objevuje v S(3) a S(1), což jsou úplné věty.

Výpočetní složitost

Pokud implementace Earleyova algoritmu používá seznam množin a ignoruje index nezpracovaného vstupního symbolu v položkách, lze prohlíží množiny z tohoto seznamu postupně, díky čemuž inkrementálně analyzuje vstupní symboly t_i pro rostoucí index i.

Earleyovy položky v množině se obvykle prohlíží v tom pořadí, v jakém byly přidávány, každá pouze jednou. Pokud má algoritmus správně fungovat pro gramatiky obsahující pravidla s prázdnou pravou stranou, musí být upraven, jak je uvedeno dále. Pro procházení množiny položek stačí fronta, pro efektivní kontrolu, že fronta danou položky dosud obsahuje, je vhodné položky z každé fronty umístit do asociativního pole. Efektivní kompletace položek, které nemají tečku na konci pravidla, vyžaduje ještě jedno asociativní pole, které obsahuje seznamy takových položek; klíčem je dvojice (X_p, i), složená ze symbolu ležícího v těchto položkách bezprostředně za tečkou a z indexu nezpracovaného terminálního symbolu. Pro efektivní predikci nové položky je třeba s každým neterminálním symbolem také svázat seznam všech pravidel, jejichž levou stranu tvoří tento symbol.

Pokud se jako výše zmíněné asociativní pole použije hašovací tabulka, pak krok zahrnující konstrukci nové Earleyovy položky a pokus o její přidání do množiny položek lze vykonat s asymptotickou složitostí O(1).

Earley ve svém článku^[2] ukázal, že v obecném případě:

i-tá množina obsahuje O(i) položek, protože jejich počet lze omezit součinem počtu možných hodnot indexu h (závislým na i), počtu pravidel a počtu možných umístění tečky na jejich pravých stranách (poslední dva činitelé jsou konstanty závislé na dané gramatice, ale nezávislé na i);
provedení načtení nebo predikce znamená O(1) kroků pro každou Earleyovu položku v libovolné množině, tedy v i-té množině položek se provede O(i) kroků;
akce kompletace provádí O(i) kroků pro každou zpracovanou položku, protože v nejhorším případě se přidává O(h) položek patřících do h-té množiny, přičemž h = O(i), takže v i-té množině položek se provede O(i²) kroků;
sečtením pro i od 0 do n dostaneme pro celkový počet kroků O(n³) a pro počet položek O(n²).

Ve stejném článku je také dokázáno, že pro jednoznačné gramatiky akce kompletace provádí v i-té množině položek O(i) kroků, což dává kvadratickou složitost algoritmu, a že třída gramatik, pro které Earleyův algoritmus funguje v lineárním čase, pokrývá všechny gramatiky, u nichž lze počet položek v každé množině shora omezit konstantou. Do této třídy naleží právě všechny gramatiky LR(k), kromě některých gramatik s pravou rekurzí, což jsou gramatiky většiny programovacích jazyků.

Earleyův algoritmus funguje obzvlášť efektivně pro gramatiky s levou rekurzí. Uvažujme například analýzu řetězce aaa v gramatice

S → Sa

S → a

Earleyův algoritmus tvoří následující položky:

Earleyova položka	Zdroj přidání do množiny položek
[S’ →₀ •₀ S]	inicializace
[S →₀ •₀ Sa]	predikce S z položky [S’ →₀ •₀ S], a pak z položky [S →₀ •₀ Sa]
[S →₀ •₀ a]	predikce S z položky [S’ →₀ •₀ S], a pak z položky [S →₀ •₀ Sa]
[S →₀ a •₁]	načtení a z položky [S →₀ •₀ a]
[S’ →₀ S •₁]	kompletace S z položky [S’ →₀ •₀ S]
[S →₀ S •₁ a]	kompletace S z položky [S →₀ •₀ Sa]
[S →₀ Sa •₂]	načtení a z položky [S →₀ S •₁ a]
[S’ →₀ S •₂]	kompletace S z položky [S’ →₀ •₀ S]
[S →₀ S •₂ a]	kompletace S z položky [S →₀ •₀ Sa]
[S →₀ Sa •₃]	načtení a z položky [₀S → S •₂ a]
[S’ →₀ S •₃]	kompletace S z položky [S’ →₀ •₀ S]
[S →₀ S •₃ a]	kompletace S z položky [S →₀ •₀ Sa]

Počet položek pro každou hodnotu indexu u tečky je 3, takže algoritmus funguje v lineárním čase.

Pro porovnaní použití gramatiky s pravou rekurzí

S → aS

S → a

pro analýzu téhož řetězce aaa vede k vytvoření následujících Earleyových položek:

Earleyova položka	Zdroj přidání do množiny položek
[S’ →₀ •₀ S]	inicializace
[S →₀ •₀ aS]	predikce S z položky [S’ →₀ •₀ S]
[S →₀ •₀ a]	predikce S z položky [S’ →₀ •₀ S]
[S →₀ a •₁ S]	načtení a z položky [S’ →₀ •₀ aS]
[S →₀ a •₁]	načtení a z položky [S’ →₀ •₀ a]
[S →₁ •₁ aS]	predikce S z položky [S →₀ a •₁ S]
[S →₁ •₁ a]	predikce S z položky [S →₀ a •₁ S]
[S’ →₀ S •₁]	kompletace S z položky [S’ →₀ •₀ S]
[S →₁ a •₂ S]	načtení a z položky [S’ →₁ •₁ aS]
[S →₁ a •₂]	načtení a z položky [S’ →₁ •₁ a]
[S →₂ •₂ aS]	predikce S z položky [S →₁ a •₂ S]
[S →₂ •₂ a]	predikce S z položky [S →₁ a •₂ S]
[S →₀ aS •₂]	kompletace S z položky [S’ →₀ a •₁ S]
[S’ →₀ S •₂]	kompletace S z položky [S’ →₀ •₀ S]
[S →₂ a •₃ S]	načtení a z položky [S’ →₂ •₂ aS]
[S →₂ a •₃]	načtení a z položky [S’ →₂ •₂ a]
[S →₃ •₃ aS]	predikce S z položky [S →₂ a •₃ S]
[S →₃ •₃ a]	predikce S z položky [S →₂ a •₃ S]
[S →₁ aS •₃]	kompletace S z položky [S’ →₁ a •₂ S]
[S →₀ aS •₃]	kompletace S z položky [S’ →₀ a •₁ S]
[S’ →₀ S •₃]	kompletace S z položky [S’ →₀ •₀ S]

Počet položek s danou hodnotou indexu u tečky se roste lineárně se zvětšováním tohoto indexu; algoritmus má pro tyto gramatiky kvadratickou časovou složitost.

Prázdná pravidla

Pokud Earleyův algoritmus prochází položky z i-té množiny pouze jednou a v pořadí, v jakém byly přidávány, pak může fungovat nesprávně pro gramatiky, které obsahují pravidla s prázdnou pravou stranou (nazývané také ε-pravidla, protože ε tradičně označuje prázdný řetězec symbolů gramatiky). Při kompletaci položky [E →_i •_i], která odpovídá prázdnému pravidlu E → ε, je třeba prohlédnout i právě vytvářenou i-tou množinu. Pokud položka [X →_h α •_i Eη] bude do ní přidána až po kompletaci položek [E →_i •_i], pak kompletace nikdy nepřidá položku [X →_h αE •_i η]. Nebudou také přidány žádné položky přímo i nepřímo z ní vyplývající. To může vést k odmítnutí správného vstupního řetězce, jak ukazuje následující příklad použití gramatiky

S → E A A A

A → E

E → ε

pro analýzu prázdného řetězce ε. V množině Earleyových položek jsou červeně označeny položky, které algoritmus měl přidat do množiny, ale nepřidal.

Earleyova položka	Zdroj přidání do množiny položek
[S’ →₀ •₀ S]	inicializace
[S →₀ •₀ E A A A]	predikce S z položky [S’ →₀ •₀ S]
[E →₀ •₀]	predikce E z položky [S →₀ •₀ E A A A]
[S →₀ E •₀ A A A]	kompletace E z položky [S →₀ •₀ E A A A]
[A →₀ •₀ E]	predikce A z položky [S →₀ E •₀ A A A]
[A →₀ E •₀]	ne kompletace E z položky [A →₀ •₀ E]
[S →₀ E A •₀ A A]	ne kompletace A z položky [S →₀ E •₀ A A A]
[S →₀ E A A •₀ A]	ne kompletace A z položky [S →₀ E A •₀ A A]
[S →₀ E A A A •₀]	ne kompletace A z položky [S →₀ E A A •₀ A]
[S’ →₀ S •₀]	ne kompletace S z položky [S’ →₀ •₀ S]

Bylo publikováno několik řešení tohoto problému:

A. V. Aho a J. D. Ullman^[10] doporučují opakovaně procházet smyčkou predikce a kompletace všech položek z i-té množiny tak dlouho, dokud postupné iterace zvětšují její velikost;
Earley^[2] navrhl pamatovat si při kompletaci položek neterminální symboly, z nichž lze vyprodukovat prázdný řetězec (anglicky nullable symbols); tyto symboly se poznají tak, že stojí na levé straně pravidla s prázdnou pravou stranou nebo složeného jen ze symbolů přepsatelných na prázdný řetězec, a při doplňování do množiny položek [A →_h α •_i Bη], pokud ze symbolu B stojícího po tečce se dá vyprodukovat prázdný řetězec, doplníme do množiny také položku [A →_h αB •_i η];
podobné řešení J. Aycocka a R. N. Horspoola^[11] spočívá v změně predikce položek na „pokud existuje položka [A →_h α •_i Bη], pak pro každé pravidlo B → β přidej položku [B →_i •_i β]; pokud ze symbolu B lze vyprodukovat prázdný řetězec, pak přidej také položku [A →_h αB •_i η]”, přičemž množinu neterminálních symbolů přepsatelných na prázdný řetězec lze snadno stanovit předem;
každou gramatiku, z jejíhož počátečního symbolu se nedá vyprodukovat prázdný řetězec, lze upravit na ekvivalentní gramatiku bez prázdných pravidel^[12].

Konstrukce derivačního lesa

Earleyova disertace^[1] stručně popisuje algoritmus pro konstruování derivačních stromů přidáním sady ukazatelů z každého neterminálu v Earleyově položce do položek, které způsobily, že byla prvně zmíněná položka rozpoznána. Tomita však upozornil^[13], že se při tom neuvažují vztahy mezi symboly, takže pokud uvažujeme gramatiku S → SS | b a řetězec bbb, každé S může generovat jeden nebo dva symboly b a proto mimo dvou správných odvození bbb produkuje chybná odvození bb a bbbb.

Je relativně jednoduché vzít úplné položky z tabulky, prohledat je shora dolů a pro vytvoření derivačního lesa použít pouze ty, které patří k sobě.

E. Scottová^[14] popsala jinou metodu, při níž se derivační les vytváří za chodu, přičemž každá Earleyova položka je rozšířena o ukazatel na uzel sdíleného pakovaného derivačního lesa (anglicky shared packed parse forest, SPPF) označený trojicí (s, i, j), kde s je symbol nebo LR(0) položka (tj. přepisovací pravidlo s tečkou) a i a j udávají část vstupního řetězce generovanou tímto uzlem. Obsahem uzlu je buď dvojice ukazatelů na děti, která udávají jedinou derivaci, nebo seznam „pakovaných“ uzlů, z nichž každý obsahuje dvojici ukazatelů a reprezentuje jednu derivaci. SPPF uzly jsou jednoznačné (existuje pouze jeden s daným označením), ale pro nejednoznačné analýzy mohou obsahovat více než jednu derivaci. Takže i kdyby nějaká operace nepřidala Earleyovu položku (protože už existuje), stále může přidat derivaci k derivačnímu lesu položky.

Predikované položky mají nulový SPPF ukazatel.
Analyzátor vytváří SPPF uzel, který reprezentuje neterminál, který právě analyzuje.
Když pak analyzátor nebo completer posouvá položku vpřed, přidá derivaci, jejíž děti jsou uzlem z položky, jejíž tečka byla posunuta vpřed a jeden pro nový symbol, přes který byl posunut vpřed (neterminál nebo dokončená položka).

Pamatujte, že SPPF uzly nejsou nikdy označeny dokončenou LR(0) položkou: místo toho jsou označeny vytvořeným symbolem, takže všechny derivace jsou zkombinované pod jedním uzlem bez ohledu na to, ze kterého přepisovacího pravidla pocházejí.

Rozpoznávání a syntaktická analýza

Výše popsaný algoritmus pouze rozpoznává, zda daný řetězec terminálních symbolů tvoří správnou větu dané bezkontextové gramatiky (takový algoritmus se anglicky nazývá recognizer), ale nevytváří syntaktický strom. Bylo navrženo několik způsobů rozšíření algoritmu na analyzátor. Komplikaci představuje počet derivačních stromů, který může být až exponenciální funkcí délky vstupní věty, a pro gramatiky s cykly může být i nekonečný. Existují však způsoby kódování všech derivačních stromů pomocí datových struktur o velikosti, která je polynomiální funkcí délky vstupní věty.


Správné derivační stromy řetězce aaa

Chybné derivační stromy řetězce aaa

V článku Earley^[2] uvedl, jak rozšířit algoritmus rozpoznávání na analyzátor doplněním výstupu neterminálních symbolů uvnitř pravých stran pravidel v položkách Earleyovy množiny ukazatelů do položek, které způsobily kompletaci těchto symbolů: při každé kompletaci způsobující vznik položek [B →_g βA •_i γ] se tvoří ukazatel od výstupu symbolu A v této položce do položek [A →_h α •_i]. M. Tomita^[15] podal však protipříklad: pro gramatiky

S → S S

S → a

a vstupní řetězec aaa parser navržený Earleyem tvoří nejen správné derivační stromy řetězce aaa, ale také nesprávné derivační stromy řetězců aa a aaaa.

Tomu je možné zabránit doplněním položek [B →_g βA •_i γ] vzniklých jako výsledek kompletace ne jedním, ale dvojicí ukazatelů: do položek [B →_g β •_h Aγ] nebo do položek [A →_h α •_i]. Při naivním použití těchto myšlenek doplněním uvedených dvojic ukazatelů do sady návěstí rozlišujících položky může časová složitost algoritmu překročit n³, což ukázal M. Johnson^[16] následujícím příkladem: pro gramatiku

S → S … S (m + 2 opakování symbolu S)

S → S S

S → a

analyzuje Earleyův algoritmus s takto definovanými položkami vstupní řetězec a … a (n + 1 opakování symbolu a, přičemž n > m) v čase Ω(n^m). V. A. Lapšin^[17] navrhl ukládat množiny takovýchto dvojic ukazatelů do asociativního pole, jehož klíčem jsou Earleyovy položky, a algoritmus vytváření derivačních stromů na základě grafu položek v kombinaci s těmito ukazateli. Pak časová složitost stejného analyzátoru bez budovaní derivačního stromu nepřekračuje řád n³. E. Scottová^[18] publikovala jiný algoritmus, který v čase O(n³) převádí graf položek na takovou verzi společně baleného lesa analýzy (anglicky shared packed parse forest) známého z analyzátorů GLR, ve které má každý uzel nejvýše dva syny.

D. Grune a C. J. H. Jacobs^[19] navrhli metodu konstrukce derivačního stromu z množiny položek za pomocí Ungerova syntaktického analyzátoru.

Náhled terminálních symbolů

Operace predikce v Earleyově algoritmu může využívat náhled (anglicky lookahead). Pak funguje takto: „pokud existuje položka [A →_h α •_i Bη], pak pro každé pravidlo B → β přidej položku [B →_i •_i β], pokud množina FIRST řetězců symbolu β obsahuje terminální symbol t_i”. Jako obvykle při používání náhledu, je vhodné umístit na konec analyzovaného řetězce symbolů zarážku t_n = $, která nepatří do množiny terminálních symbolů.

V původním Earleyově článku^[2] bylo navrženo používání náhledu také v operacích kompletace. Na rozdíl od predikce se při kompletaci nedá předem stanovit množina přípustných nástupců, pokud se nebere v úvahu jeho méně efektivní a omezená verze založená na množinách FOLLOW. Efektivní náhled při kompletaci spočívá v následujících modifikacích algoritmu:

množina přípustných nástupců počáteční položky [S’ →₀ •₀ S] má jeden prvek – zarážku $;
při operaci načtení nově vzniklá položka [A →_h αt_i •_i+1 η] dědí množinu přípustných nástupců svého předchůdce [A →_h α •_i t_iη];
při operaci predikce položka [B →_i •_i β] na základě položky [A →_h α •_i Bη] o množině přípustných nástupců N_A zjistíme přípustné nástupce nově vzniklé položky jako množinu FIRST(Bη), pokud FIRST(Bη) neobsahuje prázdný symbol ε; nebo jako sumu množin FIRST(Bη) ∪ N_A, pokud FIRST(Bη) prázdný symbol ε obsahuje;
při operaci kompletace položky [A →_h α •_i] se nová položka [B →_g βA •_i γ] přidává jen tehdy, pokud množina přípustných nástupců položek [A →_h α •_i] obsahuje i-tý terminální symbol t_i.

Je možné také používat náhled více než jednoho terminálního symbolu.

Varianty Earleyova algoritmu s náhledem používajícím různý počet symbolů při predikci a kompletaci studovali M. Bouckaert, A. Pirotte a M. Snelling^[20], kteří simulacemi zjistili, že nejlepší výsledky přináší náhled jednoho symbolu při predikci, který zmenšuje počty položek o 20–50% oproti verzi bez náhledu. Používání jakéhokoli náhledu při kompletaci však má větší režii než zisk z něho plynoucí. Mnoho implementací Earleyova algoritmu vůbec náhled nepoužívá, takže používají přímo danou gramatiku bez předzpracovávání spočívajícím v nalezení množin FIRST.

Modifikace algoritmu

F. C. N. Pereira a D. H. D. Warren ukázali^[21], jak zobecnit tabulkové metody syntaktické analýzy pro libovolné gramatické formalismy založené na unifikaci, včetně kontextových. Zahájil vlnu článků popisujících verze Earleyova algoritmu pro formalismus unifikací PATR-II^[22], gramatik s vkládáním stromů (anglicky Tree Adjoining Grammar, TAG)^[23]^[24], S-atributových gramatik (anglicky S-attribute grammar)^[25], hypergrafových gramatik (anglicky hypergraph grammar)^[26], sekvenčně indexovaných gramatik (anglicky sequentially indexed grammars)^[27] itd. Technika magických množin (anglicky magic sets)^[28] v deduktivních databázích je také založena na myšlenkách Pereiry a Warrena.

S. L. Graham a M. A. Harrison^[29] poukázali na společné rysy Earleyova algoritmu a algoritmu CYK a společně s V. R. Ruzzem vytvořili algoritmus syntaktické analýzy, který je hybridem těchto dvou algoritmů^[30].

J. Aycock a N. Horspool^[31]^[11] ukázali, jak zkonstruovat deterministický konečný automat podobný analyzátoru LR(0), který analyzuje vstupní data několikanásobně rychleji než tradiční implementace Earleyova algoritmu.

A. Päseler^[32] vytvořila variantu Earleyova algoritmu, která místo seznamů terminálních symbolů analyzuje mřížky slov (anglicky word lattice). Mřížky slov jsou užitečné při rozpoznávání řeči a analýze textů psaných bez mezer mezi výrazy, např. v jazycích Dálného východu.

A. Stolcke^[33] publikoval algoritmus, který vrací nejpravděpodobnější syntaktickou analýzu vstupního řetězce pro danou pravděpodobnostní bezkontextovou gramatiku.

G. Lyon^[34] a B. Langa^[35] vytvořil varianty Earleyova algoritmu, které fungují pro vstupní věty s chybějícími, nadbytečnými nebo neznámými fragmenty.

Zdrojový kód

V polských wikizdrojích je zdrojový kód Earleyova analyzátoru v jazyce Python, který pracuje bez náhledu, zpracovává prázdná pravidla podle Earleyova návrhu^[2], a vytváří syntaktické stromy podle Lapšinova návrhu^[17]. Výstupem programu jsou všechny syntaktické stromy pro zadaný vstupní řetězec zapsané v závorkové notaci.

Tento program nalezne čtyři derivační stromy nejednoznačné věty time flies like an arrow. Výsledek vykreslený pomocí programu phpSyntaxTree^[36] vypadá takto:

časové mouchy mají rády šíp	čas letí jako šíp	měř čas much podobných šípu	měř čas much jako šíp

Derivační stromy věty time flies like an arrow

Odkazy

Reference

V tomto článku byly použity překlady textů z článků Earley parser na anglické Wikipedii a Algorytm Earleya na polské Wikipedii.

↑ ^a ^b EARLEY, Jay. An Efficient Context-Free Parsing Algorithm. Pittsburg: Carnegie-Mellon University, Computer Science Department, 1968. Dostupné online.
↑ ^a ^b ^c ^d ^e ^f EARLEY, Jay. An efficient context-free parsing algorithm. Communications of the ACM. 1970, roč. 13, čís. 2. Dostupné online. DOI 10.1145/362007.362035.
↑ EARLEY, Jay. An Efficient Context-Free Parsing Algorithm. Communications of the ACM. Leden 1983, roč. 26, čís. 1, s. 57–61. Dostupné online. ISSN 0001-0782.
↑ MCCONNEL, Stephen. PC-PATR Reference Manual [online]. 1995-10-30. Dostupné online.
↑ ; BOULLIER, Pierre; SAGOT, Benoît. Proceedings of the Ninth International Workshop on Parsing Technology. Vancouver: [s.n.], 2005. Kapitola Efficient and robust LFG parsing: SXLFG, s. 1–10.
↑ KEGLER, Jeffrey. What is Marpa algorithm? [online]. Dostupné online.
↑ AYCOCK, John. Proceedings of the 7th International Python Conference. Houston: [s.n.], 1998. Kapitola Compiling Little Languages in Python.
↑ TRATT, Laurence. Domain Specific Language Implementation via Compile-Time Meta-Programming. ACM Transactions on Programming Languages and Systems (TOPLAS). Říjen 2008, roč. 30, čís. 6, s. 1–40. Dostupné online. ISSN 0164-0925.
↑ JURAFSKY, D. Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics and Speech Recognition. [s.l.]: Pearson Prentice Hall, 2009. Dostupné online. ISBN 9780131873216.
↑ AHO, Alfred V.; ULLMAN, Jeffrey D. The Theory of Parsing, Translation, and Compiling. Englevood Cliffs: Prentice Hall, 1972. Dostupné online. ISBN 0139145567. S. 320−332.
↑ ^a ^b AYCOCK, John; HORSPOOL, R. Nigel. Practical Earley Parsing. The Počítač Journal. Roč. listopad 2002, čís. 45(6), s. 620–630. Dostupné online. ISSN 0010-4620.
↑ GRUNE, Dick; JACOBS, Ceriel J.H. Parsing Techniques: A Practical Guide. New York: Springer, 2008. Dostupné online. ISBN 038720248X. Kapitola Eliminating ε-Rules (kapitola 4.2.3.1).
↑ TOMITA, Masaru. Efficient Parsing for Natural Language: A Fast Algorithm for Practical Systems. [s.l.]: Springer Science a Business Media, 2013-04-17. Dostupné online. ISBN 1475718853.
↑ SCOTT, Elizabeth. SPPF-Style Parsing From Earley Recognizers. Electronic Notes in Theoretical Computer Science. 2008-04-01. Dostupné online. DOI 10.1016/j.entcs.2008.03.044.
↑ TOMITA, Masaru; JOSHI (RED.), Aravind K. Proceedings of the 9th International Joint Conference on Artificial Intelligence (IJCAI-85). Los Angeles: Morgan Kaufmann, 1985. Kapitola An Efficient Context-Free Parsing Algorithm for Natural Languages, s. 756–764.
↑ JOHNSON, Mark; TOMITA, Masaru. Generalized LR Parsing. Boston/Dordrecht/London: Kluver Academic Publishers, 1991. ISBN 0792392019. Kapitola The Computational Complexity of GLR Parsing, s. 35–42.
↑ ^a ^b ЛАПШИН, Владимир А. Адаптированный для построения деревьев вывода алгоритм Эрли. Научно-техническая информация. Серия 2. Информационные процессы и системы. Roč. květen 2005, čís. 5, s. 1–14. ISSN 0548-0027. (rusky)
↑ SCOTT, Elizabeth. SPPF-Style Parsing From Earley Recognisers. Electronic Notes in Theoretical Počítač Science. Roč. duben 2008, čís. 203(2), s. 53–67. Dostupné online. ISSN 1571-0661.
↑ GRUNE, Dick; JACOBS, Ceriel J.H. Parsing Techniques: A Practical Guide. New York: Springer, 2008. Dostupné online. ISBN 038720248X. Kapitola Constructing a Parse Tree (část 7.2.1.2).
↑ BOUCKAERT, M.; PIROTTE, Alain; SNELLING, M. Efficient Parsing Algorithms for General Context-Free Parsers. Information Sciences. Roč. leden 1975, čís. 8(1), s. 1–26. ISSN 0020-0255.
↑ PEREIRA, Fernando C.N.; MARCUS (RED.), Mitch. Proceedings of the 21st Annual Meeting of the Association for Computational Linguistics. Morristown, New Jersey: Association for Computational Linguistics, 1983. Kapitola Parsing As Deduction, s. 137–144.
↑ SHIEBER, Stuart M.; MANN (RED.), William C. Proceedings of the 23rd Annual Meeting of the Association for Computational Linguistics. Morristown, New Jersey: Association for Computational Linguistics, 1985. Kapitola Using Restriction to Extend Parsing Algorithms for Complex-Feature-Based Formalisms, s. 145–152.
↑ SCHABES, Yves; HOBBS (RED.), Jerry. Proceedings of the 26th Annual Meeting of the Association for Computational Linguistics. Morristown, New Jersey: Association for Computational Linguistics, 1988. Kapitola An Earley-Type Parsing Algorithm for Tree Adjoining Grammars, s. 258–269.
↑ DE KERCADIO, Yannick. Proceedings of the Fourth International Workshop on Tree Adjoining Grammars and Related Frameworks (TAG+). Philadelphia: University of Pennsylvania, 1998. Kapitola An improved Earley parser with LTAG, s. 84–87.
↑ CORREA, Nelson; KUNZE, Jürgen; REIMANN (RED.), Dorothee. Proceedings of the Fifth Conference of the European Chapter of the Association for Computational Linguistics. Morristown, New Jersey: Association for Computational Linguistics, 1991. Kapitola An Extension of Earley's Algorithm for S-Attributed Grammars, s. 299–302.
↑ SEIFERT, Sebastian; FISCHER, Ingrid. Parsing String Generating Hypergraph Grammars. Lecture Notes in Počítač Science. Roč. 2004, čís. 3256, s. 352–367. Dostupné online. ISSN 0302-9743.
↑ VAN EIJCK, Jan. Sequentially Indexed Grammars. Journal of Logic and Computation. Roč. duben 2008, čís. 18(2), s. 205–228. Dostupné online. ISSN 0955-792X.
↑ SILBERSCHATZ (RED.), Avi. Proceedings of the Fifth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems. New York: Association for Computing Machinery, 1986. Kapitola Magic Sets and Other Strange Ways to Implement Logic Programs (Extended Abstract), s. 1–15.
↑ GRAHAM, Susan L.; HARRISON, Michael A. Parsing of General Context-Free Languages. Advances in Computers. Roč. 1976, čís. 14, s. 77–185. ISSN 0065-2458.
↑ GRAHAM, Susan L.; HARRISON, Michael A.; RUZZO, Walter R. An Improved Context-Free Recognizer. ACM Transactions on Programming Languages and Systems (TOPLAS). Roč. červen 1980, čís. 2(3), s. 415–462. Dostupné online. ISSN 0164-0925.
↑ AYCOCK, John; WILHELM (RED.), Reinhard. Proceedings of the 10th International Conference on Compiler Construction. Berlin: Springer-Verlag, 2001. ISBN 3-540-41861-X. Kapitola Directly-Executable Earley Parsing, s. 229–243.
↑ PÄSELER, Annedore; NIEMANN A IN. (RED.), H. Proceedings of the NATO Advanced Study Institute on Recent Advances in Speech Understanding and Dialog Systems. Berlin, Heidelberg: Springer-Verlag, 1988. ISBN 0-387-19245-X. Kapitola Modification of Earley's Algorithm for Speech Recognition, s. 465–472.
↑ STOLCKE, Andreas. An Efficient Probabilistic Context-Free Parsing Algorithm that Computes Prefix Probabilities. Computational Linguistics. Roč. červen 1995, čís. 21(2), s. 165–201. Dostupné online. ISSN 0891-2017.
↑ LYON, Gordon. Syntax-Directed Least-Errors Analysis for Context-Free Languages: A Practical Approach. Communications of the ACM. Roč. leden 1974, čís. 17(1), s. 3–14. Dostupné online. ISSN 0001-0782.
↑ LANG, Bernard. Proceedings of the 12th Conference on Computational Linguistics. Morristown, New Jersey: Association for Computational Linguistics, 1988. ISBN 963-8431-56-3. Kapitola Parsing Incomplete Sentences, s. 365–371.
↑ EISENBACH, Mei; EISENBACH, André. phpSyntaxTree [online]. Dostupné online.

Související články

Externí odkazy

AYCOCK, John; HORSPOOL, R. Nigel. Practical Earley Parsing. 6. vyd. Svazek 45. [s.l.]: [s.n.], 2002. DOI 10.1093/comjnl/45.6.620.
LEO, Joop M. I. M. A general context-free parsing algorithm running in linear time on every LR(k) grammar without using lookahead. 1. vyd. Svazek 82. [s.l.]: [s.n.], 1991. DOI 10.1016/0304-3975(91)90180-. .

TOMITA, Masaru. LR parsers for natural languages. In: 10th International Conference on Computational Linguistics. [s.l.]: [s.n.], 1984. Dostupné online.

ŽELEZNÝ, Miloš. Strukturální metody rozpoznávání [online]. Plzeň: Katedra kybernetiky ZČU. Dostupné online.

Implementace

Implementace pro jazyk C/C++

'Earley Parser' Earleyův analyzátor pro jazyk C - knihovna.
'C Earley Parser' Earleyův analyzátor pro jazyk C.

Implementace pro jazyk Java

PEN Java knihovna, která implementuje Earleyův algoritmus.
Pep Java knihovna, která implementuje Earleyův algoritmus a při analýze vytváří tabulky a derivační stromy.
[1] Java implementace Earleyova analyzátoru.

Implementace pro JavaScript

'JavaScript Moony Parser' Druh Earleyova analyzátoru napsaný v JavaScriptu.
Nearley Earleyův analyzátor obsahující část vylepšení použitých v analyzátoru Marpa.

Implementace pro jazyk Perl

Marpa::R2, Perlový modul. Marpa je Earleyův algoritmus zahrnující vylepšení, která navrhli Joop Leo, Aycock a Horspool.
Parse::Earley Perlový modul, který implementuje původní algoritmus Jay Earleye.

Implementace pro jazyk Python

Charty Implementace Earleyova analyzátoru pro Python.
NLTK Toolkit pro Python, který obsahuje Earleyův analyzátor.
Spark Objektově orientovaný „malý jazykový framework“ pro Python, který implementuje Earleyův analyzátor.
earley3.py Samostatná implementace algoritmu s méně než 150 řádky kódu, včetně generování lesa analýzy a příkladů.

Implementace pro jazyk Common Lisp

CL-EARLEY-PARSER Knihovna pro Common Lisp, která implementuje Earleyův analyzátor.

Implementace pro jazyk Scheme/Racket

Charty-Racket Implementace Earleyova analyzátoru pro jazyky Scheme / Racket.

Další nástroje

Překladač překladačů Accent

[Earley1-1] EARLEY, Jay. An Efficient Context-Free Parsing Algorithm. Pittsburg: Carnegie-Mellon University, Computer Science Department, 1968. Dostupné online.

[Earley2-2] ↑ ^a ^b ^c ^d ^e ^f EARLEY, Jay. An efficient context-free parsing algorithm. Communications of the ACM. 1970, roč. 13, čís. 2. Dostupné online. DOI 10.1145/362007.362035.

[3] EARLEY, Jay. An Efficient Context-Free Parsing Algorithm. Communications of the ACM. Leden 1983, roč. 26, čís. 1, s. 57–61. Dostupné online. ISSN 0001-0782.

[4] MCCONNEL, Stephen. PC-PATR Reference Manual [online]. 1995-10-30. Dostupné online.

[5] ; BOULLIER, Pierre; SAGOT, Benoît. Proceedings of the Ninth International Workshop on Parsing Technology. Vancouver: [s.n.], 2005. Kapitola Efficient and robust LFG parsing: SXLFG, s. 1–10.

[6] KEGLER, Jeffrey. What is Marpa algorithm? [online]. Dostupné online.

[7] AYCOCK, John. Proceedings of the 7th International Python Conference. Houston: [s.n.], 1998. Kapitola Compiling Little Languages in Python.

[8] TRATT, Laurence. Domain Specific Language Implementation via Compile-Time Meta-Programming. ACM Transactions on Programming Languages and Systems (TOPLAS). Říjen 2008, roč. 30, čís. 6, s. 1–40. Dostupné online. ISSN 0164-0925.

[Jurafsky-9] JURAFSKY, D. Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics and Speech Recognition. [s.l.]: Pearson Prentice Hall, 2009. Dostupné online. ISBN 9780131873216.

[10] AHO, Alfred V.; ULLMAN, Jeffrey D. The Theory of Parsing, Translation, and Compiling. Englevood Cliffs: Prentice Hall, 1972. Dostupné online. ISBN 0139145567. S. 320−332.

[Aycock-Horspool-11] AYCOCK, John; HORSPOOL, R. Nigel. Practical Earley Parsing. The Počítač Journal. Roč. listopad 2002, čís. 45(6), s. 620–630. Dostupné online. ISSN 0010-4620.

[12] GRUNE, Dick; JACOBS, Ceriel J.H. Parsing Techniques: A Practical Guide. New York: Springer, 2008. Dostupné online. ISBN 038720248X. Kapitola Eliminating ε-Rules (kapitola 4.2.3.1).

[13] TOMITA, Masaru. Efficient Parsing for Natural Language: A Fast Algorithm for Practical Systems. [s.l.]: Springer Science a Business Media, 2013-04-17. Dostupné online. ISBN 1475718853.

[14] SCOTT, Elizabeth. SPPF-Style Parsing From Earley Recognizers. Electronic Notes in Theoretical Computer Science. 2008-04-01. Dostupné online. DOI 10.1016/j.entcs.2008.03.044.

[15] TOMITA, Masaru; JOSHI (RED.), Aravind K. Proceedings of the 9th International Joint Conference on Artificial Intelligence (IJCAI-85). Los Angeles: Morgan Kaufmann, 1985. Kapitola An Efficient Context-Free Parsing Algorithm for Natural Languages, s. 756–764.

[16] JOHNSON, Mark; TOMITA, Masaru. Generalized LR Parsing. Boston/Dordrecht/London: Kluver Academic Publishers, 1991. ISBN 0792392019. Kapitola The Computational Complexity of GLR Parsing, s. 35–42.

[Lapšin-17] ЛАПШИН, Владимир А. Адаптированный для построения деревьев вывода алгоритм Эрли. Научно-техническая информация. Серия 2. Информационные процессы и системы. Roč. květen 2005, čís. 5, s. 1–14. ISSN 0548-0027. (rusky)

[18] SCOTT, Elizabeth. SPPF-Style Parsing From Earley Recognisers. Electronic Notes in Theoretical Počítač Science. Roč. duben 2008, čís. 203(2), s. 53–67. Dostupné online. ISSN 1571-0661.

[Grune-Jacobs-19] GRUNE, Dick; JACOBS, Ceriel J.H. Parsing Techniques: A Practical Guide. New York: Springer, 2008. Dostupné online. ISBN 038720248X. Kapitola Constructing a Parse Tree (část 7.2.1.2).

[20] BOUCKAERT, M.; PIROTTE, Alain; SNELLING, M. Efficient Parsing Algorithms for General Context-Free Parsers. Information Sciences. Roč. leden 1975, čís. 8(1), s. 1–26. ISSN 0020-0255.

[21] PEREIRA, Fernando C.N.; MARCUS (RED.), Mitch. Proceedings of the 21st Annual Meeting of the Association for Computational Linguistics. Morristown, New Jersey: Association for Computational Linguistics, 1983. Kapitola Parsing As Deduction, s. 137–144.

[22] SHIEBER, Stuart M.; MANN (RED.), William C. Proceedings of the 23rd Annual Meeting of the Association for Computational Linguistics. Morristown, New Jersey: Association for Computational Linguistics, 1985. Kapitola Using Restriction to Extend Parsing Algorithms for Complex-Feature-Based Formalisms, s. 145–152.

[23] SCHABES, Yves; HOBBS (RED.), Jerry. Proceedings of the 26th Annual Meeting of the Association for Computational Linguistics. Morristown, New Jersey: Association for Computational Linguistics, 1988. Kapitola An Earley-Type Parsing Algorithm for Tree Adjoining Grammars, s. 258–269.

[24] DE KERCADIO, Yannick. Proceedings of the Fourth International Workshop on Tree Adjoining Grammars and Related Frameworks (TAG+). Philadelphia: University of Pennsylvania, 1998. Kapitola An improved Earley parser with LTAG, s. 84–87.

[25] CORREA, Nelson; KUNZE, Jürgen; REIMANN (RED.), Dorothee. Proceedings of the Fifth Conference of the European Chapter of the Association for Computational Linguistics. Morristown, New Jersey: Association for Computational Linguistics, 1991. Kapitola An Extension of Earley's Algorithm for S-Attributed Grammars, s. 299–302.

[26] SEIFERT, Sebastian; FISCHER, Ingrid. Parsing String Generating Hypergraph Grammars. Lecture Notes in Počítač Science. Roč. 2004, čís. 3256, s. 352–367. Dostupné online. ISSN 0302-9743.

[27] VAN EIJCK, Jan. Sequentially Indexed Grammars. Journal of Logic and Computation. Roč. duben 2008, čís. 18(2), s. 205–228. Dostupné online. ISSN 0955-792X.

[28] SILBERSCHATZ (RED.), Avi. Proceedings of the Fifth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems. New York: Association for Computing Machinery, 1986. Kapitola Magic Sets and Other Strange Ways to Implement Logic Programs (Extended Abstract), s. 1–15.

[29] GRAHAM, Susan L.; HARRISON, Michael A. Parsing of General Context-Free Languages. Advances in Computers. Roč. 1976, čís. 14, s. 77–185. ISSN 0065-2458.

[30] GRAHAM, Susan L.; HARRISON, Michael A.; RUZZO, Walter R. An Improved Context-Free Recognizer. ACM Transactions on Programming Languages and Systems (TOPLAS). Roč. červen 1980, čís. 2(3), s. 415–462. Dostupné online. ISSN 0164-0925.

[31] AYCOCK, John; WILHELM (RED.), Reinhard. Proceedings of the 10th International Conference on Compiler Construction. Berlin: Springer-Verlag, 2001. ISBN 3-540-41861-X. Kapitola Directly-Executable Earley Parsing, s. 229–243.

[32] PÄSELER, Annedore; NIEMANN A IN. (RED.), H. Proceedings of the NATO Advanced Study Institute on Recent Advances in Speech Understanding and Dialog Systems. Berlin, Heidelberg: Springer-Verlag, 1988. ISBN 0-387-19245-X. Kapitola Modification of Earley's Algorithm for Speech Recognition, s. 465–472.

[33] STOLCKE, Andreas. An Efficient Probabilistic Context-Free Parsing Algorithm that Computes Prefix Probabilities. Computational Linguistics. Roč. červen 1995, čís. 21(2), s. 165–201. Dostupné online. ISSN 0891-2017.

[34] LYON, Gordon. Syntax-Directed Least-Errors Analysis for Context-Free Languages: A Practical Approach. Communications of the ACM. Roč. leden 1974, čís. 17(1), s. 3–14. Dostupné online. ISSN 0001-0782.

[35] LANG, Bernard. Proceedings of the 12th Conference on Computational Linguistics. Morristown, New Jersey: Association for Computational Linguistics, 1988. ISBN 963-8431-56-3. Kapitola Parsing Incomplete Sentences, s. 365–371.

[36] EISENBACH, Mei; EISENBACH, André. phpSyntaxTree [online]. Dostupné online.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]