Список рекомендуемой литературы

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.

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

Автомат (automaton, machine) [см. Распознаватель, Преобразователь] 23

- конечный (finite) 25 - 29, 30 - 34, 35 - 37

- - детерминированный (deterministic) 26 - 29

- - недетерминированный (nondeterministic) 26 - 29

А-грамматика [см. Грамматика автоматная] 12

Алфавит (alphabet) 5

- входной (input) [см. Символ входной] 23, 26

- выходной (output) [см. Символ выходной] 74

Анализ (analysis)

- синтаксический (syntactical, parse) [см. Разбор] 18, 57 - 59

- - восходящий (bottom-up) 69

- - нисходящий (top-down) 69, 70

Анализатор (parser)

- левый (left) 75 - 76

- правый (right) 76 - 77

А-язык [см. Язык автоматный] 12, 25, 48 - 49

Вершина (графа) (node, vertex) 16 - 18

Вывод (derivation) 6, 7

- левый (leftmost) 8, 68, 69, 75

- правый (rightmost) 8, 70

Грамматика (grammar) 4, 6, 11

- автоматная (automaton) 12

- - детерминированная (deterministic) 17, 29 - 30

- - недетерминированная (nondeterministic) 17, 29 - 30

- бесконтекстная [см. Грамматика контекстно-свободная] 12

- контекстно-зависимая(context-sensitive) 12

- контекстно-свободная (context-free) 12, 40 - 47, 68 - 72

- неоднозначная (ambiguous) 11, 60 - 62

- однозначная (nonambiguous) 11

- праворекурсивная (right recursive) 10

- регулярная (regular) [см. Грамматика автоматная] 12

- рекурсивная (recursive) 10, 60, 61

Граф (graph)

- переходов (автомата, грамматики) (transition) [см. Граф состояний] 16

- состояний (state) 16 - 18

Дерево (tree)

- вывода (derivation) [см. Дерево разбора] 10, 29, 40, 50, 70, 75

- разбора (parse) 4, 75

- синтаксическое (syntax) [см. Дерево разбора] 10

Длина (length)

- вывода (of a derivation) 9

- цепочки (of a string) 5

Дополнение (множества, языка) (complementation) 51, 53

Дуга (в графе) (arc, edge) 17

Замкнутость (относительно операций) (closure) 52, 53

Иерархия Хомского (Chomsky hierarchy) 11 - 13, 25

Итерация (языка) (closure) 51, 52, 54

КЗ-грамматика [см. Грамматика контекстно-зависимая] 12

Конкатенация (concatenation) 5, 51, 52, 54

КС-грамматика [см. Грамматика контекстно-свободная] 12, 40 - 47, 68 - 72

КС-язык [см. Язык контекстно-свободный] 12, 25, 49 - 51, 73

Магазин (pushdown list) 24, 63,

Метаязык (meta-language) 7

МП-автомат [см. Автомат с магазинной памятью] 25, 63 - 73

Нетерминал (nonterminal) 6, 8

- аннулирующий (nullable) 43 - 45

- начальный (starting) 6, 7

Обращение (цепочки или языка) (reversal) 5, 51, 52 - 53, 54

Объединение (union) 51, 52, 53

Основа (правовыводимой цепочки) (handle of a right sentential form) 10, 70

Память (распознавателя) (memory) 24

Пересечение (множеств, языков) (intersection) 51, 53, 56

Подстановка (языков) (substitution) 51, 52, 55

Правило (грамматики) (production) 6

Предложение (sentence) [см. Цепочка] 3, 5

Преобразователь (transducer) 24

- с магазинной памятью (pushdown) 73

- - - - детерминированный (deterministic)

- - - - расширенный (extended)

Продукция (production) [см. Правило (грамматики)] 6

Разбор (как синтаксический анализ) (parsing)

- восходящий (bottom-up) 69

- нисходящий (top-down) 69, 70

- с возвратами (backtrack) 77

Разбор (как результат синтаксического анализа) (parse) 75

- левый (left) [см. Вывод левый] 75

- правый (right) [см. Вывод правый] 75

Разность (множеств, языков) (difference) 51, 53

Рекурсия (recursion) 10, 46, 61, 62

Свертка (цепочки) (reduction) [см. Разбор типа “перенос-свертка”] 8, 70

Семантика (semantics) 4

Символ (symbol) 5

- бесполезный (в грамматике) (useless) [см. Тупик] 41 - 43

- вспомогательный [см. Нетерминал] 6

- входной (input) 23, 25, 63

- выходной (output) 74

- начальный (initial, starting) 6

- нетерминальный (nonterminal) [см. Нетерминал] 6

- терминальный (terminal) [см. Терминал] 6

Синтаксис (syntax) 4

Состояние (автомата, преобразователя, распознавателя) (state) 24, 25, 63

- допускающее (accepting) 26

- заключительное (final) [см. допускающее] 25, 26, 63

- начальное (initial) 25, 26, 63

- недостижимое (unreachable, extraneous) 33

- отвергающее (rejecting) 26

Форма Бэкуса-Наура (Backus-Naur form) 7

Цепочка (sequence, string) 5

- выводимая (sentential form) 4, 9

- допустимая (accepted) 25, 27, 64

- пустая (empty, null) 5

Эквивалентность (equivalence)

- автоматов (mashine) 27, 31

- грамматик (grammar) 9, 29, 40

Язык (language) 4, 6, 9, 25, 64

- автоматный (automaton) 12, 25, 48 - 49, 53 - 55

- ассемблера (assambly) 3

- бесконтекстный (context-free) [см. Язык контекстно-свободный] 12

- детерминированный (deterministic) 73

- естественный (natural) 3

- контекстно-зависимый (context-sensitive) 12, 25

- контекстно-свободный (context-free) 12, 25, 49 - 51, 52 - 53, 68 - 73

- неоднозначный (ambiguous) 4, 60, 61

- однозначный (unambiguous) 4

- программирования (programming) 3

- регулярный (regular) [см. Язык автоматный] 12

103