Читать онлайн «Классическая теория компиляторов»

В. Э. Карпов КЛАССИЧЕСКАЯ ТЕОРИЯ КОМПИЛЯТОРОВ Москва 2011  2 УДК 681. 3. 06 ББК 32. 973 К26 Рецензенты: докт. техн. наук И. П. Беляев (НИИ информационных технологий); канд. техн. наук А. Н. Таран (НИИ информационных систем) Карпов В. Э. К26 Теория компиляторов. Учебное пособие. 2-е изд. М. , 2010. – 91 с ISBN 5–230–16344–5 Рассматриваются основы теории формальных языков, приводятся методы и алгоритмы построения основных частей трансляторов и интерпретаторов. Для студентов, изучающих курсы «Системное программное обеспечение», «Теория компиляторов» и аналогичные. УДК 681. 3. 06 ББК 32. 973 ISBN 5–230–16344–5  Карпов В. Э. , 2003, 2011  3 ОГЛАВЛЕНИЕ ВВЕДЕНИЕ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 5 ТЕРМИНОЛОГИЯ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 6 ПРОЦЕСС КОМПИЛЯЦИИ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 7 ЛОГИЧЕСКАЯ СТРУКТУРА КОМПИЛЯТОРА... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 7 ОСНОВНЫЕ ЧАСТИ КОМПИЛЯТОРА ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 9 Лексический анализ (сканер)... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 10 Работа с таблицами ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 12 Синтаксический и семантический анализ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 12 ТЕОРИЯ ФОРМАЛЬНЫХ ЯЗЫКОВ. ГРАММАТИКИ... ... ... ... ... ... ... ... ... ... . 15 ФОРМАЛЬНОЕ ОПРЕДЕЛЕНИЕ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 15 ИЕРАРХИЯ ХОМСКОГО ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 17 РЕГУЛЯРНЫЕ ГРАММАТИКИ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 19 КОНЕЧНЫЕ АВТОМАТЫ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 20 ФОРМАЛЬНОЕ ОПРЕДЕЛЕНИЕ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 20 ДЕТЕРМИНИРОВАННЫЕ И НЕДЕТЕРМИНИРОВАННЫЕ КА... ... ... ... ... . 22 ПОСТРОЕНИЕ ДКА ПО НКА... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 27 ОБ УСЛОВИЯХ ЗАВЕРШЕНИЯ РАБОТЫ АВТОМАТА ... ... ... ... ... ... ... ... ... . . 29 ПРОГРАММИРОВАНИЕ СКАНЕРА... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 31 ОРГАНИЗАЦИЯ ТАБЛИЦ СИМВОЛОВ. ХЕШ-ФУНКЦИИ... ... ... ... ... ... . . 33 ХЕШ-АДРЕСАЦИЯ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 33 СПОСОБЫ РЕШЕНИЯ ЗАДАЧИ КОЛЛИЗИИ. РЕХЕШИРОВАНИЕ ... ... . . 34 ХЕШ-ФУНКЦИИ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 35 КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ ... ... ... ... ... ... ... ... ... ... ... ... ... ... 37 ОК-ГРАММАТИКИ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 40 СИНТАКСИЧЕСКИ УПРАВЛЯЕМЫЙ ПЕРЕВОД... ... ... ... ... ... ... ... ... ... ... ... . . 41 АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 45 ОПЕРАТОРНЫЕ ГРАММАТИКИ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 49 АЛГОРИТМ ДЕЙКСТРЫ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 52 МАТРИЦЫ ПЕРЕХОДОВ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 53 ВНУТРЕННИЕ ФОРМЫ ПРЕДСТАВЛЕНИЯ ПРОГРАММЫ... ... ... ... ... . . 58 ПОЛЬСКАЯ ФОРМА ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 58 ТЕТРАДЫ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 63 ОБ ОПЕРАТОРАХ И ВЫРАЖЕНИЯХ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 64 ОПТИМИЗАЦИЯ ПРОГРАММ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 65 ИНТЕРПРЕТАТОРЫ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 69 КОМПИЛЯТОРЫ КОМПИЛЯТОРОВ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 72 ПРИЛОЖЕНИЕ.