Глава 11. Контекстно-свободные языки 418

Распознаватели КС-языков. Автоматы с магазинной памятью 418

Определение МП-автомата 418

Эквивалентность языков МП-автоматов и КС-грамматик 420

Детерминированные МП-автоматы 423

Свойства КС-языков 423

Свойства произвольных КС-языков 423

Свойства детерминированных КС-языков 424

Лемма о разрастании КС-языков 425

Преобразование КС-грамматик. Приведенные грамматики . . . 426

Преобразование грамматик. Цель преобразования 426

Приведенные грамматики 427

Удаление недостижимых символов . 427

Удаление бесплодных символов 427

Устранение Х-правил 429

Устранение цепных правил 431

КС-грамматики в нормальной форме 433

Грамматики в нормальной форме Хомского 433

Устранение левой рекурсии. Грамматики в нормальной форме Грейбах . . 437

Распознаватели КС-языков с возвратом 441

Принципы работы распознавателей с возвратом 441

Нисходящий распознаватель с возвратом . , . . . 443

Распознаватель на основе алгоритма «сдвиг-свертка» 449

Табличные распознаватели для КС-языков . 455

Общие принципы работы табличных распознавателей 455

Алгоритм Кока—Янгера—Касами 456

Алгоритм Эрли (основные принципы) 457

Принципы построения распознавателей КС-языков без возвратов 458

Контрольные вопросы и задачи . . 460

Вопросы 460

Задачи 461

Глава 12. Классы кс-языков и грамматик . . . 463

Нисходящие распознаватели КС-языков без возвратов 463

Левосторонний разбор по методу рекурсивного спуска 463

Определение ЩК)-грамматики 471

Принципы построения распознавателей для Щ!<)-грамматик 474

Алгоритм разбора для Щ1)-грамматик 475

Восходящие распознаватели КС-языков без возвратов 486

Определение ЬН(К)-грамматики 486

Принципы построения распознавателей для 1В(К)-грамматик 489

Грамматики предшествования (основные принципы) 497

Грамматики простого предшествования 498

Грамматики операторного предшествования 508

Соотношение классов КС-языков и КС-грамматик 519

Особенности восходящих и нисходящих распознавателей 519

Отношения между классами КС-грамматик 521

Отношения между классами КС-языков 524

Контрольные вопросы и задачи 525

Вопросы . 525

Задачи . 527

Глава 13. Основные принципы построения трансляторов 529

Трансляторы, компиляторы и интерпретаторы — общая схема работы 529

Определение транслятора, компилятора, интерпретатора 529

Этапы трансляции. Общая схема работы транслятора 535

Понятие прохода. Многопроходные и однопроходные компиляторы 538

Интерпретаторы. Особенности построения интерпретаторов 540

Трансляторы с языка ассемблера («ассемблеры») 542

Таблицы идентификаторов. Организация таблиц идентификаторов 548

Назначение и особенности построения таблиц идентификаторов 548

Простейшие методы построения таблиц идентификаторов 550

Построение таблиц идентификаторов по методу бинарного дерева 551

Хэш-функции и хэш-адресация . 554

Комбинированные способы построения таблиц идентификаторов ..... 563

Лексические анализаторы (сканеры). Принципы построения сканеров 564

Назначение лексического анализатора 564

Принципы построения лексических анализаторов 568

Построение лексических анализаторов 570

Автоматизация построения лексических анализаторов

(программа LEX) 576

Синтаксические анализаторы. Синтаксически управляемый перевод 577

Основные принципы работы синтаксического анализатора 577

Дерево разбора. Преобразование дерева разбора в дерево операций . . . 579 Автоматизация построения синтаксических анализаторов

(программа YACC) 582

Контрольные вопросы и задачи 583

Вопросы 583

Задачи 585