Главная Промышленная автоматика.

Список (list)

- магазинный (pushdown) см. Магазин

- разбора (parse) 359

ССП-грамматика, см. Грамматика смешанной стратегии предшествования Степень (вершины графа) (degree)

- по входу (in-) 54 --выходу (out-) 54

СУ-перевод см. Перевод синтаксически управляемый Суффикс (цепочки) (suffix) 28 Схема перевода (translation scheme) см. Перевод Сцепление (concatenation) см. Конкатенация

Таблица (table)

- идентификаторов (symbol) см. Таблица имен

- имен (symbol) 75. 79, 80, 92, 93, 287 ~ разбора (parse) 352

- управляющая разбором (parsing) 379, 385-387, 391-395, 404, 405 см. также LR(;fe)-таблица

- LL{k) 389-391, 394, 395

- ЪЩк) 426, 427, 444-446, 451 ТАГ-система (Tag system) 42, 122

Такт (распознавателя) (move) 115, 135, 194 Тезис Чёрча-Тьюринга (Church-Turing thesis) 43 Теорема (theorem) 32

- Парика (Parikhs) 239, 241

Терминал (в грамматике) (terminal) 106, 120, 514

Точка наименьшая неподвижная (minimal fixed point) 127, 129-131, 144-146, 185, 186

Транслятор (translator) 77, 246, 247 см. такоюе Преобразователь Трансляция (translation) см. Перевод

Узел (графа) (node) см. Вершина (графа) Упорядочение (ordering) см. Порядок (как отношение) Уравнения (equations)

- определяющие (для КС-языков) (defining) 185, 186

- с регулярными коэффициентами (regular expression) 126-133, 144, 146 Уровень (вершины дерева) (level) см. Высота (вершины дерева)

Устройство управляющее с конечной памятью (finite control) 114, 498 см. также Состояние (распознавателя)

Факторизация левая (left factoring) 385 Форма (form)

- Бэкуса-Наура (Backus-Naur) 74

- нормальная Грейбах (Greibach normal) 182-188, !90, 274, 315, 402, 406 -- слабая 409

- нормальная Хомского (Chomsky normal) 176, 177, 190, 273, 274, 310, 311, 314, 352, 401

Фортран (FORTRAN) 70, 74, 77, 79, 236, 286, 346, 347, 559 Функция (function) 21, 22, 25

- биективная (bijective) 22

- взаимно однозначная см. Функция ннъективная

- всюду определенная (total) 21, 25

- действия (parsing action) 426-428, 444-446

- доступа к памяти (распознавателя) (store) 114

Функция ниъектнвная (injective) 22

- общерекурснвиая (total recursive) 41

- переходов (goto) 426-428, 444-446

- переходов (состояний аитрмата) (state transition) 135

- преобразования памяти (распознавателя) (fetch) 114

- рекурсивная (recursive) 41

- характеристическая (characteristic) 48

- частичная (partial) 22

- частично рекурсивная (partial recursive) 41

- EFF433, 444. 450

- FIRST 337, 375, 376, 396-399

- FOLLOW 383. 479

- GOTO 438-441, 444

Цепочка (string) 27, 106

- выводимая (sentential form) 106

- левовыводимая (left sentential form) 167

- правовыводимая (right sentential form) 167, 459, 460, 469-

- пустая (empty) 27

Цикл в графе (cycle, circuit) 54

--грамматике см. Грамматика без циклов

-471

Часть (portion)

- (левовыводимой цепочки) законченная (closed) 374

- незаконченная (open) 374

- (правовыводимой цепочки) замкнутая (closed) 421

- открытая (open) 421,

Эквивалентность (программ, автоматов, грамматик) (equivalence) 71, 147-150,

154-156, 162 см. также ГТроблема эквивалентности Элемент перевода (translation element) 246-248

Язык (language) 28, 103, 104, 116, 136, 195 см. также Множество

- ассемблера (assembly) 82-88

- бесконтекстный (context-free) см. Язык контекстно-свободный

- детерминированный (deterministic) 211, 216, 229-231, 238, 241, 283, 384, 450, 501, 503, 522-525

- Дика (Dyck) 2*9

- естественный (natural) 72, 97, 98, 102, 317, 351

- контекстно-зависимый (context-sensitive) 111, 112, 117, 119-12!, 237, 452

- контекстно-свободный (context-free) 111, 112, 117, 119, 12!, 237

- левых разборов (left parse) 307, 311

- линейный (linear) 191, 237, 268

- LL 376

- LCik) 402-408

- hUk) 373-408, 449, 450

- LR(A) CM. Язык детерминированный и LR(ft)-rpaMMaTHKa

- неоднозначный (ambiguous) 234-236, 238, 239, 241

- нисходящего разбора с ограниченными возвратами (ЯНРОВ) (top down parsing language, TDPL) 512-525, 528-530, 539-542

--обобщенный (ОЯНРОВ) (generalized, GTDPL) 525-542

- ограниченного контекста (bounded context) 505. 507

--правого контекста (bounded right context) 481-488, 503-507



Язык однозначный (unambiguous) 234, 240 см.. также Грамматика однозначная

- операторного предшествования (operator precedence) 493-497, 503, 504. 507 ~ (1,1)-0ПК ((l,I)-bounded-rigiit-context) 484, 503

- правых разборов (right parse) 307, 31!

- программирования (programming) 42, 69-74 , 373 см. также Алгол, ПЛ/1, ПЛ 360, Фортран, Снобол

- простого предшествоваиня (simple precedence) 455-463, 474-479, 549, 565

