Ерлијев анализатор
Ерлијев анализатор, назван по свом изумитељу Џеју Ерлију, је врста табеларног анализатора који се углавном користи за анализу у рачунарској лингвистици. Алгоритам користи динамичко програмирање. Ерлијеви анализатори су погодни зато што могу да анализирају све контекстно слободне језике. У општем случају Ерлијев анализатор завршава у кубном времену (О(n3), где је n дужина анализираног стринга), у квадратном времену (О(n2)) за једнозначне граматике, а у линеарном времену за скоро све 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-у.