7.7. A szóprobléma megoldása - szintaktikai elemzés

Ha egy adott környezetfüggetlen nyelvet generáló Greibach normálformájú nyelvtan alapján készítjük el a felismerő veremautomatát, akkor bármely wλ szó esetén az automata elfogadó számítás esetén minden lépésben az inputnak pontosan egy betűjét olvassa el. Ez azt jelenti hogy a w szó elfogadása |w| lépésben történik, vagyis lineáris, sőt valós-időben. Mindezzel az az egy probléma van, hogy a veremautomata egy nemdeterminisztikus eszköz (legalábbis a veremautomatáknak az az osztálya, amivel a teljes környezetfüggetlen nyelvosztály felismerhető). Tehát nemdeterminisztikusan egy szót végigolvasva, lineáris időben eldönthető a szóprobléma. A fejezet további részében determinisztikus algoritmusokat fogunk bemutatni a probléma megoldására.

A gyakorlati alkalmazásoknál általában nem elég egy formális nyelv felismerési problémáját csupán eldöntési problémának tekinteni, hanem egy uL szóról azt is meg kell állapítanunk, hogy az hogyan vezethető le az adott nyelvtanban. A szintaktikai elemzés tehát az adott nyelv szavainak a nyelvtani szerkezetét hivatott feltárni. Programozási nyelvek esetén is lényeges szerepe van a szintaktikai elemzésnek, mert a programok értelmezése a nyelvtani szerkezet ismeretére épül. A következőkben a környezetfüggetlen nyelvek szintaktikai elemzésének lehetőségét vizsgáljuk.

7.7.1. A CYK algoritmus

Tegyük fel, hogy az adott környezetfüggetlen nyelvtan Chomsky-féle normálalakra van hozva. Példaként tekintsük a következő nyelvtant:

G=({S, A, B, C, D}, {a, b}, S, H),

ahol a H- beli szabályok a következők:


                  S → A
                  B
 S → C
                  D
 S → C
                  B
 S → S
                  S
 A → B
                  C
 C → D
                  D
 B → S
                  C
 C → b
A → a
 D → B
                  A
 B → b.

A Cocke-Younger-Kasami-féle (vagy röviden CYK-) (ejtsd: kuk, jánger, kasami) felismerő algoritmus ezeknek a szabályoknak az alapján egy tetszőleges bemenő szóhoz igyekszik megkonstruálni a megfelelő levezetési fát. A Chomsky-féle normálalak miatt ez - a végpontokba befutó élektől eltekintve - egy bináris fa lesz, amelynek a méretét a bemenő szó hosszúsága fogja meghatározni. Ha például a bemenő szó mindössze négybetűs, akkor az összes lehetséges levezetési fának a mélysége maximum 4.

Egy n hosszúságú bemenő szó esetében a levezetési fa összes lehetséges csúcsai egy olyan háromszög mátrixba rendezhetők, amelynek a legalsó sora n- elemű, és a többi sora eggyel kevesebb elemű, mint a közvetlen alatta levő sor. Egy adott fa természetesen nem használhatja fel az összes mezőjét ennek a mátrixnak, csak az n=2 esetben.

A felismerési algoritmus ennek a háromszög mátrixnak az elemeit határozza meg úgy, hogy minden szögponthoz beírja azokat a nemterminális jeleket, amelyekből a kérdéses szögpont alatti részháromszög végpontjainak megfelelő bemenő szórészlet levezethető. Ha a mátrix kitöltését befejeztük, akkor már csak azt kell megnéznünk, hogy a háromszög legfelső csúcsához be van-e írva az S. Ha igen, akkor az adott bemenő szó levezethető az S- ből, tehát hozzátartozik az adott nyelvtan által generált nyelvhez. Ellenkező esetben viszont biztos, hogy nem tartozik hozzá, mert a kitöltés során minden lehetőséget ki fogunk meríteni.

