В.А. Серебряков, М.П. Галочкин и др. - Теория и реализация языков программирования (2006) (1134633), страница 2
Текст из файла (страница 2)
. . . . . . . . . . .C.4.1. ÊÑ-ãðàììàòèêè è ÌÏ-àâòîìàòû . .C.4.2. Àëãåáðàè÷åñêèå ñâîéñòâà ÊÑ-ÿçûêîâ.Ëåììà î ðàçðàñòàíèè. . . . . . . . . .C.4.3. Ïðåîáðàçîâàíèÿ ÊÑ-ãðàììàòèê . . .C.4.4. Ïðåäñêàçûâàþùèé ðàçáîð ñâåðõó-âíèçC.4.5. Ðàçáîð ñíèçó-ââåðõ òèïà ñäâèãñâåðòêà . . . . . . . . . . . .
. . . . .C.5. Ýëåìåíòû òåîðèè ïåðåâîäà . . . . . . . . . .C.5.3. Àòðèáóòíûå ãðàììàòèêè . . . . . . .C.9. Ãåíåðàöèÿ êîäà . . . . . . . . . . . . . . . . .C.9.1. Òðàíñëÿöèÿ àðèôìåòè÷åñêèõ âûðàæåíèé . . . . . . . . . . . . . . . . . . .C.9.2. Òðàíñëÿöèÿ ëîãè÷åñêèõ âûðàæåíèéC.9.3. Ãåíåðàöèÿ îïòèìàëüíîãî êîäà ìåòîäàìè ñèíòàêñè÷åñêîãî àíàëèçà . . .
. .Ëèòåðàòóðà7338338339339342343345347351351352352352352353ÏðåäèñëîâèåÏðåäëàãàåìàÿ âíèìàíèþ ÷èòàòåëÿ êíèãà îñíîâàíà íàêóðñå ëåêöèé, ïðî÷èòàííûõ íà ôàêóëüòåòå âû÷èñëèòåëüíîéìàòåìàòèêè è êèáåðíåòèêè ÌÃÓ èì. Ì.Â. Ëîìîíîñîâà è íàôàêóëüòåòå óïðàâëåíèÿ è ïðèêëàäíîé ìàòåìàòèêè Ìîñêîâñêîãî ôèçèêî-òåõíè÷åñêîãî èíñòèòóòà â 19912002 ãã. Àâòîðû íàäåþòñÿ, ÷òî èçäàíèå êíèãè âîñïîëíèò ñóùåñòâåííûéïðîáåë â ëèòåðàòóðå íà ðóññêîì ÿçûêå ïî ðàçðàáîòêå êîìïèëÿòîðîâ. êíèãå ïðåäñòàâëåíû ¾êëàññè÷åñêèå¿ ðàçäåëû òåîðèèðàçðàáîòêè êîìïèëÿòîðîâ: ëåêñè÷åñêèé è ñèíòàêñè÷åñêèéàíàëèç, îðãàíèçàöèÿ ïàìÿòè êîìïèëÿòîðà (òàáëèöû ñèìâîëîâ) è ïåðèîäà èñïîëíåíèÿ (ìàãàçèíà), ãåíåðàöèÿ êîäà.Ðàññìàòðèâàþòñÿ òàêèå ñðåäñòâà àâòîìàòèçàöèè ïðîöåññàðàçðàáîòêè òðàíñëÿòîðîâ, êàê LEX, YACC, ÑÓÏÅÐ, ìåòîäû ãåíåðàöèè îïòèìàëüíîãî êîäà. Ñäåëàíà ïîïûòêà íà ïðîòÿæåíèè âñåãî èçëîæåíèÿ ïðîâåñòè åäèíóþ ¾àòðèáóòíóþ¿òî÷êó çðåíèÿ íà ïðîöåññ ðàçðàáîòêè êîìïèëÿòîðà.  êíèãåíå çàòðàãèâàþòñÿ ÷ðåçâû÷àéíî âàæíûå âîïðîñû ãëîáàëüíîé îïòèìèçàöèè è ðàçðàáîòêè êîìïèëÿòîðîâ äëÿ ìàøèí ñïàðàëëåëüíîé àðõèòåêòóðîé.
Àâòîðû íàäåþòñÿ âîñïîëíèòüýòè ïðîáåëû â áóäóùåì.Êíèãà ðàññ÷èòàíà êàê íà ñòóäåíòîâ è àñïèðàíòîâ ïðîãðàììèñòñêèõ ñïåöèàëüíîñòåé, òàê è íà ïðîôåññèîíàëîâ âîáëàñòè ïðîãðàììèðîâàíèÿ.Àâòîðû áëàãîäàðÿò âñåõ, êòî ñïîñîáñòâîâàë âûõîäó ýòîéêíèãè â Ñâåò è ñ ïðèçíàòåëüíîñòüþ ïðèìóò âñå êîíñòðóêòèâíûå çàìå÷àíèÿ ïî å¼ ñîäåðæàíèþ è îôîðìëåíèþ.Ãëàâà 1.Ââåäåíèå1.1. Ìåñòî êîìïèëÿòîðà â ïðîãðàììíîì îáåñïå÷åíèèÊîìïèëÿòîðû ñîñòàâëÿþò ñóùåñòâåííóþ ÷àñòü ïðîãðàììíîãî îáåñïå÷åíèÿ ÝÂÌ. Ýòî ñâÿçàíî ñ òåì, ÷òî ÿçûêè âûñîêîãî óðîâíÿ ñòàëè îñíîâíûì ñðåäñòâîì ðàçðàáîòêèïðîãðàìì. Ñåãîäíÿ òîëüêî î÷åíü ìàëàÿ ÷àñòü ïðîãðàììíîãî îáåñïå÷åíèÿ, òðåáóþùàÿ îñîáîé ýôôåêòèâíîñòè, ðàçðàáàòûâàåòñÿ ñ ïîìîùüþ àññåìáëåðîâ.  íàñòîÿùåå âðåìÿèìååò ïðèìåíåíèå äîâîëüíî ìíîãî ÿçûêîâ ïðîãðàììèðîâàíèÿ. Íàðÿäó ñ òðàäèöèîííûìè ÿçûêàìè, òàêèìè, íàïðèìåð,êàê Ôîðòðàí, øèðîêîå ðàñïðîñòðàíåíèå ïîëó÷èëè òàê íàçûâàåìûå ¾óíèâåðñàëüíûå¿ ÿçûêè (Ïàñêàëü, Ñè, Ìîäóëà-2,Àäà è äðóãèå), à òàêæå íåêîòîðûå ñïåöèàëèçèðîâàííûå (íàïðèìåð, ÿçûê îáðàáîòêè ñïèñî÷íûõ ñòðóêòóð Ëèñï).
Êðîìåòîãî, áîëüøîå ðàñïðîñòðàíåíèå ïîëó÷èëè ÿçûêè, ñâÿçàííûåñ óçêèìè ïðåäìåòíûìè îáëàñòÿìè, òàêèå, êàê âõîäíûå ÿçûêè ïàêåòîâ ïðèêëàäíûõ ïðîãðàìì.Äëÿ ðÿäà íàçâàííûõ ÿçûêîâ èìååòñÿ äîâîëüíî ìíîãî ðåàëèçàöèé. Òàê, íà ðûíêå ïðîãðàììíîãî îáåñïå÷åíèÿ ïðåäñòàâëåíû äåñÿòêè ðåàëèçàöèé ÿçûêîâ Ïàñêàëÿ, Ìîäóëû-2èëè Ñè äëÿ ÝÂÌ òèïà IBM PC.10Ãëàâà 1. ÂâåäåíèåÑ äðóãîé ñòîðîíû, ïîñòîÿííî ðàñòóùàÿ ïîòðåáíîñòü âíîâûõ êîìïèëÿòîðàõ ñâÿçàíà ñ áóðíûì ðàçâèòèåì àðõèòåêòóð ÝÂÌ. Ýòî ðàçâèòèå èä¼ò ïî ðàçëè÷íûì íàïðàâëåíèÿì. Íàðÿäó ñ âîçíèêíîâåíèåì íîâûõ àðõèòåêòóð, ñîâåðøåíñòâóþòñÿ ñòàðûå àðõèòåêòóðû êàê â êîíöåïòóàëüíîì îòíîøåíèè, òàê è ïî îòäåëüíûì, êîíêðåòíûì ïàðàìåòðàì. Ýòî ìîæíî ïîêàçàòü íà ïðèìåðå ìèêðîïðîöåññîðà Intel-80X86.
Ïîñëåäîâàòåëüíûå âåðñèè ýòîãî ìèêðîïðîöåññîðà 8086, 80186, 80286, 80386, 80486, 80586 îòëè÷àþòñÿ íå òîëüêî òåõíè÷åñêèìè õàðàêòåðèñòèêàìè, íî è, ÷òîáîëåå âàæíî, íîâûìè âîçìîæíîñòÿìè è, çíà÷èò, èçìåíåíèåì (ðàñøèðåíèåì) ñèñòåìû êîìàíä. Åñòåñòâåííî, ýòî òðåáóåò íîâûõ êîìïèëÿòîðîâ (èëè ìîäèôèêàöèè ñòàðûõ). Òî æåìîæíî ñêàçàòü î ìèêðîïðîöåññîðàõ Motorola 68010, 68020,68030, 68040. ðàìêàõ òðàäèöèîííûõ ïîñëåäîâàòåëüíûõ ìàøèí ðàçâèâàåòñÿ áîëüøîå ÷èñëî ðàçëè÷íûõ íàïðàâëåíèé àðõèòåêòóð.
Ïðèìåðàìè ìîãóò ñëóæèòü àðõèòåêòóðû CISC, RISC.Òàêèå âåäóùèå ôèðìû, êàê Intel, Motorola, Sun, íà÷èíàþò ïåðåõîäèòü íà âûïóñê ìàøèí ñ RISCàðõèòåêòóðàìè.Åñòåñòâåííî, äëÿ êàæäîé íîâîé ñèñòåìû êîìàíä òðåáóåòñÿ ïîëíûé íàáîð íîâûõ êîìïèëÿòîðîâ ñ ðàñïðîñòðàí¼ííûõÿçûêîâ.Íàêîíåö, áóðíî ðàçâèâàþòñÿ ðàçëè÷íûå ïàðàëëåëüíûåàðõèòåêòóðû. Ñðåäè íèõ îòìåòèì âåêòîðíûå, ìíîãîïðîöåññîðíûå, ñ øèðîêèì êîìàíäíûì ñëîâîì àðõèòåêòóðû (âàðèàíòîì êîòîðûõ ÿâëÿþòñÿ ñóïåðñêàëÿðíûå ÝÂÌ).
Íà ðûíêåóæå èìåþòñÿ äåñÿòêè òèïîâ ÝÂÌ ñ ïàðàëëåëüíîé àðõèòåêòóðîé, íà÷èíàÿ îò ñóïåð-ÝÂÌ (Cray, CDC è äðóãèå), ÷åðåç ðàáî÷èå ñòàíöèè (íàïðèìåð, IBM RS/6000) è êîí÷àÿïåðñîíàëüíûìè êîìïüþòåðàìè (íàïðèìåð, íà îñíîâå ìèêðîïðîöåññîðà I-860). Åñòåñòâåííî, äëÿ êàæäîé èç íîâûõìàøèí ñîçäàþòñÿ íîâûå êîìïèëÿòîðû äëÿ ìíîãèõ ÿçûêîâïðîãðàììèðîâàíèÿ.
Çäåñü íåîáõîäèìî òàêæå îòìåòèòü, ÷òîíîâûå àðõèòåêòóðû òðåáóþò ðàçðàáîòêè ñîâåðøåííî íîâûõïîäõîäîâ ê ñîçäàíèþ êîìïèëÿòîðîâ, òàê ÷òî íàðÿäó ñ ñîáñòâåííî ðàçðàáîòêîé êîìïèëÿòîðîâ âåä¼òñÿ è áîëüøàÿ íàó÷íàÿ ðàáîòà ïî ñîçäàíèþ íîâûõ ìåòîäîâ òðàíñëÿöèè.1.2. Ñòðóêòóðà êîìïèëÿòîðà111.2. Ñòðóêòóðà êîìïèëÿòîðàÎáîáù¼ííàÿ ñòðóêòóðà êîìïèëÿòîðà è îñíîâíûå ôàçûêîìïèëÿöèè ïîêàçàíû íà ðèñ. 1.1.Íà íà÷àëüíîé ôàçå ëåêñè÷åñêîãî àíàëèçà âõîäíàÿ ïðîãðàììà, ïðåäñòàâëÿþùàÿ ñîáîé ïîòîê ëèòåð, ðàçáèâàåòñÿíà ëåêñåìû ñëîâà â ñîîòâåòñòâèè ñ îïðåäåëåíèÿìè ÿçûêà.Îñíîâíûìè ôîðìàëèçìàìè, ëåæàùèì â îñíîâå ðåàëèçàöèèëåêñè÷åñêèõ àíàëèçàòîðîâ, ÿâëÿþòñÿ êîíå÷íûå àâòîìàòûè ðåãóëÿðíûå âûðàæåíèÿ. Ëåêñè÷åñêèé àíàëèçàòîð ìîæåòðàáîòàòü â äâóõ îñíîâíûõ ðåæèìàõ: ëèáî êàê ïîäïðîãðàììà, âûçûâàåìàÿ ñèíòàêñè÷åñêèì àíàëèçàòîðîì äëÿ ïîëó÷åíèÿ î÷åðåäíîé ëåêñåìû, ëèáî êàê ïîëíûé ïðîõîä, ðåçóëüòàòîì êîòîðîãî ÿâëÿåòñÿ ôàéë ëåêñåì. ïðîöåññå âûäåëåíèÿ ëåêñåì ëåêñè÷åñêèé àíàëèçàòîðìîæåò êàê ñàìîñòîÿòåëüíî ñòðîèòü òàáëèöû îáúåêòîâ (÷èñåë, ñòðîê, èäåíòèôèêàòîðîâ è òàê äàëåå), òàê è âûäàâàòüçíà÷åíèÿ äëÿ êàæäîé ëåêñåìû ïðè î÷åðåäíîì ê íåìó îáðàùåíèè.
 ýòîì ñëó÷àå òàáëèöû îáúåêòîâ ñòðîÿòñÿ â ïîñëåäóþùèõ ôàçàõ (íàïðèìåð, â ïðîöåññå ñèíòàêñè÷åñêîãîàíàëèçà).Íà ýòàïå ëåêñè÷åñêîãî àíàëèçà îáíàðóæèâàþòñÿ íåêîòîðûå (ïðîñòåéøèå) îøèáêè (íåäîïóñòèìûå ñèìâîëû, íåïðàâèëüíàÿ çàïèñü ÷èñåë, èäåíòèôèêàòîðîâ è äðóãèå).Öåíòðàëüíàÿ çàäà÷à ñèíòàêñè÷åñêîãî àíàëèçà ðàçáîðñòðóêòóðû ïðîãðàììû. Êàê ïðàâèëî, ïîä ñòðóêòóðîé ïîíèìàåòñÿ äåðåâî, ñîîòâåòñòâóþùåå ðàçáîðó â êîíòåêñòíîñâîáîäíîé ãðàììàòèêå ÿçûêà.  íàñòîÿùåå âðåìÿ ÷àùå âñåãî èñïîëüçóåòñÿ ëèáî LL(1)-àíàëèç (è åãî âàðèàíò ðåêóðñèâíûé ñïóñê), ëèáî LR(1)-àíàëèç è åãî âàðèàíòû (LR(0),SLR(1), LALR(1) è äðóãèå).
