|
|
|
|
А.Ахо, Дж. Ульман
«Теория синтаксического анализа, перевода и компиляции», том 1 (М.: Мир, |
|
|
Посвящается Адриенне и Холли
ПРЕДИСЛОВИЕ Эта книга задумана как пособие для одно- или двухсеместрового курса лекций по теории компиляции для
студентов старших курсов. В ней дается теоретическая трактовка предмета,
имеющего практическое значение. При её написании мы исходили из следующих
трёх соображений. (1) В преподавании такой быстро развивающейся
области, какой является наука о вычислительных процессах, правильный
педагогический принцип состоит в том, чтобы больше внимания уделять идеям, а
не техническим подробностям реализации. Мы надеемся, что алгоритмы и понятия,
изложенные в этой книге, переживут следующее поколение вычислительных машин и
языков программирования и что хотя бы некоторые из них найдут применение не
только при построении компиляторов, но и в других областях. (2)
Прогресс в построении компиляторов достиг того этапа, когда компилятор можно
расчленить на много составных частей и каждую часть подвергнуть
запланированной оптимизации. Поэтому важно снабдить людей, предпринимающих
попытки такой оптимизации, подходящими математическими средствами. (3)
Для полного понимания некоторых из самых полезных и самых эффективных
алгоритмов компиляции (например, алгоритма LR (k)-анализа) требуется
основательная математическая подготовка. Мы полагаем, что хорошая
теоретическая подготовка становится всё более существенной для тех, кто
строит компиляторы. Включая
в книгу трудные теоремы, имеющие отношение к компиляции, мы старались сделать
изложение как можно более доступным. Для этого приводится много примеров,
причем в каждом из них используется какая-нибудь малая грамматика, а не те
большие грамматики, что встречаются на практике. Мы надеемся, что в тех
случаях, когда трудно следить за теоретическими построениями, для иллюстрации
основных идей этих примеров будет достаточно О пользовании книгой
Книга
возникла из записей лекций, прочитанных на старших курсах Принстонского университета
и Стивенсовского технологического института. По ним
читались как односеместровый курс, так и двухсеместровый. В первом случае курсу по теории
компиляции предшествовал курс теории конечных автоматов и
контекстно-свободных языков, поэтому не было необходимости излагать материал
гл. 0, 2 и 8. Остальные же главы излагались подробно. В
случае двухсеместрового курса большая часть
материала первого тома излагалась в первом семестре, а большая часть второго,
исключая гл. 8,— во втором. При этом доказательствам и технике доказательств
уделялось больше внимания, чем в одно-семестровом
курсе. Ясно,
что одни разделы книги более важны, чем другие. Поэтому нам хочется кратко
пояснить читателю, как мы оцениваем относительную важность различных частей
первого тома. Общее замечание состоит в том, что большинство доказательств,
по-видимому, можно пропустить. Мы включили доказательства всех главных
результатов потому, что считаем их необходимыми для глубокого понимания
предмета. Однако в курсах, посвящённых компиляции, обычно предпочитают не
особенно углубляться во многие вопросы, причем разумный уровень понимания
достигается при довольно поверхностном знакомстве с доказательствами. В
гл. 0 (математические основы) и 1 (обзор компиляции) почти весь материал
существен, за исключением, быть может, разд. 1.3, в котором рассматриваются
приложения синтаксического анализа, не связанные с компиляцией. Мы
считаем, что каждое понятие и теорема, введённые в гл. 2 (теория языков),
найдут применение где-нибудь в остальных девяти главах. Однако в курсе лекций
по компиляторам некоторый материал следует опустить. Подходящим кандидатом
для этого служит довольно трудный материал об уравнениях с регулярными
коэффициентами из разд. 2.2.1. Придётся опустить тогда часть материала из
разд. 2.2.2, касающегося праволинейных грамматик (а
результат об эквивалентности между ними и конечными автоматами вывести другим
способом), и материал из разд. 2.4.5 о преобразовании грамматики в грамматику
в нормальной форме Грейбах методом Розенкранца. Понятия,
излагаемые в гл. 3 (перевод), очень важны для остальной части книги. Однако
разд. 3.2.3 об иерархии синтаксически управляемых переводов довольно труден и
его можно опустить. Мы
думаем, что разд. 4.1 о методах разбора с возвратами менее важен, чем разд.
4.2, в котором рассматриваются табличные методы. Глава
5 (однопроходный синтаксический анализ) большей частью очень важна.
Максимальное предпочтение мы предлагаем отдать LL-грамматикам (разд. 5.1), LR-грамматикам
(разд. 5.2), грамматикам предшествования (разд. 5.3.2 и 5.3.4) и грамматикам
операторного предшествования (разд. 5.4.3). Другие разделы при необходимости
можно опустить Глава
6 (алгоритмы с возвратами) менее важна, чем большая часть гл. 5 или разд.
4.2. Если надо выбирать, то мы предпочли бы изложить разд. 6.1, а не 6.2.
Организация книги
Вся
книга состоит из двух томов:
|
|
|
|
|