A szóban forgó háromszög mátrixot felismerési mátrixnak nevezzük, és minden elemének tulajdonképpen egy rekeszt feleltetünk meg, ahová a változókat beírjuk. (Egy-egy rekeszbe a nemterminálisok egy-egy halmaza fog kerülni, mégpedig pontosan azok, amelyekből a mező alatti háromszögnek megfelelő terminális szó levezethető.) Ezeket a rekeszeket a következő ábrán megadott módon indexeljük. (Az ábrán a felismerési mátrix indexelését n=5 esetre láthatjuk.) A kitöltést az alsó (= első) sornál kezdve soronként balról-jobbra végezzük, a sorokat pedig alulról felfelé történő sorrendben töltjük ki.

Legyen a megvizsgálandó bemenő szó w=a 1 a 2a n . Az első sor i- edik rekeszébe beírjuk az B- t, ha szerepel egy Ba i szabály a nyelvtanban. (Ugyanabba a rekeszbe általában több változót is beírhatunk.) A mátrix további sorainak a kitöltésekor, minden egyes rekesz tartalmának a meghatározása az adott rekesz alatti részháromszög befogói mentén található rekeszek tartalmának a felhasználásával történik. Pontosabban az (i, j) rekesz kitöltéséhez az (1, j) rekeszben található változókat egyenként párosítjuk az (i-1, j+1) rekeszben találhatókkal, majd ugyanezt tesszük a (2, j) és (i-2, j+2), …, és végül az (i-1, j) és (1, j+i-1) rekesz-párokkal. Ha egy ilyen párosítás alkalmával olyan párt találunk, amely szerepel egy szabály jobb oldalán (a megfelelő sorrendben), akkor a szabály bal oldalán álló változót felvesszük az (i, j) rekeszbe. Formálisan: A- t akkor írjuk be az (i, j) rekeszbe, ha van olyan k∈{1, …, i-1}, hogy B szerepel a (k, j) rekeszeben miközben C szerepel a (i-k, j+k) rekeszben, és AB CH. (A feldolgozás menetét a következő ábra szemlélteti.)

A példánkban az a a b b a b a bemenő szóhoz ily módon megkonstruált felismerési mátrixot az alábbi ábra szemlélteti.

A CYK algoritmus helyességének bizonyítása: Indukcióval belátjuk, hogy bármely (i, j) rekeszre egy A nemterminális pontosan akkor eleme a rekesznek, ha belőle levezethető az input a j a i+j-1 részszava.

Az indukció alapját az (1, j) rekeszek jelentik. Állítás: A pontosan akkor szerepel (1, j) rekeszben ha A* a j . Az algoritmus szerint akkor került az A az (1, j) rekeszbe, ha a Chomsky-normálformájú nyelvtanban szerepel az Aa j alakú szabály. Egy Chomsky normálformájú nyelvtan esetén egy egybetűs szót pontosan akkor lehet levezetni egy adott nemterminálisból, ha azt egy lépésben, közvetlenül megtehetjük egy szabály segítségével. Ily módon az (1, j) rekeszekre beláttuk állításunkat.

Tekintsük most az (i, j) rekeszt valamely i>1 értékre. Tegyük fel most, indukciós feltevésként, hogy minden (k, j) (k<i) rekeszre igaz az állítás. Ha A szerepel az (i, j) rekeszben, akkor az algortimus működése miatt, csak úgy kerülhetett oda, ha van olyan k∈{1, …, i-1}, hogy B szerepel a (k, j) rekeszben és C szerepel a (i-k, j+k) rekeszben, valamint AB CH. Mivel k<i és i-k<i az indukciós feltevésünk miatt B* a j a j+k-1 és C* a j+k a i-k+j+k-1, vagyis C* a j+k a i+j-1. De hiszen éppen akkor vezethető le egy Chomsky normálalakú nyelvtanban egy egy betűnél hosszabb szó egy A nemterminálisból, ha van A → B C szabály, és a szó első része levezethető a B, a második része pedig a C nemterminálisból. Vagyis AB C* a j a j+k-1 a j+k a i-k+j+k-1 valamilyen k értékre, pontosan akkor ha A szerepel az (i, j) rekeszben. Egy nyelvtan által generált nyelvben pontosan azok a szavak szerepelnek amelyek a nyelvtan S mondatszimbólumából levezethetőek. Éppen ennek tesztelése (vagyis a legfelső rekeszben szerepel-e az S ) adja meg a választ arra kérdésre, hogy a keresett u szó benne van-e a generált nyelvben. Az állítást bebizonyítottuk.

