Учебное пособие. Теория языков программирования

И методы трансляции

Теория языков программирования

Ганичева О.Г.

· Начальные сведения о компиляции

· Лексический анализ

· Определение лексем

· Формальные языки и грамматики

· Синтаксический анализ

· Нисходящий анализ

· Восходящий синтаксический анализ

· Генерация кода. Методы генерации кода

· Синтаксически управляемая трансляция

Содержание

Введение………………………………………………………………………………….6

1. Начальные сведения о компиляции………………………………………..7

1.1 Общие сведения о языке программирования и структуре транслятора…..7

1.2 Модель анализа-синтеза компиляции…………………………………………...8

1.3 Понятие прохода. Однопроходные и многопроходные компиляторы………9

1.4 Фазы компилятора………………………………………………………………..10

1.5 Управление таблицей символов………………………………………………...11

1.6 Обнаружение ошибок и сообщение о них……………………………………...12

1.7 Фазы анализа………………………………………………………………………13

2. Лексический анализ…………………………………………………………15

2.1 Назначение лексического анализатора………………………………………...15

2.2 Атрибуты лексем………………………………………………………………….20

2.3 Общие принципы построения лексических анализаторов………………….21

2.4 Определение границ лексем……………………………………………………..22

2.5 Выполнение действий, связанных с лексемами………………………………22

2.6 Практическая реализация лексических анализаторов………………………23

2.7 Лексические ошибки……………………………………………………………..24

2.8 Способы построения лексических анализаторов……………………………..25

3. Определение лексем…………………………………………………………26

3.1 Строки и языки……………………………………………………………………27

3.2 Операции над языками…………………………………………………………...27

3.3 Регулярные выражения…………………………………………………………..28

3.4 Регулярные определения…………………………………………………………30

3.5 Распознавание лексем и регулярные выражения…………………………….31

3.6 Диаграммы переходов……………………………………………………………33

3.7 Конечные автоматы………………………………………………………………36

3.7.1 Недетерминированные конечные автоматы…………………………..36

3.7.2 Детерминированный конечный автомат……………………………….38

3.7.3 Преобразования НКА………………………………………………………39

3.7.4 Построение конечного автомата по регулярной грамматике………...42

4. Формальные языки и грамматики…………………………………….44

4.1 Цепочки символов. Операции над цепочками символов……………………44

4.2 Понятие языка. Формальное определение языка……………………………..45

4.3 Способы задания языков………………………………………………………….46

4.4 Синтаксис и семантика языка …………………………………………………..47

4.5 Особенности языков программирования……………………………………….48

4.6 Понятие о грамматике языка…………………………………………………….50

4.7 Формальное определение грамматики. Форма Бэкуса-Наура………………52

4.8 Принцип рекурсии в правилах грамматики ………………………………….54

4.9 Другие способы задания грамматик…………………………………………….55

4.10 Запись правил грамматик с использованием метасимволов………………56

4.11 Запись правил грамматик в графическом виде………………………………57

4.12 Классификация языков и грамматик…………………………………………60

4.12.1 Классификация грамматик по Хомскому…………………………….60

4.12.2 Классификация языков …………………………………………………..63

4.12.3 Примеры классификации языков и грамматик………………………66

4.13 Цепочки вывода. Сентенциальная форма. Вывод. Цепочки вывода……...68

4.14 Сентенциальная форма грамматики. Язык, заданный грамматикой …..…69

4.15 Левосторонний и правосторонний выводы……………………………………70

4.16 Дерево вывода. Методы построения дерева вывода…………………………71

5.Синтаксический анализ.…………………………………………………...73

5.1 Основные принципы работы синтаксического анализатора……………….73

5.2 Роль синтаксического анализатора ……………………………………………...75

5.3 Обработка синтаксических ошибок………………………………………………..77

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

5.5 Порождение……………………………………………………………………………80

5.6 Деревья разбора и приведения…………………………………………………...82

5.7 Неоднозначность грамматик. Устранение неоднозначности………………...85

5.8 Устранение левой рекурсии……………………………………………………..86

5.9 Левая факторизация……………………………………………………………88

5.10 Эквивалентные преобразования КС-грамматик……………………………89

5.11 КС-языки и магазинные автоматы……………………………………………90

6. Нисходящий анализ………………………………………………………...94

6.1 Анализ методом рекурсивного спуска………………………………………..94

6.2 Предиктивные анализаторы……………………………………………………...96

6.3 Нерекурсивный предиктивный анализ……………………………………....96

6.4 Множества FIRST и FOLLOW………………………………………………….98

6.5 Построение таблиц предиктивного анализа………………………………100

6.6 LL(1)-грамматики……………………………………………………………….102

7. Восходящий синтаксический анализ……………………………………103

7.1 Понятие основы……………………………………………………………………..104

7.2 Стековая реализация ПС-анализа…………………………………………….106

7.3 Конфликты в процессе ПС-анализа……………………………………..….108

7.4 Синтаксический анализ приоритета операторов…………………………...108

7.4.1 Грамматики простого предшествования……………………………....109

7.4.2 Грамматики операторного предшествования………………………...110

7.4.3 Использование отношений приоритетов операторов……………….111

7.4.4 Нахождение отношений приоритетов операторов…………………...113

7.4.5 Обработка ошибок переноса/свертки………………………………….114

7.4.6 Алгоритм синтаксического анализа простого предшествования…117

7.4.7 Алгоритм синтаксического анализа приоритета операторов………118

7.5 LR-анализаторы………………………………………………………………...119

7.5.1 Алгоритм LR-анализа……………………………………………………120

7.5.2 Построение таблиц SLR-анализа……………………………………….122

7.5.3 Операция замыкания……………………………………………………..123

7.5.4 Операция goto……………………………………………………………..125

7.5.5 Построение множеств пунктов………………………………………….125

7.5.6 Построение таблицы разбора SLR-анализа…………………………...127

7.5.7 LR-грамматики…………………………………………………………...134

8. Генерация кода. Методы генерации кода………………………………135

8.1 Общие принципы генерации кода…………………………………………….135

8.2 Внутреннее представление программы ……………………………………...137

8.3 Способы внутреннего представления программ……………………………138

8.4 Синтаксические деревья……………………………………………………….139

Дата добавления: 2014-12-27