Карпов - Основы построения трансляторов (2005)

уО. Г. и р е тНМЧЕ И ТИНОЛОТИН ПРОП ДИМИРОМНИН М Травслацие, амнегнююв на стр|мтурс тесте. Твари» Н. лмеснага арра ме мви р ию еаю м. тущецалие гревммтнл Хамсаюе. Друпю мадеви евеентю ваылевг лювматы. цюмамтюю С рвасевнневе асигаеетам, саги гуетрн а Струлцра н свечение. Дереве самеда ютг санаев аамвнннюаатм вепнслмюн. дтрнбугнаю трюююмни. Дсусмыююниые ~рвммлпию В уииварселвныв рватюлнвющвв влпцтлаюи УДК б81.3.0б8 ББК 32.973.018 К2б Карпов Ю. Г.

Теория и технология программирования. Основы построения трансляторов. — СПб.: БХВ-Петербург, 2005. — 272 с.: ил, 1Я ВХ 5-94157-285-9 Рассмотрены формальные модели грамматик и языков, грамматики Хомского, методы синтаксического анализа формальных языков и приемы генерации кода в современных компиляторах. Особое внимание уделено постановке базовых проблем теории формальных языков, пониманию основных задач построения трансляторов. Приводится большое количество примеров и задач к каждой главе. Дая студентов и лреиодавптелей' технических вузов УДК 681.3.068 ББК 32.973.018 Группа подготовки издания: Рецензенты: Доктор технических наук, профессор, заведующий кафедрой, декан факультста Технической кибернетики СПбГПУ И.

Г. Чсрноруцкий Доктор технических наук, профессор, заведующий кафедрой СПбГУАП Е. А. Крук Лицензия ИД йа 02429 от 24.07.00. Подписано е печать 14 12.04. Формат 70х100'/1в. Печать офсетная. Усл. печ. л. 21,93. Тираж 3000 экз. Заказ Йа 3754 "БХВ-Петербург", 190005, Санкт-Петербург, Измайловский пр., 29.

Санитарно-эпидемиологическое заключение на продукцию йа 77.99.02,953.Д.006421.11.04 от 11.11.2004 г. выдано Федеральной службой по надзору в сфере защиты прав потребителей и благополучия человека. Отпечатано с готовых диапозитивов в ГУП "Типография "Наука" 199034, Санкт-Петербург, 9 линия, 12 © Карпов Ю Г, 2005 © Оформление, издательство "БХВ-Петербург", 2005 1БВХ 5-94157-285-9 Главный редактор Зам. главного редактора Зав. редакцией Редактор Компьютерная верстка Корректор Дизайн обложки Зав.

производством Екптеринп Кондуковп Людмилп Ерел~еевскпя Григорий допин Тптьянп Лаианп Ольги Сергиенко Зинаида Дмитриевп Йгоря Цырульниковп Ннколпй Тверских Содержание ведение.....................°..............°...............°....... ° .. ° .°... В ............................. 9 Глава 1. Синтаксически-ориентированная трансляция 1.1. Задача трансляции 1.1.1. Компиляторы, интерпретаторы, препроцессоры 1.2.

Трансляция, основанная на структуре текста 1.3. Теория Н. Хомского, 1.4. Заключение,.................................,...,............. Задачи к главе 1 .13 .14 .16 22 23 .24 Глава 2 е ЯЗыки и грамматики а ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° е ° ° ° ° ° ° ° 2.1. Языки. 2.2. Грамматики 2.3. Грамматики Хомского 2.3.1. Как грамматика порождает язык? 2.4. Примеры грамматик......,...,.......................................,..........

2.5. Иерархия грамматик Хомского, 2.5.1. Грамматики типа 0 2.5.2. Грамматики тигга 1 2.5.3. Грамматики типа 2 2.5.4. Грамматики типа 3 2.5.5. Вложение грамматик и языков для порождающих 2.6. Распознающие автоматы . 2.6.1. Машины Тьюринга 2.6.2. Линейно-ограниченные автоматы ...........,....,.............. 2.6.3.

Автоматы с магазинной памятью. 2.6.4. Конечные автоматы 2.7. Другие модели задания языков. 2.7, !. Нотация Бэкуса — Наура. 2.7.2. язык синтаксических диаграмм ....... 2.7.3. Грамматики с рассеянным контекстом. 30 32 36 56 59 грамматик Хомского....,..59 .60 .60 ....65 .65 .69 .69 .70 .72 .75 редисловие ............................................................................................

7 П Содержание ....77 ...78 ..82 ....87 ....91 ..... 9 1 .....94 .....96 .....97 .....97 100 ..102 102 ... 106 ... 109 ... 110 119 124 125 .. 128 .... 130 .... 1 3 1 ... 132 135 135 Глава 5. Нисходящие методы синтаксического анализа .........................°....153 154 157 .... 157 .... 159 2.7.4. Трансформационные грамматики. 2.7.5, Языки сетей Петри 2.8.

Заключение ....................., Задачи к главе 2 Глава 3. Структура и значение .. 3.1. Дерево вывода как основа семантических вычислений. 3.2. Атрибутные трансляции. 3.2.1. Семантические атрибуты 3.2.2. Синтезированные и унаследованные атрибуты 3.2.3. Корректность атрибутных грамматик ..... 3.3. Примеры атрибутных грамматик 3.3.1. Вычисление двоичных чисел 3.3.2, Координаты мобильного робота 3.4.