Mivel szintaktikai elemzésről beszélünk, nézzük meg, hogyan is tudunk a felimerési mátrix alapján egy levezetési fát előállítani. A CYK algoritmus alulról felfelé elemzést valósít meg, és az összes lehetséges levezetési fát/részfát tartalmazza. Módosítsuk egy kicsit az algoritmust: amikor egy (i, j) rekeszbe beírunk egy A nemterminális szimbólumot, akkor írjuk be az indexébe, hogy miért is írtuk oda (hogyan került be a mátrixba): A helyett írjunk A B(k, j)C(i-k, j+k)- t ha a (k, j) rekeszben szereplő B és (i-k, j+k) rekeszben szereplő C, valamint az A → B C szabály alapján írtuk be az A- t. A módosított algoritmus alapján egyszerű egy leveztési fa előállítása: nézzük meg az (n, 1) (vagyis a legfelső) rekeszben szereplő S indexét, ebből kiolvasható, hogy mely S → A B alakú szabály alkalmazásakor került ide az S, márészt az is, hogy mely rekeszekben szereplenek az adott nemterminálisok, ezek indexeinek segítségével megállapíthatjuk ezek milyen szabály segítségével kerültek ide, és így tovább, amíg eljutunk az (1, j) rekeszekig, ahova az Aa j szabályok alapján írtunk be a megfelelő nemterminálisokat.

Az alábbi ábrán berajzoltunk egy levezetésfát. A levezetésben nem szereplő nemterminálisokat a jobb áttekinthetőség érdekében elhagytuk.

7.35. példa - Cocke-Younger-Kasami algoritmus 1. feladat


Tekintsük a következő grammatikát!
G=({S,A,B},{0,1},S,H),ahol H szabályai:
{S → SA, S → AB, A → BS, B → SA, A → 1, S → 1, B → 0}
Bizonyítsuk be, hogy az 10011 szó benne van a grammatika
által generált nyelvben, majd adjuk meg az összes legbaloldalibb levezetéset!


Megoldás: Jelölje V
               
                  i,j
               
 az (i,j) rekeszt.
1. levezetés: SSASAAABAA⇒ 1BAA⇒ 10AA⇒ 10BSA⇒100SA⇒1001A⇒ 10011
Nézzük, hogyan kerültek a levezetésbe az új nemterminálisok!

SV 5,1, mert SV 4,1 és AV 5,5, ahol S → SA-t használtuk. Kövessük a baloldali nemterminálist!
SV 4,1, mert SV 2,1 és AV 4,3, ahol S → SA-t használtuk ismét. Most ismét a balodali nemterminálist követjük
SV 2,1, mert AV 1,1 és BV 2,2, ahol S → AB-t használtuk.
AV 1,1, mert A → 1 ∈H
BV 2,2, mert B → 0 ∈H
AV 4,3, mert BV 3,3 és SV 4,4, ahol A → BS-t használtuk.
BV 3,3, mert B → 0 ∈H
SV 4,4, mert S → 1 ∈H
AV 5,5, mert A → 1 ∈H


2. levezetés: S⇒ SA⇒ ABA⇒1BA⇒10A⇒ 10BS⇒ 100S⇒100SA⇒ 1001A⇒ 10011

SV 5,1, mert SV 2,1 és AV 5,3, ahol S → SA-t használtuk. Kövessük a baloldali nemterminálist!
SV 2,1, mert AV 1,1 és BV 2,2, ahol S → AB-t használtuk. Kövessük a baloldali nemterminálist!
AV 1,1, mert A → 1 ∈H
BV 2,2, mert B → 0 ∈H
AV 5,3, mert BV 3,3 és SV 5,4, ahol A → BS-t használtuk. Kövessük ismét a baloldali nemterminálist!
BV 3,3, mert B → 0 ∈H
SV 5,4, mert SV 4,4 és AV 5,5, ahol S → SA-t használtuk. Kövessük a baloldali nemterminálist!
SV 4,4, mert S → 1 ∈H
AV 5,5, mert A → 1 ∈H

7.36. példa - Cocke-Younger-Kasami algoritmus 2. feladat


