ВУЗ:
Составители:
5
Оглавление
ОГЛАВЛЕНИЕ................................................................................................................................................................ 3
1. ОСНОВЫ ТЕОРИИ ФОРМАЛЬНЫХ ЯЗЫКОВ................................................................................................. 6
О
СНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ
......................................................................................................................... 6
С
ПОСОБЫ ЗАДАНИЯ СХЕМ ГРАММАТИК
........................................................................................................................ 7
К
ЛАССИФИКАЦИЯ ГРАММАТИК И ЯЗЫКОВ ПО
Х
ОМСКОМУ
........................................................................................ 10
2. ПОСТРОЕНИЕ ГРАММАТИК. ГРАММАТИКИ, ОПИСЫВАЮЩИЕ ОСНОВНЫЕ КОНСТРУКЦИИ
ЯЗЫКОВ ПРОГРАММИРОВАНИЯ ........................................................................................................................ 12
3. РАЗБОР ЦЕПОЧЕК. РАСПОЗНАВАТЕЛИ........................................................................................................ 17
Р
АЗБОР ЦЕПОЧЕК
.......................................................................................................................................................... 17
О
БЩАЯ СХЕМА РАСПОЗНАВАТЕЛЯ
.............................................................................................................................. 19
В
ИДЫ РАСПОЗНАВАТЕЛЕЙ
........................................................................................................................................... 19
К
ЛАССИФИКАЦИЯ РАСПОЗНАВАТЕЛЕЙ ПО ТИПАМ ЯЗЫКОВ
........................................................................................ 20
П
ОСТАНОВКА ЗАДАЧИ РАЗБОРА
................................................................................................................................... 22
4. ТРАНСЛЯТОРЫ, ИНТЕРПРЕТАТОРЫ, КОМПИЛЯТОРЫ. ЭТАПЫ ТРАНСЛЯЦИИ. ОБЩАЯ
СХЕМА РАБОТЫ ТРАНСЛЯТОРА......................................................................................................................... 23
Т
РАНСЛЯТОРЫ
............................................................................................................................................................. 23
К
ОМПИЛЯТОРЫ
............................................................................................................................................................ 24
И
НТЕРПРЕТАТОРЫ
....................................................................................................................................................... 25
И
СТОРИЯ РАЗВИТИЯ КОМПИЛЯТОРОВ
......................................................................................................................... 25
Э
ТАПЫ ТРАНСЛЯЦИИ
.
О
БЩАЯ СХЕМА РАБОТЫ ТРАНСЛЯТОРА
................................................................................... 26
М
НОГОПРОХОДНЫЕ И ОДНОПРОХОДНЫЕ КОМПИЛЯТОРЫ
.......................................................................................... 28
О
СОБЕННОСТИ ПОСТРОЕНИЯ ИНТЕРПРЕТАТОРОВ
....................................................................................................... 30
5. ЛЕКСИЧЕСКИЙ АНАЛИЗ. ТАБЛИЦЫ ИДЕНТИФИКАТОРОВ. ЛЕКСИЧЕСКИЕ АНАЛИЗАТОРЫ
.......................................................................................................................................................................................... 31
Н
АЗНАЧЕНИЕ И ОСОБЕННОСТИ ПОСТРОЕНИЯ ТАБЛИЦ ИДЕНТИФИКАТОРОВ
............................................................... 31
Н
АЗНАЧЕНИЕ ЛЕКСИЧЕСКОГО АНАЛИЗАТОРА
(
СКАНЕРА
)........................................................................................... 32
П
РИНЦИПЫ ПОСТРОЕНИЯ ЛЕКСИЧЕСКИХ АНАЛИЗАТОРОВ
.......................................................................................... 34
6. АВТОМАТНЫЕ ГРАММАТИКИ И КОНЕЧНЫЕ АВТОМАТЫ .................................................................. 36
А
ЛГОРИТМ РАЗБОРА ЦЕПОЧЕК
..................................................................................................................................... 36
А
ЛГОРИТМ РАЗБОРА ПО ДИАГРАММЕ СОСТОЯНИЙ
...................................................................................................... 37
Н
ЕДЕТЕРМИНИРОВАННЫЙ РАЗБОР
............................................................................................................................... 40
А
ЛГОРИТМ ПОСТРОЕНИЯ ДЕТЕРМИНИРОВАННОГО
КА
ПО
НКА................................................................................. 40
М
ИНИМИЗАЦИЯ КОНЕЧНЫХ АВТОМАТОВ
................................................................................................................... 41
7. СИНТАКСИЧЕСКИЙ АНАЛИЗ ........................................................................................................................... 42
Г
РАММАТИКИ ПРЕДШЕСТВОВАНИЯ
............................................................................................................................. 43
Г
РАММАТИКИ ПРОСТОГО ПРЕДШЕСТВОВАНИЯ
........................................................................................................... 43
А
ЛГОРИТМ
«
СДВИГ
-
СВЕРТКА
»
ДЛЯ ГРАММАТИК ПРОСТОГО ПРЕДШЕСТВОВАНИЯ
..................................................... 46
Г
РАММАТИКИ ОПЕРАТОРНОГО ПРЕДШЕСТВОВАНИЯ
................................................................................................... 46
А
ЛГОРИТМ
«
СДВИГ
-
СВЕРТКА
»
ДЛЯ ГРАММАТИК ОПЕРАТОРНОГО ПРЕДШЕСТВОВАНИЯ
............................................ 48
О
БЩИЙ АЛГОРИТМ РАБОТЫ СИНТАКСИЧЕСКОГО АНАЛИЗАТОРА
................................................................................ 49
С
ЕМАНТИЧЕСКИЙ АНАЛИЗ
........................................................................................................................................... 50
8. ГЕНЕРАЦИЯ КОДА ................................................................................................................................................50
А
ЛГОРИТМ ГЕНЕРАЦИИ ОБЪЕКТНОГО КОДА ПО ДЕРЕВУ ВЫВОДА
............................................................................... 52
П
ОСТРОЕНИЕ АССЕМБЛЕРНОГО КОДА ПО ДЕРЕВУ ВЫВОДА
........................................................................................ 53
П
ОСТРОЕНИЕ СПИСКА ТРИАД ПО ДЕРЕВУ ВЫВОДА
..................................................................................................... 55
О
ПТИМИЗАЦИЯ ОБЪЕКТНОГО КОДА МЕТОДОМ СВЕРТКИ
............................................................................................ 57
О
ПТИМИЗАЦИЯ ОБЪЕКТНОГО КОДА МЕТОДОМ ИСКЛЮЧЕНИЯ ЛИШНИХ ОПЕРАЦИЙ
................................................... 58
О
БЩИЙ АЛГОРИТМ ГЕНЕРАЦИИ И ОПТИМИЗАЦИИ ОБЪЕКТНОГО КОДА
....................................................................... 60
БИБЛИОГРАФИЧЕСКИЙ СПИСОК...................................................................................................................... 60
