Erlijev analizator, nazvan po svom izumitelju Džeju Erliju, je vrsta tabelarnog analizatora koji se uglavnom koristi za analizu u računarskoj lingvistici. Algoritam koristi dinamičko programiranje. Erlijevi analizatori su pogodni zato što mogu da analiziraju sve kontekstno slobodne jezike. U opštem slučaju Erlijev analizator završava u kubnom vremenu (O(-{n}-3), gde je -{n}- dužina analiziranog stringa), u kvadratnom vremenu (O(-{n}-2)) za jednoznačne gramatike, a u linearnom vremenu za skoro sve -{LR(k)}- gramatike. Naročito se dobro ponaša kada su pravila gramatike levo rekurzivna. Algoritam U sledećim opisima, α, β, i γ predstavljaju bilo koji string završnih ili nezavršnih simbola (uključujući i prazan string), X, Y, i -{Z}- predstavljaju pojedinačne nezavršne simbole, a -{a}- predstavlja završni simbol. Erlijev algoritam je algoritam naniže dinamičkog programiranja. U sledećem, koristićemo Erlijevu notaciju sa tačkom: ako imamo pravilo X → αβ, notacija X → α • β predstavlja stanje u kome je α već pročitano, a β se očekuje. Za svaku ulaznu poziciju (što predstavlja poziciju između tokena), analizator generiše uređeni skup stanja. Svako stanje je uređeni par (X → α • β, -{i}-), koga čine pravilo koje se trenutno primenjuje (X → α β) trenutna pozicija u tom pravilu (predstavljene tačkom) pozicija -{i}- na ulazu na kojoj je poklapanje sa ovim pravilom počelo: početna pozicija (Prvobitni Erlijev algoritam je uključivao preduvid u stanje; kasnija istraživanja su pokazala da ovo ima malo praktičnog efekta na efikasnost analize, te je postepeno izbačeno iz većine implementacija.) Skup stanja na ulaznoj poziciji k zove se -{S}-(k). Analizator sadrži -{S}-(0) koji je sačinjen samo od početnog pravila. Analizator zatim iterativno radi u tri faze: predviđanje, skeniranje, i završavanje. Predviđanje: Za svako stanje u -{S}-(k) forme (X → α • Y β, j) (gde je j početna pozicija kao gore), dodati (Y → • γ, k) u -{S}-(k) za svako pravilo koje ima Y na levoj strani. Skeniranje: Ako je a sledeći simbol ulaznog toka, za svako stanje u -{S}-(k) forme (X → α • a β, j), dodati (X →α a • β, j) u -{S}-(k+1). Završavanje: Za svako stanje u -{S}-(k) forme (X → γ • , j), pronaći stanja u -{S}-(j) forme (Y → α • X β, -{i}-) i dodati (Y → α X • β, -{i}-) u -{S}-(k).
Ovi koraci se ponavljaju sve do trenutka kada više ni jedno novo stanje ne može biti dodato u skup. Skup se uglavnom implementira kao red stanja za izvršavanje (ali se određeno stanje mora pojaviti samo na jednom mestu), a koja će se operacija izvršiti zavisi od vrste stanja. Primer Uzmimo sledeću jednostavnu gramatiku aritmetičkih izraza:
-{P → S}- # početno pravilo -{S → S}- + M | M M → M * T | T T → broj
Sa ulazom: 2 + 3 * 4
Ovo su skupovi stanja:
(br. stanja) Pravilo (Poreklo) # Komentar
== -{S}-(0): • 2 + 3 * 4 == (1) -{P → • S }- (0) # početno pravilo (2) -{ S → • S + M}- (0) # predviđanje (1) (3) -{S → • M}- (0) # predviđanje (1) (4) M → • M * T (0) # predviđanje (3) (5) M → • T (0) # predviđanje (3) (6) T → • broj (0) # predviđanje (5)
== -{S}-(1): 2 • + 3 * 4 == (1) T → broj • (0) # skeniranje -{S}-(0)(6) (2) M → T • (0) # završavanje -{S}-(0)(5) (3) M → M • * T (0) # završavanje -{S}-(0)(4) (4) -{S}- → M • (0) # završavanje -{S}-(0)(3) (5) -{S → S • + M}- (0) # završavanje -{S}-(0)(2) (6) -{P → S}- • (0) # završavanje -{S}-(0)(1)
== -{S}-(2): 2 + • 3 * 4 == (1) -{S → S + • M}- (0) # skeniranje -{S}-(1)(5) (2) M → • M * T (2) # predviđanje (1) (3) M → • T (2) # predviđanje (1) (4) T → • broj (2) # predviđanje (3)
== -{S}-(3): 2 + 3 • * 4 == (1) T → broj • (2) # skeniranje -{S}-(2)(4) (2) M → T • (2) # završavanje -{S}-(2)(3) (3) M → M • * T (2) # završavanje -{S}-(2)(2) (4) -{S → S + M •}- (0) # završavanje -{S}-(2)(1) (5) -{S → S • + M}- (0) # završavanje -{S}-(0)(2) (6) -{P → S}- • (0) # završavanje -{S}-(0)(1)
== -{S}-(4): 2 + 3 * • 4 == (1) M → M * • T (2) # skeniranje -{S}-(3)(3) (2) T → • broj (4) # predviđanje (1)
== -{S}-(5): 2 + 3 * 4 • == (1) T → broj • (4) # skeniranje -{S}-(4)(2) (2) M → M * T • (2) # završavanje -{S}-(4)(1) (3) M → M • * T (2) # završavanje -{S}-(2)(2) (4) -{S → S + M •}- (0) # završavanje -{S}-(2)(1) (5) -{S → S • + M}- (0) # završavanje -{S}-(0)(2) (6) -{P → S •}- (0) # završavanje -{S}-(0)(1)
Stanje (-{P → S}- •, 0) predstavlja završenu analizu. Ovo stanje se takođe pojavljuje u -{S}-(3) i -{S}-(1), što su potpune rečenice. Vidi još -{CYK}- algoritam Kontekstno slobodne gramatike
Spoljašnje veze Parse::Earley Erlijev analizator u Perlu. 'early' Erlijev analizator u C-u.
Категорија:Преводиоци (рачунарство)