В книге рассматриваются основные теоретические принципы и реализующие их технологии, лежащие в основе современных средств разработки программного обеспечения. В ней содержится вся необходимая информация о трансляторах, компиляторах, интерпретаторах, а также о других составляющих систем программирования, от базовых теоретических сведений до современных технологий разработки распределенных программ. Третье издание полностью отвечает содержанию дисциплины «Системное программное обеспечение» по новой версии стандарта. По сравнению с предыдущей редакцией книги автор постарался придать материалу практическую направленность. С одной стороны, это позволило сократить теоретические разделы книги, не отклоняясь от требований образовательного стандарта, что, по мнению автора, должно способствовать лучшему усвоению учебного материала, а с другой стороны, книга может оказаться полезной не только студентам, но и специалистам, чья деятельность напрямую связана с созданием средств обработки текстов и структурированных текстовых команд.
Допущено Министерством образования и науки Российской Федерации в качестве учебника для студентов высших учебных заведений, обучающихся по специальностям «Вычислительные машины, комплексы, системы и сети» и «Автоматизированные системы обработки информации и управления» направления подготовки дипломированных специалистов «Информатика и вычислительная техника».
Содержание
Предисловие
Введение Глава 1. Формальные языки и грамматики
Языки и цепочки символов. Способы задания языков
Цепочки символов. Операции над цепочками символов
Понятие языка. Формальное определение языка
Способы задания языков. Синтаксис и семантика языка
Особенности языков программирования
Грамматики и распознаватели
Формальное определение грамматики. Форма Бэкуса-Наура
Принцип рекурсии в правилах грамматики
Другие способы задания грамматик
Распознаватели. Общая схема распознавателя
Классификация распознавателей по структуре
Классификация языков и грамматик
Классификация грамматик. Четыре типа грамматик по Хомскому
Классификация языков
Задача разбора. Классификация распознавателей по типам
Примеры классификации языков и грамматик
Цепочки вывода. Сентенциальная форма
Вывод. Цепочки вывода
Сентенциальная форма грамматики. Язык, заданный грамматикой
Левосторонний и правосторонний выводы
Дерево вывода. Методы построения дерева вывода
Проблемы однозначности и эквивалентности грамматик
Однозначные и неоднозначные грамматики
Проверка однозначности и эквивалентности грамматик
Правила, задающие неоднозначность в грамматиках
Контрольные вопросы и задачи
Вопросы
Задачи Глава 2. Основные принципы построения трансляторов
Трансляторы, компиляторы и интерпретаторы — общая схема работы
Определение транслятора, компилятора, интерпретатора
Этапы компиляции. Общая схема работы компилятора
Понятие прохода. Многопроходные и однопроходные компиляторы
Современные компиляторы и интерпретаторы
Принципы работы современных компиляторов
Интерпретаторы. Особенности построения интерпретаторов
Трансляторы с языка ассемблера («ассемблеры»)
Макроязыки и макрогенерация
Таблицы идентификаторов. Организация таблиц идентификаторов
Назначение и особенности построения таблиц идентификаторов
Простейшие методы построения таблиц идентификаторов
Построение таблиц идентификаторов по методу бинарного дерева
Хеш-функции и хеш-адресация
Комбинированные способы построения таблиц идентификаторов
Контрольные вопросы и задачи
Вопросы
Задачи
Упражнения Глава 3. Лексические анализаторы
Лексические анализаторы (сканеры). Принципы построения сканеров
Назначение лексического анализатора
Принципы построения лексических анализаторов
Проблемы построения лексических анализаторов
Регулярные языки и грамматики
Регулярные и автоматные грамматики
Конечные автоматы
Детерминированные и недетерминированные конечные автоматы
Минимизация конечных автоматов
Регулярные множества и регулярные выражения
Свойства регулярных языков
Построение лексических анализаторов
Три способа задания регулярных языков
Построение регулярного выражения для языка,
заданного леволинейной грамматикой
Построение конечного автомата на основе леволинейной грамматики
Автоматизация построения лексических
анализаторов (программа LEX)
Контрольные вопросы и задачи
Вопросы
Задачи
Упражнения Глава 4. Синтаксические анализаторы
Основные принципы работы синтаксических анализаторов
Назначение синтаксических анализаторов
Автоматы с магазинной памятью (МП-автоматы)
Построение синтаксических анализаторов
Преобразование КС-грамматик. Приведенные грамматики
Цель преобразования КС-грамматик. Приведенные грамматики
Удаление бесплодных символов
Удаление недостижимых символов
Устранение ?-правил
Устранение цепных правил
Устранение левой рекурсии
Синтаксические распознаватели с возвратом
Принципы работы распознавателей с возвратом
Нисходящий распознаватель с подбором альтернатив
Восходящий распознаватель на основе алгоритма «сдвиг-свертка»
Нисходящие распознаватели КС-языков без возвратов
Левосторонний разбор по методу рекурсивного спуска
Расширенные варианты метода рекурсивного спуска
LL(k)-грамматики
Синтаксический разбор для LL(1)-грамматик
Восходящие синтаксические распознаватели без возвратов
LR(k)-грамматики
Синтаксический разбор для LR(0)-грамматик
Синтаксический разбор для LR(1)-грамматик
SLR(1) и LALR(1)-грамматики
Автоматизация построения синтаксических анализаторов (программа YACC
Синтаксические распознаватели на основе грамматик предшествования
Общие принципы грамматик предшествования
Грамматики простого предшествования
Грамматики операторного предшествования
Контрольные вопросы и задачи
Вопросы
Задачи
Упражнения Глава 5. Генерация и оптимизация кода
Семантический анализ и подготовка к генерации кода
Назначение семантического анализа
Этапы семантического анализа
Идентификация лексических единиц языков программирования
Распределение памяти
Принципы распределения памяти
Простые и сложные структуры данных. Выравнивание границ данных
Статическое и динамическое связывание. Менеджеры памяти
Дисплей памяти процедуры (функции). Стековая
организация дисплея памяти
Исключительные ситуации и их обработка
Память для типов данных (RTTI-информация)
Генерация кода. Методы генерации кода
Общие принципы генерации кода. Синтаксически управляемый перевод
Способы внутреннего представления программ
Обратная польская запись операций
Оптимизация кода. Основные методы оптимизации
Общие принципы оптимизации кода
Оптимизация линейных участков программы
Другие методы оптимизации программ
Машинно-зависимые методы оптимизации
Контрольные вопросы и задачи
Вопросы
Задачи
Упражнения Глава 6. Современные системы программирования
Понятие и структура системы программирования
Понятие о системе программирования
Возникновение систем программирования
Появление интегрированных сред разработки
Структура современной системы программирования
Принципы функционирования систем программирования
Функции текстовых редакторов в системах программирования
Компилятор как составная часть системы программирования
Компоновщик. Назначение и функции компоновщика
Загрузчики и отладчики. Функции загрузчика
Библиотеки подпрограмм
Библиотеки подпрограмм как составная часть
систем программирования
Статические библиотеки подпрограмм
Динамические библиотеки подпрограмм
Ресурсы пользовательского интерфейса. Редакторы ресурсов
Мобильность и переносимость программного обеспечения
Разработка приложений в двухзвенной архитектуре
Принципы работы в двухзвенной архитектуре.
Простейшие двухзвенные архитектуры
Архитектура приложений «клиент-сервер»
Современные серверы данных. Язык SQL
Технологии доступа к серверам данных
Проблемы и недостатки архитектуры «клиент-сервер»
Разработка программ в многоуровневой архитектуре
Принципы разработки приложений в трехуровневой и
многоуровневой архитектуре
Серверы приложений. Методы доступа к серверам приложений
Организация взаимодействия приложений
в многоуровневой архитектуре
Возможности трехуровневой и многоуровневой архитектуры
Разработка программного обеспечения для сети Интернет
Особенности разработки программного обеспечения для сети Интернет
Разработка статических веб-страниц
Разработка динамических веб-страниц
Контрольные вопросы и задачи
Вопросы
Задачи
Ответы на вопросы и задачи
Указатель литературы
Алфавитный указатель
Перед вами русскоязычное издание бестселлера "Agile web development with Rails", написанного Д. Томасом - автором книги "Programming Ruby" и Д. Х. Хэнссоном - создателем Rails. Rails - это открытый фреймворк, который не просто позволяет создавать сложные и многофункциональные веб-приложения, но и делает их невероятно легкими. Полный код приложения, написанного на Rails, вполне может оказаться меньше, чем простой конфигурационный файл того же приложения, написанного с использованием другого фреймворка.
В работе изложены основы, касающиеся разработки, реализации и применения конструкций как императивных, так и функциональных языков программирования. Значительное внимание уделяется применению денотационной семантики, позволяющей в полной мере извлечь преимущества объектно-ориентированного подхода, что, в конечном счете, позволяет построить результирующую вычислительную модель чисто функционального типа.
