Составители:
6
грамматик и соответствующих им распознавателей. Главу 6 о машинах
Тьюринга в данном пособии можно рассматривать как факультативную,
поскольку эта тема традиционно излагается в курсе по теории алгоритмов.
Однако её материал необходим для понимания последующих глав 7 и 8, в
которых излагается связь языков типа 0 с машинами Тьюринга, и языков типа
1 — с линейно ограниченными автоматами. Несколько особняком стоит глава
9, в которой рассматриваются свойства замкнутости языков относительно
элементарных операций и отображений. Она дополняет главу 3, в которой
рассматриваются свойства замкнутости регулярных множеств.
Часть II посвящена описанию двух классов контекстно-свободных языков:
LL(k) и LR(k) ввиду их практической важности. Первый является наибольшим
естественным классом языков, допускающих детерминированный нисходящий
разбор посредством
k-предсказывающего алгоритма анализа. Второй
представляет столь же естественный класс языков, допускающих
детерминированный восходящий разбор посредством канонического
анализатора Д. Кнута. Тот и другой имеют линейную сложность по времени.
Как известно, метод Кнута используется в инструменте YACC — популярном
построителе синтаксических анализаторов, а также в более развитых
модификациях этого технологического средства. Фактически в них
используются
LR(1)-грамматики с дополнительными оптимизирующими
ограничениями — так называемые
LALR(1)-грамматики. Последние
обсуждаются в конце этой части. В части II рассматриваются также некоторые
классы синтаксически-управляемых трансляций с входными языками
упомянутых классов и соответствующие алгоритмы их реализации. Последние
описываются с достаточной для практики полнотой и обоснованием
корректности и оценок сложности.
В Приложении приводится краткая сводка алгоритмически разрешимых и
неразрешимых проблем, касающихся формальных языков. Она позволит
практикующему читателю сориентироваться, что возможно или невозможно в
мире формальных языков.
В пособии имеется достаточное число примеров, но нет задач и
упражнений. Автор надеется исправить этот недостаток, подготавливая к
изданию «Сборник задач и упражнений по теории формальных языков и
трансляций».
Автор признателен рецензентам: профессору И. Л. Братчикову из Санкт-
Петербургского государственного университета и доценту Ю. Л. Костюку из
Томского государственного университета — за критические замечания,
которые по возможности были приняты во внимание.
Особую благодарность хочется выразить профессору В. О.
Сафонову,
заведующему
лабораторией Java-технологии Научно-исследовательского
института математики и механики СПбГУ им. академика В. И.
Смирнова,
предоставившему технические средства для подготовки оригинал-макета
данного пособия.
Б. К. Мартыненко
Старый Петергоф,
Июнь 2002 г.
Страницы
- « первая
- ‹ предыдущая
- …
- 5
- 6
- 7
- 8
- 9
- …
- следующая ›
- последняя »
