Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 124
Текст из файла (страница 124)
Функция иньективная — всюду определенная (!о1а1) 21, 25 — действия (рагйпй асИоп) 426 — 428, 444 — 446 — доступа и памяти (распознавателя) (йоге) !!4 604 нкцня ниъектнвная (и!есИче) 22 общерекурснвная (1о|а! гесигь!че) 4! переходов (Во1о) 426 — 428, 444 — 446 переходов (состояний ажомата) (ь!а1е |гапйИоп) 135 преобразования памяти (распознавателя) (|е(сЬ) 114 рекурсивная (гесцгйче) 41 характеристическая (сбагас!епзИс) 48 частичная (рэгИа|) 22 частична рекурсивная (рагИа! гасить!че) 4! В РР 433, 444, 450 Р!ЯБТ 337, 375, 376, 396 399 Р01Л.ОТУ 383. 479 СОТО 438 — 441, 444 Цепочка (йг!пй) 27, 106 — выводимая (зеп1епба! 1апп) 106 — левовываднмая (|еН ьеп1епИа| 1апп) ! 67 — нрававывадимая (пВЬ| зеп|епИа! !оггп) !67, 459, 460, 469 — 47! — пустая (епр1у) 27 Цикл в графе (сус|е с|гсиИ) 54 — — грамматике см.
Грамматика беэ циклов Часть (рогИоп) — (левовыводимой цепочки) законченная (с!оьгд) 374 — незаконченная (ореп) 374 — (правовыводимой цепочки) замкнутая (с1оьеь() 42! — открытая (арен) 421 Эквивалентность (программ, автоматов, грамматик) (ейи|ча!епсе) 71, 147 †1, 154 в 156, !62 см, также Проблема эквивалентности Элемент перевода (!галь(вИоп е1епеп1) 246 — 248 Язык (!апйиайе) 28, 103, 104, !!б, 136, 195 см, ьплкже Множество — ассемблера (аслегпЬ|у) 82 — 88 — бссконтекстиый (сап|ех14гее) гм. Язык контенстно-свободный — детерминированный (бе!егпь!п(ьИс) 2! 1, 216, 229 — 231, 238, 241, 283, 384, 450, 501, 503, 522 — 525 — Дика (Рус1г) 239 — естественный (па1ига1) 72, 97, 98, 102, 3!7, 351 — контекстно-зависимый (соп1ех(-ьспь!Ичс) !11, 112, 117, 1!9 — 121, 237, 452 — контенстна-свободный (соп!ех14гее) Н1, 112 117, 1!9, !21, 237 — левых разборов (!еИ рагье) 307, 3! 1 — линейный (Инсат) 191, 237, 268 — 1.1.
376 — 1С(д) 402 †4 — Щл) 373 †4, 449, 450 — ЬВ(э) см. Язык детерминированный и Гй(й)-грамматика — неоднозначный (аьпЫВиоиь) 234 — 236, 238, 239, 241 — нисходяиьсго разбора с ограиичеаиымн возвратами (ЯНРОВ) (1ор доъп рагйпй 1эпниайе, ТРР1) 5!2 — 525, 528 — 530. 539 — 542 — — обобщенный (ОЯНРОВ) (Вепега(!шд, ОТРР1) 525 — 542 — ограниченнога коьпокста (Ьоипбеб соп1ех1) 505 507 — правого контекста (Ьоипбеб г!ВЬ! соп1ех!) 481 — 488, 503 — 507 605 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ ОГЛАВЛЕНИЕ ОТ РЕДАКТОРА ПЕРЕВОДА 5 ПРЕДИСЛОВИЕ 7 0.2.
Множества цепочек 26 0.2.1. Цепочки 27 0.2.2. Языки 28 0.2.3. Операции над языкамн 29 Упражнения 30 Язык однозначный (ппашЬ!Епоцз) 234, 240 см. также Грамматика однозначная — операторного предшествоваиия -(орега!ог ргесебепсе) 493 — 497, 503, 504. 507 — (1,1)-ОПК ((1,1)-Ьонпды(-г!Еййсоп1ех!) 484, 503 — правых разборов (г!ЕЬ! рагзе) 307, 311 — программирования (ргойгашш!пй) 42, 69 — 74, 373 см. лиагже Алгол, ПЛ/1, ПЛ 360, Фортран, Онобол — простота предшествоваиня (з!шр!с ргсссг!спсе) 455 — 463, 474 — 479, 549, 565 — расширяемый (ех!епз!Ые) 74, 75, 559 — 562 — регулярный (гейп1аг) см. Множества регулярное — существенно неоднозначный (!пйегеп! ашЬ!Ецопз) см.
Язык неоднозначный — Флойда — Эванса (Р!оуФЕчапз) 411, 497 — 502, 507, 5ГΠ— характеризующий (сЬагасщг!х!ЕЕ) 269 — 273, 282 ЯНРОВ см. Язык нисходящего раабора с ограни ееииымн возвратами ПРЕДВАРИТЕЛЬНЫЕ МАТЕМАТИЧЕСКИЕ СВЕДЕНИЯ 1! О.!. Основные понятия теории множеств !1 0.13. Множества 11 0.1.2. Операции над множествами 14 0.1.3.
Отношения 16 0.1.4. Замыкание отношений !8 0.1,5. Отношения порядка 20 0.1.6. Отображения 21 Упражнения 23 0.3. Некоторые понятия математической логики 31 0.3.1. Доказательства 3! 0.3.2. Доказательства индукцией 32 О 3 3, Логические связки ЗЗ Упражнения 35 Замечания по литературе 38 0 4. Алгоритмы (частичные н всюду определенные) 38 ОЗЬ!. Частичные алгоритмы 38 0.4.2. Алгоритмы 40 0.4.3: Рекурсивные фуикцна 41 ОМ.4. Задание алгоритмов 42 0.4.5. Проблемы 43 0.4.6.
Проблема соответствий Поста 47 Упражнения 48 Замечания па литературе 51 >ГЛАВЛЕННЕ 0.5. Некоторые понятия теории графов 52 ОЛ.1. Ориентированные графы 52 0.5.2. Ориентированные ациклические графы 54 0.5.3. Деревья 55 0.5.4. Упорядоченные графы 56 0.5.5. Иидукция по ацнклическому графу 58 0.5.6. Вложение частичного порядка в линейный 59 0.5.7, Представления деревьев 61 0.5.8.
Пути в графе 62 Упражнения 66 Замечания по литературе 68 ВВЕДЕНИЕ В КОМПИЯЯЦИ)О 69 1.1. Языки программирования 69 1.1.!. Задание языков программирования 69 1.!.2. Синтаксис и семантика 71 Замечания по литературе 74 1.2. Обзор процесса компиляции 75 !.2.1. Основные части компилятора 75 1.2.2.
Лексический анализ 76 1.2.3. Работа с таблицами 79 1.2.4. Синтаксический анализ 80 1.2.5. Генерации кода 82 1.2.6. Оптимизация кода 88 1.2.7. Анализ и исправление ошвбок 90 1.2.8. Резюме 9! Упражнения 92 Замечания по литературе 95 1.3. Другие приложения алгоритмов разбора и перевода 96 1,3.1. Естественные языки 97 1,3.2. Структурное описание образов 98 Замечания по литературе 102 ЭЛЕМЕНТЫ ТЕОРИИ ЯЗЫНОВ 103 2.!. Способы определения языков 103 2.1.1. Мотивировка 104 2. 1,2, Грамматики !05 2.1.3, Грамматики с ограничениями на правила 1!! 2.1.4. Распознаватели 112 Упражнения )16 Замечания по литературе 123 2.2.
Регулярные множества, нх распознавание н порождение !24 2.2.!. Регулярные множества н регулярные выражения 124 2,2.2, Регулярные множества и праволинейные грамматики 13! 2.2.3. Конечные автоматы 134 ОГЛАВЛЕНИЕ 2.24. Конечные автоматы и регулярные множества 14) 2.2.5. Резюме ! 53 Упражнения 143 Замечания по литературе 147 2.3. Свойства регулярных множестя 147 2.3.!. Минимизация конечных автоматов,!47 2.3.2. Лемма о разрастании для регулярных множеств !5! 2.3.3.
Свойства замкнутости регулярных множеств 152 2.3.4. Разрешимые проблемы, связанные с регулярнымн множествами 154 Упражнения 156 Замечания по литературе !62 2 4. Контекстно-свободные языки !63 2И.1. Деревья выводов 163 2.4.2. Преобразования КС-грамматик !68 2.4.3. Нормальная форма Хамского 176 2.4.4. Нормальная форма Грейбах !78 2.4.5. Другой метод преобразовании к нормальной форме Грейбах !84 Упражнения 188 Замечания по литературе !92 2.5. Автоматы с магазинной памятью 192 2.5.1, Основное определение 193 2.5.2.
Варианты МП-автоматов !98 2.5.3. Эквивалентность МП-автоматов и КС-грамматик 203 2.5.4. Детерминированные МП-автоматы 2!! Упражнения 217 Замечания по литературе 220 2.6. Свойства контекстно-свободных языков 220 2.6.!. Лемма Огдеиа 220 2.6.2. Свойства замкнутости класса КС-языков 227 2.6.3. Результаты о разрешимости 227 2.6кй Свойства детерминированных КС.явыкав 230 2.6.5. Неоднозначность 231 Упражнения 236 Замечання по литературе 24! ТЕОРИЯ ПЕРЕВОДА 242 3.1. Формализмы, используемые для определения перевода 242 3.1.1. Перевод и семантика 242 3.1.2. Схемы синтаксически управляемого перевода 246 3.!.3.
Конечные |~реобрззовзтели 254 3.!.4. Преобразователи с магазинной памятью 258 Упражнения 264 Замечании по литературе 268 ОГЛАВЛЕ НИП ОГЛАВЛЕНИЯ 5.2. 5.4.5. Резюме 502 Упражнении 505 Замечания по литературе 5Г0 610,. 3.2. Свойства синтаксически управляемых переводов 268 3.2.1, Характеризующие нзыкн 269 3.2.2. Свойства гростых СУ-переводов 273 3.2.3.
Иерархия СУ-переводов 274 Упражнения 28! Замечании по литературе 283 3.3. Лексический анализ 283 3.3.1. Язык расширенных регулярных выражений 284 3.3.2. Непрямой лексический анализ 286 3.3.3. Примой лексический анализ 290 3.3.4. Программное люделнрование конечных преобразователей 293 Угражиения 294 Замечания па литературе 295 3.4.
Синтаксический анализ 296 3.4.!. Определение разбора 296 3.4.2. Нисходящий разбор 297 3.4.3. Восходящий разбор 301 3.4.4. Сравнение нисходящего разбора с восходящим 304 3.4.5. Грамматическое покрытие 309 Упражнения 3!5 Замечания по литературе ОБЩИЕ МЕТОДЫ СИНТАКСИЧЕСКОГО АНАЛИЗА 316 4.1. Синтаксический анализ с возвратами 3!7 4.1.1. Моделирование МП.преобразователя 317 4.1.2. Неформальное описание нисходнщего разбора 321 4 1.3. Алгоритм нисходящего разбора 325 4.1.4. Временная и емкостиая сложность нисходящего анализатора 333 4.1.5. Восходящий разбор 338 Упражнения 344 Замечания по литературе 351 4.2. Табличные методы синтаксяческого анализа 352 4.2.1.
Алгоритм Кока — Яигсра — Касамн 352 4.2.2. Алгоритм Эрлн 358 Упражнения 369 Замечании по литературе 372 ОДНОПРОХОДНЫЙ СИНТАКСИЧЕСКИЙ АНАЛИЗ БЕЗ ВОЗВРАТОВ 373 5.1. 1.1.(й)-грамматики 374 5.1.1. Определение (.1(й) грамматики 374 5.1.2. Предсказывающие алгоритмы разбора 378 5.1.3, Следствия определения С(.(й)-гралзматики 382 5.1.4. Разбор длн (.Ц1)-грамматик 387 5.1.5. Разбор для СС(й)-грамматик 388 5;1.6. Проверка С(.(й)-условия 396 Упражнения 400 Замечания по литературе 408 Дополнение.
О л~етодах разбора „по текущему символу". В. Н. АгаФонов 408 Детерминированный восходящий синтаксический анализ 420 5,2.1, Разбор с помощью детермнвировзнного алгоритма типа „перенас — свертка" 420 5.2.2. (,К (й).грамматики 423 5.2.,3. Следствия определения 1.К (й)-грамматики 432 5.2.4. Проверка ~.Гт (й).условия 442 5.2.5. Детерминированные правые анализаторы для СЯ(й)-грамматик 443 5.2.6.
Реализация Щ/з). и СК(й).анализаторов 448 Упражнения 448 Замечания по литературе 452 5.3. Грамматики аредшествования 452 5.3.1. Формальное определение алгоритма типа „перенос — свертка" 452 5.3.2. Грамматики простого предшестаования 455 5.3.3. Грамматики расширенного предшествоваиия 463 5.3.4. Грамматики слабого предшествовання 469 Упражнения 477 Замечания по литературе 480 5.4. Другие классы грамматик, анализируемых методом „перенос †сверт" 481 5.4.1. Грамматики ограниченного правого контекста 48! 5гй2. Грамматики смешанной стратегии предшествования 488 5.4.3. Грамматики операторного предшествования 492 5.4.4.
Язык Флойда †Эван 497 АЛГОРИТМЫ РАЗБОРА С ОГРАНИЧЕННЫМИ ВОЗВРАТАМИ 511 Нисходящий разбор с ограпичепнымн возвратами 511 6.1.1. Язык нисходящего разбора с ограниченными вазари. тзчн 512 6.1.2. ЯНРОВ и детерминированные КС-языки 522 6.!.3. Обобщенный Я!!РОВ 525 6. !.4. Вречеаназ сложаасть ОЯНРОВ-языкав 530 6.!.б. Рсалязапня ОЯНРОВ-программ 533 Упражнения 539 Замечания по литературе 542 ОГЛАВЛЕНИЕ 6.2, Восходящий разбор с ограннченнымя возвратами 542 6.2,!.
Неканоиическнй разбор 542 6.2.2. Анализаторы с днумя магазинами 544 6.2.3. Отношения предшествовання Колмераузра 547 6.2.4. Проверка условий предшествования Колмераузра 549 Упражнения 556 Замечания по литературе 558 ПРяложение 559 Г1,!.
Синтаксис расширяемого языка 559 П.2. Синтаксис операторов языка Снобол 4 562 П.З. Синтаксис ПЛ 360 565 П.4. Схема синтаксически управляемого перевода для языка РАС 569 Список литературы 575 Указатель обозначений 590 Указатель лемм, теорем и алгоритмов 59! Именной указатель 593 Предметный указатель 596 УВАЖАЕМЫЙ ЧИТАТЕЛЫ Ваши замечания о содержании книги, ее оформлении, качестве перевода и другие просим присылать по адресу: !29620, Г»!осина, И-!!О, ГСП, 1-й Рижский пер., д. 2, издательство «Мир».
.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