Tekintsük a G=({S,A,B,X,Y,Z},{a,b},S,H) grammatikát, ahol H szabályai:
{S → AY, Y → XB, X → BA, X → ZA, Z → BX,

                  A → a, B → b}!
Benne van-e a G nyelvtan által generált nyelvben az abbaab szó?


Megoldás:


Mivel S∈ V
               6,1, ezért a abbaab szó benne van a G grammatika által generált nyelvben. ★

7.37. példa - Cocke-Younger-Kasami algoritmus 3. feladat


Tekintsük a G=({S,A,B,C,D},{a,b,c},S,H) grammatikát, ahol H szabályai:
{S → AB, A → CA, A → SS, B → CD,

                  A → b, D → a, C → c, C → b}.
Döntsük el, benne van-e a grammatika által generált nyelvben az abcacb és a bbcbba szó,
majd ha lehet adjuk meg az összes legbaloldalibb levezetését!


Megoldás:


Mivel S ∉ V
               6,1, ezért az abcacb szó
nincs benne az adott grammatika által generált nyelvben.

Nézzük most a másik keresett szót:


Mivel S∈ V
               6,1, ezért a bbcbba szó benne van az adott grammatika által generált nyelvben.
Az egyetlen legbaloldalibb levezetés pedig:
S⇒ AB⇒ CAB⇒ bAB⇒ bCAB⇒ bbAB⇒ bbCAB⇒ bbcAB⇒ bbcbB⇒ bbcbCD
bbcbbD⇒ bbcbba ★

7.38. példa - Cocke-Younger-Kasami algoritmus 4. feladat


 Tekintsük a G=({S,A,B},{0,1},S,H) grammatikát ,ahol H szabályai:
 {S → AS, S → SB, S → AB, B → SB, A → SB, B → AS,

                   A → 0,B → 1}.
 Döntsük el CYK-algoritmus segítségével, hogy levezethető-e a nyelvtanban a 001111 szó!
 


Megoldás:

Tehát mivel S∈ V
               6,1, ezért a 001111 szó benne van az adott grammatika által generált nyelvben. ★

Az itt ismertetett algoritmus Chomsky-féle normálalakú nyelvtan esetén működött, a következő részben olyan algoritmust ismertetünk, amely bármilyen környezetfüggetlen nyelvtan esetén használható.

7.7.2. Az Earley-féle algoritmus

Ennél az algoritmusnál (az előző alfejezetben ismertetett algoritmushoz hasonlóan) az adott bemenő szóhoz felismerési mátrixot készítünk. Itt azonban a felismerési mátrix elemei nemterminálisok helyett úgynevezett pontozott szabályokat fognak tartalmazni. Legyen mondjuk A → p r, ahol p, r∈(NT)*, egy tetszőleges szabálya az adott környezetfüggetlen nyelvtannak. Ekkor az A → p.r egy, az eredeti szabályhoz tartozó pontozott szabály lesz, ahol a pont lényegében azt jelzi, hogy az adott szabály tekintetében balról jobbra haladva meddig jutottunk el az elemzésben.

Eszerint ha az elemzéssel a bemenő szó j- edik betűjéig jutottunk el, miközben megállapítottuk, hogy léteznek olyan p, q, r, t∈(NT)* szavak, melyekre S* p A q, p* a 1a i , r* a i+1a j és Ar tH. Ezt a körülményt fejezzük ki azzal, hogy az A → r.t pontozott szabályt beírjuk a felismerési mátrix i- edik sorának j- edik elemébe. A felismerési mátrixot (mely ismét egy háromszög mátrix) most az ábrán megadott módon indexeljük.

A felismerési mátrix most annyi sort és eggyel több oszlopot fog tartalmazni, mint ahány betűből a bemenő szó áll. A bemenő szó akkor és csak akkor tartozik a nyelvhez, ha a 0- dik sor n- edik elemében állni fog egy S → t. alakú pontozott szabály ( t∈(NT)* ). Az előbbiek értelmében ugyanis ez azt jelenti, hogy StH, és t* a 1a n .

