В.А. Серебряков, М.П. Галочкин и др. - Теория и реализация языков программирования (2006) (1134633), страница 17
Текст из файла (страница 17)
 ïåðâîì ñëó÷àå ðàçâîðà÷èâàåì A ïî ñîîòâåòñòâóþùåìó ïðàâèëó, âî âòîðîì óäàëÿåì A èç ìàãàçèíà.Åñëè íà âåðõóøêå ìàãàçèíà òåðìèíàëüíûé ñèìâîë, òîìîæíî óäàëèòü âñå òåðìèíàëüíûå ñèìâîëû ñ âåðõóøêè ìàãàçèíà âïëîòü äî ïåðâîãî (ñâåðõó) íåòåðìèíàëüíîãî ñèìâîëà è ïðîäîëæàòü òàê, êàê ýòî áûëî îïèñàíî âûøå.4.6. Ðàçáîð ñíèçó-ââåðõ òèïà ñäâèãñâ¼ðòêà4.6.1. Îñíîâà ïðîöåññå ðàçáîðà ñíèçó-ââåðõ òèïà ñäâèã-ñâ¼ðòêàñòðîèòñÿ äåðåâî ðàçáîðà âõîäíîé öåïî÷êè, íà÷èíàÿ ñ ëèñòüåâ (ñíèçó) ê êîðíþ (ââåðõ). Ýòîò ïðîöåññ ìîæíî ðàññìàòðèâàòü êàê ¾ñâ¼ðòêó¿ öåïî÷êè w ê íà÷àëüíîìó ñèìâîëó ãðàììàòèêè.
