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

3.2.1. Характеризующие кзыки 269

3.2.2. Свойства простых СУ-переводов 273

3.2.3. Иерархия СУ-переводов 274 Упражнения 281

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

3.3. Лексический анализ 283

3.3.1. Язык расширенных регулярных выражений 284 3.3.2-. Непрямой лексический анализ 286

3.3.3. Прямой лексический анализ 290

3.3.4. Программное моделирование конечных преобразователей Упражнения 294

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

3.4. Синтаксический анализ 296

3.4.1. Определение разбора 296

3.4.2. Нисходящий разбор 297

3.4.3. Восходящий разбор 301

3.4.4. Сравнение нисходящего разбора с восходящим 304

3.4.5. Грамматическое покрытие 309 Упражнения 315

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

ОБЩИЕ МЕТОДЫ СИНТАКСИЧЕСКОГО АНАЛИЗА 316

4.1. Синтаксический анализ с возвратами 317

4.1.1. Моделирование МП-преобразователя 317

4.1.2. Неформальное описание нисходящего разбора 321

4.1.3. Алгоритм нисходящего разбора 325

4.1.4. Временная и емкостная сложность нисходящего анализатора 333

4.1.5. Восходящий разбор 338 Упражнения 344 Замечания по литературе 351

4.2. Табличные методы сиитаксического анализа 352

4.2.1. Алгоритм Кока

4.2.2. Алгорзитм Эрли Упражнения 369 Замечания по литературе 372

- Я нгера - Касамн 352 358

ОДНОПРОХОДНЫЙ СИНТАКСИЧЕСКИЙ АНАЛИЗ БЕЗ ВОЗВРАТОВ 373

5.1. ЬГ(й)-грамматики 374

5.1.1. Определение ГГ(й)-грамматики 374

5.1.2. Предсказывающие алгоритмы разбора 378

5.1.3. Следствия определения ГЬ()-грамматики 382

5.1.4. Разбор для ГГ(1-)-грамматнк 387

5.1.5. Разбор для ГГ(й)-грамматнк 388 5; 1.6. Проверка ЬЬ(й)-условия 396 Упражнения 400

Зafeчaния по литературе 408

Дополнение. О методах разбора „по текущему символу"л S. Я. Агафонов 408

5.2. Детерминированный восходящий синтаксический анализ 420

5.2.1. Разбор с помощью детерминированного алгоритма типа „перенос -свертка" 420

5.2.2. LR (й)-грамматики 423

5.2.3. Следствия определения LR (/е)-грамматнки 432

5.2.4. Проверка LR (й)-условия 442

5.2.5. Детерминированные правые анализаторы для LR(ft)-rpaMMaTHK 443

5.2.6. Реализация LL(/;)- и LR(/г)-aнaлизaтopOБ 448 Упражнения 448

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

5.3. Грамматики предшествования 452

5.3.1. Формальное определение алгоритма типа „перенос - свертка" 452

5.3.2. Грамматики простого предшествования 455

5.3.3. Грамматики расширенного предшествования 463

5.3.4. Грамматики слабого предшествования 469 Упражнения 477

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

5.4. Другие классы грамматик, анализируемых методом „перенос - свертка" 481

5.4.1. Грамматики ограниченного правого контекста 481

5.4.2. Грамматики смешанной стратегии предшествования 48

5.4.3. Грамматики операторного предшествования 492

5.4.4. Язык Флойда -Эванса 497

5.4.5. Резюме 502 Упражнения 505 Замечания по литературе 510

АЛГОРИТМЫ РАЗБОРА С ОГРАНИЧЕННЫМИ ВОЗВРАТАМИ 511

6.1. Нисходящий разбор с ограниченными возвратами 511

6.1.1. Язык нисходящего разбора с ограниченными возвратами 512

6.1.2. ЯНРОВ п детерминированные КС-языки 522 0.1.3. Обобщенный ЯНРОВ 525

6.1.4. Временная сложность ОЯНРОВ-языков 530

6.1.5. Реализация ОЯНРОВ-программ 533 Упражнения 539

Замечатшя по литературе 542

ОГЛАВЛЕНИЕ

6.2. Восходящий разбор с ограниченными возвратами 542

6.2.1. Неканонический разбор 542

6.2.2. Анализаторы с двумя магазинами 544

6.2.3. Отношения нредшествовання Колмерауэра 547

6.2.4. Проверка условий предшествования Колмерауэра Упражнения 556

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

Прило.жение

П.]. Синтаксис расширяемого языка 559 П.2. Синтаксис операторов языка Снобол 4 П.З. Синтаксис ПЛ 360 565

П.4. Схема синтаксически управляемого перевода для языка PAL 569

Список литературы 575

Указатель обозначений 590

Указатель лемм, теорем и алгоритмов 591

Именной указатель 593

Предметный указатель 596

УВАЖАЕМЫЙ ЧИТАТЕЛЬ!

Ваши замечания о содержании книги, ее оформлении, качестве перевода и другие просим присылать по адресу: 129820, Москва, И-110, ГСП, 1-й Рижский пер., д. 2, издательство «Мир».