Lássuk most az algoritmus pontos leírását. Ha a nyelvtan nem λ- mentes, akkor az Üresszó-lemmanál leírt módón készítsük el azon nemterminálisok U halmazát, amelyekből az üresszó levezethető. Az üresszavas szabályokat ennek az U halmaznak a segítségével fogjuk figyelembe venni. Tehát az algoritmusban a környezetfüggetlen nyelvtan λ- mentes részére szorítkozunk (vagyis nem használjuk az A → λ alakú szabályokat); viszont minden egyes Ar.B t pontozott szabály esetén ( A, BN, r, t∈(NT)* ) ha ez a szabály bekerült a felismerési mátrix egy cellájába, és BU, akkor Ar B.t pontozott szbályt is beírjuk az adott cellába ezzel figyelembe véve a B* λ esetet a szóbanforgó B- re. Ha a feladatunk az, hogy eldöntsük λL(G) teljesül-e, akkor ezt az SU kérdés alapján válaszoljuk meg. A továbbiakban nézzük meg ha hosszabb szóra kell megoldanunk a feladatot. Jelöljük a bemenő szó i- edik betűjét a i - vel, tehát legyen w=a 1a n . Legyen továbbá G=(N, T, S, H) egy környezetfüggetlen nyelvtan, és jelöljük az előző ábra szerint indexelt felismerési mátrix i- edik sorának j- edik elemét F i, j - vel. Legyen továbbá U={A | AN, A* λ}, és H ' a H λ- mentes része, vagyis H '={A | ApH, pλ}. Kezdetben a felismerési márix minden eleme üres, és az algoritmus mindegyikbe egy vagy több pontozott szabályt írhat be, vagy üresen is hagyhatja. A felismerési mátrix kitöltését oszloponként alulról fölfelé végezzük, kivéve a fődiagonálisban lévő elemeket, amelyeket az adott oszlopban utoljára töltünk ki. Az egyes oszlopokat balról jobbra vesszük sorra (ahogy az előző ábra mutatja). Az Earley-féle algoritmus lépései egy wλ input szóra a következőek. Mindegyik lépés előtt informálisan megadjuk, hogy miről is szól az adott lépés, ezután formálisan (matematikailag pontosan) is megadjuk az adott lépést.

0. (Segédlépés: nem λ-mentes nyelvtanok esetére) minden egyes pontozott szabály beírása után alkalmazandó: Ha a pont után BU nemterminális áll, akkor az adott szabályt felvesszük úgy is, hogy a pont már a B nemterminális után áll, az így beírt szabályt is viszgáljuk ez alapján.

1. (Kezdőlépés: az S- el kezdődő, vagyis az S → p alakú szabályok felvétele a legelső cellába kezdőponttal.) Minden SpH ' szabályra legyen S → .pF 0, 0, és legyen j=0.

2. (Főátlóbeli elemek kitöltése: ha az adott oszlopban a pont után szerepel B nemterminális, akkor felvesszük a B- vel kezdődő szabályokat kezdőponttal.) Ha BpH ' és van olyan k ≤ j, hogy Ar.B tF k, j valamely r, t∈(NT)*- ra, akkor legyen B → .pF j, j . Ekkor az újonnan beírt szabályokra is megvizsgáljuk az adott feltételek fennállását.

3. (Eggyel jobbra lépés.) Ha j<n, akkor növeljük j értékét eggyel, és legyen i=j-1.

4. (A baloldali szomszéd cellából szabálymásolás az oszlop terminálisnának átlépésével.) Legyen Ar a j .tF i, j , ha Ar.a j tF i, j-1.

5. (Cella hasonlítások: az oszlopban kitöltött legalsó cellát a kitöltendő cella balszomszédjával hasonlítjuk, aztán az oszlopban fölfelé haladunk az aktuális celláig, a sorban pedig balra a legelsőig; ha az oszlopban levő cellában van pontra végződő pontozott szabály, ami B nemterminálissal kezdődik, akkor a sorban levő cellából szabályt másolhatunk miközben átlépjük a B- t.) Legyen Ar B.tF i, j , ha van olyan k, melyre i ≤ k<j, és Ar.B tF i, k , Bp.∈F k, j valamely p∈(NT)*- ra.

