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

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

Algoritmus je vhodný i pro nejednoznačné bezkontextové jazyky používané pro zpracování přirozeného jazyka, 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(n3), kde n je délka analyzovaného řetězce; pro jednoznačné gramatiky pracuje v kvadratickém čase O(n2), 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.

Earleyův analyzátor () je syntaktický analyzátor založený na Earleyově algoritmu. Často jej používají projektové frameworky podporující Rapid Application Development (RAD) 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 (). 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 () 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žívá 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), Xk je jeden terminální nebo neterminální symbol, malá písmena tn 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 t1 … tn (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í věty; před načtením prvního symbolu je vstupní pozice 0.

Earleyova položka pro pravidlo gramatiky A → X1 … Xq je výraz tvaru [A →h X1 … Xp •i Xp + 1 … Xq], přičemž tečka může být v libovolném místě počínaje pozicí bezprostředně před X1 až po pozici bezprostředně za Xq, 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’ →0 •0 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 () 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 →h X1 … Xp •i Xp+1 … Xq], která má za tečkou neterminální symbol, tj. Xp+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í () je načtení terminálního symbolu shodného s očekáváním analyzátoru shora dolů: Jestliže ti+1 je první dosud nenačtený symbol ve vstupním řetězci, pak pro každou položku [A →h α •i ti+1η], která má tento symbol bezprostředně za tečkou, přidáme položku [A →h αti+1 •i+1 η]. Kompletace () realizuje část analýzy zdola nahoru: Pro každou kompletní položku, to jest položku tvaru [A →h α •i], která má tečku na konci, 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ěněn 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á.

Alternativní zápis Earleyovy položky se někdy rozdělují podle vstupní pozice (tj. indexu za tečkou) do různých množin 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 → X1 … Xp • Xp + 1 … Xq, 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: 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í: jestliže další symbol ve vstupním řetězci je ti+1, pro každou položku v S(i) tvaru (X → α • ti+1 β, h), přidáme (X → α ti+1 • β, h) do S(i+1). Kompletace: 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, kterou napsal Daniel Jurafsky a James H. Martin. Earleyovy položky se nazývají state, jejich množina je S; predikát FINISHED je pravdivý, pokud tečka v položce je na konci pravé strany, funkce NEXT_ELEMENT_OF vrací první symbol za tečkou, počáteční symbol je #.

DECLARE ARRAY S;

function INIT(words) S ← CREATE_ARRAY(LENGTH(words) + 1) for k ← from 0 to LENGTH(words) do S[k] ← EMPTY_ORDERED_SET

function EARLEY_PARSE(words, grammar) INIT(words) ADD_TO_SET((# → •S, 0), S) for k ← from 0 to LENGTH(words) do for each state in S[k] do { S[k] se v této smyčce může zvětšovat } if not FINISHED(state) then if NEXT_ELEMENT_OF(state) is a nonterminal then PREDICTOR(state, k, grammar) { neterminál } else do SCANNER(state, k, words) { terminál } else do COMPLETER(state, k) end end return chart

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

procedure SCANNER((A → α•aβ, j), k, words) if a ⊂ PARTS_OF_SPEECH(words[k]) then ADD_TO_SET((A → αa•β, j), S[k+1]) end

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

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 TheDet blackAdj catN ateV aDet whiteAdj mouseN vytváří algoritmus následující množiny Earleyových položek:

náhled|300px|Derivační strom věty the black cat ate a white mouse

náhled|166px|Derivační strom věty the black cat ate

{| class="wikitable" |- style="background-color: #efefef;" ! Earleyova položka ! Zdroj přidání do množiny položek

| [S’ →0 •0 S] | inicializace

| [S →0 •0 NP VP] | predikce S z položky [S’ →0 •0 S]

| [NP →0 •0 Det N] | predikce NP z položky [S →0 •0 NP VP]

| [NP →0 •0 Det Adj N] | predikce NP z položky [S →0 •0 NP VP]

| [NP →0 Det •1 N] | načtení Det z položky [NP →0 •0 Det N]

| [NP →0 Det •1 Adj N] | načtení Det z položky [NP →0 •0 Det Adj N]

| [NP →0 Det Adj •2 N] | načtení Adj z položky [NP →0 Det •1 Adj N]

| [NP →0 Det Adj N •3] | načtení N z položky [NP →0 Det Adj •2 N]

| [S →0 NP •3 VP] | kompletace NP z položky [S0 → •0 NP VP]

| [VP →3 •3 V] | predikce VP z položky [S →0 NP •3 VP]

| [VP →3 •3 V NP] | predikce VP z položky [S →0 NP •3 VP]

| [VP →3 V •4] | načtení V z položky [VP →3 •3 V]

| [VP →3 V •4 NP] | načtení V z položky [VP →3 •3 V NP]

| [S →0 NP VP •4] | kompletace VP z položky [S →0 NP •3 VP]

| [NP →4 •4 Det N] | predikce NP z položky [VP →3 V •4 NP]

| [NP →4 •4 Det Adj N] | predikce NP z položky [VP →3 V •4 NP]

| [S’ →0 S •4] | kompletace S z položky [S’ →0 •0 S]

| [NP →4 Det •5 N] | načtení Det z položky [NP →4 •4 Det N]

| [NP →4 Det •5 Adj N] | načtení Det z položky [NP →4 •4 Det Adj N]

| [NP →4 Det Adj •6 N] | načtení Adj z položky [NP →4 Det •5 Adj N]

| [NP →4 Det Adj N •7] | načtení N z položky [NP →4 Det Adj •6 N]

| [VP →3 V NP •7] | kompletace NP z položky [VP →3 V •4 NP]

| [S →0 NP VP •7] | kompletace VP z položky [S →0 NP •3 VP]

| [S’ →0 S •7] | kompletace S z položky [S’ →0 •0 S]

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

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