А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 2
Текст из файла (страница 2)
Синтаксический анализ 251 252 252 253 254 256 258 4.1 4.2 258 260 261 263 265 266 267 269 272 273 273 275 278 279 280 281 283 285 288 292 4.3 4.4 295 298 301 302 302 304 306 309 4.5 Введение 4.1.1 Роль синтаксического анализатора 4.1.2 Образцы грамматик 4.1.3 Обработка синтаксических ошибок 4.1.4 Стратегии восстановления после ошибок Контекстно-свободные грамматики 4.2.1 Формальное определение контекстно-свободной грамматики 4.2.2 Соглашения об обозначениях 4.2.3 Порождения 4.2.4 Деревья разбора и порождения 4.2.5 Неоднозначность 4.2.6 Проверка языка, сгенерированного грамматикой 4.2.7 Контекстно-свободные грамматики и регулярные выражения 4.2.8 Упражнения к разделу 4.2 Разработка грамматики 4.3.1 Лексический и синтаксический анализ 4.3.2 Устранение неоднозначности 4.3.3 Устранение левой рекурсии 4.3.4 Левая факторизация 4.3.5 Не контекстно-свободные языковые конструкции 4.3.6 Упражнения к разделу 4.3 Нисходящий синтаксический анализ 4.4.1 Синтаксический анализ методом рекурсивного спуска 4.4.2 Р1КБТ и Р01Л 0% 4.4.3 1.Ь(1)-грамматики 4.4.4 Нерекурсивный предиктивный синтаксический анализ 4.4.5 Восстановление после ошибок в предиктивном синтаксическом анализе 4.4.6 Упражнения к разделу 4.4 Восходящий синтаксический анализ 4.5.1 Свертки 4.5.2 Обрезка основ 4.5.3 Синтаксический анализ "перенос/свертка" 4.5.4 Конфликты в процессе ПС-анализа 4.5.5 Упражнения к разделу 4.5 Содержание 4.7 353 357 358 361 363 364 368 371 372 375 375 378 4.
10 4.1 1 383 384 384 387 390 391 391 393 394 394 5.1 5.2 Введение в 1.К-анализ: простой ЬК 4.6.1 Обоснование использования 1.К-анализаторов 4.6.2 Пункты и 1.К(0)-автомат 4.6.3 Алгоритм 1.К-анализа 4.6.4 Построение таблиц БЬК-анализа 4.6.5 Активные префиксы 4.6.6 Упражнения к разделу 4.6 Более мощные ЬК-анализаторы 4.7.! Канонические 1.К(1)-пункты 4.7.2 Построение множеств 1.К(1)-пунктов 4.7.3 Канонические таблицы 1.К(1)-анализа 4.7.4 Построение 1.А1.К-таблиц синтаксического анализа 4.7.5 Эффективное построение таблиц 1.А1.К-анализа 4.7.6 Уплотнение таблиц ЬК-анализа 4.7.7 Упражнения к разделу 4.7 Использование неоднозначных грамматик 4.8.! Использование приоритетов и ассоциативности для разрешения конфликтов 4.8.2 Неоднозначность "висящего е1зе" 4.8.3 Восстановление после ошибок в 1.К-анализе 4.8.4 Упражнения к разделу 4.8 Генераторы синтаксических анализаторов 4.9.1 Генератор синтаксических анализаторов хасс 4.9.2 Использование Хасс с неоднозначной грамматикой 4.9.3 Создание лексического анализатора в х асс с помощью 1,ех 4.9.4 Восстановление после ошибок в хасс 4.9.5 Упражнения к разделу 4.9 Резюме к главе 4 Список литературы к главе 4 Глава 5.
Синтаксически управляемая трансляция Синтаксически управляемые определения 5.1.1 Наследуемые и синтезируемые атрибуты 5.!.2 Вычисление СУО в узлах дерева разбора 5.!.3 Упражнения к разделу 5.1 Порядок вычисления в СУО 5.2.1 Графы зависимостей 5.2.2 Упорядочение вычисления атрибутов 5.2.3 8-атрибутные определения 5.2.4 Ь-атрибутные определения 309 310 311 317 322 326 328 330 33! 332 336 338 344 349 352 353 12 Содержание 396 398 399 400 404 406 406 407 5.3 5.4 407 410 411 414 421 422 5.5 423 425 428 434 439 439 44! 5.6 5.7 Глава 6. Генерация промежуточного кода 443 445 445 6.1 Варианты синтаксических деревьев 6.1.1 Ориентированные ациклические графы для выражений 6.1.2 Метод номера значения для построения ориентированных ациклических графов 6.1.3 Упражнения к разделу 6.1 Трехадресный код 6.2.! Адреса и команды 6.2.2 Четверки 6.2.3 Тройки 6.2.4 Представление в виде статических единственных присваиваний 6.2.5 Упражнения к разделу 6.2 Типы н объявления 6.3.! Выражения типов 6.3.2 Эквивалентность типов 447 450 450 450 454 455 6.2 457 458 459 459 461 6.3 5.2.5 Семантические правила с контролируемыми побочными действиями 5.2.6 Упражнения к разделу 5.2 Применения синтаксически управляемой трансляции 5.3.1 Построение синтаксических деревьев 5.3.2 Структура типа 5.3.3 Упражнения к разделу 5.3 Синтаксически управляемые схемы трансляции 5.4.1 Постфиксные схемы трансляции 5.4.2 Реализация постфиксной СУТ с использованием стека синтаксического анализатора 5.4.3 СУТ с действиями внутри продукций 5.4.4 Устранение левой рекурсии из СУТ 5.4.5 СУТ для Ь-атрибутных определений 5.4.6 Упражнения к разделу 5.4 Реализация 1.-атрибутных СУО 5.5.! Трансляция в процессе синтаксического анализа методом рекурсивного спуска 5.5.2 Генерация кода "на лету" 5.5.3 Ь-атрибутные СУО и ЬЬ-синтаксический анализ 5.5.4 Восходящий синтаксический анализ 1.-атрибутных СУО 5.5.5 Упражнения к разделу 5.5 Резюме к главе 5 Список литературы к главе 5 Содержание 6.4 6.5 6.6 496 499 501 502 504 6.7 504 505 508 511 512 514 514 6.8 515 517 517 6.9 6.3.3 Объявления 6.3.4 Размещение локальных имен в памяти 6.3.5 Последовательности обьявлений 6.3.6 Поля в записях и классах 6.3.7 Упражнения к разделу 6.3 Трансляция выражений 6.4.1 Операции в выражениях 6.4.2 Инкрементная трансляция 6.4.3 Адресация элементов массива 6.4.4 Трансляция обращений к массиву 6.4.5 Упражнения к разделу 6.4 Проверка типов 6.5.1 Правила проверки типов 6.5.2 Преобразования типов 6.5.3 Перегрузка функций и операторов 6.5.4 Выведение типа и полиморфные функции 6.5.5 Алгоритм унификации 6.5.6 Упражнения к разделу 6.5 Поток управления 6.6.1 Булевы выражения 6.6.2 Код сокращенного вычисления 6.6.3 Инструкции потока управления 6.6.4 Трансляция логических выражений с помощью потока управления 6.6.5 Устранение излишних команд перехода 6.6.6 Булевы значения и код с переходами 6.6.7 Упражнения к разделу 6.6 Обратные поправки 6.7.1 Однопроходная генерация кода с использованием обратных поправок 6.7.2 Обратные поправки для булевых выражений 6.7.3 Инструкции потока управления 6.7.4 Инструкции Ьгеа1с, сопйпне и 8о1о 6.7.5 Упражнения к разделу 6.7 Инструкции выбора 6.8.1 Трансляция инструкций выбора 6.8.2 Синтаксически управляемая трансляция инструкций выбора 6.8.3 Упражнения к разделу 6.8 Промежуточный код процедур 462 462 464 466 467 468 468 470 471 473 475 477 477 478 481 482 487 490 491 492 492 493 14 Содержание Резюме к главе 6 Список литературы к главе 6 520 521 6.10 6.1 1 Глава 7.1 7.2 7.3 7.4 7.5 7.6 7.
Среды времени выполнении Организация памяти 7.1.1 Статическое и динамическое распределение памяти Выделение памяти в стеке 7.2.1 Деревья активации 7.2.2 Записи активации 7.2.3 Последовательности вызовов 7.2.4 Данные переменной длины в стеке 7.2,5 Упражнения к разделу 7.2 Доступ к нелокальным данным в стеке 7.3.1 Доступ к данным при отсутствии вложенных процедур 7.3.2 Вложенные процедуры 7.3.3 Язык с вложенными объявлениями процедур 7.3.4 Глубина вложенности 7.3.5 Связи доступа 7.3.6 Работа со связями доступа 7.3.7 Связи доступа для процедур, являющихся параметрами 7.3.8 Дисплеи 7.3.9 Упражнения к разделу 7.3 Управление кучей 7.4.1 Диспетчер памяти 7.4.2 Иерархия памяти компьютера 7.4.3 Локальность в программах 7,4.4 Снижение фрагментации 7.4.5 Освобождение памяти вручную 7.4.6 Упражнения к разделу 7.4 Введение в сборку мусора 7.5.! Цели проектирования сборщиков мусора 7.5.2 Достижимость 7.5.3 Сборщики мусора с подсчетом ссылок 7.5.4 Упражнения к разделу 7.5 Введение в сборку на основе отслеживания 7.6.1 Базовый сборщик мусора 7.6.2 Базовая абстракция 7.6.3 Оптимизация алгоритма "пометить и подмести" 7.6.4 Сборщики мусора "пометить и сжать" 7.6.5 Копирующие сборщики 7.6.6 Сравнение стоимости 525 525 527 528 529 532 535 539 540 542 542 543 544 545 547 548 550 55! 554 555 555 557 559 56! 565 568 568 569 572 574 576 576 577 580 582 583 587 589 15 Содержание 590 591 591 593 596 597 599 603 604 605 608 7.7 608 609 610 611 614 7.9 7.10 Глава 8.
Генерация кода 8.1 8.2 8.3 8.4 7.6.7 Упражнения к разделу 7.6 Распределенная сборка мусора 7.7.1 Инкрементная сборка мусора 7.7.2 Инкрементный анализ достижимости 7.7.3 Основы частичной сборки 7.7.4 Сборка мусора по поколениям 7.7.5 Алгоритм поезда 7.7.6 Упражнения к разделу 7.7 Дополнительные вопросы сборки мусора 7.8.1 Параллельная сборка мусора 7.8.2 Частичное перемещение объектов 7.8.3 Консервативная сборка мусора для небезопасных языюв программирования 7.8.4 Слабые ссылки 7.8.5 Упражнения к разделу 7.8 Резюме к главе 7 Список литературы к главе 7 Вопросы проектирования генератора кода 8.1.1 Вход генератора кода 8.1.2 Целевая программа 8.1.3 Выбор юманд 8.1.4 Распределение регистров 8.1.5 Порядок вычислений Целевой язык 8.2.1 Простая модель целевой машины 8.2.2 Стоимость программ и команд 8.2.3 Упражнения к разделу 8.2 Адреса в целевом коде 8.3.1 Статическое выделение памяти 8.3.2 Выделение памяти в стеке 8.3.3 Адреса имен времени выполнения 8.3.4 Упражнения к разделу 8.3 Базовые блоки и графы потоков 8.4.1 Базовые блоки 8.4.2 Информация о дальнейшем использовании 8.4.3 Графы потоков 8.4.4 Представление графов потоков 8.4.5 Циклы 8.4.6 Упражнения к разделу 8.4 617 619 619 620 621 623 625 625 625 629 630 632 632 635 638 639 640 641 643 644 646 646 647 16 Содержание 8.5 648 648 649 651 652 653 655 8.6 8.7 8.8 8.9 684 685 686 688 688 689 8.10 690 Оптимизация базовых блоков 8.5.1 Представление базовых блоков с использованием ориентированных ациклических графов Поиск локальных общих подвыражений Устранение неиспользуемого кода Применение алгебраических тождеств Представление обращений к массивам Присваивание указателей и вызовы процедур Сборка базового блока из ориентированного ациклического графа 8.5.8 Упражнения к разделу 8.5 Простой генератор кода 8.6.1 Дескрипторы регистров и адресов 8.6.2 Алгоритм генерации кода 8.6.3 Разработка функции деИед 8.6.4 Упражнения к разделу 8.6 Локальная оптимизация 8.7.1 Устранение излишних загрузок и сохранений 8.7.2 Устранение недостижимого кода 8.7.3 Оптимизация потока управления 8.7.4 Алгебраические упрощения и снижение стоимости 8.7.5 Использование машинных идиом 8.7.6 Упражнения к разделу 8.7 Распределение и назначение регистров 8.8.1 Глобальное распределение регистров 8.8.2 Счетчики использований 8.8.3 Назначение регистров для внешних циклов 8.8.4 Распределение регистров путем раскраски графа 8.8.5 Упражнения к разделу 8.8 Выбор команд путем переписывания дерева 8.9.1 Схемы трансляции деревьев 8.9.2 Генерация кода путем замощения входного дерева 8.9.3 Поиск соответствий с использованием синтаксического анализа 8.9.4 Программы семантической проверки 8.9.5 Обобщенный поиск соответствий 8.9.6 Упражнения к разделу 8.9 Генерация оптимального кода для выражений 8.10.1 Числа Ершова 8.10.2 Генерация кода на основе помеченных деревьев выражений 656 658 660 661 661 665 667 668 668 669 670 671 671 671 672 672 673 676 676 677 677 678 681 17 Содержание 692 694 8.! 1 8.12 8.13 695 696 697 700 700 702 Глава 9.1 9.4 761 762 8.10.3 Вычисление выражений при недостаточном количестве регистров 8.10.4 Упражнения к разделу 8.10 Генерация кода с использованием динамического программирования 8.11.1 Последовательные вычисления 8.11.2 Алгоритм динамического программирования 8.11.3 Упражнения к разделу 8.11 Резюме к главе 8 Список литературы к главе 8 9.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