6. (Ha a legutolsó cellát töltöttük ki, akkor w benne van a generált nyelvben pontosan akkor, ha ebben a cellában van S → p. alakú szabály; egyébként eggyel följebb lépünk és vissza a 4. lépésre, vagy ha legfelül vagyunk, akkor urás a főátlóra, és a 2. lépésre.) Ha i=0 és j=n, akkor wL(G) pontosan akkor ha van olyan p∈(NT)*, hogy Sp.∈F 0, n . Egyébként: ha i>0, akkor csökkentsük az i értékét eggyel, és térjünk vissza a negyedik lépésre. Ha i=0, akkor pedig térjünk vissza a második lépésre.

Ezzel az algoritmussal tehát megadtuk a felismerési mátrixot, amelyből a w szó levezetése viszonylag egyszerűen rekonstruálható, amennyiben wL(G). Az algoritmus helyességének a bizonyításához be kell látnunk a következő tételt.

58. Tétel. Az Earley-féle algoritmussal nyert felismerési mátrixban egy A → p.r pontozott szabály (p, r∈(NT)*) pontosan akkor szerepel az F i, j - ben, ha Ap rH, p* a i+1a j , és van olyan t∈(NT)* szó, amelyre S* a 1a i A t.

Bizonyítás. A bizonyítást először a λ- mentes nyelvtanokra végezzük el.

Először a feltétel szükségességét látjuk be. A bizonyítást a mátrix elemeire vonatkozó teljes indukcióval végezzük.

Az F 0, 0 esetében az 1. és a 2. lépések szerint csak olyan pontozott szabályok jöhetnek szóba, ahol a jobb oldalon a pont előtti rész üres. Ha tehát A → .r, akkor vagy A=S és SrH, vagy ArH és S* A t valamely t- re.

Az indukciót ezek után az (i, j) indexpároknak egy olyan elrendezésével végezzük, amely pontosan megfelel a mátrix kitöltési sorrendjének. A fődiagonális elemeit külön kell kezelnünk. Tegyük fel tehát, hogy a bizonyítandó állítás minden F l, m - re teljesül, ha m<j, vagy m=j és i<l<j.

Legyen most Ap.rF i, j . Ha ij, akkor ezt a szabályt csak az algoritmus 4. vagy 5. lépésében írhattuk be ide. Az első esetben p=p 'a j és Ap '.a j rF i, j-1. De akkor az indukciós feltevésből S* a 1a i A t következik valamilyen t szóra, és p '⇒* a i+1a j-1, amiből az állításunk közvetlenül adódik. Ha viszont az 5. lépésben írtuk be a szabályt, akkor p=p 'B valamely p '∈(NT)* szóra és B változóra úgy, hogy van egy olyan k index, melyre Ap '.B rF i, k , és Bq.∈F k, j valamely t szóra.

Az indukciós feltevésből most S* a 1a i A t, valamint p '⇒* a i+1a k , illetve S* a 1a k B t, és q* a k+1a j adódik. Ezekből a BqH figyelembevételével nyilván p 'B* a i+1a k a k+1a j amivel az állításunkat bebizonyítottuk.

Hátra van még az i=j eset ( i>0 ), vagyis a fődiagonálisban levő elemek esete. Az indukciós feltevés ebben az esetben azokra az F l, m elemekre vonatkozik, ahol m<j, vagy m=j és 0<l<j. A fődiagonális elemeibe csak az algoritmus 2. lépésében írhattunk be szabályokat. De itt is csak olyan B → .q alakú szabályok jöhetnek szóba, amelyekre van olyan i ≤ j, hogy Ap.B rF i, j . Itt az i=j eset is előfordulhat. Tekintsük azonban azt a szabályt, amelyet az algoritmus először helyez el az F j, j - ben. Ebben az esetben az i<j kell, hogy fennálljon. Az indukciós feltevésből tehát S* a 1a i A t és p* a i+1a j következik. Ugyanakkor nyilván A* p B r is fennáll, amiből S* a 1a j B r t következik, s ezzel állításunkat igazoltuk. Az indukciós feltevést most már minden új szabály elhelyezésénél alkalmazhatjuk az F j, j - be beírt szabályokra is. Ha tehát egy B → .q szabályt az algoritmus azért vesz fel az F j, j - be, mert BqH, és Ap.B rF j, j , akkor itt nyilván p=λ és S* a 1a j A t, és ezért S* a 1a j B r t, amivel a bizonyítást befejeztük.

