Лекция 23, 24. Тақырыбы: LR(1)-кестені құру

Лекция 23, 24.

Тақырыбы: LR(1)-кестені құру

2. LR(1)-кесте құру әдісінің негізгі идеясы

3. LR(1)- жағдайлар жиынының канондық жүйесін құру

4. LR(1)-кестені құру алгоритмі

1. LR(1)-анализаторды басқаратын кестені құру алгоритмін қарастырамыз.

Айталық G = (N, T, P, S) –КБ-грамматика. Берілген осы G грамматика үшін толықтырылған грамматика деп мына КБ грамматиканы айтамыз:

яғни S' бастапқы символ және S' S жаңа ереже енгізілген эквивалентті грамматика.

Бұл қосымша ереже анализатордың қашан талдауды тоқтатып, енуге рұқсат беруді анықтау үшін енгізіледі. (зафиксировать допуск входа). Осылайша, анализатор S' S ережесі бойынша қайтару жасауға дайын болған кезде ғана енуге рұқсат етіледі.

LR(1)-жағдай деп [A . , a] жұбын айтамыз, мұнда A -грамматика ережесі, а – терминал немесе оң жақтағы соңғы маркер $. Жағдайдың екінші компоненті авантізбек деп аталады.

Егер S _r^* Aw _r w шығаруы бар болса, мұнда = және не а – w-ң бірінші символы, не w = e, a = $., онда LR(1)-жағдай – [A . , a] белсенді δ үшін мүмкін делінеді.

(Будем говорить, что LR(1)-ситуация допустима для активного префикса , если существует вывод S _r^* Aw _r w, где = и либо a - первый символ w, либо w = e и a = $. )

Егер жағдай қайсыбір белсенді префикс үшін мүмкін болса, онда мұндай жағдайды мүмкін жағдай дейтін боламыз.

Мысал 4.9. G = ({S, B}, {a, b}, P, S) берілген. Ережелері:

	S BB
B aB | b

Оңжақты шығару бар S _r^*aaBab _raaaBab. Егер жоғарыдағы анықтамадағы = aa, A = B, w = ab, = a, = B десек, онда [B a.B, a] жағдайы белсенді = aaa префиксі үшін мүмкін екендігі оңай көрінеді. Сонымен бірге оңжақты S _r^*BaB _rBaaB шығаруы да бар. Сондықтан белсенді Baa префиксі үшін [B a.B, $] жағдайы мүмкін.

2. Әдістің негізгі идеясы берілген грамматика бойынша белсенді префикстерді танитын детерминант автомат құрылуында жатыр.

Жылжыту-қайыру типінде солдан оңға қарай жұмыс істейтін анализатор магазиннің төбесіндегі негізді тани алуы керек. (Анализатор, работающий слева-направо по типу сдвиг-свертка, должен уметь распознавать основы на верхушке магазина). Магазин мәнін оқығаннан кейінгі автомат мәні және ағымдағы енуші символ автоматтың кезектегі әрекетін анықтайды. Бұл шекті автоматтың ауысу функциясы болып LR-анализатордың ауысу функциясы табылады. Талдаудың әр қадамында магазинді қарап шыға бермеу үшін магазин түбінен жоғарысына дейін грамматика символдарын оқып шыққаннан кейінгі автомат жағдайы магазиннің төбесінде сақталынады.

Қайсыбір белсенді z префиксі үшін мүмкін болған жағдайлар жиынынан [A .B , a] түріндегі жағдайды қарастыралық. Сонда мына оңжақты шығару бар болады S _r^*yAax _ry B ax, мұнда z = y . Айталық ax-тан терминал bw қатары шығарылады. Онда қайсыбір B q түріндегі шығару ережесі үшін S _r^*zBbw _rzqbw шығаруы бар болады. Осылайша [B .q, b] жағдайы да z үшін мүмкін және [A B. , a] жағдайы белсенді zB префиксі үшін мүмкін. Мұнда не b β-дан шығарылатын біріші терминал бола алады, не β-дан ax _r^*bw шығаруында е шығарылады және сонда b тең а-ға болады, яғни, b - FIRST( ax)-ке тиісті. Осындай жағдайлардың барлығын берілген жағдайлар жиыны үшін құру, яғни оның тұйықталуын төменде келтірілген closure функциясы құрады.

Толықтырылған грамматиканың барлық мүмкін активті префикстері үшін мүмкін болған LR(1)-жағдайлардың жиындар жүйесі мүмкін болған LR(1)-жағдайлар жиынының канондық жүйесі деп аталады. Жиындардың канандық жүйесін құру алгоритмі төменде келтірілген.