Ðåêóðñèâíûé ñïóñê ÷àùå èñïîëüçóåòñÿ ïðè ðó÷íîì ïðîãðàììèðîâàíèè ñèíòàêñè÷åñêîãîàíàëèçàòîðà, LR(1) ïðè èñïîëüçîâàíèè ñèñòåì àâòîìàòè÷åñêîãî ïîñòðîåíèÿ ñèíòàêñè÷åñêèõ àíàëèçàòîðîâ.Ðåçóëüòàòîì ñèíòàêñè÷åñêîãî àíàëèçà ÿâëÿåòñÿ ñèíòàêñè÷åñêîå äåðåâî ñî ññûëêàìè íà òàáëèöû îáúåêòîâ. Îøèáêè, ñâÿçàííûå ñî ñòðóêòóðîé ïðîãðàììû, òàêæå îáíàðóæèâàþòñÿ â ïðîöåññå ñèíòàêñè÷åñêîãî àíàëèçà.12Ãëàâà 1. ÂâåäåíèåÍà ýòàïå êîíòåêñòíîãî àíàëèçà âûÿâëÿþòñÿ çàâèñèìîñòè ìåæäó ÷àñòÿìè ïðîãðàììû, êîòîðûå íå ìîãóò áûòüîïèñàíû êîíòåêñòíî-ñâîáîäíûì ñèíòàêñèñîì.
Ýòî, â îñíîâíîì, ñâÿçè ¾îïèñàíèå-èñïîëüçîâàíèå¿, â ÷àñòíîñòè, àíàëèçòèïîâ îáúåêòîâ, àíàëèç îáëàñòåé âèäèìîñòè, ñîîòâåòñòâèåïàðàìåòðîâ, ìåòêè è äðóãèå.  ïðîöåññå êîíòåêñòíîãî àíàëèçà òàáëèöû îáúåêòîâ ïîïîëíÿþòñÿ èíôîðìàöèåé îá îïèñàíèÿõ (ñâîéñòâàõ) îáúåêòîâ.Îñíîâíûì ôîðìàëèçìîì, èñïîëüçóåìûì ïðè êîíòåêñòíîì àíàëèçå, ÿâëÿåòñÿ àïïàðàò àòðèáóòíûõ ãðàììàòèê.
Ðåçóëüòàòîì êîíòåêñòíîãî àíàëèçà ÿâëÿåòñÿ àòðèáóòèðîâàííîå äåðåâî ïðîãðàììû. Èíôîðìàöèÿ îá îáúåêòàõ ìîæåòáûòü êàê ðàññðåäîòî÷åíà â ñàìîì äåðåâå, òàê è ñîñðåäîòî÷åíà â îòäåëüíûõ òàáëèöàõ îáúåêòîâ.  ïðîöåññå êîíòåêñòíîãî àíàëèçà òàêæå ìîãóò áûòü îáíàðóæåíû îøèáêè, ñâÿçàííûå ñ íåïðàâèëüíûì èñïîëüçîâàíèåì îáúåêòîâ.Çàòåì ïðîãðàììà ìîæåò áûòü ïåðåâåäåíà âî âíóòðåííååïðåäñòàâëåíèå. Ýòî äåëàåòñÿ äëÿ öåëåé îïòèìèçàöèè è/èëèóäîáñòâà ãåíåðàöèè êîäà.
Åù¼ îäíîé öåëüþ ïðåîáðàçîâàíèÿïðîãðàììû âî âíóòðåííåå ïðåäñòàâëåíèå ÿâëÿåòñÿ æåëàíèå èìåòü ïåðåíîñèìûé êîìïèëÿòîð. Òîãäà òîëüêî ïîñëåäíÿÿ ôàçà (ãåíåðàöèÿ êîäà) ÿâëÿåòñÿ ìàøèííîçàâèñèìîé. Âêà÷åñòâå âíóòðåííåãî ïðåäñòàâëåíèÿ ìîæåò èñïîëüçîâàòüñÿ ïðåôèêñíàÿ èëè ïîñòôèêñíàÿ çàïèñü, îðèåíòèðîâàííûéãðàô, òðîéêè, ÷åòâ¼ðêè è äðóãèå ñïîñîáû.Ôàç îïòèìèçàöèè ìîæåò áûòü íåñêîëüêî. Îïòèìèçàöèèîáû÷íî äåëÿò íà ìàøèííî-çàâèñèìûå è ìàøèííî-íåçàâèñèìûå, ëîêàëüíûå è ãëîáàëüíûå. Îïðåäåë¼ííàÿ ÷àñòüìàøèííî-çàâèñèìîé îïòèìèçàöèè âûïîëíÿåòñÿ íà ôàçåãåíåðàöèè êîäà. Ãëîáàëüíàÿ îïòèìèçàöèÿ ïûòàåòñÿ ïðèíÿòü âî âíèìàíèå ñòðóêòóðó âñåé ïðîãðàììû, ëîêàëüíàÿ òîëüêî íåáîëüøèõ å¼ ôðàãìåíòîâ.
Ãëîáàëüíàÿ îïòèìèçàöèÿ îñíîâûâàåòñÿ íà ãëîáàëüíîì ïîòîêîâîì àíàëèçå,êîòîðûé âûïîëíÿåòñÿ íà ãðàôå ïðîãðàììû è ïðåäñòàâëÿåòïî ñóùåñòâó ïðåîáðàçîâàíèå ýòîãî ãðàôà. Ïðè ýòîì ìîãóòó÷èòûâàòüñÿ òàêèå ñâîéñòâà ïðîãðàììû, êàê ìåæïðîöåäóðíûé àíàëèç, ìåæìîäóëüíûé àíàëèç, àíàëèç îáëàñòåéæèçíè ïåðåìåííûõ è òàê äàëåå.1.2. Ñòðóêòóðà êîìïèëÿòîðà13Íàêîíåö, ãåíåðàöèÿ êîäà ïîñëåäíÿÿ ôàçà òðàíñëÿöèè.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