- расширяемый (extensible) 74, 75, 559-562

- регулярный (regular) см. Множество регулярное

- существенно неодиозиачиый (inherent ambiguous) см. Язык неоднозначный

- Флойда-Эиаиса (Floyd-Evans) 411, 497-502, 507, 510

- характеризующий (characterizing) 269-273, 282

ЯНРОВ см. Язык нисходящего разбора с ограниченными возвратами

ОГЛАВЛЕНИЕ

ОТ РЕДАКТОРА ПЕРЕВОДА 5 ПРЕДИСЛОВИЕ 7

ПРЕДВАРИТЕЛЬНЫЕ МАТЕМАТИЧЕСКИЕ СВЕДЕНИЯ !1

ОЛ. Основные понятия теории множеств И

0.1.1. Множества 1!

0.1.2. Операции над множествами 14

0.1.3. Отиошеиия 16

0.1.4. Замыкание отношений 18

0.1.5. Отиошеиия порядка 20

0.1.6. Отображения 21

Упражнения 23

0.2. Множества цепочек 26

0.2.1. Цепочки 27

0.2.2. Языки 28

0.2.3. Операции над языками 29

Упражнения 30

0.3. Некоторые понятия математической логики 31

0.3.1. Доказательства 31

0.3.2. Доказательство индукцией 32

0.3.3. Логические связки 33

Упражнения 35

Замечания по литературе 38

0.4. Алгоритмы (частичные и всюду определенные) 38

0.4.1. Частичные алгоритмы 38

0.4.2. Алгоритмы 40

0.4.3; Рекурсивные функции 41

0.4.4. Задание алгоритмов 42

0.4,5. Проблемы 43

0.4.6. Проблема соответствий Поста 47

Упражнения 48

Замечания по литературе 51



ОГЛАВЛЕНИЕ

0.5. Некоторые понятия теории графов 52

0.5.1. Ориентированные графы 52

0.5.2. Ориентированные ациклические графы 54

0.5.3. Деревья 55

0.5.4. Упорядоченные графы 56

0.5.5. Индукция по ациклическому графу 58

0.5.6. Вложение частичного порядка в линейный

0.5.7. Представления деревьев 6!

0.5.8. Пути в графе 62

Упражнения 66

Замечания по литературе 6S

ВВЕДЕНИЕ В КОМПИЛЯЦИЮ 69

1.1. Языки программирования 69

1.1.1. Задание языков программирования 69

1.1.2. Синтаксис и семантика 71 Замечания по литературе 74

1.2. Обзор процесса компиляции 75

1.2.1. Основные части компилятора 75

1.2.2. Лексический анализ 76

1.2.3. Работа с таблицами 79

1.2.4. Синтаксический анализ 80 1.2,5- Генерация кода 82

1.2,6. Оптимизация кода 88

!.2,7. Анализ и исправление ошибок 90

1.2.8. Резюме 91

Упражнения 92

Замечания по литературе 95

1.3. Другие приложения алгоритмов разбора и перевода 96

1.3.1. Естественные языки 97

1.3.2. Структурное описание образов 98 Замечания по литературе 102

ЭЛЕМЕНТЫ ТЕОРИИ ЯЗЫКОВ 103

2.1. Способы определения языков

2.!.!. Мотивировка 104

2.1.2. Грамматики 105

2.1.3. Грамматики с ограничениями на правила

2.1.4. Распознаватели 112 Упражнения ! 16 Замечания по литературе 123

2.2. Регулярные множества, нх распознавание и порождение 124

2.2.!. Регулярные множества и регулярные выражения 124

2.2.2. Регулярные множества и праволинейные грамматики 131

2.2.3. Конечные автоматы 134

ОГЛАВЛЕНИЕ

2.2.4. Конечные автоматы и регулярные множества 141

2.2.5. Резюме 153 Упражнения 143 Замечания по литературе 147

2.3. Свойства регулярных множеств 147

2.3.1. Минимизация конечных автоматов ,147

2.3.2. Лемма о разрастании для регулярных множеств 151

2.3.3. Свойства замкнутости регулярных множеств 152

2.3.4. Разрешимые проблемы, связанные с регулярными множествами 154

Упражнения 156

Замечания по литературе 162

2.4. Контекстно-свободные языки 163

2.4.1. Деревья выводов 163

2.4.2. Преобразования КС-грамматнк 168

2.4.3. Нормальная форма Хомского 176 2.4-4. Нормальная форма Грейбах 178

2.4.5. Другой метод преобразования к нормальной форме Грейбах 184

Упражнения 188

Замечания по литературе 192

2.5. Автоматы с магазинной памятью 192

2.5.1. Основное определение 193

2.5.2. Варианты МП-автоматов 198

2.5.3. Эквивалентность МП-автоматов и КС-грамматик

2.5.4. Детерминироваппые МП-автоматы 211 Упражнения 217

Замечания по литературе 220

2.6. Свойства контекстно-свободных языков 220

2.6.1. Лемма Огдеиа 220

2.6.2. Свойства замкнутости класса КС-языков

2.6.3. Результаты о разрешимости 227

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

2.6.5. Неоднозначность 231 Упражнения 236 Замечания по литературе 241

227 230

ТЕОРИЯ ПЕРЕВОДА 242

3.1. Формализмы, используемые для определения перевода 242

3.1.1. Перевод и семантика 242

3.1.2. Схемы синтаксически управляемого перевода

3.1.3. Конечные преобразователи 254

3.1.4. Преобразователи с магазинной памятью 258 Упражнения 264

Замечания по литературе 268





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 [100] 101

0.0035