Двусмысленные грамматики 3.4.1. Грамматика операторов цикла языка Милан 3.4.2. Грамматика условных операторов. 3.5. Трансляция арифметических выражений. 3,5,1. Грамматики арифметических выражений.................. 3.5.2. Перевод арифметических выражений в ПОЛИЗ. 3.5.3. И нтерпретация арифметических выражений 3.5.4. Компиляция арифметических выражений 3.5.5.

Символьное дифференцирование,..... 3.6. Грамматика языка Милан 3.7. Заключение . Задачи к главе 3. Глава 4. Теория контекстно-свободных языков .... 4.1. Преобразования грамматик 4.1.1. Бесполезные продукции 4.1.2. в-свободные и неукорачивающие КС-грамматики . 4.1.3, Циклические символы. 4.1.4. Левая рекурсия .. 4.1.5. Факторизация грамматик ....,.............. 4.2.

Нормальные формы грамматик 4.2.1. Нормальная форма Хомского. 4.2.2. Нормальная форма Грейбах 4.3. Функции 1=1ЮТ и ГО!1 ОЧ~ 4.4. Алгоритмические проблемы 4,5. Синтаксический анализ КС-языков.. Задачи к главе 4. 5.1. Автоматные грамматики и конечные автоматы 5.2. Синтаксический и семантический анализ автоматных языков. 5.2.1. Синтаксический анализ при трансляции автоматных языков...... 5.2,2. Семантические операции при трансляции автоматных языков... .„135 ...

137 ... 138 139 140 .141 ... 141 142 143 . 146 „ 147 .. 151 Содержание .160 ... 160 ... 164 ... 165 .167 . 171 ... 173 Глава 6. Восходящие алгоритмы синтаксического анализа..........................207 24! ~44 244 251 251 257 ..... 260 .1. Алгоритм Эрли.

.". Алгоритм Кока — Янгера — Касами Задачи к главе 7........................................... ° ° ° ° ° ° .....261 261 ~.1. Плекс-грамматики. .......................... 267 Список литературы . ..........................269 Предметный указатель ................. 3.3. Пр!!мер!>! построения трс!нсляторов а!ггоматных языков. 5.3.1. Обработка потока телеграмм. 5.3.2.

Язык перечисления номеров страниц. 5.3.3. Римские числа.....................................................,.....„.......... 5.4. Лексический а!!'!лиз языков г!рогр !ммирования 5.4.1. Лексический анализ языка Милан. 5.5. я-граммат!!ки. 5.5.1. Синтаксические диаграммы ь-грамматик как скелеты распознающих алгоритмов . 5.6, Грам мати ки рекурсивного спуска.

5.7. Трансляция языка Милан методом рекурсивного спуска 5.7.1. Входной язык .. 5.7.2. Выходной язык 5.7.3. Компилятор 5.8. И41)-грамматики. э.9. Сем'!нти~!~ ские вычислени~! в нисходящих методах анализа. 5.! О, Пример транслятора рекурсивного спуска 5.11. Заключение ......................................................................,......... 3;!дачи к главе 5 б.1. Восстановление дерева вывода при синтаксическом анализе снизу вверх. б 2. Грамматики простого предшествования 6.3. ! К(К)-грамматики . 6.3.1. 1 К(0)-грамматики. 6.3.2. 1 К(! )-грамматики. 6.4.

Ы К(К)- и 1А! К(К)-грамматики 6.4,1. Я К(К)-анализ;!торы. 6.4.2. ! А1 К(1с)-анализаторы 6.5. 1 К(0)-, Я К(1)-, 1А1 К(1)- и 1 К(1)-анализаторы 6.6. Синтаксический анализ 1 К(К)-языков 6,7. Семантические вычисления при восходящем распознавании.

1.-атрибутная семантика 6.8. Заключение..................,......................,............ Задачи к главе 6 Глава 7. Универсальные методы синтаксического анализа Глава 8. Обобщения грамматик Хомского ............. .... 177 .!78 .185 ... 186 . 187 . 188 .!94 .!99 201 203 204 208 209 2!7 218 223 224 226 227 233 235 Предисловие Построение трансляторов является областью информатики, в которой глубокие теоретические результаты привели к решению важных практических проблем. Эта область объединяет идеи, методы и алгоритмы синтаксического и семантического анализа искусственных языков, а также огромный накопленный практический опыт техники и технологии разработки трансляторов для различных языков программирования высокого уровня для различных архитектур процессоров и разнообразных операционных систем.

Как и в любой другой сравнительно новой области науки, в области построения трансляторов не существует общепринятого мнения по вопросу о том, что должно быть представлено в базовом университетском курсе по этому предмету. Многие учебные пособия делают упор именно на практические и технологические аспекты этой области. В данном пособии изложена основная концепция трансляции — концепция синтаксически-ориентированной обработки предложений входного языка. Зта концепция состоит в том.

что выход транслятора формируется на основе структуры входного предложения. Понимание этой концепции помогает ясному осознанию задач и алгоритмов каждого функционального блока современных трансляторов, в какой бы технологии и какими бы средствами они ни создавались. Число основных идей, на которых базируется эта концепция, не так много. В их круг входят понятия и идеи формальных грамматик и формальных языков, а также идея семантических вычислений — связи "структуры со с.иыслоя" для символьных цепочек, приводящая к пониманию процедуры трансляции как отображению символьных цепочек на их значения на основе структуры„приписанной этим цепочкам.