3. Алгоритм 4.9. мүмкін болған LR(1)-жағдайлар жиынының канондық жүйесі құру

Кірісі. КБ-грамматика G = (N, T, P, S).

Шығысы. G грамматикасы үшін мүмкін болған LR(1)-жағдайлар жиынының C канондық жүйесі

Тәсіл. Толықтырылған G' грамматикасы үшін items процедурасын орындаудан тұрады. items процедурасы closure және goto функцияларын қолданады.

function closure(I){ /* I – жағдайлар жиыны */

for (I –дегі әрбір[A .B , a] жағдай үшін

G'-тағы әрбір B шығару ережесі үшін,

FIRST( a)-ғы әрбір b терминал үшін,

егер I-де [B . , b] жоқ болса, онда)

I-ге [B . , b]-ы қосу;

}

while ( I-ге жаңа жағдайды қосуға болады);

}

X – грамматика символы */

Пусть J = {[A X. , a] | [A .X , a] I};

return closure(J);

}

 

procedure items(G'){ /* G' – толықтырылған грамматика */

C = {I₀};

do{

for (С жүйесіндегі әрбір I жағдайлар жиыны,

goto(I, X) бос болмаса және C –ға тиісті болмаса)

goto(I, X)-ті C жүйесіне қосу;

}

while (C-ға жаңа жағдайлардың жаңа жиынын қосуға болады);

Егер I – қайсыбір белсенді δ префиксі үшін мүмкін болған жағдайлар жиыны, онда goto(I, X) – белсенді δX префиксі үшін мүмкін болған жағдайлар жиыны.

Мүмкін болған LR(1)-жағдайлар жиынынң С жүйесін құру алгоритмі С-ға жағдайлардың бастапқы I₀ = closure({[S' .S, $]}) жиынын орналастырудан басталады. Бұдан соң goto функциясы көмегімен жағдайлардың жаңа жиыны есептеліп, С-ға енгізіледі. Негізінен goto(I, X) функциясы – бұл шекті автоматтың I жағдайдан Х символы бойынша ауысуы.

LR(1)-жағдайлар жиынының жүйесі бойынша LR(1)- кестенің құрылуын, яғни LR(1)-анализатордың ауысу және әрекеттер функцияларын қарастырамыз.

4. Алгоритм 4.10. LR(1)-кестені құру.

Кіріс. G грамматикасы үшін мүмкін болған LR(1)- жағдайлардың канондық жүйесі C = {I₀, I₁, ..., I_n}.

Шығыс. G грамматикасы үшін LR(1)-кестені құрастыратын Action және Goto функциялары.

Тәсіл. Әрбір і жағдай үшін Action[i, a] и Goto[i, X] функциялары жағдайлардың I_i жиыны бойынша құрылады:

• 
  Әрекет функциясының мәні (Action) i жағдайы үшін (состояние) келесі түрде анықталады:
  
  • 
    егер [A .a , b] I_i (a - терминал) және goto(I_i, a) = I_j, онда Action[i, a] = shift j дейміз;
    
  • 
    егер [A ., a] I_i, мұнда A S', онда Action[i, a] = reduce A дейміз;
    
  • 
    егер [S' S., $] I_i, онда Action[i, $] = accept дейміз.
    
• 
  І жағдайы үшін ауысу функциясының мәні келесі түрде анықталады: егер goto(I_i, A) = I_j, онда Goto[i, A] = j (мұнда A - бейтерминал).
  
• 
  2 және 3 қадамдармен анықталмаған Action және Goto-ға енушілерді error-ға тең деп аламыз.
  
• 
  Анализатордың бастапқы жағдайы[S' .S, $] жағдайына ие болған жиындардан құрылады.
  
• 
  4.10 алгоритмі жұмысының нәтижесінде алынған Action және Goto функцияларының негізінде құрылған кесте канондық LR(1)-кесте деп аталады.Осы кестемен жұмыс істейтін LR(1)-анализатор канондық LR(1)-анализатор деп аталады.
  

 

	(0) E' E
	(1) E E + T
	(2) E T
	(3) T T * F
	(4) T F
	(5) F id

 

Осы грамматика үшін Goto бойынша ауысулар мен жағдайлар жиыны 4.11-суретте келтірілген. Бұл грамматика үшін LR(1)-кесте 4.9-суретте келтірілген.