A feltétel elégségességének bizonyítását ugyancsak teljes indukcióval végezzük. Először nézzük az F 0, 0- t. Tegyük fel, hogy S* B t teljesül valamely B változóra és t∈(NT)* szóra, és BqH. Az S* B t levezetés lépésszámára vonatkozóan egy külön teljes indukciót végzünk. Ha a lépésszám nulla, akkor B=S és t=λ, és ezért az algoritmus a B → .t szabályt már az első lépésben felveszi az F 0, 0- ba. Tegyük fel, hogy az állítás k lépésre igaz, és legyen az S* B t levezetés lépésszáma k+1. Ekkor nyilván van olyan A nemterminális és t ' szó, hogy S* A t ', AB t '', ahol t=t ''t ' és az S* A t ' levezetés lépésszáma k. Ezért az indukciós feltevésből A → .B t ''∈F 0, 0, tehát az algoritmus 2. lépése szerint B → .qF 0, 0.

Most tegyük fel, hogy az algoritmus elégséges volta igaz minden olyan F l, m - re, ahol m<j, vagy s=m és i<l<j. Legyen akkor Ap rH, p* a i+1a j , és S* a 1a i A t valamely t szóra. Ha most p=p 'a j , akkor az indukciós feltevés szerint Ap '.a j rF i, j-1, és az algoritmus 4. lépése alapján Ap 'a j .rF i, j . Egyébként p=p 'B, ahol B* a k+1a j és p '⇒* a i+1a k valamilyen k- ra. Az indukciós feltevésből most Ap '.B rF i, k és Bq.∈F k, j adódik valamilyen q szóra, amelyre q* a k+1a j és BqH. De akkor az algoritmus 5. lépése szerint Ap 'B.rF i, j .

Végül vegyük a fődiagonális elemeit. Az indukciós feltevést most azokra az F l, m elemekre tesszük, amelyekre m ≤ j és 0<l<j. Legyen tehát ArH és S* a 1a j A t. Ez a levezetés nyilván átrendezhető úgy, hogy a változók közül a legbaloldalibbat helyettesítjük be először mindaddig, amíg az a j - t meg nem kapjuk. Eszerint van egy olyan A ' változó, hogy S* a 1a k A 't '⇒* a 1a k a k+1a j A t ''t ', ahol t ''t '⇒* t. Ha itt k<j, akkor az indukciós feltevés szerint A ' → a k+1a j .A t ''∈F k, j , és így az algoritmus 2. lépése szerint A → .rF j, j . A k=j esetben viszont az indukciós feltevést már alkalmazhatjuk az A ' → A t '' szabályra és az S* a 1a j A 't ' levezetésre, hiszen ez a levezetés véges számú lépésből áll, tehát véges számú lépésben el kell jutnunk egy olyan esethez, ahol k<j. Az A ' → .A t ''∈F j, j - ből pedig az algoritmus 2. lépése szerint A → .rF j, j következik, és ezzel a tétel bizonyítását befejeztük a λ-mentes esetre.

Ha a nyelvtan nem λ- mentes akkor az algoritmus 0. lépése ezt éppen úgy veszi figyelembe, ahogyan az Üresszó lemma bizonyításában konstruáltunk ekvivalens nyelvtant az eredetihez, vagyis minden olyan nemterminális esetén amiből az üresszó levezethető úgy is tekinhetjük a levezetésben, hogy az üres szót vezetjük le belőle. Ezek alapján nyilvánvaló, hogy az algoritmus az ilyen esetlekben is helyesen működik. ∎

Az algoritmus futása során az input szó négyzetével arányos méretű táblázat (a felismerési mátrix) kitöltése történik. Az egy mezőbe írható pontozott szabályok számának felső korlátja kiszámolható a H szabályhalmaz elemeinek száma és hosszai alapján. Az algoritmus lépéseit megvizsgálva láthatjuk, hogy a 2. és 5. lépésekben az adott cella kitöltéséhez maximum a szó hosszának megfelelő mennyiségű cellában, illetve cellapárban található pontozott szabályokat kell megvizsgálni. Így a program futásának ideje, hasonlóan a CYK algoritmushoz, az input szó hosszának köbével arányos.

