Трансляция формальных языков, Курс лекций, Сергеенко С.В., 2023

Трансляция формальных языков, Курс лекций, Сергеенко С.В., 2023.

   В данном учебном издании излагаются вопросы трансляции формальных языков: фазы трансляции, построение ДКА, синтаксический и контекстный анализ, генерация промежуточного представления и целевого кода, оптимизация.
Предназначается для студентов специальностей «Прикладная информатика (веб-программирование и компьютерный дизайн)» (дисциплина «Теория автоматов и формальных языков»), «Программное обеспечение информационных технологий» (дисциплина «Низкоуровневое программирование и трансляторы»).




Трансляторы, интерпретаторы, компиляторы.
Программы, написанные на языках программирования высокого уровня (или проблемно-ориентированных языках), перед выполнением на ЭВМ должны транслироваться в эквивалентные программы, написанные в машинном коде. Языки высокого уровня появились в середине 50-х годов, примерами первых таких языков могут служить Фортран и Кобол, а примерами недавно созданных - Алгол 68. Паскаль и Ада. Программа, которая транслирует любую программу, написанную на конкретном языке высокого уровня, в эквивалентную программу на другом языке (обычно это код машины). называется компилятором. Компилирование программы включает анализ - определение предусмотренного результата действия программы и последующий синтез - генерирование эквивалентной программы в машинном коде. В процессе анализа компилятор должен выяснить, является ли входная программа недействительной в каком-либо смысле (т.е. принадлежит ли она к языку, для которого написан данный компилятор), и если она окажется недействительной. - выдать соответствующее сообщение программисту. Этот аспект компиляции называется обнаружением ошибок.

В построении компиляторов достигнуты значительные успехи. Первые компиляторы использовали специальные методы, были медленными и не носили структурного характера. В современных компиляторах применяются более системные методы: эти компиляторы относительно быстрые и строятся таким образом, чтобы как можно более четко выделять отдельные аспекты компиляции.

ОГЛАВЛЕНИЕ.
Введение.
1. Основные понятия теории автоматов и формальных языков.
1.1. Алфавит, цепочки символов и операции над ними.
1.2. Формальный язык. Операции над формальными языками.
1.3. Представление языков. Способы описания языка. Их эквивалентность.
1.4. Порождающие грамматики. Классификация порождающих грамматик и формальных языков.
1.5. Автоматы как абстрактная модель.
2. Обзор процесса трансляции.
2.1. Трансляторы, интерпретаторы, компиляторы.
2.2. Стадии работы компилятора.
2.3. Лексическая спецификация.
2.4. Вывод в контекстно-свободных грамматиках. Деревья разбора. Неоднозначные грамматики.
2.5. Базовые блоки и граф потока.
3. Способы задания грамматик.
3.1. Форма Бэкуса-Наура.
3.2. Расширенная форма Бэкуса-Наура.
3.3. Итерационная форма.
3.4. Синтаксические диаграммы.
3.5. Способ описания грамматики для языков С, C++ и подобных.
4. Построение грамматик. Эквивалентные преобразования контекстно-свободных грамматик.
4.1. Рекомендации по построению грамматик.
4.2. Примеры грамматик.
4.3. Нормальная форма Хомского.
4.4. Исключение леворекурсивных правил.
4.5. Левая факторизация.
5. Конечные автоматы.
5.1. Понятие конечного автомата. Определение недетерминированного конечного автомата.
5.2. Всюду определенные конечные автоматы. Тупиковые состояния конечного автомата.
5.3. Детерминированные конечные автоматы. Способы задания детерминированных конечных автоматов.
5.4. Эквивалентность конечных автоматов. Построение эквивалентного детерминированного конечного автомата.
5.5. Минимизация детерминированного конечного автомата.
6. Регулярные выражения.
6.1. Регулярные языки и выражения. Операции над регулярными языками.
6.2. Эквивалентные преобразования регулярных выражении.
6.3. Лемма о накачке для регулярных языков.
6.4. Построение эквивалентного регулярному выражению конечного автомата.
7. Автоматы с магазинной памятью.
7.1. Определение автоматов с магазинной памятью.
7.2. Языки автоматов с магазинной памятью.
7.3. Соотношение между регулярными языками. КС-языками и языками детерминированных МП-автоматов.
7.4. Лемма о накачке для контекстно-свободных языков.
7.5. Свойства замкнутости и разрешимости контекстно-свободных языков.
8. Синтаксический анализ.
8.1. Назначение и принципы работы синтаксического анализатора. Распознаватели.
8.2. Нисходящий синтаксический анализ. Метод рекурсивного спуска.
8.3. Множества FIRST и FOLLOW.
8.4. LL-грамматнки. Предиктивный нисходящий синтаксический анализатор.
8.5. Восходящий синтаксический анализ. LR-автомат.
8.6. Разбирающие выражения грамматики.
9. Синтаксически управляемая трансляция. Преобразователи.
9.1. Синтаксически управляемые определения. Атрибутные грамматики. Аннотированные деревья разбора.
9.2. Синтаксически управляемые схемы трансляции. Транслирующие грамматики.
9.3. Преобразователи с магазинной памятью.
10. Автоматизация построения трансляторов.
10.1. Генератор лексических анализаторов Lex.
10.2. Генератор синтаксических анализаторов YACC.
10.3. Совместное использование Lex и YACC.
11. Промежуточный код.
11.1. Представление в виде ориентированного графа.
11.2. Инфиксная и постфиксная формы.
11.3. Трехадресный код.
11.4. Статические единственные присваивания. Проект LLVM
12. Оптимизация.
12.1. Основные источники оптимизации.
12.2. Анализ потока данных.
12.3. Распространение констант.
12.4. Устранение частичной избыточности.
12.5. Циклы в графах потоков.
13. Генерация целевого кода.
13.1. Общие принципы генерации кода.
13.2. Модели целевой машины.
13.3. Адреса в целевом коде.
13.4. Простой алгоритм генерации кода.
13.5. Распределение и назначение регистров.
13.6. Локальная оптимизация.
Список рекомендуемой литературы.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Трансляция формальных языков, Курс лекций, Сергеенко С.В., 2023 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу


Скачать - pdf - Яндекс.Диск.




Теги: учебник по программированию :: программирование :: Сергеенко