- •Е.И.Чигарина, м.А.Шамашов
- •Isbn 978-5-7883-0506-6
- •Глава 1. Языки и грамматики. Обозначения, определения и классификация 6
- •Глава 1. Языки и грамматики. Обозначения, определения и классификация
- •1.1 Понятие грамматики языка. Обозначения
- •1.2. Классификация грамматик по Хомскому
- •1.3. Техника построения кс - и а - грамматик
- •1.4. Синтаксические деревья вывода в кс-грамматиках. Представление а-грамматик в виде графа состояний. Неоднозначность грамматик
- •1.5. Синтаксический анализ а-языков
- •Упражнения к первой главе
- •Глава 2. Распознаватели и автоматы
- •Глава 3. Автоматные грамматики и конечные автоматы
- •3.1. Автоматные грамматики и конечные автоматы
- •3.2. Эквивалентность недетерминированных и детерминированных а-грамматик
- •Упражнения к третьей главе
- •Глава 4. Эквивалентные преобразования контекстно-свободных и автоматных грамматик
- •4.1. Декомпозиция правил грамматики
- •4.2. Исключение тупиковых правил из грамматик
- •4.3. Обобщенные кс-грамматики и приведение их к удлиняющей форме
- •4.4. Устранение левой рекурсии и левая факторизация
- •Упражнения к четвертой главе
- •Глава 5. Свойства автоматных и контекстно-свободных языков
- •5.1. Общий вид цепочек а-языков и кс-языков
- •5.2. Операции над языками
- •5.2.1. Операции над кс-языками
- •5.2.2 Операции над а-языками
- •5.2.3. Операции над контекстными языками
- •5.3. Выводы для практики
- •5.4. Неоднозначность кс-грамматик и языков
- •Упражнения к пятой главе
- •Глава 6. Синтаксический анализ кс-языков
- •6.1.Методы анализа кс-языков. Грамматики предшествования
- •6.2. Грамматики предшествования Вирта
- •6.3. Грамматика предшествования Флойда
- •6.4 Функции предшествования
- •Упражнения к шестой главе
- •Глава 7. Введение в семантику
- •7.1. Польская инверсная запись
- •7.2. Интерпретация полиЗа
- •7.3. Генерирование команд по полиЗу
- •7.4. Алгоритм Замельсона и Бауэра перевода выражений в полиз
- •7.5. Атрибутные грамматики
- •Упражнения к седьмой главе
- •Глава 8. Основные фазы компиляции
- •Заключение
- •Приложение
- •Список рекомендуемой литературы
- •Чигарина Елена Ивановна
Список рекомендуемой литературы
1. Ахо, А. Теория синтаксического анализа, перевода и компиляции. Том 1. Синтаксический анализ/ А. Ахо, Д. Ульман. - М.: Мир, 1978.
2. Ахо, А. Теория синтаксического анализа, перевода и компиляции. Том 2. Компиляция/ А.Ахо, Д. Ульман. - М.:Мир, 1978.
3. Братчиков, И.Л. Синтаксис языков программирования/И.Л. Братчиков. - М.: Наука, 1975.
4. Гилл, А. Введение в теорию конечных автоматов/А.Гилл. - М.: Наука, 1966.
5. Гинзбург, С. Математическая теория контекстно-свободных языков/С.Гинзбург. - М.: Мир, 1970.
6. Гладкий, А.В. Формальные грамматики и языки/А.В.Гладкий. - М.: Наука, 1973.
7. Грис, Д. Конструирование компиляторов для цифровых вычислительных машин/Д.Грис. - М.: Мир, 1975.
8. Гросс, М. Теория формальных грамматик/ М.Гросс, А. Лантен. - М.: Мир, 1971.
9. Донован, Д. Системное программирование/Д.Донован.- М.:Мир, 1975.
10.Лебедев, В.Н. Введение в системы программирования/В.Н.Лебедев.- М.:Статистика, 1975.
11. Льюис, Ф. Теоретические основы проектирования компиляторов/Ф.Льюис, Д.Розенкранц, Р.Стирнз - М.: Мир, 1979.
12. Семантика языков программирования. Сборник статей.- М.:Мир,1980.
13.Шамашов, М.А.Теория формальных языков. Грамматики и автоматы. Учебное пособие./М.А.Шамашов.-Самара: Самарский муниципальный комплекс непрерывного образования «Университет Наяновой», 1996, 92 с.
14.Хантер, Р. Проектирование и конструирование компиляторов/Р.Хантер. – М.:Финансы и статистика, 1984.
15.Хомский, Н. Формальные свойства грамматик/Н.Хомский// Кибернетический сборник, новая серия - вып. 2. - М.: ИЛ, 1966.
16.Хомский, Н. Алгебраическая теория контекстно-свободных языков/ Н. Хомский, М. Шютценберже // Кибернетический сборник, новая серия, вып. 3. - М.: ИЛ, 1966.
17.Хопгуд, Ф. Методы компиляции/Ф. Хопгуд.- М.:Мир, 1972.
18. Форстер, Дж. Автоматический синтаксический анализ/Дж. Фостер.-М.:Мир, 1972.
19.Шамашов, М.А. Основные структуры данных и алгоритмы компиляции: учеб. пособие/М.А.Шамашов.- Самара: Научно-внедренческая фирма «Сенсоры, модули, системы», 1999. –115 с.
20.Шамашов, М.А. Синтаксический анализ автоматных языков. Метод. указания/ М.А. Шамашов, Л.Ф. Штернберг. - Куйбышев: КуАИ, 1990.
21. Штернберг, Л.Ф. Теория формальных грамматик/Л.Ф. Штернберг. - Куйбышев: КуАИ, 1979.
22. Языки и автоматы: сб. статей. - М.: Мир, 1975.
Учебное издание
Чигарина Елена Ивановна
Шамашов Михаил Анатольевич
ТЕОРИЯ КОНЕЧНЫХ
АВТОМАТОВ
И ФОРМАЛЬНЫХ ЯЗЫКОВ
Учебное пособие
Подписано в печать . Формат
Бумага офсетная. Печать офсетная. Печ. л.
Тираж Заказ ИП -76/2007.
Самарский государственный аэрокосмический университет имени академика С.П.Королева.
443086 Самара, Московское шоссе, 34.
Издательство Самарского государственного аэрокосмического университета.
443086 Самара, Московское шоссе, 34.