Az Earley-féle algoritmus működését először a következő egyszerű példán szemléltetjük.

7.39. példa - Earley algoritmus 1.feladat

A G generatív nyelvtan legyen a következő formában definiált: G=({S, A, B}, {a, +, ×, (, )}, S, H), ahol H szabályhalmaz a következő: {SS+A, A → A×B, B → (S), S → A, A → B, B → a}.


Tekintsük most az a×a+a bemenő szó szintaktikai elemzését. Az algoritmus az első lépésben az S → .S+A, S → .A szabályokat veszi fel az F 0, 0- ba. Ezután a 2. lépés alapján kiegészíti az F 0, 0- at az A → .A×B, A → .B, B → .(S), B → .a szabályokkal. Utána j értéke 1 lesz, és az algoritmus a 4. lépésben az F 0, 1- be felveszi a B → a. pontozott szabályt, mivel a bemenő szó első betűje a. Az 5. lépésben az F 0, 1 kiegészül még az alábbi szabályokkal: A → B., AAB, S → A., S → S.+A.

Ezután a 2. lépés következik, ahol most F 1, 1- et kell kitölteni. De az F 0, 1- ben szereplő szabályokhoz nem található egyetlen olyan szabály sem, amely a feltételeket kielégíti, hiszen az F 0, 1- beli szabályokban a pont után közvetlenül nem is fordul elő változó. Ezért az F 1, 1 üres marad. Az algoritmus ezután a j=2 értékre hajtja végre a 4. lépést, melynek során az F 1, 2 nyilván szintén üres marad, az F 0, 2- be pedig az AA×.B szabály fog bekerülni. Az 5. lépésben mind az F 1, 2, mind az F 0, 2 változatlan marad. Az F 2, 2- be ezután a 2. lépés során bekerülnek a B → .(S) és B → .a szabályok, mivel AA×.BF 0, 2.

A felismerési mátrix kitöltésének további menetét nem részletezzük, de a következő ábrán megadjuk a teljes mátrixot. Mivel ebben a mátrixban SS+A.∈F 0, 5, a kérdéses bemenő szó benne van az L(G)- ben. A tételünk szerint ugyanis ez pontosan akkor áll fenn, ha SS+AH és S+A* a×a+a, továbbá van olyan t szó, amelyre S* S t, mely utóbbi összefüggés már nem is lényeges most a mi szempontunkból.

7.40. példa - Earley algoritmus 2. feladat


 Tekintsük a G=({S,A,B},{0,1},S,H) grammatikát, ahol H szabályai:
 {S → 1A0,S → 0B1, A → B0, B → S0, A → 1, B → 0}.
 Döntsük el Earley-algoritmus segítségével, hogy levezethető-e a nyelvtanban a 011001 szó!
 


Megoldás:

Mivel a jobbfelső "cella" tartalmaz S-ből kiinduló pontra végződő szabályt,
ezért a 011001 szó benne van az adott grammatika által generált nyelvben. ★

7.41. példa - Earley algoritmus 3. feladat


 Tekintsük a G=({S,A,B},{a,b,c,+,(,)},S,H) grammatikát, ahol H szabályai:
 {S → S+A,S → A, A → AB, A → B, B → (S), B → a, B → b, B → c}.
 Döntsük el Earley-algoritmus segítségével, hogy levezethető-e a nyelvtanban az a(b+c) szó!
 


Megoldás:


Mivel a jobbfelső "cella" tartalmaz S-ből kiinduló pontra végződő szabályt,
ezért az a(b+c) szó benne van az adott grammatika által generált nyelvben. ★

7.42. példa - Earley algoritmus 4. feladat


 Tekintsük a G=({S,A,B},{a,b},S,H) grammatikát, ahol H szabályai:
 {S → AB,S   → λ, A → SAB, A → a, B → S, B → b}.
 Döntsük el Earley-algoritmus segítségével, hogy levezethető-e a nyelvtanban az aabb szó!
 


Megoldás:


Mivel a jobbfelső "cella" tartalmaz S-ből kiinduló pontra végződő szabályt,
ezért az aabb szó benne van az adott grammatika által generált nyelvben. ★