В.А. Серебряков, М.П. Галочкин и др. - Теория и реализация языков программирования (2006) (1134633)
Текст из файла
Â.À.Ñåðåáðÿêîâ, Ì.Ï.Ãàëî÷êèí,Ä.Ð.Ãîí÷àð, Ì.Ã.ÔóðóãÿíÒåîðèÿ è ðåàëèçàöèÿÿçûêîâ ïðîãðàììèðîâàíèÿ'LJLW('LJLW'LJLW'LJLW('LJLW 'LJLW'LJLWÂòîðîå èçäàíèå, èñïðàâëåííîå è äîïîëíåííîå.Ðåêîìåíäîâàíî Ó÷åáíî-ìåòîäè÷åñêèì îáúåäèíåíèåìâûñøèõ ó÷åáíûõ çàâåäåíèé Ðîññèéñêîé Ôåäåðàöèè ïîîáðàçîâàíèþ â îáëàñòè ïðèêëàäíûõ ìàòåìàòèêè è ôèçèêèâ êà÷åñòâå ó÷åáíîãî ïîñîáèÿ ïî êóðñó òåîðèè è ðåàëèçàöèèÿçûêîâ ïðîãðàììèðîâàíèÿÌîñêâà, ÌÇ Ïðåññ, 2006ÓÄÊ 004.43ÁÁÊ 32.973.26-018.2C 28Ñåðèÿ ¾Åñòåñòâåííûå íàóêè. Ìàòåìàòèêà. Èíôîðìàòèêà¿Ðåäàêöèîííûé ñîâåò ñåðèè :Âåëèõîâ Å.Ï., Èâàííèêîâ Â.Ï., Êèíãñåï À.Ñ., Ëåâàíîâ Å.È.,Ëîáàíîâ À.È. (îòâ.
ñåêðåòàðü ñåðèè), Ðèçíè÷åíêî Ã.Þ.,Õîëîäîâ À.Ñ., Øàíàíèí À.À.Ðåöåíçåíòû :×ë.-êîðð. ÐÀÍ, ïðîô. Þ.À.Ôë¼ðîâ (ÂÖ ÐÀÍ)Êàôåäðà ñèñòåìíîãî ïðîãðàììèðîâàíèÿ ÂÌèÊ ÌÃÓÑåðåáðÿêîâ Â.À. è äð.C 28 Òåîðèÿ è ðåàëèçàöèÿ ÿçûêîâ ïðîãðàììèðîâàíèÿ:Ó÷åáíîå ïîñîáèå./ Â.À.Ñåðåáðÿêîâ, Ì.Ï.Ãàëî÷êèí, Ä.Ð.Ãîí÷àð,Ì.Ã.Ôóðóãÿí. - Ì.: ÌÇ Ïðåññ, 2006. - 352 ñ.: èë.ISBN 5-94073-094-9Íà îñíîâå ëåêöèé, ïðî÷èòàííûõ íà ÂÌèÊ ÌÃÓ èÔÓÏÌ ÌÔÒÈ â 19912004 ãã., èçëàãàþòñÿ îñíîâíûå ðàçäåëû òåîðèè ðàçðàáîòêè êîìïèëÿòîðîâ. Ðàññìàòðèâàþòñÿòàêèå ñðåäñòâà àâòîìàòèçàöèè ïðîöåññà ðàçðàáîòêè òðàíñëÿòîðîâ, êàê LEX, YACC, ÑÓÏÅÐ, ìåòîäû ãåíåðàöèè îïòèìàëüíîãî êîäà.
Âîñïîëíÿåòñÿ çíà÷èòåëüíûé (ñ 1991 ã.)ïðîáåë â ëèòåðàòóðå íà ðóññêîì ÿçûêå ïî äàííîé òåìå.Äëÿ ñòóäåíòîâ, àñïèðàíòîâ ïðîãðàììèñòñêèõ ñïåöèàëüíîñòåé è ïðîôåññèîíàëîâ - ïðîãðàììèñòîâ è ðàçðàáîò÷èêîâêîìïèëÿòîðîâ.ÓÄÊ 004.43ÁÁÊ 32.973.26-018.2ISBN 5-94073-094-9Êîìïüþòåðíàÿ â¼ðñòêà: Ãàëî÷êèí Ì.Ï., Ãîëóáåâ À.Â.,Ãîí÷àð Ä.Ð., Ëàóôåð Ê.Ì., Õàðèí Ê.Â.Èçäàòåëü: Ç.À. ÎòàðàøâèëèÎãëàâëåíèåÏðåäèñëîâèå81. Ââåäåíèå91.1. Ìåñòî êîìïèëÿòîðà â ïðîãðàììíîì îáåñïå÷åíèè . . . .
. . . . . . . . . . . . . . . . . . .1.2. Ñòðóêòóðà êîìïèëÿòîðà . . . . . . . . . . .2. ßçûêè è èõ ïðåäñòàâëåíèå2.1. Àëôàâèòû, öåïî÷êè è ÿçûêè . . . . . . . . .2.2. Ïðåäñòàâëåíèå ÿçûêîâ . . . . . . . . . . . .2.3. Ãðàììàòèêè . . . . .
. . . . . . . . . . . . .2.3.1. Ôîðìàëüíîå îïðåäåëåíèå ãðàììàòèêè2.3.2. Òèïû ãðàììàòèê è èõ ñâîéñòâà . . .2.4. Ìàøèíû Òüþðèíãà . . . . . . . . . . . . . .2.4.1. Íåðàçðåøèìîñòü ïðîáëåìû îñòàíîâà2.4.2. Êëàññ ðåêóðñèâíûõ ìíîæåñòâ . . . .2.5. Ñâÿçü ìàøèí Òüþðèíãà è ãðàììàòèê òèïà 02.6. Ëèíåéíî-îãðàíè÷åííûå àâòîìàòû è èõ ñâÿçüñ êîíòåêñòíî-çàâèñèìûìè ãðàììàòèêàìè . .3. Ëåêñè÷åñêèé àíàëèç3.1. Ðåãóëÿðíûå ìíîæåñòâà è âûðàæåíèÿ . . . .3.2. Êîíå÷íûå àâòîìàòû .
. . . . . . . . . . . . .3.3. Àëãîðèòìû ïîñòðîåíèÿ êîíå÷íûõ àâòîìàòîâ911151518202022293133353844465054Îãëàâëåíèå3.3.1. Ïîñòðîåíèåíåäåòåðìèíèðîâàííîãîêîíå÷íîãî àâòîìàòà ïî ðåãóëÿðíîìóâûðàæåíèþ . . . . . . . . . . . . . . .3.3.2. Ïîñòðîåíèå äåòåðìèíèðîâàííîãî êîíå÷íîãî àâòîìàòà ïî íåäåòåðìèíèðîâàííîìó . . .
. . . . . . . . . . . . . .3.3.3. Ïîñòðîåíèå äåòåðìèíèðîâàííîãî êîíå÷íîãî àâòîìàòà ïî ðåãóëÿðíîìó âûðàæåíèþ . . . . . . . . . . . . . . . .3.3.4. Ïîñòðîåíèå äåòåðìèíèðîâàííîãî êîíå÷íîãî àâòîìàòà ñ ìèíèìàëüíûì ÷èñëîì ñîñòîÿíèé . . . . . . . . . . . . .3.4. Ñâÿçü ðåãóëÿðíûõ ìíîæåñòâ, êîíå÷íûõ àâòîìàòîâ è ðåãóëÿðíûõ ãðàììàòèê . . . . . . .3.5. Ïðîãðàììèðîâàíèå ëåêñè÷åñêîãî àíàëèçà .3.6. Êîíñòðóêòîð ëåêñè÷åñêèõ àíàëèçàòîðîâ LEX4. Ñèíòàêñè÷åñêèé àíàëèç4.1.
Êîíòåêñòíîñâîáîäíûå ãðàììàòèêè è àâòîìàòû ñ ìàãàçèííîé ïàìÿòüþ . . . . . . . . .4.2. Ïðåîáðàçîâàíèÿ ÊÑ-ãðàììàòèê . . . . . . .4.2.1. Àëãîðèòì Êîêà-ßíãåðà-Êàñàìè . . .4.3. Ïðåäñêàçûâàþùèé ðàçáîð ñâåðõó-âíèç . . .4.3.1. Àëãîðèòì ðàçáîðà ñâåðõó-âíèç . . .4.3.2. Ôóíêöèè F IRST è F OLLOW . . . .4.3.3. Êîíñòðóèðîâàíèå òàáëèöû ïðåäñêàçûâàþùåãî àíàëèçàòîðà .
. . . . . . . .4.3.4. LL(1)-ãðàììàòèêè . . . . . . . . . . .4.4. LL(k)-ãðàììàòèêè . . . . . . . . . . . . . . .4.5. Ñëåäñòâèÿ îïðåäåëåíèÿ LL(k)-ãðàììàòèêè4.5.1. Óäàëåíèå ëåâîé ðåêóðñèè . . . . . .4.5.2. Ëåâàÿ ôàêòîðèçàöèÿ . . . . . . . . .4.5.3. Ðåêóðñèâíûé ñïóñê . . . . . . . . . .4.5.4. Âîññòàíîâëåíèå ïðîöåññà àíàëèçà ïîñëå ñèíòàêñè÷åñêèõ îøèáîê . .
. . .4.6. Ðàçáîð ñíèçó-ââåðõ òèïà ñäâèã-ñâ¼ðòêà . . .4.6.1. Îñíîâà . . . . . . . . . . . . . . . . .4.6.2. LR(1)-àíàëèçàòîðû . . . . . . . . . .354575963667075808089919292961011021041051061081091101111111134Îãëàâëåíèå4.6.3. Êîíñòðóèðîâàíèå LR(1)-òàáëèöû . .4.6.4. LR(1)-ãðàììàòèêè . .
. . . . . . . . .4.6.5. Âîññòàíîâëåíèå ïðîöåññà àíàëèçà ïîñëå ñèíòàêñè÷åñêèõ îøèáîê . . . . .4.6.6. Âàðèàíòû LR-àíàëèçàòîðîâ . . . . .5. Ýëåìåíòû òåîðèè ïåðåâîäà5.1. Ïðåîáðàçîâàòåëè ñ ìàãàçèííîé ïàìÿòüþ . .5.2. Ñèíòàêñè÷åñêè óïðàâëÿåìûé ïåðåâîä . . . .5.2.1. Ñõåìû ñèíòàêñè÷åñêè óïðàâëÿåìîãîïåðåâîäà .
. . . . . . . . . . . . . . .5.2.2. Îáîáù¼ííûå ñõåìû ñèíòàêñè÷åñêèóïðàâëÿåìîãî ïåðåâîäà . . . . . . . .5.3. Àòðèáóòíûå ãðàììàòèêè . . . . . . . . . . .5.3.1. Îïðåäåëåíèå àòðèáóòíûõ ãðàììàòèê5.3.2. Êëàññû àòðèáóòíûõ ãðàììàòèê è èõðåàëèçàöèÿ . . . . . . . . . . . . . . .5.3.3. ßçûê îïèñàíèÿ àòðèáóòíûõ ãðàììàòèê . . . . . . . . . . . . . . . .
. . .6. Ïðîâåðêà êîíòåêñòíûõ óñëîâèé6.1. Îïèñàíèå îáëàñòåé âèäèìîñòè è áëî÷íîéñòðóêòóðû . . . . . . . . . . . . . . . . . . .6.2. Çàíåñåíèå â ñðåäó è ïîèñê îáúåêòîâ . . . .7. Îðãàíèçàöèÿ òàáëèö ñèìâîëîâ7.1.7.2.7.3.7.4.7.5.7.6.7.7.Òàáëèöû èäåíòèôèêàòîðîâ . . . . . . .Òàáëèöû ðàññòàíîâêè . . . . . . . . . .Òàáëèöû ðàññòàíîâêè ñî ñïèñêàìè . .Ôóíêöèè ðàññòàíîâêè . . . . . . . . .
.Òàáëèöû íà äåðåâüÿõ . . . . . . . . . .Ðåàëèçàöèÿ áëî÷íîé ñòðóêòóðû . . . .Ñðàâíåíèå ìåòîäîâ ðåàëèçàöèè òàáëèö.....................8. Ïðîìåæóòî÷íîå ïðåäñòàâëåíèå ïðîãðàììû8.1. Ïðåäñòàâëåíèå â âèäå îðèåíòèðîâàííîãîãðàôà . . . . . . . . . . . . . . . . . . . . . .8.2. Òð¼õàäðåñíûé êîä . . . . . . . . . . . .
. . .118125129130132133134134138141141146149154154156165166168171173174179180182182183Îãëàâëåíèå8.3. Ëèíåàðèçîâàííûå ïðåäñòàâëåíèÿ . . . . . .8.4. Âèðòóàëüíàÿ ìàøèíà Java . . . . . . . . . .8.4.1. Îðãàíèçàöèÿ ïàìÿòè . . . . . . . . .8.4.2. Íàáîð êîìàíä âèðòóàëüíîé ìàøèíû8.5. Îðãàíèçàöèÿ èíôîðìàöèè â ãåíåðàòîðå êîäà8.6. Óðîâåíü ïðîìåæóòî÷íîãî ïðåäñòàâëåíèÿ .9. Ãåíåðàöèÿ êîäà9.1.
Ìîäåëü ìàøèíû . . . . . . . . . . . . . . . .9.2. Äèíàìè÷åñêàÿ îðãàíèçàöèÿ ïàìÿòè . . . . .9.2.1. Îðãàíèçàöèÿ ìàãàçèíà ñî ñòàòè÷åñêîéöåïî÷êîé . . . . . . . . . . . . . . . .9.2.2. Îðãàíèçàöèÿ ìàãàçèíà ñ äèñïëååì .9.3. Íàçíà÷åíèå àäðåñîâ . . . . . . . . . . . . .
.9.4. Òðàíñëÿöèÿ ïåðåìåííûõ . . . . . . . . . . .9.5. Òðàíñëÿöèÿ öåëûõ âûðàæåíèé . . . . . . .9.6. Òðàíñëÿöèÿ àðèôìåòè÷åñêèõ âûðàæåíèé .9.7. Òðàíñëÿöèÿ ëîãè÷åñêèõ âûðàæåíèé . . . .9.8. Âûäåëåíèå îáùèõ ïîäâûðàæåíèé . . . . . .9.9. Òðàíñëÿöèÿîáúåêòíî-îðèåíòèðîâàííûõñâîéñòâ ÿçûêîâ ïðîãðàììèðîâàíèÿ . . . . .9.9.1. Âèðòóàëüíûå áàçîâûå êëàññû .
. . .9.9.2. Ìíîæåñòâåííîå íàñëåäîâàíèå . . . .9.9.3. Åäèíè÷íîå íàñëåäîâàíèå è âèðòóàëüíûå ôóíêöèè . . . . . . . . . . . . . .9.9.4. Ìíîæåñòâåííîå íàñëåäîâàíèå è âèðòóàëüíûå ôóíêöèè . . . . . . . . . . . .9.9.5. Âèðòóàëüíûå áàçîâûå êëàññû ñ âèðòóàëüíûìè ôóíêöèÿìè . . . . . . . . .9.10. Ãåíåðàöèÿ îïòèìàëüíîãî êîäà ìåòîäàìè ñèíòàêñè÷åñêîãî àíàëèçà . . .
. . . . . . . . . .9.10.1. Ñîïîñòàâëåíèå îáðàçöîâ . . . . . . .9.10.2. Ñèíòàêñè÷åñêèé àíàëèç äëÿ T-ãðàììàòèê . . . . . . . . . . . . . . . . . .9.10.3. Âûáîð äåðåâà âûâîäà íàèìåíüøåé ñòîèìîñòè . . . . . . . . . . . . . . . . .9.10.4. Àòðèáóòíàÿ ñõåìà äëÿ àëãîðèòìà ñîïîñòàâëåíèÿ îáðàçöîâ . . . . . . . . .51881911911921951961971982022032082092112152162262362412412422442452472502502552612646Îãëàâëåíèå10.Ñèñòåìû àâòîìàòèçàöèè ïîñòðîåíèÿ òðàíñëÿòîðîâ26910.1. Ñèñòåìà ÑÓÏÅÐ . .
. . . . . . . . . . . . . .10.2. Ñèñòåìà YACC . . . . . . . . . . . . . . . .A. Ñåìàíòèêà êîíòåêñòíî-ñâîáîäíûõ ÿçûêîâA.1.A.2.A.3.A.4.A.5.Ââåäåíèå . . . . . . . . . . . . . .Ôîðìàëüíûå ñâîéñòâà . . . . . . .Ïðîâåðêà íà çàöèêëåííîñòü . . .Ïðîñòîé ÿçûê ïðîãðàììèðîâàíèÿÎáñóæäåíèå . . . . . . . . . . . ...............................B. Àòðèáóòíûå ãðàììàòèêèB.1.B.2.B.3.B.4.B.5.Ââåäåíèå . . .
. . . . . . . . . . . . . . . . .Îïðåäåëåíèå àòðèáóòíûõ ãðàììàòèê . . . .Àòðèáóòèðîâàííîå äåðåâî ðàçáîðà . . . . .Íåçàöèêëåííûå àòðèáóòíûå ãðàììàòèêè . .Âû÷èñëèòåëüíûå ïîñëåäîâàòåëüíîñòè è êîððåêòíîñòü. Îïðåäåëåíèå âèçèòà . . . . . . .B.6. ×èñòûå ìíîãîâèçèòíûå ãðàììàòèêè . . . .B.7. Àáñîëþòíî íåçàöèêëåííûå àòðèáóòíûå ãðàììàòèêè . . . . . .
. . . . . . . . . . . . . . .B.8. Ïðîñòûå ìíîãîâèçèòíûå àòðèáóòíûå ãðàììàòèêè . . . . . . . . . . . . . . . . . . . . . . .B.9. Îäíîâèçèòíûå àòðèáóòíûå ãðàììàòèêè . .B.10.Ìíîãîïðîõîäíûå ãðàììàòèêè . . . . . . . .C. Çàäà÷è ïî ðàçäåëàì êíèãèC.2. ßçûêè è èõ ïðåäñòàâëåíèå . . .
. . . . . . .C.2.1. Àëôàâèòû, öåïî÷êè è ÿçûêè . . . .C.2.2. Ïðåäñòàâëåíèå ÿçûêîâ . . . . . . . .C.2.3. Ãðàììàòèêè . . . . . . . . . . . . . .C.3. Ëåêñè÷åñêèé àíàëèç . . . . . . . . . . . . . .C.3.1. Ðåãóëÿðíûå ìíîæåñòâà è âûðàæåíèÿC.3.2. Êîíå÷íûå àâòîìàòû . . . . . . . . . .C.3.3. Àëãîðèòìû ïîñòðîåíèÿ êîíå÷íûõ àâòîìàòîâ . . . . . . . .
. . . . . . . . .270272276277282287292301307307308309310311313315319320321329329329329330335335337338ÎãëàâëåíèåC.3.4. Ðåãóëÿðíûå ìíîæåñòâà è èõ ïðåäñòàâëåíèÿ . . . . . . . . . . . . . . . . . .C.3.5. Àëãåáðàè÷åñêèå ñâîéñòâà ðåãóëÿðíûõìíîæåñòâ. Ëåììà î ðàçðàñòàíèè. . .C.4. Ñèíòàêñè÷åñêèé àíàëèç .
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