Íà êàæäîì øàãå ñâ¼ðòêè ïîäöåïî÷êà, êîòîðóþ ìîæíî ñîïîñòàâèòü ïðàâîé ÷àñòè íåêîòîðîãî ïðàâèëà âûâîäà, çàìåíÿåòñÿ ñèìâîëîì ëåâîé ÷àñòè ýòîãî ïðàâèëà âûâîäà, è åñëè íà êàæäîì øàãå âûáèðàåòñÿ ïðàâèëüíàÿïîäöåïî÷êà, òî â îáðàòíîì ïîðÿäêå ïðîñëåæèâàåòñÿ ïðàâîñòîðîííèé âûâîä (ðèñ. 4.7). Çäåñü êî âõîäíîé öåïî÷êå, òàêæå êàê è ïðè àíàëèçå LL(1)-ãðàììàòèê, ïðèïèñàí êîíöåâîéìàðêåð $.Îñíîâîé öåïî÷êè íàçûâàåòñÿ ïîäöåïî÷êà ñåíòåíöèàëüíîé ôîðìû, êîòîðàÿ ìîæåò áûòü ñîïîñòàâëåíà ïðàâîé ÷àñòè íåêîòîðîãî ïðàâèëà âûâîäà, ñâ¼ðòêà ïî êîòîðîìó ê ëå-112Ãëàâà 4.
Ñèíòàêñè÷åñêèé àíàëèç666; ;D<<D=DEÐèñ. 4.7.âîé ÷àñòè ïðàâèëà ñîîòâåòñòâóåò îäíîìó øàãó â îáðàùåíèèïðàâîñòîðîííåãî âûâîäà. Ñàìàÿ ëåâàÿ ïîäöåïî÷êà, êîòîðàÿñîïîñòàâëÿåòñÿ ïðàâîé ÷àñòè íåêîòîðîãî ïðàâèëà âûâîäàA → γ , íå îáÿçàòåëüíî ÿâëÿåòñÿ îñíîâîé, ïîñêîëüêó ñâ¼ðòêà ïî ïðàâèëó A → γ ìîæåò äàòü öåïî÷êó, êîòîðàÿ íå ìîæåòáûòü ñâåäåíà ê àêñèîìå.Ôîðìàëüíî, îñíîâà ïðàâîé ñåíòåíöèàëüíîé ôîðìû z ýòî ïðàâèëî âûâîäà A → γ è ïîçèöèÿ â z , â êîòîðîé ìîæåòáûòü íàéäåíà öåïî÷êà γ òàêèå, ÷òî â ðåçóëüòàòå çàìåíûγ íà A ïîëó÷àåòñÿ ïðåäûäóùàÿ ñåíòåíöèàëüíàÿ ôîðìà âïðàâîñòîðîííåì âûâîäå z . Òàê, åñëè S ⇒∗r αAβ ⇒r αγβ ,òî A → γ â ïîçèöèè, ñëåäóþùåé çà α, ýòî îñíîâà öåïî÷êè αγβ .
Ïîäöåïî÷êà β ñïðàâà îò îñíîâû ñîäåðæèò òîëüêîòåðìèíàëüíûå ñèìâîëû.Âîîáùå ãîâîðÿ, ãðàììàòèêà ìîæåò áûòü íåîäíîçíà÷íîé,ïîýòîìó íå åäèíñòâåííûì ìîæåò áûòü ïðàâîñòîðîííèé âûâîä αγβ è íå åäèíñòâåííîé ìîæåò áûòü îñíîâà. Åñëè ãðàììàòèêà îäíîçíà÷íà, òî êàæäàÿ ïðàâàÿ ñåíòåíöèàëüíàÿ ôîðìà ãðàììàòèêè èìååò â òî÷íîñòè îäíó îñíîâó.
Çàìåíà îñíîâû â ñåíòåíöèàëüíîé ôîðìå íà íåòåðìèíàë ëåâîé ÷àñòè íàçûâàåòñÿ îòñå÷åíèåì îñíîâû. Îáðàùåíèå ïðàâîñòîðîííåãîâûâîäà ìîæåò áûòü ïîëó÷åíî ñ ïîìîùüþ ïîâòîðíîãî ïðèìåíåíèÿ îòñå÷åíèÿ îñíîâû, íà÷èíàÿ ñ èñõîäíîé öåïî÷êè w.4.6. Ðàçáîð ñíèçó-ââåðõ òèïà ñäâèã-ñâ¼ðòêà113Åñëè w ñëîâî â ðàññìàòðèâàåìîé ãðàììàòèêå, òî w = αn ,ãäå αn n-ÿ ïðàâàÿ ñåíòåíöèàëüíàÿ ôîðìà åù¼ íåèçâåñòíîãî ïðàâîãî âûâîäà S = α0 ⇒r α1 ⇒r . . .⇒r αn−1 ⇒r αn = w.×òîáû âîññòàíîâèòü ýòîò âûâîä â îáðàòíîì ïîðÿäêå, âûäåëÿåì îñíîâó γn â αn è çàìåíÿåì γn íà ëåâóþ ÷àñòü íåêîòîðîãî ïðàâèëà âûâîäà An → γn , ïîëó÷àÿ (n − 1)-þ ïðàâóþñåíòåíöèàëüíóþ ôîðìó αn−1 .
Çàòåì ïîâòîðÿåì ýòîò ïðîöåññ, òî åñòü âûäåëÿåì îñíîâó γn−1 â αn−1 è ñâîðà÷èâàåìýòó îñíîâó, ïîëó÷àÿ ïðàâóþ ñåíòåíöèàëüíóþ ôîðìó αn−2 .Åñëè, ïîâòîðÿÿ ýòîò ïðîöåññ, ìû ïîëó÷àåì ïðàâóþ ñåíòåíöèàëüíóþ ôîðìó, ñîñòîÿùóþ òîëüêî èç íà÷àëüíîãî ñèìâîëàS , òî îñòàíàâëèâàåìñÿ è ñîîáùàåì îá óñïåøíîì çàâåðøåíèèðàçáîðà.
Îáðàùåíèå ïîñëåäîâàòåëüíîñòè ïðàâèë, èñïîëüçîâàííûõ â ñâ¼ðòêàõ, åñòü ïðàâûé âûâîä âõîäíîé ñòðîêè.Òàêèì îáðàçîì, ãëàâíàÿ çàäà÷à àíàëèçàòîðà òèïà ñäâèãñâ¼ðòêà ýòî âûäåëåíèå è îòñå÷åíèå îñíîâû.4.6.2. LR(1)-àíàëèçàòîðû íàçâàíèè LR(1) ñèìâîë L óêàçûâàåò íà òî, ÷òî âõîäíàÿöåïî÷êà ÷èòàåòñÿ ñëåâà-íàïðàâî, R íà òî, ÷òî ñòðîèòñÿïðàâûé âûâîä, íàêîíåö, 1 óêàçûâàåò íà òî, ÷òî àíàëèçàòîðâèäèò îäèí ñèìâîë íåïðî÷èòàííîé ÷àñòè âõîäíîé öåïî÷êè.LR(1)-àíàëèç ïðèâëåêàòåëåí ïî íåñêîëüêèì ïðè÷èíàì: LR(1)-àíàëèç íàèáîëåå ìîùíûé ìåòîä àíàëèçà áåçâîçâðàòîâ òèïà ñäâèã-ñâ¼ðòêà; LR(1)-àíàëèç ìîæåò áûòü ðåàëèçîâàí äîâîëüíî ýôôåêòèâíî; LR(1)-àíàëèçàòîðû ìîãóò áûòü ïîñòðîåíû äëÿ ïðàêòè÷åñêè âñåõ êîíñòðóêöèé ÿçûêîâ ïðîãðàììèðîâàíèÿ; êëàññ ãðàììàòèê, êîòîðûå ìîãóò áûòü ïðîàíàëèçèðîâàíû LR(1)-ìåòîäîì, ñòðîãî âêëþ÷àåò êëàññ ãðàììàòèê, êîòîðûå ìîãóò áûòü ïðîàíàëèçèðîâàíû ïðåäñêàçûâàþùèìè àíàëèçàòîðàìè (ñâåðõó-âíèç òèïà LL(1)).Ñõåìàòè÷åñêè ñòðóêòóðà LR(1)-àíàëèçàòîðà èçîáðàæåíà íà ðèñ.
4.8. Àíàëèçàòîð ñîñòîèò èç âõîäíîé ëåíòû, âûõîäíîé ëåíòû, ìàãàçèíà, óïðàâëÿþùåé ïðîãðàììû è òàáëèöû àíàëèçà (LR(1)-òàáëèöû), êîòîðàÿ èìååò äâå ÷àñòè 114Ãëàâà 4. Ñèíòàêñè÷åñêèé àíàëèçôóíêöèþ äåéñòâèé (Action) è ôóíêöèþ ïåðåõîäîâ (Goto).Óïðàâëÿþùàÿ ïðîãðàììà îäíà è òà æå äëÿ âñåõ LR(1)àíàëèçàòîðîâ, ðàçíûå àíàëèçàòîðû îòëè÷àþòñÿ òîëüêî òàáëèöàìè àíàëèçà.Àíàëèçàòîð ÷èòàåò ñèìâîëû íà âõîäíîé ëåíòå ïî îäíîìó çà øàã.  ïðîöåññå àíàëèçà èñïîëüçóåòñÿ ìàãàçèí, âêîòîðîì õðàíÿòñÿ ñòðîêè âèäà S0 X1 S1 X2 S2 . . .
Xm Sm (Sm âåðõóøêà ìàãàçèíà). Êàæäûé Xi ñèìâîë ãðàììàòèêè(òåðìèíàëüíûé èëè íåòåðìèíàëüíûé), à Si ñèìâîë ñîñòîÿíèÿ.Çàìåòèì, ÷òî ñèìâîëû ãðàììàòèêè (ëèáî ñèìâîëû ñîñòîÿíèé) íå îáÿçàòåëüíî äîëæíû ðàçìåùàòüñÿ â ìàãàçèíå.Îäíàêî, èõ èñïîëüçîâàíèå îáëåã÷àåò ïîíèìàíèå ïîâåäåíèÿLR-àíàëèçàòîðà.FZ]Zabg<oh^6P;P D DL DQ /5ZgZebaZlhj<uoh^6P;P6 $FWLRQ*RWRÐèñ. 4.8.Ýëåìåíò ôóíêöèè äåéñòâèé Action[Sm , ai ] äëÿ ñèìâîëàñîñòîÿíèÿ Sm è âõîäà ai ∈ T ∪ {$}, ìîæåò èìåòü îäíî èç÷åòûð¼õ çíà÷åíèé:1) shift S (ñäâèã), ãäå S ñèìâîë ñîñòîÿíèÿ,2) reduce A→γ (ñâ¼ðòêà ïî ïðàâèëó ãðàììàòèêè A→γ ),3) accept (äîïóñê),4) error (îøèáêà).4.6. Ðàçáîð ñíèçó-ââåðõ òèïà ñäâèã-ñâ¼ðòêà115Ýëåìåíò ôóíêöèè ïåðåõîäîâ Goto[Sm , A] äëÿ ñèìâîëàñîñòîÿíèÿ Sm è âõîäà A ∈ N , ìîæåò èìåòü îäíî èç äâóõçíà÷åíèé:1) S , ãäå S ñèìâîë ñîñòîÿíèÿ,2) error (îøèáêà).Êîíôèãóðàöèåé LR(1)- àíàëèçàòîðà íàçûâàåòñÿ ïàðà,ïåðâàÿ êîìïîíåíòà êîòîðîé ñîäåðæèìîå ìàãàçèíà, à âòîðàÿ íåïðîñìîòðåííûé âõîä:(S0 X1 S1 X2 S2 . .
. Xm Sm , ai ai+1 . . . an $)Ýòà êîíôèãóðàöèÿ ñîîòâåòñòâóåò ïðàâîé ñåíòåíöèàëüíîé ôîðìåX1 X2 . . . Xm ai ai+1 . . . anÏðåôèêñû ïðàâûõ ñåíòåíöèàëüíûõ ôîðì, êîòîðûå ìîãóò ïîÿâèòüñÿ â ìàãàçèíå àíàëèçàòîðà, íàçûâàþòñÿ àêòèâíûìè ïðåôèêñàìè. Îñíîâà ñåíòåíöèàëüíîé ôîðìû âñåãäàðàñïîëàãàåòñÿ íà âåðõóøêå ìàãàçèíà. Òàêèì îáðàçîì, àêòèâíûé ïðåôèêñ ýòî òàêîé ïðåôèêñ ïðàâîé ñåíòåíöèàëüíîé ôîðìû, êîòîðûé íå ïåðåõîäèò ïðàâóþ ãðàíèöó îñíîâûýòîé ôîðìû.Êîãäà àíàëèçàòîð íà÷èíàåò ðàáîòó, â ìàãàçèíå íàõîäèòñÿ òîëüêî ñèìâîë íà÷àëüíîãî ñîñòîÿíèÿ S0 , íà âõîäíîé ëåíòå àíàëèçèðóåìàÿ öåïî÷êà ñ ìàðêåðîì êîíöà.Êàæäûé î÷åðåäíîé øàã àíàëèçàòîðà îïðåäåëÿåòñÿ òåêóùèì âõîäíûì ñèìâîëîì ai è ñèìâîëîì ñîñòîÿíèÿ íà âåðõóøêå ìàãàçèíà Sm ñëåäóþùèì íèæå îáðàçîì.Ïóñòü LR(1)-àíàëèçàòîð íàõîäèòñÿ â êîíôèãóðàöèè(S0 X1 S1 X2 S2 .
. . Xm Sm , ai ai+1 . . . an $)Àíàëèçàòîð ìîæåò ïðîäåëàòü îäèí èç ñëåäóþùèõ øàãîâ:1. Åñëè Action[Sm , ai ] = shift S , òî àíàëèçàòîð âûïîëíÿåò ñäâèã, ïåðåõîäÿ â êîíôèãóðàöèþ(S0 X1 S1 X2 S2 . . . Xm Sm ai S, ai+1 . . . an $)116Ãëàâà 4. Ñèíòàêñè÷åñêèé àíàëèçÒî åñòü, â ìàãàçèí ïîìåùàþòñÿ âõîäíîé ñèìâîë ai èñèìâîë ñîñòîÿíèÿ S , îïðåäåëÿåìûé Action[Sm , ai ]. Òåêóùèì âõîäíûì ñèìâîëîì ñòàíîâèòñÿ ai+1 .2. Åñëè Action[Sm , ai ] = reduce A → γ , òî àíàëèçàòîðâûïîëíÿåò ñâ¼ðòêó, ïåðåõîäÿ â êîíôèãóðàöèþ(S0 X1 S1 X2 S2 .
. . Xm−r Sm−r AS, ai ai+1 . . . an $)ãäå S = Goto[Sm−r , A] è r äëèíà γ , ïðàâîé ÷àñòèïðàâèëà âûâîäà.Àíàëèçàòîð ñíà÷àëà óäàëÿåò èç ìàãàçèíà 2r ñèìâîëîâ(r ñèìâîëîâ ñîñòîÿíèÿ è r ñèìâîëîâ ãðàììàòèêè), òàê÷òî íà âåðõóøêå îêàçûâàåòñÿ ñîñòîÿíèå Sm−r . Çàòåìàíàëèçàòîð ïîìåùàåò â ìàãàçèí A ëåâóþ ÷àñòü ïðàâèëà âûâîäà, è S ñèìâîë ñîñòîÿíèÿ, îïðåäåëÿåìûéGoto[Sm−r , A]. Íà øàãå ñâ¼ðòêè òåêóùèé âõîäíîé ñèìâîë íå ìåíÿåòñÿ.
Äëÿ LR(1)-àíàëèçàòîðîâ ïîñëåäîâàòåëüíîñòü ñèìâîëîâ ãðàììàòèêè Xm−r+1 . . . Xm , óäàëÿåìûõ èç ìàãàçèíà, âñåãäà ñîîòâåòñòâóåò γ ïðàâîé÷àñòè ïðàâèëà âûâîäà, ïî êîòîðîìó äåëàåòñÿ ñâ¼ðòêà.Ïîñëå îñóùåñòâëåíèÿ øàãà ñâ¼ðòêè ãåíåðèðóåòñÿ âûõîä LR(1)-àíàëèçàòîðà, òî åñòü èñïîëíÿþòñÿ ñåìàíòè÷åñêèå äåéñòâèÿ, ñâÿçàííûå ñ ïðàâèëîì, ïî êîòîðîìóäåëàåòñÿ ñâ¼ðòêà, íàïðèìåð, ïå÷àòàþòñÿ íîìåðà ïðàâèë, ïî êîòîðûì äåëàåòñÿ ñâ¼ðòêà.Çàìåòèì, ÷òî ôóíêöèÿ Goto òàáëèöû àíàëèçà, ïîñòðîåííàÿ ïî ãðàììàòèêå G, ôàêòè÷åñêè ïðåäñòàâëÿåò ñîáîé ôóíêöèþ ïåðåõîäîâ äåòåðìèíèðîâàííîãî êîíå÷íîãî àâòîìàòà, ðàñïîçíàþùåãî àêòèâíûå ïðåôèêñû G.3. Åñëè Action[Sm , ai ] = accept, òî ðàçáîð óñïåøíî çàâåðø¼í.4.
Åñëè Action[Sm , ai ] = error, òî àíàëèçàòîð îáíàðóæèë îøèáêó, è âûïîëíÿþòñÿ äåéñòâèÿ ïî äèàãíîñòèêåè âîññòàíîâëåíèþ.Ïðèìåð 4.10. Ðàññìîòðèì ãðàììàòèêó àðèôìåòè÷åñêèõâûðàæåíèé G = ({E, T, F }, {id, +, ∗}, P, E) ñ ïðàâèëàìè:4.6. Ðàçáîð ñíèçó-ââåðõ òèïà ñäâèã-ñâ¼ðòêà117(1) E → E + T(2) E → T(3) T → T ∗ F(4) T → F(5) F → idÍà ðèñ. 4.9 èçîáðàæåíû ôóíêöèè Action è Goto, îáðàçóþùèå LR(1)-òàáëèöó äëÿ ýòîé ãðàììàòèêè. Ýëåìåíò Si ôóíêöèèAction îçíà÷àåò ñäâèã è ïîìåùåíèå â ìàãàçèí ñîñòîÿíèÿ ñ íîìåðîì i, Rj ñâ¼ðòêó ïî ïðàâèëó íîìåð j , acc äîïóñê, ïóñòàÿêëåòêà îøèáêó.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
