Основы теории формальных языков, автоматов и трансляций: учебное пособие

Description

В пособии систематически изложены основные положения теории формальных языков и автоматов, рассмотрены модели и методы синтаксического анализа и перевода, а также их применение на различных этапах разработки языков программирования и построения трансляторов. Пособие содержит большое количество примеров, упражнений и заданий для использования в практических и лабораторных занятиях. Предназначено для студентов вузов, обучающихся по направлениям «Программная инженерия», «Математическое обеспечение и администрирование информационных систем». ОГЛАВЛЕНИЕ ПРЕДИСЛОВИЕ ГЛАВА 1 ВВЕДЕНИЕ В ПРОБЛЕМАТИКУ РАЗРАБОТКИ И РЕАЛИЗАЦИИ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ 1.1. ЯЗЫКИ ПРОГРАММИРОВАНИЯ И ФОРМАЛЬНЫЕ ЯЗЫКИ 1.2. ПОНЯТИЕ ТРАНСЛЯТОРА И КОМПИЛЯТОРА. ФАЗЫ КОМПИЛЯЦИИ 1.3. ИНСТРУМЕНТЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ И РЕАЛИЗАЦИИ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ ГЛАВА 2 СПОСОБЫ ЗАДАНИЯ ФОРМАЛЬНЫХ ЯЗЫКОВ 2.1. МАТЕМАТИЧЕСКИЙ АППАРАТ ТЕОРИИ ФОРМАЛЬНЫХ ЯЗЫКОВ 2.2. ЦЕПОЧКИ И ЯЗЫКИ 2.3. ГРАММАТИКИ 2.4. РАСПОЗНАВАТЕЛИ 2.5. РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ И СИНТАКСИЧЕСКИЕ ДИАГРАММЫ 2.6. СООТВЕТСТВИЯ МЕЖДУ СПОСОБАМИ ОПИСАНИЯ ЯЗЫКОВ 2.7. УПРАЖНЕНИЯ И ЗАДАНИЯ ГЛАВА 3 ОСНОВЫ ТЕОРИИ ПЕРЕВОДА И ЕЕ ПРИМЕНЕНИЕ К СИНТАКСИЧЕСКОМУ АНАЛИЗУ 3.1. ОПРЕДЕЛЕНИЕ ПЕРЕВОДА 3.2. СХЕМЫ СИНТАКСИЧЕСКИ УПРАВЛЯЕМЫХ ПЕРЕВОДОВ 3.3. МОДЕЛИ ПРОСТЕЙШИХ ТРАНСЛЯТОРОВ 3.4. ОПРЕДЕЛЕНИЕ СИНТАКСИЧЕСКОГО РАЗБОРА 3.5. МОДЕЛИ АНАЛИЗАТОРОВ 3.6. МОДЕЛИ СИНТАКСИЧЕСКИ УПРАВЛЯЕМОЙ ТРАНСЛЯЦИИ 3.7. УПРАЖНЕНИЯ И ЗАДАНИЯ ГЛАВА 4 КОНСТРУИРОВАНИЕ СКАНЕРОВ 4.1. ОБЩАЯ ХАРАКТЕРИСТИКА ПРОЦЕССА СКАНИРОВАНИЯ 4.2. ОПИСАНИЕ ЛЕКСЕМ В ЯЗЫКЕ РАСШИРЕННЫХ РЕГУЛЯРНЫХ ВЫРАЖЕНИЙ 4.3. ПОСТРОЕНИЕ НЕДЕТЕРМИНИРОВАННОГО КОНЕЧНОГО АВТОМАТА ПО РАСШИРЕННОМУ РЕГУЛЯРНОМУ ВЫРАЖЕНИЮ 4.4. ПРЕОБРАЗОВАНИЕ СИНТАКСИЧЕСКОЙ ДИАГРАММЫ В КОНЕЧНЫЙ АВТОМАТ 4.5. ПРЕОБРАЗОВАНИЕ НЕДЕТЕРМИНИРОВАННОГО КОНЕЧНОГО АВТОМАТА В ДЕТЕРМИНИРОВАННЫЙ 4.6. ПРЕДСТАВЛЕНИЕ РЕЗУЛЬТАТОВ СКАНИРОВАНИЯ 4.7. МЕТОДИКИ КОНСТРУИРОВАНИЯ СКАНЕРОВ 4.8. УПРАЖНЕНИЯ И ЗАДАНИЯ ГЛАВА 5 ПРИМЕНЕНИЕ КС-ЯЗЫКОВ И ГРАММАТИК В РАЗРАБОТКЕ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ 5.1. ПРОБЛЕМАТИКА 5.2. СВОЙСТВА КС-ЯЗЫКОВ И ГРАММАТИК 5.3. ЭКВИВАЛЕНТНЫЕ ПРЕОБРАЗОВАНИЯ КС-ГРАММАТИК 5.4. КЛАССЫ ЛЕВО- И ПРАВОАНАЛИЗИРУЕМЫХ ГРАММАТИК 5.5. ОТНОШЕНИЯ МЕЖДУ КЛАССАМИ КС-ГРАММАТИК И ЯЗЫКОВ 5.6. УПРАЖНЕНИЯ И ЗАДАНИЯ ГЛАВА 6 КОНСТРУИРОВАНИЕ ОДНОПРОХОДНЫХ АНАЛИЗАТОРОВ 6.1. ОБЩАЯ ХАРАКТЕРИСТИКА МОДЕЛЕЙ И МЕТОДОВ ДЕТЕРМИНИРОВАННОГО СИНТАКСИЧЕСКОГО АНАЛИЗА 6.2. МОДЕЛЬ ЛЕВОГО LL(K)-АНАЛИЗАТОРА 6.3. АЛГОРИТМЫ ПОСТРОЕНИЯ УПРАВЛЯЮЩИХ ТАБЛИЦ LL(K)-АНАЛИЗАТОРА 6.4. МОДЕЛЬ ПРАВОГО LR(K)-АНАЛИЗАТОРА 6.5. КЛАСС АЛГОРИТМОВ ТИПА «ПЕРЕНОС–СВЕРТКА» 6.6. КОНСТРУИРОВАНИЕ АЛГОРИТМОВ ТИПА «ПЕРЕНОС–СВЕРТКА» ДЛЯ НЕСКОЛЬКИХ КЛАССОВ ГРАММАТИК ПРЕДШЕСТВОВАНИЯ ГЛАВА 7 СЕМАНТИЧЕСКИЙ АНАЛИЗ И СИНТЕЗ ВНУТРЕННЕГО ПРЕДСТАВЛЕНИЯ ПРОГРАММЫ 7.1. ОБЩИЕ ЗАМЕЧАНИЯ О СЕМАНТИЧЕСКОМ АНАЛИЗЕ И ГЕНЕРАЦИИ КОДА 7.2. ОСНОВНЫЕ ФУНКЦИИ СЕМАНТИЧЕСКОГО АНАЛИЗА 7.3. ИНТЕРПРЕТАЦИЯ ПРОМЕЖУТОЧНОЙ ПРОГРАММЫ И ПРЕОБРАЗОВАНИЕ В АССЕМБЛЕРНЫЙ КОД 7.4. УПРАЖНЕНИЯ И ЗАДАНИЯ ЗАКЛЮЧЕНИЕ БИБЛИОГРАФИЧЕСКИЙ СПИСОК