В.А. Серебряков, М.П. Галочкин и др. - Теория и реализация языков программирования (2006) (1134633), страница 18
Текст из файла (страница 18)
Äëÿ ôóíêöèè Goto ñèìâîë i îçíà÷àåò ïîìåùåíèå â ìàãàçèí ñîñòîÿíèÿ ñ íîìåðîì i, ïóñòàÿ êëåòêà îøèáêó.Íà âõîäå id+id∗id ïîñëåäîâàòåëüíîñòü ñîñòîÿíèé ìàãàçèíà èâõîäíîé ëåíòû ïîêàçàíû íà ðèñ. 4.10. Íàïðèìåð, â ïåðâîé ñòðîêåLR-àíàëèçàòîð íàõîäèòñÿ â íóëåâîì ñîñòîÿíèè è ¾âèäèò¿ ïåðâûé âõîäíîé ñèìâîë id. Äåéñòâèå S6 â íóëåâîé ñòðîêå è ñòîëáöåid â ïîëå Action (ðèñ. 4.9) îçíà÷àåò ñäâèã è ïîìåùåíèå ñèìâîëàñîñòîÿíèÿ 6 íà âåðõóøêó ìàãàçèíà.
Ýòî è èçîáðàæåíî âî âòîðîéñòðîêå: ïåðâûé ñèìâîë id è ñèìâîë ñîñòîÿíèÿ 6 ïîìåùàþòñÿ âìàãàçèí, à id óäàëÿåòñÿ ñî âõîäíîé ëåíòû.Ñîñòîÿíèÿ012345678idS6S6S6Action+*$S4R2R4S7R4accR2R4R1R5S7R5R1R5R3R3R3E1GotoT F2 3538Ðèñ. 4.9.Òåêóùèì âõîäíûì ñèìâîëîì ñòàíîâèòñÿ +, è äåéñòâèåì â ñîñòîÿíèè 6 íà âõîä + ÿâëÿåòñÿ ñâ¼ðòêà ïî F → id. Èç ìàãàçèíàóäàëÿþòñÿ äâà ñèìâîëà (îäèí ñèìâîë ñîñòîÿíèÿ è îäèí ñèìâîëãðàììàòèêè).
Çàòåì àíàëèçèðóåòñÿ íóëåâîå ñîñòîÿíèå. Ïîñêîëüêó Goto â íóëåâîì ñîñòîÿíèè ïî ñèìâîëó F ýòî 3, F è 3 ïîìåùàþòñÿ â ìàãàçèí. Òåïåðü èìååì êîíôèãóðàöèþ, ñîîòâåòñò-118Ãëàâà 4. Ñèíòàêñè÷åñêèé àíàëèçÀêòèâíûé ÌàãàçèíÂõîäïðåôèêñ0id + id ∗ id$id0 id 6+id ∗ id$F0F 3+id ∗ id$T0T 2+id ∗ id$E0E1+id ∗ id$E+0E 1+4id ∗ id$E + id0 E 1 + 4 id 6∗id$E+F0E 1+4F 3∗id$E+T0E 1+4T 5∗id$E + T∗0E 1+4T 5∗7id$E + T ∗ id 0 E 1 + 4 T 5 ∗ 7 id 6$E+T ∗F 0E 1+4T 5∗7F 8$E+T0E 1+4T 5$E0E1ÄåéñòâèåñäâèãF → idT →FE→TñäâèãñäâèãF → idT →FñäâèãñäâèãF → idT →T ∗FE →E+TäîïóñêÐèñ. 4.10.âóþùóþ òðåòüåé ñòðîêå.
Îñòàëüíûå øàãè îïðåäåëÿþòñÿ àíàëîãè÷íî.4.6.3. Êîíñòðóèðîâàíèå LR(1)-òàáëèöûÐàññìîòðèì àëãîðèòì êîíñòðóèðîâàíèÿ òàáëèöû,óïðàâëÿþùåé LR(1) - àíàëèçàòîðîì.Ïóñòü G = (N, T, P, S) ÊÑ-ãðàììàòèêà. Ïîïîëíåííîéãðàììàòèêîé äëÿ äàííîé ãðàììàòèêè G íàçûâàåòñÿ ÊÑãðàììàòèêàG0 = (N ∪ {S 0 }, T, P ∪ {S 0 → S}, S 0 ),òî åñòü ýêâèâàëåíòíàÿ ãðàììàòèêà, â êîòîðîé ââåä¼í íîâûéíà÷àëüíûé ñèìâîë S 0 è íîâîå ïðàâèëî âûâîäà S 0 → S .Ýòî äîïîëíèòåëüíîå ïðàâèëî ââîäèòñÿ äëÿ òîãî, ÷òîáûîïðåäåëèòü, êîãäà àíàëèçàòîð äîëæåí îñòàíîâèòü ðàçáîð èçàôèêñèðîâàòü äîïóñê âõîäà. Òàêèì îáðàçîì, äîïóñê èìååò4.6. Ðàçáîð ñíèçó-ââåðõ òèïà ñäâèã-ñâ¼ðòêà119ìåñòî òîãäà è òîëüêî òîãäà, êîãäà àíàëèçàòîð ãîòîâ îñóùåñòâèòü ñâ¼ðòêó ïî ïðàâèëó S 0 → S .LR(1)-ñèòóàöèåé íàçûâàåòñÿ ïàðà [A → α.β, a], ãäåA → αβ ïðàâèëî ãðàììàòèêè, a - òåðìèíàë èëè ïðàâûéêîíöåâîé ìàðêåð $. Âòîðàÿ êîìïîíåíòà ñèòóàöèè íàçûâàåòñÿ àâàíöåïî÷êîé.Áóäåì ãîâîðèòü, ÷òî LR(1)-ñèòóàöèÿ [A → α.β, a] äîïóñòèìà äëÿ àêòèâíîãî ïðåôèêñà δ , åñëè ñóùåñòâóåò âûâîäS ⇒∗r γAw ⇒r γαβw, ãäå δ = γα è ëèáî a ïåðâûé ñèìâîëw, ëèáî w = e è a = $.Áóäåì ãîâîðèòü, ÷òî ñèòóàöèÿ äîïóñòèìà, åñëè îíà äîïóñòèìà äëÿ êàêîãî-ëèáî àêòèâíîãî ïðåôèêñà.Ïðèìåð 4.11.
Äàíà ãðàììàòèêà G = ({S, B}, {a, b}, P, S) ñïðàâèëàìèS → BBB → aB | bÑóùåñòâóåò ïðàâîñòîðîííèé âûâîä S ⇒∗r aaBab ⇒r aaaBab.Ëåãêî âèäåòü, ÷òî ñèòóàöèÿ [B → a.B, a] äîïóñòèìà äëÿ àêòèâíîãî ïðåôèêñà δ = aaa, åñëè â îïðåäåëåíèè âûøå ïîëîæèòüγ = aa, A = B , w = ab, α = a, β = B . Ñóùåñòâóåò òàêæå ïðàâîñòîðîííèé âûâîä S ⇒∗r BaB ⇒r BaaB .
Ïîýòîìó äëÿ àêòèâíîãîïðåôèêñà Baa äîïóñòèìà ñèòóàöèÿ [B → a.B, $].Öåíòðàëüíàÿ èäåÿ ìåòîäà çàêëþ÷àåòñÿ â òîì, ÷òî ïîãðàììàòèêå ñòðîèòñÿ äåòåðìèíèðîâàííûé êîíå÷íûé àâòîìàò, ðàñïîçíàþùèé àêòèâíûå ïðåôèêñû. Äëÿ ýòîãî ñèòóàöèè ãðóïïèðóþòñÿ âî ìíîæåñòâà, êîòîðûå è îáðàçóþò ñîñòîÿíèÿ àâòîìàòà. Ñèòóàöèè ìîæíî ðàññìàòðèâàòü êàê ñîñòîÿíèÿ íåäåòåðìèíèðîâàííîãî êîíå÷íîãî àâòîìàòà, ðàñïîçíàþùåãî àêòèâíûå ïðåôèêñû, à èõ ãðóïïèðîâêà íà ñàìîìäåëå åñòü ïðîöåññ ïîñòðîåíèÿ äåòåðìèíèðîâàííîãî êîíå÷íîãî àâòîìàòà èç íåäåòåðìèíèðîâàííîãî.Àíàëèçàòîð, ðàáîòàþùèé ñëåâà-íàïðàâî ïî òèïó ñäâèãñâ¼ðòêà, äîëæåí óìåòü ðàñïîçíàâàòü îñíîâû íà âåðõóøêåìàãàçèíà.
Ñîñòîÿíèå àâòîìàòà ïîñëå ïðî÷òåíèÿ ñîäåðæèìîãî ìàãàçèíà è òåêóùèé âõîäíîé ñèìâîë îïðåäåëÿþò î÷åðåäíîå äåéñòâèå àâòîìàòà. Ôóíêöèåé ïåðåõîäîâ ýòîãî êîíå÷íîãî àâòîìàòà ÿâëÿåòñÿ ôóíêöèÿ ïåðåõîäîâ LR-àíàëèçàòîðà.120Ãëàâà 4. Ñèíòàêñè÷åñêèé àíàëèç×òîáû íå ïðîñìàòðèâàòü ìàãàçèí íà êàæäîì øàãå àíàëèçà,íà âåðõóøêå ìàãàçèíà âñåãäà õðàíèòñÿ òî ñîñòîÿíèå, â êîòîðîì äîëæåí îêàçàòüñÿ ýòîò êîíå÷íûé àâòîìàò ïîñëå òîãî,êàê îí ïðî÷èòàë ñèìâîëû ãðàììàòèêè â ìàãàçèíå îò äíà êâåðõóøêå.Ðàññìîòðèì ñèòóàöèþ âèäà [A → α.Bβ, a] èç ìíîæåñòâàñèòóàöèé, äîïóñòèìûõ äëÿ íåêîòîðîãî àêòèâíîãî ïðåôèêñàz . Òîãäà ñóùåñòâóåò ïðàâîñòîðîííèé âûâîä S ⇒∗r yAax ⇒ryαBβax, ãäå z = yα. Ïðåäïîëîæèì, ÷òî èç βax âûâîäèòñÿ òåðìèíàëüíàÿ ñòðîêà bw.
Òîãäà äëÿ íåêîòîðîãî ïðàâèëàâûâîäà âèäà B → q èìååòñÿ âûâîä S ⇒∗r zBbw ⇒r zqbw.Òàêèì îáðàçîì [B → .q, b] òàêæå äîïóñòèìà äëÿ z è ñèòóàöèÿ [A → αB.β, a] äîïóñòèìà äëÿ àêòèâíîãî ïðåôèêñà zB .Çäåñü ëèáî b ìîæåò áûòü ïåðâûì òåðìèíàëîì, âûâîäèìûìèç β , ëèáî èç β âûâîäèòñÿ e â âûâîäå βax ⇒∗r bw è òîãäàb ðàâíî a. Òî åñòü b ïðèíàäëåæèò F IRST (βax).
Ïîñòðîåíèå âñåõ òàêèõ ñèòóàöèé äëÿ äàííîãî ìíîæåñòâà ñèòóàöèé,òî åñòü åãî çàìûêàíèå, äåëàåò ïðèâåä¼ííàÿ íèæå ôóíêöèÿclosure.Ñèñòåìà ìíîæåñòâ äîïóñòèìûõ LR(1)-ñèòóàöèé äëÿ âñåâîçìîæíûõ àêòèâíûõ ïðåôèêñîâ ïîïîëíåííîé ãðàììàòèêèíàçûâàåòñÿ êàíîíè÷åñêîé ñèñòåìîé ìíîæåñòâ äîïóñòèìûõLR(1)-ñèòóàöèé. Àëãîðèòì ïîñòðîåíèÿ êàíîíè÷åñêîé ñèñòåìû ìíîæåñòâ ïðèâåä¼í íèæå.Àëãîðèòì 4.10.
Êîíñòðóèðîâàíèå êàíîíè÷åñêîé ñèñòåìû ìíîæåñòâ äîïóñòèìûõ LR(1)-ñèòóàöèé.Âõîä. ÊÑ-ãðàììàòèêà G = (N, T, P, S).Âûõîä. Êàíîíè÷åñêàÿ ñèñòåìà C ìíîæåñòâ äîïóñòèìûõLR(1)-ñèòóàöèé äëÿ ãðàììàòèêè G.Ìåòîä. Âûïîëíèòü äëÿ ïîïîëíåííîé ãðàììàòèêè G0 ïðîöåäóðó items, êîòîðàÿ èñïîëüçóåò ôóíêöèè closure è goto.function closure(I ){ /* I - ìíîæåñòâî ñèòóàöèé */do{for (êàæäîé ñèòóàöèè [A → α.Bβ, a] èç I ,êàæäîãî ïðàâèëà âûâîäà B → γ èç G0 ,êàæäîãî òåðìèíàëà b èç F IRST (βa),4.6. Ðàçáîð ñíèçó-ââåðõ òèïà ñäâèã-ñâ¼ðòêà}}121òàêîãî, ÷òî [B → .γ, b] íåò â I )äîáàâèòü [B → .γ, b] ê I ;while (ê I ìîæíî äîáàâèòü íîâóþ ñèòóàöèþ);return I ;function goto(I ,X ){ /* I - ìíîæåñòâî ñèòóàöèé;}X - ñèìâîë ãðàììàòèêè */Ïóñòü J = {[A → αX.β, a] | [A → α.Xβ, a] ∈ I};return closure(J );procedure items(G0 ){ /* G0 - ïîïîëíåííàÿãðàììàòèêà */I0 = closure({[S 0 → .S, $]});C = {I0 };do{for (êàæäîãî ìíîæåñòâà ñèòóàöèé I èçñèñòåìû C , êàæäîãî ñèìâîëà ãðàììàòèêè Xòàêîãî, ÷òî goto(I, X) íå ïóñòîè íå ïðèíàäëåæèò C )äîáàâèòü goto(I, X) ê ñèñòåìå C ;}while (ê C ìîæíî äîáàâèòü íîâîå ìíîæåñòâîñèòóàöèé);Åñëè I ìíîæåñòâî ñèòóàöèé, äîïóñòèìûõ äëÿ íåêîòîðîãî àêòèâíîãî ïðåôèêñà δ , òî goto(I, X) ìíîæåñòâîñèòóàöèé, äîïóñòèìûõ äëÿ àêòèâíîãî ïðåôèêñà δX .Ðàáîòà àëãîðèòìà ïîñòðîåíèÿ ñèñòåìû C ìíîæåñòâ äîïóñòèìûõ LR(1)-ñèòóàöèé íà÷èíàåòñÿ ñ òîãî, ÷òî â C ïîìåùàåòñÿ íà÷àëüíîå ìíîæåñòâî ñèòóàöèé I0 = closure({[S 0 →.S, $]}).
Çàòåì ñ ïîìîùüþ ôóíêöèè goto âû÷èñëÿþòñÿ íîâûå ìíîæåñòâà ñèòóàöèé è âêëþ÷àþòñÿ â C . Ïî-ñóùåñòâó,goto(I, X) ïåðåõîä êîíå÷íîãî àâòîìàòà èç ñîñòîÿíèÿ I ïîñèìâîëó X .122Ãëàâà 4. Ñèíòàêñè÷åñêèé àíàëèçÐàññìîòðèì òåïåðü, êàê ïî ñèñòåìå ìíîæåñòâ LR(1)-ñèòóàöèé ñòðîèòñÿ LR(1)-òàáëèöà, òî åñòü ôóíêöèè äåéñòâèéè ïåðåõîäîâ LR(1)-àíàëèçàòîðà.Àëãîðèòì 4.11. Ïîñòðîåíèå LR(1)-òàáëèöû.Âõîä. Êàíîíè÷åñêàÿ ñèñòåìà C = {I0 , I1 , . . . , In } ìíîæåñòâ äîïóñòèìûõ LR(1)-ñèòóàöèé äëÿ ãðàììàòèêè G.Âûõîä. Ôóíêöèè Action è Goto, ñîñòàâëÿþùèå LR(1)òàáëèöó äëÿ ãðàììàòèêè G.Ìåòîä. Äëÿ êàæäîãî ñîñòîÿíèÿ i ôóíêöèè Action[i, a] èGoto[i, X] ñòðîÿòñÿ ïî ìíîæåñòâó ñèòóàöèé Ii :(1) Çíà÷åíèÿ ôóíêöèè äåéñòâèÿ (Action) äëÿ ñîñòîÿíèÿ iîïðåäåëÿþòñÿ ñëåäóþùèì îáðàçîì:à) åñëè [A→ α.aβ, b]∈Ii (a òåðìèíàë) è goto(Ii , a)= Ij , òî ïîëàãàåì Action[i, a] = shift j ;á) åñëè [A → α., a] ∈ Ii , ïðè÷¼ì A 6= S 0 , òî ïîëàãàåìAction[i, a] = reduce A → α;â) åñëè [S 0 → S., $] ∈ Ii , òî ïîëàãàåì Action[i, $] =accept.(2) Çíà÷åíèÿ ôóíêöèè ïåðåõîäîâ äëÿ ñîñòîÿíèÿ i îïðåäåëÿþòñÿ ñëåäóþùèì îáðàçîì: åñëè goto(Ii , A) = Ij , òîGoto[i, A] = j (çäåñü A íåòåðìèíàë).(3) Âñå âõîäû â Action è Goto, íå îïðåäåë¼ííûå øàãàìè2 è 3, ïîëàãàåì ðàâíûìè error.(4) Íà÷àëüíîå ñîñòîÿíèå àíàëèçàòîðà ñòðîèòñÿ èç ìíîæåñòâà, ñîäåðæàùåãî ñèòóàöèþ [S 0 → .S, $].Òàáëèöà íà îñíîâå ôóíêöèé Action è Goto, ïîëó÷åííûõâ ðåçóëüòàòå ðàáîòû àëãîðèòìà 4.11., íàçûâàåòñÿ êàíîíè÷åñêîé LR(1)-òàáëèöåé.
Ðàáîòàþùèé ñ íåé LR(1)-àíàëèçàòîð,íàçûâàåòñÿ êàíîíè÷åñêèì LR(1)-àíàëèçàòîðîì.Ïðèìåð 4.12. Ðàññìîòðèì ñëåäóþùóþ ãðàììàòèêó, ÿâëÿþùóþñÿ ïîïîëíåííîé äëÿ ãðàììàòèêè èç ïðèìåðà 4.8.:4.6. Ðàçáîð ñíèçó-ââåðõ òèïà ñäâèã-ñâ¼ðòêà(0)(1)(2)(3)(4)(5)123E0 → EE →E+TE→TT →T ∗FT →FF → id.Ìíîæåñòâà ñèòóàöèé è ïåðåõîäû ïî goto äëÿ ýòîé ãðàììàòèêè ïðèâåäåíû íà ðèñ.
4.11. LR(1)-òàáëèöà äëÿ ýòîé ãðàììàòèêèïðèâåäåíà íà ðèñ. 4.9.Ïðîñëåäèì ïîñëåäîâàòåëüíîñòü ñîçäàíèÿ ýòèõ ìíîæåñòâ áîëåå ïîäðîáíî.1. Âû÷èñëÿåì I0 = closure({[E 0 → .E, $]}).1.1. Ñèòóàöèÿ [E 0 → .E, $] ïîïàäàåò â íåãî ïî óìîë÷àíèþ êàêèñõîäíàÿ.1.2. Åñëè îáðàòèòüñÿ ê îáîçíà÷åíèÿì ôóíêöèè closure, òîäëÿ íå¼α = β = e, B = E , a = $,f irst(βa) = f irst($) = {$}.Çíà÷èò, äëÿ òåðìèíàëà $ äîáàâëÿåì ñèòóàöèè íà îñíîâå ïðàâèë ñî çíàêîì E â ëåâîé ÷àñòè ïðàâèëà.Ýòî ïðàâèëàE →E+Tè E→Tè ñîîòâåòñòâóþùèå èì ñèòóàöèè[E → .E + T, $]è[E → .T, $].1.3. Ïðîñìàòðèâàåì ïîëó÷èâøèåñÿ ñèòóàöèè.Äëÿ ñèòóàöèè [E → .E + T, $]β = +, ïîýòîìó f irst(βa) = f irst(+$) = {+}.Íà îñíîâå ýòîãî äîáàâëÿåì ê I0è[E → E + .T, +][E → .T, +].1.4. Äëÿ ñèòóàöèè [E → .T, $]Ïîýòîìó äîáàâëÿåì ê I0[T → .T ∗ F, $]èβ = e,f irst(βa) = {$}.[T → .F, $].1.5. Ïîäîáíî ýòîìó äëÿ ñèòóàöèè [E → .T, +]β = e, f irst(βa) = {+}.Ïîýòîìó äîáàâëÿåì ê I0[T → .T ∗ F, +]è[T → .F, +].1.6.
Èç ñèòóàöèè [T → .T ∗ F, +]β = ∗, f irst(βa) = {∗}.124Ãëàâà 4. Ñèíòàêñè÷åñêèé àíàëèç,>(o(@>(o(7@>(o7@>7o7)@>7o)@>)oLG@>(o(7@>(o7@>7o7)@>7o)@>7o7)@>7o)@>)oLG@>)oLG@LG,>(o(@>(o(7@>(o(7@(,>(o7@>7o7)@>(o7@>7o7)@>7o7)@7),>(o(7@>(o(7@>7o7)@>7o)@>7o7)@>7o)@>)oLG@>)oLG@>7o7)@>7o)@>)oLG@)7,>7o7)@>7o7)@>7o7)@>)oLG@>)oLG@>)oLG@,>7o)@>7o)@>7o)@LG,>(o(7@>(o(7@>7o7)@>7o7)@>7o7)@LG),>7o7)@>7o7)@>7o7)@,>)oLG@>)oLG@>)oLG@Ðèñ. 4.11.Ïîýòîìó äîáàâëÿåì ê I0[T → .T ∗ F, ∗]è[T → .F, ∗].1.7. Äàëåå èç ñèòóàöèè [T → .F, ∗] ïîëó÷àåì ñèòóàöèþ[F → .id, ∗].4.6. Ðàçáîð ñíèçó-ââåðõ òèïà ñäâèã-ñâ¼ðòêà125èç ñèòóàöèè [T → .F, $] ñèòóàöèþ [F → .id, $], àèç ñèòóàöèè [T → .F, +] [F → .id, ∗].Òàêèì îáðàçîì, âñå 14 èñêîìûõ ñèòóàöèé I0 ïîëó÷åíû.Âîçâðàùàåìñÿ â ãîëîâíóþ ôóíêöèþ items, âêëþ÷àåì I0 âìíîæåñòâî C è èññëåäóåì íåïóñòûå èòîãè ïðèìåíåíèÿ ôóíêöèègoto(I0 , X), ãäå X ∈ {E 0 , E, T, F, +, ∗, $, id}.Åñëè ïîñìîòðåòü íà âèä ïðàâèë â ôóíêöèè goto(I0 , X), òîâèäíî, ÷òî X äîëæåí âñòðåòèòüñÿ â ïðàâîé ÷àñòè õîòÿ áû îäíîãî ïðàâèëà.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
