В.А. Серебряков, М.П. Галочкин и др. - Теория и реализация языков программирования (2006) (1134633), страница 19
Текст из файла (страница 19)
Äëÿ E 0 òàêèõ ïðàâèë ó íàñ íåò, ïîýòîìó çíà÷åíèåôóíêöèè goto(I0 , E 0 ) ïóñòî.Âîçüì¼ì goto(I0 , E). E âñòðå÷àåòñÿ ïîñëå òî÷êè â ïðàâûõ÷àñòÿõ äâóõ ñèòóàöèé èç I0 , çíà÷èò áåð¼ì ýòè äâà ïðàâèëà èïåðåíîñèì â íèõ òî÷êè íà îäèí ñèìâîë âïðàâî (ïîêà åñòü êóäà íå óï¼ðëèñü â çàïÿòóþ), ïîëó÷àåì:[E 0 → E., $]è[E → E. + T, $|+]Âû÷èñëèì îò êàæäîé èç ýòèõ ñèòóàöèé ôóíêöèþ closure.Íî, ïîñêîëüêó ñïðàâà îò òî÷êè çäåñü ëèáî ïóñòàÿ öåïî÷êà, ëèáîòåðìèíàë, òî íèêàêèõ íîâûõ ñèòóàöèé íå âîçíèêàåò. Äàëüøå îòñëåæèâàåì, ìîæåò ëè êóäà-òî ñäâèíóòüñÿ òî÷êà äàëüøå íà ïðàâî è ïî êàêîìó ñèìâîëó. Åñëè ìîæåò, ñòðîèì ñîîòâåòñòâóþùååìíîæåñòâî (ñì. ðèñ.
4.11). È ò.ä.4.6.4. LR(1)-ãðàììàòèêèÅñëè äëÿ ÊÑ-ãðàììàòèêè G ôóíêöèÿ Action, ïîëó÷åííàÿ â ðåçóëüòàòå ðàáîòû àëãîðèòìà 4.11., íå ñîäåðæèò íåîäíîçíà÷íî îïðåäåë¼ííûõ âõîäîâ, òî ãðàììàòèêà íàçûâàåòñÿLR(1)-ãðàììàòèêîé.ßçûê L íàçûâàåòñÿ LR(1)-ÿçûêîì, åñëè îí ìîæåò áûòüïîðîæä¼í íåêîòîðîé LR(1)-ãðàììàòèêîé.Èíîãäà èñïîëüçóåòñÿ äðóãîå îïðåäåëåíèå LR(1)-ãðàììàòèêè. Ãðàììàòèêà íàçûâàåòñÿ LR(1), åñëè èç óñëîâèé1. S 0 ⇒∗r uAw ⇒r uvw,2. S 0 ⇒∗r zBx ⇒r uvy ,3.
F IRST (w) = F IRST (y)ñëåäóåò, ÷òî uAy = zBx (òî åñòü u = z , A = B è x = y ).Ñîãëàñíî ýòîìó îïðåäåëåíèþ, åñëè uvw è uvy ïðàâîâûâîäèìûå öåïî÷êè ïîïîëíåííîé ãðàììàòèêè, ó êîòîðûõ126Ãëàâà 4. Ñèíòàêñè÷åñêèé àíàëèçF IRST (w) = F IRST (y) è A → v ïîñëåäíåå ïðàâèëî,èñïîëüçîâàííîå â ïðàâîì âûâîäå öåïî÷êè uvw, òî ïðàâèëî A → v äîëæíî ïðèìåíÿòüñÿ è â ïðàâîì ðàçáîðå ïðèñâ¼ðòêå uvy ê uAy . Òàê êàê A äà¼ò v íåçàâèñèìî îò w, òîLR(1)-óñëîâèå îçíà÷àåò, ÷òî â F IRST (w) ñîäåðæèòñÿ èíôîðìàöèÿ, äîñòàòî÷íàÿ äëÿ îïðåäåëåíèÿ òîãî, ÷òî uv çàîäèí øàã âûâîäèòñÿ èç uA.
Ïîýòîìó íèêîãäà íå ìîæåò âîçíèêíóòü ñîìíåíèé îòíîñèòåëüíî òîãî, êàê ñâåðíóòü î÷åðåäíóþ ïðàâîâûâîäèìóþ öåïî÷êó ïîïîëíåííîé ãðàììàòèêè.Ìîæíî äîêàçàòü, ÷òî ýòè äâà îïðåäåëåíèÿ ýêâèâàëåíòíû.Äàäèì òåïåðü îïðåäåëåíèå LR(k)-ãðàììàòèêè.Îïðåäåëåíèå. Ïóñòü G = (N, Σ, P, S) - ÊÑ-ãðàììàòèêàè G0 = (N 0 , Σ, P 0 , S 0 ) - ïîëó÷åííàÿ èç íå¼ ïîïîëíåííàÿãðàììàòèêà. Áóäåì íàçûâàòü G LR(k)-ãðàììàòèêîé äëÿk > 0, åñëè èç óñëîâèé(1)S 0 ⇒∗G0r αAω ⇒G0r αβω,(2)S 0 ⇒∗G0r γBx ⇒G0r αβy,(3)F IRSTk (ω) = F IRSTk (y)ñëåäóåò, ÷òî αAy = γBx (ò.å. α = γ, A = B è x = y).Ãðàììàòèêà G íàçûâàåòñÿ LR-ãðàììàòèêîé, åñëè îíàLR(k)-ãðàììàòèêà äëÿ íåêîòîðîãî k > 0.Èíòóèòèâíî ýòî îïðåäåëåíèå ãîâîðèò î òîì, ÷òî åñëèαβw è αβy ïðàâîâûâîäèìûå öåïî÷êè ïîïîëíåííîé ãðàììàòèêè, ó êîòîðûõ F IRSTk (w) = F IRSTk (y), è A → β ïîñëåäíåå ïðàâèëî, èñïîëüçîâàííîå â ïðàâîì âûâîäå öåïî÷êè αβw, òî ïðàâèëî A → β äîëæíî èñïîëüçîâàòüñÿ òàêæåâ ïðàâîì ðàçáîðå ïðè ñâ¼ðòêå αβy ê αAy .
Òàê êàê A äà¼òβ íåçàâèñèìî îò w, òî LR(k )-óñëîâèå ãîâîðèò î òîì, ÷òîâ F IRSTk (w) ñîäåðæèòñÿ èíôîðìàöèÿ, äîñòàòî÷íàÿ äëÿîïðåäåëåíèÿ òîãî, ÷òî αβ çà îäèí øàã âûâîäèòñÿ èç αA. Ïîýòîìó íèêîãäà íå ìîæåò âîçíèêíóòü ñîìíåíèé îòíîñèòåëüíî òîãî, êàê ñâåðíóòü î÷åðåäíóþ ïðàâîâûâîäèìóþ öåïî÷êó ïîïîëíåííîé ãðàììàòèêè. Êðîìå òîãî, ðàáîòàÿ ñ LR(k )ãðàììàòèêîé, ìû âñåãäà çíàåì, äîïóñòèòü ëè äàííóþ âõîäíóþ öåïî÷êó èëè ïðîäîëæàòü ðàçáîð.4.6.
Ðàçáîð ñíèçó-ââåðõ òèïà ñäâèã-ñâ¼ðòêà127Ïðèìåð 4.13. Ðàññìîòðèì ãðàììàòèêó G ñ ïðàâèëàìèS → Sa | aÑîãëàñíî îïðåäåëåíèþ, G íå LR(0)-ãðàììàòèêà, òàê êàê èçòð¼õ óñëîâèé(1)S 0 ⇒0G0r S 0 ⇒G0r S;(2)S 0 ⇒G0r S ⇒G0r Sa,(3)F IRST0 (e) = F IRST0 (a) = eíå ñëåäóåò, ÷òî S 0 a = S.
Ïðèìåíÿÿ îïðåäåëåíèå ê ýòîé ñèòóàöèè, èìååì α = e, β = S, ω = e, γ = e, A = S 0 , B = S, x = eè y = a. Ïðîáëåìà çäåñü çàêëþ÷àåòñÿ â òîì, ÷òî íåëüçÿ óñòàíîâèòü, ÿâëÿåòñÿ ëè S îñíîâîé ïðàâîâûâîäèìîé öåïî÷êè Sa, íåâèäÿ ñèìâîëà, ñòîÿùåãî ïîñëå S (ò.å. íàáëþäàÿ ¾íóëåâîå¿ êîëè÷åñòâî ñèìâîëîâ).  ñîîòâåòñòâèè ñ èíòóèöèåé G íå äîëæíàáûòü LR(0)- ãðàììàòèêîé è îíà íå áóäåò åþ, åñëè ïîëüçîâàòüñÿïåðâûì îïðåäåëåíèåì. Ýòî îïðåäåëåíèå ìû è áóäåì èñïîëüçîâàòü äàëåå.Ïðèìåð 4.14. Ïóñòü G - ëåâîëèíåéíàÿ ãðàììàòèêà ñ ïðàâèëàìèS → Ab | BcA → Aa | eB → Ba | eÇàìåòèì, ÷òî G íå ÿâëÿåòñÿ LR(k)-ãðàììàòèêîé íè äëÿ êàêîãî k.Äîïóñòèì, ÷òî G − LR(k)-ãðàììàòèêà. Ðàññìîòðèì äâà ïðàâûõ âûâîäà â ïîïîëíåííîé ãðàììàòèêå G0 :S 0 ⇒r S ⇒∗r Aak b ⇒r ak bèS 0 ⇒r S ⇒∗r Bak c ⇒r ak cÝòè äâà âûâîäà óäîâëåòâîðÿþò óñëîâèþ èç îïðåäåëåíèÿLR(k)-ãðàììàòèêè ïðè α = e, β = e, ω = ak b, γ = e è y = ak c.Íî òàê êàê çàêëþ÷åíèå íåâåðíî, ò.å.
A 6= B , òî G - íå LR(k)ãðàììàòèêà. Áîëåå òîãî, òàê êàê LR(k)-óñëîâèå íàðóøàåòñÿ äëÿâñåõ k, òî G - íå LR-ãðàììàòèêà.Åñëè ãðàììàòèêà íå ÿâëÿåòñÿ LR(1), òî àíàëèçàòîð òèïà ñäâèã-ñâ¼ðòêà ïðè àíàëèçå íåêîòîðîé öåïî÷êè ìîæåò äîñòèãíóòü êîíôèãóðàöèè, â êîòîðîé îí, çíàÿ ñîäåðæèìîå ìàãàçèíà è ñëåäóþùèé âõîäíîé ñèìâîë, íå ìîæåò ðåøèòü, äåëàòü ëè ñäâèã èëè ñâ¼ðòêó (êîíôëèêò ñäâèã/ñâ¼ðòêà), èëè128Ãëàâà 4. Ñèíòàêñè÷åñêèé àíàëèçíå ìîæåò ðåøèòü, êàêóþ èç íåñêîëüêèõ ñâ¼ðòîê ïðèìåíèòü(êîíôëèêò ñâ¼ðòêà/ñâ¼ðòêà). ÷àñòíîñòè, íåîäíîçíà÷íàÿ ãðàììàòèêà íå ìîæåò áûòüLR(1).
Äëÿ äîêàçàòåëüñòâà ðàññìîòðèì äâà ðàçëè÷íûõ ïðàâûõ âûâîäà(1) S ⇒r u1 ⇒r . . . ⇒r un ⇒r w, è(2) S ⇒r v1 ⇒r . . . ⇒r vm ⇒r w.Íåòðóäíî çàìåòèòü, ÷òî LR(1) - óñëîâèå (ñîãëàñíî âòîðîìóîïðåäåëåíèþ LR(1)-ãðàììàòèêè) íàðóøàåòñÿ äëÿ íàèìåíüøåãî èç ÷èñåë i, äëÿ êîòîðûõ un−i 6= vm−i .Ïðèìåð 4.15. Ðàññìîòðèì åù¼ ðàç ãðàììàòèêó óñëîâíûõîïåðàòîðîâ:S → if E then S | if E then S else S | aE→bÅñëè àíàëèçàòîð òèïà ñäâèã-ñâ¼ðòêà íàõîäèòñÿ â êîíôèãóðàöèè, òàêîé, ÷òî íåîáðàáîòàííàÿ ÷àñòü âõîäíîé öåïî÷êè èìååò âèä else . . . $, à â ìàãàçèíå íàõîäèòñÿ .
. . if E then S , òîíåëüçÿ îïðåäåëèòü, ÿâëÿåòñÿ ëè if E then S îñíîâîé, âíå çàâèñèìîñòè îò òîãî, ÷òî ëåæèò â ìàãàçèíå íèæå. Ýòî êîíôëèêòñäâèã/ñâ¼ðòêà.  çàâèñèìîñòè îò òîãî, ÷òî ñëåäóåò íà âõîäå çàelse, ïðàâèëüíîé ìîæåò áûòü ñâ¼ðòêà ïî S → if E then Sèëè ñäâèã else, à çàòåì ðàçáîð äðóãîãî S è çàâåðøåíèå îñíîâû if E then S else S . Òàêèì îáðàçîì íåëüçÿ ñêàçàòü, íóæíî ëèâ ýòîì ñëó÷àå äåëàòü ñäâèã èëè ñâ¼ðòêó, òàê ÷òî ãðàììàòèêà íåÿâëÿåòñÿ LR(1).Ýòà ãðàììàòèêà ìîæåò áûòü ïðåîáðàçîâàíà ê LR(1)-âèäóñëåäóþùèì îáðàçîì:S→M |UM → if E then M else M | aU → if E then S | if E then M else UE→bÎñíîâíàÿ ðàçíèöà ìåæäó LL(1)- è LR(1)- ãðàììàòèêàìèçàêëþ÷àåòñÿ â ñëåäóþùåì. ×òîáû ãðàììàòèêà áûëà LR(1)ãðàììàòèêîé, íåîáõîäèìî ðàñïîçíàâàòü âõîæäåíèå ïðàâîé÷àñòè ïðàâèëà âûâîäà, ïðîñìîòðåâ âñ¼, ÷òî âûâåäåíî èçýòîé ïðàâîé ÷àñòè è òåêóùèé ñèìâîë âõîäíîé öåïî÷êè.
Ýòî4.6. Ðàçáîð ñíèçó-ââåðõ òèïà ñäâèã-ñâ¼ðòêà129òðåáîâàíèå ñóùåñòâåííî ìåíåå ñòðîãîå, ÷åì òðåáîâàíèå äëÿLL(1)-ãðàììàòèêè, êîãäà íåîáõîäèìî îïðåäåëèòü ïðèìåíèìîå ïðàâèëî, âèäÿ òîëüêî ïåðâûé ñèìâîë, âûâîäèìûé èçåãî ïðàâîé ÷àñòè. Òàêèì îáðàçîì, êëàññ LL(1)-ãðàììàòèêåñòü ñîáñòâåííûé ïîäêëàññ êëàññà LR(1)-ãðàììàòèê.Ñïðàâåäëèâû òàêæå ñëåäóþùèå óòâåðæäåíèÿ [2].Òåîðåìà 4.7. Êàæäûé LR(1)-ÿçûê ÿâëÿåòñÿ äåòåðìèíèðîâàííûì ÊÑ-ÿçûêîì.Òåîðåìà 4.8. Åñëè L äåòåðìèíèðîâàííûé ÊÑ-ÿçûê,òî ñóùåñòâóåò LR(1)-ãðàììàòèêà, ïîðîæäàþùàÿ L.Òåîðåìà 4.9. Äëÿ ëþáîé LR(k)-ãðàììàòèêè äëÿ k > 1ñóùåñòâóåò ýêâèâàëåíòíàÿ åé LR(k − 1)-ãðàììàòèêà.Äîêàçàíî, ÷òî ïðîáëåìà îïðåäåëåíèÿ, ïîðîæäàåò ëèãðàììàòèêà LR-ÿçûê, ÿâëÿåòñÿ àëãîðèòìè÷åñêè íåðàçðåøèìîé.4.6.5.
Âîññòàíîâëåíèå ïðîöåññà àíàëèçàïîñëå ñèíòàêñè÷åñêèõ îøèáîêÎäíèì èç ïðîñòåéøèõ ìåòîäîâ âîññòàíîâëåíèÿ ïîñëåîøèáêè ïðè LR(1)-àíàëèçå ÿâëÿåòñÿ ñëåäóþùèé. Ïðè ñèíòàêñè÷åñêîé îøèáêå ïðîñìàòðèâàåì ìàãàçèí îò âåðõóøêè,ïîêà íå íàéä¼ì ñîñòîÿíèå s ñ ïåðåõîäîì íà âûäåëåííûéíåòåðìèíàë A. Çàòåì ñêàíèðóþòñÿ âõîäíûå ñèìâîëû, ïîêà íå áóäåò íàéäåí òàêîé, êîòîðûé äîïóñòèì ïîñëå A. Âýòîì ñëó÷àå íà âåðõóøêó ìàãàçèíà ïîìåùàåòñÿ ñîñòîÿíèåGoto[s, A] è ðàçáîð ïðîäîëæàåòñÿ. Äëÿ íåòåðìèíàëà A ìîæåò èìåòüñÿ íåñêîëüêî òàêèõ âàðèàíòîâ. Îáû÷íî A ýòîíåòåðìèíàë, ïðåäñòàâëÿþùèé îäíó èç îñíîâíûõ êîíñòðóêöèé ÿçûêà, íàïðèìåð îïåðàòîð.Ïðè áîëåå äåòàëüíîé ïðîðàáîòêå ðåàêöèè íà îøèáêèìîæíî â êàæäîé ïóñòîé êëåòêå àíàëèçàòîðà ïîñòàâèòü îáðàùåíèå ê ñâîåé ïîäïðîãðàììå.
Òàêàÿ ïîäïðîãðàììà ìîæåò âñòàâëÿòü èëè óäàëÿòü âõîäíûå ñèìâîëû èëè ñèìâîëûìàãàçèíà, ìåíÿòü ïîðÿäîê âõîäíûõ ñèìâîëîâ.130Ãëàâà 4. Ñèíòàêñè÷åñêèé àíàëèç4.6.6. Âàðèàíòû LR-àíàëèçàòîðîâ×àñòî ïîñòðîåííûå òàáëèöû äëÿ LR(1)-àíàëèçàòîðàîêàçûâàþòñÿ äîâîëüíî áîëüøèìè. Ïîýòîìó ïðè ïðàêòè÷åñêîé ðåàëèçàöèè èñïîëüçóþòñÿ ðàçëè÷íûå ìåòîäû èõ ñæàòèÿ.
Ñ äðóãîé ñòîðîíû, ÷àñòî îêàçûâàåòñÿ, ÷òî ïðè ïîñòðîåíèè äëÿ ÿçûêà ñèíòàêñè÷åñêîãî àíàëèçàòîðà òèïà ¾ñäâèãñâ¼ðòêà¿ äîñòàòî÷íî áîëåå ïðîñòûõ ìåòîäîâ. Íåêîòîðûå èçýòèõ ìåòîäîâ áàçèðóþòñÿ íà îñíîâå LR(1)-àíàëèçàòîðîâ.Îäíèì èç ñïîñîáîâ òàêîãî óïðîùåíèÿ ÿâëÿåòñÿ LR(0)àíàëèç ÷àñòíûé ñëó÷àÿ LR-àíàëèçà, êîãäà íè ïðè ïîñòðîåíèè òàáëèö, íè ïðè àíàëèçå íå ó÷èòûâàåòñÿ àâàíöåïî÷êà.Åù¼ îäíèì âàðèàíòîì LR-àíàëèçà ÿâëÿþòñÿ òàê íàçûâàåìûå SLR(1)-àíàëèçàòîðû (Simple LR(1)). Îíè ñòðîÿòñÿñëåäóþùèì îáðàçîì. Ïóñòü C = {I0 , I1 , . . .
, In } íàáîðìíîæåñòâ äîïóñòèìûõ LR(0)-ñèòóàöèé. Ñîñòîÿíèÿ àíàëèçàòîðà ñîîòâåòñòâóþò Ii . Ôóíêöèè äåéñòâèé è ïåðåõîäîâ àíàëèçàòîðà îïðåäåëÿþòñÿ ñëåäóþùèì îáðàçîì.1. Åñëè [A → u.av] ∈ Ii è goto(Ii , a) = Ij , òî îïðåäåëèìAction[i, a] = shift j .2. Åñëè [A → u.] ∈ Ii , òî, äëÿ âñåõ a ∈ F OLLOW (A),A 6= S 0 , îïðåäåëèì Action[i, a] = reduce A → u3. Åñëè [S 0 →S.] ∈ Ii , òî îïðåäåëèì Action[i, $] = accept.4. Åñëè goto(Ii , A) = Ij , ãäå A ∈ N , òî îïðåäåëèìGoto[i, A] = j .5. Îñòàëüíûå âõîäû äëÿ ôóíêöèé Action è Goto îïðåäåëèì êàê error.6. Íà÷àëüíîå ñîñòîÿíèå ñîîòâåòñòâóåò ìíîæåñòâó ñèòóàöèé, ñîäåðæàùåìó ñèòóàöèþ [S 0 → .S].Ðàñïðîñòðàí¼ííûì âàðèàíòîì LR(1)-àíàëèçà ÿâëÿåòñÿòàêæå LALR(1)-àíàëèç.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
