В.А. Серебряков, М.П. Галочкин и др. - Теория и реализация языков программирования (2006) (1134633), страница 36
Текст из файла (страница 36)
9.28.RULEReg ::= '@' RegSEMANTICSif (Match<0> ñîäåðæèò Reg â i-é ïîçèöèè)Match<2>=<<'+' Reg Const>,Reg>;if (Match<0> ñîäåðæèò <'@' '+' Reg Const>â j-é ïîçèöèè)äîáàâèòü ê Match<2> <'+' Reg Const> â k ïîçèöèè;if (Match<0> ñîäåðæèò Reg â i-é ïîçèöèè)Pattern<0>[i]=Pattern<2>[1]|Pattern<2>[2];268Ãëàâà 9. Ãåíåðàöèÿ êîäàif (Match<0> ñîäåðæèò <'@' '+' Reg Const>â j-é ïîçèöèè)Pattern<0>[j]=Pattern<2>[k].Îáðàçöû, ñîîòâåòñòâóþùèå ýòîìó ïðàâèëó, ñëåäóþùèå:(3) Reg → '@' '+' Reg Const,(7) Reg → '@' Reg .Ñîîòâåòñòâåííî, àòðèáóòó Match âòîðîãî ñèìâîëà â êà÷åñòâå îáðàçöîâ ïðè ñîïîñòàâëåíèè ìîãóò áûòü ïåðåäàíû <'+' Reg Const> (îáðàçåö 3) èëè <Reg> (îáðàçåö7).
Èç àíàëèçà äðóãèõ ïðàâèë ìîæíî çàêëþ÷èòü, ÷òîïðè ñîïîñòàâëåíèè îáðàçöîâ ïðåäêîâ ëåâîé ÷àñòè äàííîãî ïðàâèëà àòðèáóòó Match ìîãóò áûòü ïåðåäàíû îáðàçöû<'@' '+' Reg Const> (èç îáðàçöà 6) è Reg.RULEReg ::= ConstSEMANTICSif (Pattern<0> ñîäåðæèò Const â j-é ïîçèöèè)Pattern<0>[j]=true;if (Pattern<0> ñîäåðæèò Reg â i-é ïîçèöèè)Pattern<0>[i]=true.Äëÿ äåðåâà ðèñ.
9.24 ïîëó÷èì çíà÷åíèÿ àòðèáóòîâ, ïðèâåä¼ííûå íà ðèñ. 9.28. Çäåñü M îáîçíà÷àåò Match, P Pattern, C Const, R Reg.Ãëàâà 10.ÑèñòåìûàâòîìàòèçàöèèïîñòðîåíèÿòðàíñëÿòîðîâÑèñòåìû àâòîìàòèçàöèè ïîñòðîåíèÿ òðàíñëÿòîðîâ(ÑÀÏÒ) ïðåäíàçíà÷åíû äëÿ àâòîìàòèçàöèè ïðîöåññàðàçðàáîòêè òðàíñëÿòîðîâ. Î÷åâèäíî, ÷òî äëÿ òîãî, ÷òîáûîïèñàòü òðàíñëÿòîð, íåîáõîäèìî èìåòü ôîðìàëèçì äëÿîïèñàíèÿ. Ýòîò ôîðìàëèçì çàòåì ðåàëèçóåòñÿ â âèäåâõîäíîãî ÿçûêà ÑÀÏÒ. Êàê ïðàâèëî, ôîðìàëèçìû îñíîâàíû íà àòðèáóòíûõ ãðàììàòèêàõ. Íèæå îïèñàíû äâåÑÀÏÒ, ïîëó÷èâøèå ðàñïðîñòðàíåíèå: ÑÓÏÅÐ [4] è Yacc. îñíîâó ïåðâîé ñèñòåìû ïîëîæåíû LL(1)-ãðàììàòèêè èL-àòðèáóòíûå âû÷èñëèòåëè, â îñíîâó âòîðîé LALR(1)ãðàììàòèêè è S-àòðèáóòíûå âû÷èñëèòåëè.270Ãëàâà 10. Àâòîìàòèçàöèÿ ïîñòðîåíèÿ òðàíñëÿòîðîâ10.1. Ñèñòåìà ÑÓÏÅÐÏðîãðàììà íà âõîäíîì ÿçûêå ÑÓÏÅÐ (¾ìåòàïðîãðàììà¿) ñîñòîèò èç ñëåäóþùèõ ðàçäåëîâ: Çàãîëîâîê; Ðàçäåë êîíñòàíò; Ðàçäåë òèïîâ; Àëôàâèò; Ðàçäåë ôàéëîâ; Ðàçäåë áèáëèîòåêè; Àòðèáóòíàÿ ñõåìà.Çàãîëîâîê îïðåäåëÿåò èìÿ àòðèáóòíîé ãðàììàòèêè, ïåðâûå òðè áóêâû èìåíè çàäàþò ðàñøèðåíèå èìåíè âõîäíîãîôàéëà äëÿ ðåàëèçóåìîãî òðàíñëÿòîðà.Ðàçäåë êîíñòàíò ñîäåðæèò îïèñàíèå êîíñòàíò, ðàçäåëòèïîâ îïèñàíèå òèïîâ.Àëôàâèò ñîäåðæèò ïåðå÷èñëåíèå íåòåðìèíàëüíûõ ñèìâîëîâ è êëàññîâ ëåêñåì, à òàêæå àòðèáóòîâ (è èõ òèïîâ),ñîïîñòàâëåííûõ ýòèì ñèìâîëàì.
Êëàññû ëåêñåì ÿâëÿþòñÿòåðìèíàëüíûìè ñèìâîëàìè ñ òî÷êè çðåíèÿ ñèíòàêñè÷åñêîãîàíàëèçà, íî ìîãóò èìåòü àòðèáóòû, âû÷èñëÿåìûå â ïðîöåññåëåêñè÷åñêîãî àíàëèçà. Îïðåäåëåíèå êëàññà ëåêñåì ñîñòîèòâ çàäàíèè èìåíè êëàññà, èì¼í àòðèáóòîâ äëÿ ýòîãî êëàññàè òèïîâ ýòèõ àòðèáóòîâ. ðàçäåëå îïðåäåëåíèÿ íåòåðìèíàëüíûõ ñèìâîëîâ ñîäåðæèòñÿ ïåðå÷èñëåíèå ýòèõ ñèìâîëîâ ñ óêàçàíèåì ïðèïèñàííûõ èì àòðèáóòîâ è èõ òèïîâ. Àêñèîìà ãðàììàòèêè óêàçûâàåòñÿ ïåðâûì ñèìâîëîì â ñïèñêå íåòåðìèíàëîâ.Ðàçäåë áèáëèîòåêè ñîäåðæèò çàãîëîâêè ïðîöåäóð èôóíêöèé, èñïîëüçóåìûõ â ôîðìóëàõ àòðèáóòíîé ãðàììàòèêè.Ðàçäåë ôàéëîâ ñîäåðæèò îïèñàíèå ôàéëîâûõ ïåðåìåííûõ, èñïîëüçóåìûõ â ôîðìóëàõ àòðèáóòíîé ãðàììàòèêè.Ôàéëîâûå ïåðåìåííûå ìîæíî ðàññìàòðèâàòü êàê àòðèáóòû àêñèîìû.Àòðèáóòíàÿ ñõåìà ñîñòîèò èç ñïèñêà ñèíòàêñè÷åñêèõïðàâèë è ñîïîñòàâëåííûõ èì ñåìàíòè÷åñêèõ ïðàâèë. Äëÿîïèñàíèÿ ñèíòàêñèñà ÿçûêà èñïîëüçóåòñÿ ðàñøèðåííàÿ10.1.
Ñèñòåìà ÑÓÏÅÐ271ôîðìà Áýêóñà-Íàóðà. Òåðìèíàëüíûå ñèìâîëû â ïðàâîé ÷àñòè çàêëþ÷àþòñÿ â êàâû÷êè, êëàññû ëåêñåì è íåòåðìèíàëûçàäàþòñÿ èõ èìåíàìè. Äëÿ çàäàíèÿ â ïðàâîé ÷àñòè íåîáÿçàòåëüíûõ ñèìâîëîâ èñïîëüçóþòñÿ ñêîáêè [ ], äëÿ çàäàíèÿïîâòîðÿþùèõñÿ êîíñòðóêöèé èñïîëüçóþòñÿ ñêîáêè ( ). Âýòîì ñëó÷àå ìîæåò áûòü óêàçàí ðàçäåëèòåëü ñèìâîëîâ (ïîñëå /). Íàïðèìåð,A ::= B [ C ] ( D ) ( E / ',' )Ïåðâûì ïðàâèëîì â àòðèáóòíîé ñõåìå äîëæíî áûòü ïðàâèëî äëÿ àêñèîìû.Êàæäîìó ñèíòàêñè÷åñêîìó ïðàâèëó ìîãóò áûòü ñîïîñòàâëåíû ñåìàíòè÷åñêèå äåéñòâèÿ. Êàæäîå òàêîå äåéñòâèå ýòî îïåðàòîð, êîòîðûé ìîæåò èñïîëüçîâàòü àòðèáóòûêàê ñèìâîëîâ äàííîãî ïðàâèëà (ëîêàëüíûå àòðèáóòû), òàêè ñèìâîëîâ, ìîãóùèõ áûòü ïðåäêàìè (äèíàìè÷åñêè) ñèìâîëà ëåâîé ÷àñòè äàííîãî ïðàâèëà â äåðåâå ðàçáîðà (ãëîáàëüíûå àòðèáóòû).
Äëÿ ññûëêè íà ëîêàëüíûå àòðèáóòûñèìâîëû äàííîãî ïðàâèëà (êàê òåðìèíàëüíûå, òàê è íåòåðìèíàëüíûå) íóìåðóþòñÿ îò 0 (äëÿ ñèìâîëà ëåâîé ÷àñòè).Ïðè ññûëêå íà ãëîáàëüíûå àòðèáóòû íàäî èìåòü â âèäó,÷òî àòðèáóòû èìåþò îáëàñòè âèäèìîñòè íà äåðåâå ðàçáîðà. Îáëàñòüþ âèäèìîñòè àòðèáóòà âåðøèíû, ïîìå÷åííîé N,ÿâëÿåòñÿ âñ¼ ïîääåðåâî N, çà èñêëþ÷åíèåì åãî ïîääåðåâüåâ,òàêæå ïîìå÷åííûõ N.Èñïîëíåíèå îïåðàòîðîâ ñåìàíòè÷åñêîé ÷àñòè ïðàâèëàïðèâÿçûâàåòñÿ ê îáõîäó äåðåâà ðàçáîðà ñâåðõó âíèç ñëåâàíàïðàâî.
Äëÿ ýòîãî êàæäûé îïåðàòîð ìîæåò áûòü ïîìå÷åíìåòêîé, ñîñòîÿùåé èç íîìåðà âåòâè ïðàâèëà, ê âûïîëíåíèþêîòîðîé äîëæåí áûòü ïðèâÿçàí îïåðàòîð, è, âîçìîæíî, îäíîãî èç ñóôôèêñîâ A, B, E, M.Ñóôôèêñ A çàäà¼ò âûïîëíåíèå îïåðàòîðà ïåðåä êàæäûì âõîæäåíèåì ñèíòàêñè÷åñêîé êîíñòðóêöèè, çàêëþ÷¼ííîé â ñêîáêè ïîâòîðåíèé ( ). Ñóôôèêñ B çàäà¼ò âûïîëíåíèå îïåðàòîðà ïîñëå êàæäîãî âõîæäåíèÿ ñèíòàêñè÷åñêîéêîíñòðóêöèè, çàêëþ÷¼ííîé â ñêîáêè ïîâòîðåíèé ( ). Ñóôôèêñ M çàäà¼ò âûïîëíåíèå îïåðàòîðà ìåæäó âõîæäåíèÿìè272Ãëàâà 10. Àâòîìàòèçàöèÿ ïîñòðîåíèÿ òðàíñëÿòîðîâñèíòàêñè÷åñêîé êîíñòðóêöèè, çàêëþ÷¼ííîé â ñêîáêè ïîâòîðåíèé ( ).
Ñóôôèêñ E çàäà¼ò âûïîëíåíèå îïåðàòîðà â òîìñëó÷àå, êîãäà êîíñòðóêöèÿ, çàêëþ÷¼ííàÿ â ñêîáêè [ ], îòñóòñòâóåò.Ïðèìåð èñïîëüçîâàíèå ìåòîê àòðèáóòíûõ ôîðìóë:D ::= 'd' =>$0.y:=$0.x+1.A ::= B (C) [D] =>$2.x:=1;2M: $2.x:=$2.x+1;$3.x:=$2.x;3E: $3.y:=$3.x;3: writeln($3.y).Ïðîöåäóðà writeln íàïå÷àòàåò ÷èñëî âõîæäåíèé ñèìâîëà C â C-ñïèñîê, åñëè D îïóùåíî.  ïðîòèâíîì ñëó÷àå íàïå÷àòàííîå ÷èñëî áóäåò íà åäèíèöó áîëüøå.10.2. Ñèñòåìà YACC îñíîâó ñèñòåìû YACC ïîëîæåí ñèíòàêñè÷åñêèé àíàëèçàòîð òèïà LALR(1), ãåíåðèðóåìûé ïî âõîäíîé (ìåòà)ïðîãðàììå. Ýòà ïðîãðàììà ñîñòîèò èç òð¼õ ÷àñòåé:%{Ñè-òåêñò%}%token Ñïèñîê èì¼í ëåêñåì%%Ñïèñîê ïðàâèë òðàíñëÿöèè%%Ñëóæåáíûå Ñè-ïîäïðîãðàììûÑè-òåêñò (êîòîðûé âìåñòå ñ îêðóæàþùèìè ñêîáêàìè %{ è %} ìîæåò îòñóòñòâîâàòü) îáû÷íî ñîäåðæèò Ñèîáúÿâëåíèÿ (âêëþ÷àÿ #include è #define), èñïîëüçóåìûå âòåêñòå íèæå.
Ýòîò Ñè-òåêñò ìîæåò ñîäåðæàòü è îáúÿâëåíèÿ(èëè ïðåäîáúÿâëåíèÿ) ôóíêöèé.10.2. Ñèñòåìà YACC273Ñïèñîê èì¼í ëåêñåì ñîäåðæèò èìåíà, êîòîðûå ïðåîáðàçóþòñÿ YACC-ïðåïðîöåññîðîì â îáúÿâëåíèÿ êîíñòàíò(#define). Êàê ïðàâèëî, ýòè èìåíà èñïîëüçóþòñÿ êàê èìåíà êëàññîâ ëåêñåì è ñëóæàò äëÿ îïðåäåëåíèÿ èíòåðôåéñà ñëåêñè÷åñêèì àíàëèçàòîðîì.Êàæäîå ïðàâèëî òðàíñëÿöèè èìååò âèäËåâàÿ_÷àñòü : àëüòåðíàòèâà_1{ñåìàíòè÷åñêèå_äåéñòâèÿ_1}| àëüòåðíàòèâà_2 {ñåìàíòè÷åñêèå_äåéñòâèÿ_2}|...| àëüòåðíàòèâà_n {ñåìàíòè÷åñêèå_äåéñòâèÿ_n};Êàæäîå ñåìàíòè÷åñêîå äåéñòâèå ýòî ïîñëåäîâàòåëüíîñòü îïåðàòîðîâ Ñè.
Ïðè ýòîì êàæäîìó íåòåðìèíàëó ìîæåò áûòü ñîïîñòàâëåí îäèí ñèíòåçèðóåìûé àòðèáóò. Íààòðèáóò íåòåðìèíàëà ëåâîé ÷àñòè ññûëêà îñóùåñòâëÿåòñÿïîñðåäñòâîì çíà÷êà $$, íà àòðèáóòû ñèìâîëîâ ïðàâîé ÷àñòè ïîñðåäñòâîì çíà÷êîâ $1, $2 , . . . , $n, ïðè÷¼ì íîìåðñîîòâåòñòâóåò ïîðÿäêó ýëåìåíòîâ ïðàâîé ÷àñòè, âêëþ÷àÿñåìàíòè÷åñêèå äåéñòâèÿ. Êàæäîå ñåìàíòè÷åñêîå äåéñòâèåìîæåò âûðàáàòûâàòü çíà÷åíèå â ðåçóëüòàòå âûïîëíåíèÿïðèñâàèâàíèÿ $$=Âûðàæåíèå. Èñïîëíåíèå òàêîãî îïåðàòîðàâ ïîñëåäíåì ñåìàíòè÷åñêîì äåéñòâèè îïðåäåëÿåò çíà÷åíèåàòðèáóòà ñèìâîëà ëåâîé ÷àñòè. íåêîòîðûõ ñëó÷àÿõ äîïóñêàåòñÿ èñïîëüçîâàíèå ãðàììàòèê, èìåþùèõ êîíôëèêòû. Ïðè ýòîì ñèíòàêñè÷åñêèéàíàëèçàòîð ðàçðåøàåò êîíôëèêòû ñëåäóþùèì îáðàçîì: êîíôëèêòû òèïà ñâ¼ðòêà/ñâ¼ðòêà ðàçðåøàþòñÿ âûáîðîì ïðàâèëà, ïðåäøåñòâóþùåãî âî âõîäíîé ìåòàïðîãðàììå; êîíôëèêòû òèïà ñäâèã/ñâ¼ðòêà ðàçðåøàþòñÿ ïðåäïî÷òåíèåì ñäâèãà. Ïîñêîëüêó ýòèõ ïðàâèë íå âñåãäà äîñòàòî÷íî äëÿ ïðàâèëüíîãî îïðåäåëåíèÿ àíàëèçàòîðà, äîïóñêàåòñÿîïðåäåëåíèå ñòàðøèíñòâà è àññîöèàòèâíîñòè òåðìèíàëîâ.Íàïðèìåð, îáúÿâëåíèå%left '+' '-'274Ãëàâà 10.
Àâòîìàòèçàöèÿ ïîñòðîåíèÿ òðàíñëÿòîðîâîïðåäåëÿåò + è −, èìåþùèìè îäèíàêîâûé ïðèîðèòåò è èìåþùèìè ëåâóþ àññîöèàòèâíîñòü. Îïåðàöèþ ìîæíî îïðåäåëèòü êàê ïðàâîàññîöèàòèâíóþ â ðåçóëüòàòå îáúÿâëåíèÿ:%right '^'Áèíàðíóþ îïåðàöèþ ìîæíî îïðåäåëèòü êàê íåàññîöèàòèâíóþ (òî åñòü íå äîïóñêàþùóþ ïîÿâëåíèÿ îáúåäèíåíèÿäâóõ ïîäðÿä èäóùèõ çíàêîâ îïåðàöèè):%nonassoc '<'Ñèìâîëû, ïåðå÷èñëåííûå â îäíîì îáúÿâëåíèè, èìåþòîäèíàêîâîå ñòàðøèíñòâî. Ñòàðøèíñòâî âûøå äëÿ êàæäîãîïîñëåäóþùåãî îáúÿâëåíèÿ. Êîíôëèêòû ðàçðåøàþòñÿ ïóò¼ì ïðèñâàèâàíèÿ ñòàðøèíñòâà è àññîöèàòèâíîñòè êàæäîìó ïðàâèëó ãðàììàòèêè è êàæäîìó òåðìèíàëó, ó÷àñòâóþùèì â êîíôëèêòå. Åñëè íåîáõîäèìî âûáðàòü ìåæäó ñäâèãîì âõîäíîãî ñèìâîëà s è ñâ¼ðòêîé ïî ïðàâèëó A → w,ñâ¼ðòêà äåëàåòñÿ, åñëè ñòàðøèíñòâî ïðàâèëà áîëüøå ñòàðøèíñòâà s èëè åñëè ñòàðøèíñòâî îäèíàêîâî, à ïðàâèëî ëåâîàññîöèàòèâíî.
 ïðîòèâíîì ñëó÷àå äåëàåòñÿ ñäâèã.Îáû÷íî çà ñòàðøèíñòâî ïðàâèëà ïðèíèìàåòñÿ ñòàðøèíñòâî ñàìîãî ïðàâîãî òåðìèíàëà ïðàâèëà.  òåõ ñëó÷àÿõ, êîãäà ñàìûé ïðàâûé òåðìèíàë íå äà¼ò íóæíîãî ïðèîðèòåòà,ýòîò ïðèîðèòåò ìîæíî íàçíà÷èòü ñëåäóþùèì îáúÿâëåíèåì:%prec òåðìèíàëÑòàðøèíñòâî è àññîöèàòèâíîñòü ïðàâèëà â ýòîì ñëó÷àå áóäóò òàêèìè æå, êàê ó óêàçàííîãî òåðìèíàëà.YACC íå ñîîáùàåò î êîíôëèêòàõ, ðàçðåøàåìûõ ñ ïîìîùüþ àññîöèàòèâíîñòè è ïðèîðèòåòîâ. Âîññòàíîâëåíèå ïîñëåîøèáîê óïðàâëÿåòñÿ ïîëüçîâàòåëåì ñ ïîìîùüþ ââåäåíèÿ âãðàììàòèêó ¾ïðàâèë îøèáêè¿ âèäàA → error w.Çäåñü error êëþ÷åâîå ñëîâî YACC.
Êîãäà âñòðå÷àåòñÿ ñèíòàêñè÷åñêàÿ îøèáêà, àíàëèçàòîð òðàêòóåò ñîñòîÿíèå,íàáîð ñèòóàöèé äëÿ êîòîðîãî ñîäåðæèò ïðàâèëî äëÿ error,10.2. Ñèñòåìà YACC275íåêîòîðûì ñïåöèàëüíûì îáðàçîì: ñèìâîëû èç ñòåêà âûòàëêèâàþòñÿ äî òåõ ïîð, ïîêà íà âåðõóøêå ñòåêà íå áóäåò îáíàðóæåíî ñîñòîÿíèå, äëÿ êîòîðîãî íàáîð ñèòóàöèé ñîäåðæèòñèòóàöèþ âèäà [A → .error w]. Ïîñëå ÷åãî â ñòåê ôèêòèâíî ïîìåùàåòñÿ ñèìâîë error, êàê åñëè áû îí âñòðåòèëñÿ âîâõîäíîé ñòðîêå.Åñëè w ïóñòî, äåëàåòñÿ ñâ¼ðòêà.
Ïîñëå ýòîãî àíàëèçàòîð ïðîïóñêàåò âõîäíûå ñèìâîëû, ïîêà íå íàéä¼ò òàêîé, ñêîòîðûì ìîæíî ïðîäîëæèòü íîðìàëüíûé ðàçáîð.Åñëè w íå ïóñòî, ïðîñìàòðèâàåòñÿ âõîäíàÿ ñòðîêà è äåëàåòñÿ ïîïûòêà ñâåðíóòü w. Åñëè w ñîñòîèò òîëüêî èç òåðìèíàëîâ, ýòà ñòðîêà èùåòñÿ âî âõîäíîì ïîòîêå.Ïðèëîæåíèå A.Ñåìàíòèêàêîíòåêñòíî-ñâîáîäíûõÿçûêîâÄ.Ý. Êíóò 1California Institute of TechnologyÍàéòè ¾çíà÷åíèå¿ öåïî÷êè ÊÑ-ÿçûêà ìîæíî, âû÷èñëèââ êàæäîì óçëå äåðåâà å¼ âûâîäà òàê íàçûâàåìûå ¾àòðèáóòû¿. Àòðèáóòû âû÷èñëÿþòñÿ ñ ïîìîùüþ ôóíêöèé, ñîïîñòàâëåííûõ ñèíòàêñè÷åñêèì ïðàâèëàì ãðàììàòèêè.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
