Erlijev analizator

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³), gde je n dužina analiziranog stringa), u kvadratnom vremenu (O(n²)) 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.