Главная Промышленная автоматика.

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

Книга возникла из записей лекций, прочитанных на старших курсах Принстонского университета и Стивенсовского технологического института. По ним читались как односемсстровый курс, так и двухсеместровый. В первом случае курсу ио теории компиляции предшествовал курс теории конечных автоматов и контекстно-свободных языков, поэтому не было необходимости излагать материал гл. О, 2 и 8. Остальные же главы излагались подробно.

В случае двухсеместрового курса большая часть материала первого тома излагалась в первом семестре, а большая часть второго, исключая гл. 8,- во втором. При этом доказательствам и технике доказательств уделялось больше внимания, чем в одно-семестровом курсе.

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

В гл. О (математические основы) и 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. Синтаксический анализ (гл. О-6) и

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

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

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

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

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



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

ПРЕДВАРИТЕЛЬНЫЕ МАТЕМАТИЧЕСКИЕ СВЕДЕНИЯ

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

0.1. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ МНОЖЕСТВ

В этом разделе будет сделан краткий обзор некоторых из самых основных понятий теории множеств, таких, как отношения, функции, упорядочения, а также обычные операции над множествами.

0.1.1. Множества

В дальнейшем мы будем предполагать, что существуют объекты, называемые атомами. Этим словом обозначается первоначальное понятие,- иначе говоря, термин „атом" остается не определенным. Что называть атомом, зависит от рассматриваемой области. Часто бывает удобно считать атомами целые числа или буквы некоторого алфавита.

Мы будем также постулировать абстрактное понятие принадлежности. Если а принадлежит Л, то пишут аА. Отрицание этого утверждения записывается так: аА. Предполагается, что если а - атом, то ему ничто не принадлежит, т. е. ладля всех X из рассматриваемой области.

Будут также использоваться некоторые примитивные объекты, называемые множествами, которые не являются атомами. Если

Мы благодарны также Ханне Крессе и Дороти Лючиани чя то, что они великолепно напечатали рукопись. Кроме того мы выражаем признательность лабораториям компанией Бел™

с помошьТишх Р"™"- Она была ускорена

PDP 11 п°"fi*™"™? Т"" "числительной

Томпсоном Ра=Работаннои Деннисом Ричи и Кеннетом



Л - множество, то его элементы-это те объекты а (не обязательно атомы), ДЛЯ которых аА. Каждый элемент множества представляет собой либо атом, либо другое множество. Предполагается, что каждый элемент множества появляется в нем точно один раз. Если А содержит конечное число элементов, то Л называется конечным множеством, и часто пишут А = {а, а,.. • а„}, если а, ...,а„-все элементы множества Л и а-Фа для 1ф\. Заметим, что порядок элементов не играет роли. Можно было бы, например, написать Л - {а„, .... aJ. Мы резервируем символ 0 для обозначения пустого множества, т. е. множества, в котором нет элементов. Заметим, что атом тоже не имеет элементов, по пустое множество не атом и атом не является пустым множеством.

Утверждение Л = п означает, что множество Л имеет п элементов.

Пример 0.1. Пусть атомами будут неотрицательные целые числа. Тогда Л = {1, -12,3}, 4} - множество. Элементами А служат 1, {2, 3} и 4. Элемент {2, 3\ множества А сам является множеством, состоящим из атомов 2 и 3. Однако атомы 2 и 3 не принадлежат множеству Л. Можно писать Л {4, 1, 3, 2}}. Заметим, что :Л = 3. П

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

Пример 0.2. Только что отмеченное явление называется парадоксом Рассела. Пусть Р (X) -предикат „X не является элементом самого себя", т. е. ХХ. Тогда мы могли бы подумать, что можно определить множество Y всех тех X, для которых Р (Х) истинно, т. е. У состоит в точности из тех множеств, которые не являются элементами самих себя. Так как большинство обычных множеств не являются элементами самих себя, возникает искушение допустить, что множество Y существует.

Но если V существует, мы должны суметь ответить на вопрос: „Является ли Y элементом самого себя?" А это приводит к невозможной ситуации. Если У У, то Р (У) ложно, и К не является элементом самого себя по определению У. Отсюда невозможно, чтобы УУ. Допустим наоборот, что УУ. Тогда по определению У снова УУ. Мы видим, что УУ влечет УУу а УУ

влечет КК. Так как либо КК, либо УУ истинно, то эти утверждения истинны - ситуация, которую мы считаем невозможной. Единственный выход из положения состоит в том, чтобы предположить, что У не существует. □

Обычный способ избежать парадокса Рассела заключается в том, чтобы определять множества только с помощью предикатов Р (Х) вида „X принадлежит Л и Я, (X)", где А - известное множество, а Р -произвольный предикат. Если множество А подразумевается, то мы будем вместо „X принадлежит Л и Pi (X)" писать просто Pi(X).

Если Р (X) - предикат, будем обозначать множество объектов X, для которых Р (X) истинно, через {ХР(Х)}.

Пример 0.3. Пусть Р (X) - предикат „X - неотрицательное четное число", т. е. Р (X) имеет вид „X принадлежит множеству неотрицательных целых чисел и Pi (X)", где Pi (X)-предикат „X четно". Тогда Л ]Х Р (X)} будет множеством, которое часто записывают так: -jO, 2, 4, ..., 2п, ,..}. Если по ходу дела ясно, что речь идет о множестве неотрицательных целых чисел, то можно писать Л --jXIX четно}. П

Мы не останавливаемся здесь подробно на аксиоматической теории множеств. Интересующемуся читателю рекомендуем книги Халмоша [I960] и Суппеса [1960] (см. список литературы).

Определение. Говорят, что множество Л содержится в множестве В, и пишут Л 5, если каждый элемент из Л является элементом из В. Иногда в этом случае говорят, что В содержит (или включает) Л, и пишут ВА. Говорят также, что Л -подмножество В, а В-надмножество Л.

Если В содержит ) элемент, не принадлежащий Л, и ЛВ,

то говорят, что Л собственно содержится в В, и пишут ЛВ (или что В собственно включает Л, и пишут ВЛ). Можно

также сказать, что А - собственное подмножество В или что В - собстве?шое надмножество Л.

Два множества Л и £f называются равными, если А В п ВА.

Для того чтобы графически изобразить включение множеств, часто пользуются так называемыми диаграммами Венна. На рис. 0.1 показана диаграмма Венна для отношения Л<В.

) Русский термин „содержит" (и его производные) обозначает в силу традиции два разных понятия: множество В содержит множество А, т. е.

ВЭЛ, или ЛВ, и множество В содержит элемент Ь, т. е. ЬВ. Из контекста каждый раз ясно, о чем идет речь, н можно надеяться, что у читателя трудностей по этой причине не возникнет.-Ярц-и, ред.





[0] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101

0.4705