А.Ахо, Дж. Ульман

«Теория синтаксического анализа,

перевода и компиляции»,

том 1

 

(М.: Мир, 1978 г.)

 

 

 

Посвящается Адриенне и Холли

 

ПРЕДИСЛОВИЕ

 

Эта книга задумана как пособие для одно- или двухсеместрового курса лекций по теории компиляции для студентов старших курсов. В ней дается теоретическая трактовка предмета, имеющего практическое значение. При её написании мы исходили из следующих трёх соображений.

(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.

 

Организация книги

Вся книга состоит из двух томов:

I. Синтаксический анализ (гл. 0—6) и

II. Компиляция (гл. 7—11). (Во втором томе рассматриваются оптимизация анализаторов, теория детерминированного разбора, перевод, работа с таблицами и оптимизация кода.)

В конце каждого раздела (с номером i. j) приводятся упражнения, задачи и замечания по литературе. Задачи делятся на открытые и предлагаемые для дальнейшего исследования, а в упражнениях звёздочками указывается степень трудности. Для решения упражнения, помеченного одной звёздочкой, требуется одна существенная догадка, а для упражнения с двумя звёздочками — более чем одна.

Чтение курса по этой книге предлагается сопровождать лабораторными работами по программированию, в ходе которых должны быть спроектированы и осуществлены какие-то части компилятора. В конце некоторых разделов книги приведены упражнения на программирование, которые можно использовать в этих лабораторных работах.

 

Благодарности

Многие люди внимательно прочли различные части рукописи и серьёзно помогли нам при её подготовке к печати. Мы особенно хотим поблагодарить Джона Бруно, Стефена Чена, Джеймса Гимпеля, Дана Ихбиа, Брайана Кернигана, Дугласа Мак-Илроя, Роберта Мартина и Роберта Морриса, а также рецензентов Томаса Читэма, Майкла Фишера и Уильяма Мак-Кимана. Важные замечания сделали многие студенты, пользовавшиеся нашими записями лекций, среди них Алан Демерс, Нахед Эль Джабри, Мэтью Хехт, Петер Хендерсон, Петер Майка, Томас Петерсон, Рави Сети, Кеннет Силлз и Стивен Сквайрз.

Мы благодарны также Ханне Крессе и Дороти Лючиани за то, что они великолепно напечатали рукопись. Кроме того, мы выражаем признательность лабораториям компании „Белл телефон" за содействие при подготовке рукописи. Она была ускорена с помощью UNIX, операционной системы для вычислительной машины PDP-11, разработанной Деннисом Ричи и Кеннетом Томпсоном.

 

Альфред В. Ахо Джефри Д. Ульман

 

 

 

 

 

 

 

 

 

 

 

 

 



Используются технологии uCoz