Ерлијев анализатор

Ерлијев анализатор, назван по свом изумитељу Џеју Ерлију, је врста табеларног анализатора који се углавном користи за анализу у рачунарској лингвистици. Алгоритам користи динамичко програмирање. Ерлијеви анализатори су погодни зато што могу да анализирају све контекстно слободне језике. У општем случају Ерлијев анализатор завршава у кубном времену (О(n³), где је n дужина анализираног стринга), у квадратном времену (О(n²)) за једнозначне граматике, а у линеарном времену за скоро све LR(k) граматике. Нарочито се добро понаша када су правила граматике лево рекурзивна.

Алгоритам

У следећим описима, α, β, и γ представљају било који стринг завршних или незавршних симбола (укључујући и празан стринг), X, Y, и Z представљају појединачне незавршне симболе, а a представља завршни симбол. Ерлијев алгоритам је алгоритам наниже динамичког програмирања. У следећем, користићемо Ерлијеву нотацију са тачком: ако имамо правило X → αβ, нотација X → α • β представља стање у коме је α већ прочитано, а β се очекује. За сваку улазну позицију (што представља позицију између токена), анализатор генерише уређени скуп стања. Свако стање је уређени пар (X → α • β, i), кога чине

правило које се тренутно примењује (X → α β)
тренутна позиција у том правилу (представљене тачком)
позиција i на улазу на којој је поклапање са овим правилом почело: почетна позиција

(Првобитни Ерлијев алгоритам је укључивао предувид у стање; каснија истраживања су показала да ово има мало практичног ефекта на ефикасност анализе, те је постепено избачено из већине имплементација.) Скуп стања на улазној позицији к зове се S(к). Анализатор садржи S(0) који је сачињен само од почетног правила. Анализатор затим итеративно ради у три фазе: предвиђање, скенирање, и завршавање.

Предвиђање: За свако стање у S(к) форме (X → α • Y β, ј) (где је ј почетна позиција као горе), додати (Y → • γ, к) у S(к) за свако правило које има Y на левој страни.
Скенирање: Ако је а следећи симбол улазног тока, за свако стање у S(к) форме (X → α • а β, ј), додати (X →α а • β, ј) у S(к+1).
Завршавање: За свако стање у S(к) форме (X → γ • , ј), пронаћи стања у S(ј) форме (Y → α • X β, i) и додати (Y → α X • β, i) у S(к).

Ови кораци се понављају све до тренутка када више ни једно ново стање не може бити додато у скуп. Скуп се углавном имплементира као ред стања за извршавање (али се одређено стање мора појавити само на једном месту), а која ће се операција извршити зависи од врсте стања.

Пример

Узмимо следећу једноставну граматику аритметичких израза:

 P → S      # почетно правило
 S → S + M
    | M
 M → M * Т
    | Т
 Т → број

Са улазом: 2 + 3 * 4

Ово су скупови стања:

(бр. стања) Правило (Порекло) # Коментар
 ---------------------------------
 == S(0): • 2 + 3 * 4 ==
 (1)  P → • S         (0)    # почетно правило
 (2)  S → • S + M     (0)    # предвиђање (1)
 (3)  S → • M         (0)    # предвиђање (1)
 (4)  M → • M * Т     (0)    # предвиђање (3)
 (5)  M → • Т         (0)    # предвиђање (3)
 (6)  Т → • број      (0)    # предвиђање (5)
 
 == S(1): 2 • + 3 * 4 ==
 (1)  Т → број •      (0)    # скенирање  S(0)(6)
 (2)  M → Т •         (0)    # завршавање S(0)(5)
 (3)  M → M • * Т     (0)    # завршавање S(0)(4)
 (4)  S → M •         (0)    # завршавање S(0)(3)
 (5)  S → S • + M     (0)    # завршавање S(0)(2)
 (6)  P → S •         (0)    # завршавање S(0)(1)
 
 == S(2): 2 + • 3 * 4 ==
 (1)  S → S + • M     (0)    # скенирање S(1)(5)
 (2)  M → • M * Т     (2)    # предвиђање (1)
 (3)  M → • Т         (2)    # предвиђање (1)
 (4)  Т → • број      (2)    # предвиђање (3)
 
 == S(3): 2 + 3 • * 4 ==
 (1)  Т → број •      (2)    # скенирање S(2)(4)
 (2)  M → Т •         (2)    # завршавање S(2)(3)
 (3)  M → M • * Т     (2)    # завршавање S(2)(2)
 (4)  S → S + M •     (0)    # завршавање S(2)(1)
 (5)  S → S • + M     (0)    # завршавање S(0)(2)
 (6)  P → S •         (0)    # завршавање S(0)(1)
 
 == S(4): 2 + 3 * • 4 ==
 (1)  M → M * • Т     (2)    # скенирање S(3)(3)
 (2)  Т → • број      (4)    # предвиђање (1)
 
 == S(5): 2 + 3 * 4 • ==
 (1)  Т → број •      (4)    # скенирање S(4)(2)
 (2)  M → M * Т •     (2)    # завршавање S(4)(1)
 (3)  M → M • * Т     (2)    # завршавање S(2)(2)
 (4)  S → S + M •     (0)    # завршавање S(2)(1)
 (5)  S → S • + M     (0)    # завршавање S(0)(2)
 (6)  P → S •         (0)    # завршавање S(0)(1)

Стање (P → S •, 0) представља завршену анализу. Ово стање се такође појављује у S(3) и S(1), што су потпуне реченице.

Види још

Спољашње везе

Парсе::Еарлеy Ерлијев анализатор у Перлу.
'еарлy' Ерлијев анализатор у C-у.