Теория формальных языков программирования

В.А. Серебряков — Теория и реализация языков программирования

PDF-файл из архива «В.А. Серебряков — Теория и реализация языков программирования», который расположен в категории » «. Всё это находится в предмете «формальные языки и автоматы» из 6 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .

Просмотр PDF-файла онлайн

Текст из PDF

ОГЛАВЛЕНИЕПредисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Г л а в а 1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . .1.1. Место компилятора в программном обеспечении1.2. Структура компилятора . . . . . . . . . . . . . . . . . . .1.3. Реализация множеств и отображений в Java . . . 6. 77811Г л а в а 2. Языки и их представление . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.1. Алфавиты, цепочки и языки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.2. Представление языков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.3. Грамматики. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.3.1. Формальное определение грамматики (17). 2.3.2. Типы грамматик и их свойства (18).2.4. Машины Тьюринга . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.4.1. Неразрешимость проблемы останова (21). 2.4.2. Класс рекурсивных множеств (22).2.5. Связь машин Тьюринга и грамматик типа 0 . . . . . . . . . . . . . . . . . . . . .2.6. Линейно ограниченные автоматы и их связь с контекстно-зависимымиграмматиками . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .14141617Г л а в а 3. Лексический анализ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.1. Регулярные множества и выражения . . . . . . . . . . . . . . . . . . . . . . . . . .3.2. Конечные автоматы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.3. Интерпретатор НКА на Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.4. Алгоритмы построения конечных автоматов. . . . . . . . . . . . . . . . . . . . .3.4.1. Построение недетерминированного конечного автомата по регулярному выражению (41). 3.4.2. Построение детерминированного конечного автомата по недетерминированному (43). 3.4.3. Реализация наJava (44). 3.4.4. Обоснование (45). 3.4.5. Построение детерминированного конечного автомата по регулярному выражению (46). 3.4.6. Построение ДКА по РВ на Java (49). 3.4.7. Обоснование (49).3.5. Связь регулярных множеств, конечных автоматов и регулярных грамматик . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.5.1. Построение детерминированного конечного автомата с минимальным числом состояний (54). 3.5.2. Проверка эквивалентности регулярных языков (58). 3.5.3. Реализация на Java (61).3.6. Программирование лексического анализа . . . . . . . . . . . . . . . . . . . . . . .3.7. Конструктор лексических анализаторов LEX . . . . . . . . . . . . . . . . . . . .3335374041Г л а в а 4. Синтаксический анализ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4.1. Контекстно-свободные грамматики и автоматы с магазинной памятью4.2. Преобразования КС-грамматик . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4.3. Алгоритм Кока–Янгера–Касами. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4.4. Разбор сверху-вниз (предсказывающий разбор) . . . . . . . . . . . . . . . . . .4.4.1. Алгоритм разбора сверху-вниз (80). 4.4.2. Функции F IRSTи F OLLOW (83). 4.4.3. Конструирование таблицы предсказывающегоанализатора (87). 4.4.4. LL(k )-грамматики (87). 4.4.5. Удаление левой рекурсии (90). 4.4.6. Левая факторизация (91). 4.4.7. Рекурсивный спуск (92). 4.4.8. Конструктор LL(1)-анализаторов на Java (93).4.4.9. Восстановление процесса анализа после синтаксических ошибок (93).4.5. Разбор снизу-вверх типа сдвиг-свертка . . . . . . . . . . . . . . . . . . . . . . . .4.5.1. Основа (93). 4.5.2. LR(1)-анализаторы (95). 4.5.3. Конструирование LR(1)-таблицы (98). 4.5.4. Конструктор LR(1)-анализаторов2024275162667070788080934Оглавлениена Java (103). 4.5.5. Корректность построения (103). 4.5.6. LR(k )грамматики (106). 4.5.7. Восстановление процесса анализа после синтаксических ошибок (109). 4.5.8. Варианты LR-анализаторов (109).Г л а в а 5. Элементы теории перевода . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5.1. Преобразователи с магазинной памятью . . . . . . . . . . . . . . . . . . . . . . .5.2. Синтаксически управляемый перевод . . . . . . . . . . . . . . . . . . . . . . . . . .5.2.1. Схемы синтаксически управляемого перевода (112). 5.2.2. Обобщенные схемы синтаксически управляемого перевода (115).5.3. Атрибутные грамматики . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5.3.1. Определение атрибутных грамматик (117). 5.3.2. Классы атрибутных грамматик и их реализация (120). 5.3.3. Язык описания атрибутных грамматик (123).111111112117Г л а в а 6. Проверка контекстных условий . . . . . . . . . . . . . . . . . . . . . . . . . 1276.1. Описание областей видимости и блочной структуры . . . . . . . . . . . . . . 1276.2. Занесение в среду и поиск объектов . . . . . . . . . . . . . . . . . . . . . . . . . . 128Г л а в а 7. Организация таблиц символов . .7.1. Таблицы идентификаторов. . . . . . . . . .7.2. Таблицы расстановки . . . . . . . . . . . . .7.3. Таблицы расстановки со списками . . . .7.4. Функции расстановки . . . . . . . . . . . . .7.5. Таблицы на деревьях. . . . . . . . . . . . . .7.6. Реализация блочной структуры . . . . . .7.7. Сравнение методов реализации таблиц. Г л а в а 8. Промежуточное представление программы8.1. Представление в виде ориентированного графа . .8.2. Трехадресный код . . . . . . . . . . . . . . . . . . . . . . . .8.3. Линеаризованные представления . . . . . . . . . . . . .8.4. Виртуальная машина Java . . . . . . . . . . . . . . . . . .8.4.1. Организация памяти (156). 8.4.2. Набормашины (157).8.5. Организация информации в генераторе кода . . . .8.6. Уровень промежуточного представления . . . . . . . 137137139141143144148148. команд виртуальной149149150154156. . . . . . . . . . . . . . . . 159. . . . . . . . . . . . . . . . 160Г л а в а 9. Генерация кода . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9.1. Модель машины . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9.2. Динамическая организация памяти . . . . . . . . . . . . . . . . . . . . . . . . . . .9.2.1. Организация магазина со статической цепочкой (165). 9.2.2. Организация магазина с дисплеем (169).9.3. Назначение адресов. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9.4. Трансляция переменных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9.5. Трансляция целых выражений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9.6. Трансляция арифметических выражений . . . . . . . . . . . . . . . . . . . . . . .9.7. Трансляция логических выражений . . . . . . . . . . . . . . . . . . . . . . . . . . .9.8. Выделение общих подвыражений. . . . . . . . . . . . . . . . . . . . . . . . . . . . .9.9. Трансляция объектно-ориентированных свойств языков программирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9.9.1. Виртуальные базовые классы (194). 9.9.2. Множественное наследование (195). 9.9.3. Единичное наследование и виртуальные функции (196). 9.9.4. Множественное наследование и виртуальные функции (196). 9.9.5. Виртуальные базовые классы с виртуальными функциями (198).1611611641701711741751831901945Оглавление9.10. Генерация оптимального кода методами сопоставления образцов . . . . . 2009.10.1. Сопоставление образцов (200).9.10.2. Построение покрытия (203). 9.10.3. Выбор дерева вывода наименьшей стоимости (208).9.10.4. Синтаксический анализ для T-грамматик (209). 9.10.5. Атрибутная схема для алгоритма сопоставления образцов (210).Г л а в а 10. Системы автоматизации построения трансляторов . . . . . . . . . 21510.1. Система СУПЕР . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21510.2. Система YACC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217П р и л о ж е н и е . Классы атрибутных грамматик . . . . . . . . . .A.1. Атрибутированное дерево разбора . . . . . . . . . . . . . . . . . .A.2. Незацикленные атрибутные грамматики . . . . . . . . . . . . .A.3. Вычислительные последовательности и корректность.визита. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .A.4. Чистые многовизитные грамматики . . . . . . . . . . . . . . . . .A.5. Абсолютно незацикленные атрибутные грамматики . . . . .A.6. Простые многовизитные атрибутные грамматики . . . . . . .A.7. Одновизитные атрибутные грамматики . . . . . . . . . . . . . .A.8. Многопроходные грамматики. . . . . . . . . . . . . . . . . . . . . . Определение. 220220220222223224227228229Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234ПРЕДИСЛОВИЕПредлагаемая вниманию читателя книга основана на курсе лекций, прочитанных на факультете вычислительной математики и кибернетики МГУим. М.В. Ломоносова и на факультете управления и прикладной математикиМосковского физико-технического института. Диапазон вопросов, затронутых в книге, достаточно широк — от свойств формальных языков и до техники трансляции.

Источник

Теория формальных языков

Символом [math] \star [/math] помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.

Автоматы и регулярные языки

Регулярные языки и ДКА

НКА

Минимизация ДКА

Свойства конечных автоматов

Другие автоматы

• Локальные автоматы [math] ^\star [/math]
• Двусторонний детерминированный конечный автомат [math] ^\star [/math]
• Квантовые конечные автоматы [math] ^\star [/math]
• Автоматы Мура и Мили [math] ^\star [/math]
• Автоматы в современном мире [math] ^\star [/math]

Контекстно-свободные грамматики

Базовые понятия о грамматиках

Нормальные формы КС-грамматик

Алгоритмы разбора

Опровержение контекстно-свободности языка

МП-автоматы

• Автоматы с магазинной памятью
• МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность
• Совпадение множества языков МП-автоматов и контекстно-свободных языков
• Детерминированные автоматы с магазинной памятью
• Детерминированные автоматы с магазинной памятью, допуск по пустому стеку
• Нормальная форма ДМП-автомата [math] ^\star [/math]
• Эквивалентность ДМП-автоматов [math] ^\star [/math]
• Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами
• ДМП-автоматы и неоднозначность

Источник