Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Подходящим кандидатом для этого служит довольно трудный материал об уравнениях с регулярными коэффициентами из равд. 2.2.1. Придется опустить тогда часть материала из разд. 2.2.2, касающегося праволииейных грамматик (а результат об эквивалентности между ними и конечными автоматами вывести другим способом), и материал из равд. 2.4.5 о преобразовании грамматики в грамматику в нормальной форме Грейбах методом Розенкранца. Понятия, излзгаемые в гл. 3 (перевод), очень важны для остальной части книги. Однако равд. 3.2.3 об иерархии синтаксически управляемых переводов довольно труден и его можно опустить.

Мы думаем, что равд. 4.1 о методах разбора с возвратами з менее важен, чем равд. 4.2, в котором рассматриваются табличные методы. Глава 5 (однопроходный синтаксический анализ) большей частью очень важна. Максимальное предпочтение мы предлагаем отдать 1.1.-грамматикам (разд. 5.1), Ьй-грамматикам (равд. 5.2), грамматикам предшествования (равд. 5.3.2 и 5.3.4) и грамматикам операторного предшествования (равд.

5.4.3). Другие разделы при необходимости можно Опустить. ! лава 6 (алгоритмы с возвратами) менее важна, чем большая часть гл. 5 нли равд. 4.2. Если надо выбирать, то мы предпочли бы изложить разд. 6.1, а не 6.2. Организация книги Вся книга состоит из двух томов: 1. Синтаксический анализ (гл. 0 — 6) и П.

Компиляция (гл. 7 — 11). (Во втором томе рассматриваются оптимизация анализаторов, теория детерминированного разбора, перевод, работа с таблицами и оптимизация кода.) В конпе каждого раздела (с номером ~'. 1) приводятся упражнения, проблемы и замечания по литературе. Проблемы делятся па открытые н предлагаемые для дальнейшего исследования, а в упражнениях звездочками указывается степень трудности. Для решения упражнения, помеченного одной звездочкой, тре.

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

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

Ахо Джефри Д. Ульиаи 6.1А. Множества Мы благодарны также Ханне Крессе и Доро Л ороти ючиани за то, что они великолепно напечатали рукопись. К вы ажаем п ись, ';роме того, мы о" р , ризнательность лабораториям компании „Б , ф н" за содействие при подготовке рукописи. Он б ии „елл теле- и. на ыла ускорена , операционной системы для вычислительной Томпсоном. машины РОР-!1, разработанной Деннисом Ричи и Кеннет еннетом о ПРЕДВАРИТЕЛЬНЫЕ МАТЕМАТИЧЕСКИЕ СВЕДЕНИЯ Чтобы говорить ясно и точно, нам нужен точный и правильный язык.

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

Читатели, знакомые с основами этих областей математики, могут только бегло просмотреть главу и использовать ее как справочник обозначений и определений. ОА. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ МНОЖЕСТВ В этом разделе будет сделан краткий обзор некоторых из самых основных понятий теории множеств, таких, как отношения, функции, упорядочения, а также обычные операции над множествами. В дальнейшем мы будем предполагать, что существуют объекты, называемые атомами. Этим словом обозначается первоначальное понятие, — иначе говоря, термин,„атом" остается не определенным. Что называть атомом, зависит от рассматриваемой области.

Часто бывает удобно считать атомами целые числа или буквы некоторого алфавита. Мы будем также постулировать абстрактное понятие принадлежности. Если а принадлежит А, то пишут аЕА. Отрицание этого утверждения записывается так: а ( А. Предполагается, что если а — атом, то ему ничто не принадлежит, т. е. х(а для всех х из рассматриваемой области. Будут также использоваться некоторые примитивные объекты, называемые множестеаии, которые не являются атомами. Если ГЛ. Ь. 'НвнднлпитвльнЫВ мятемятичесхие Сакле ния ол.

ОснОВнын. НОнятия теОРии мнОжеств А — множество, то его элементы — это те объекты а (ие обязательно атомы), для которых аЕ А. Каждый элемент множества представляет собой либо атом, либо другое множество. Предполагается, что каждый элемент множества появляется в нем точно один раз. Если А содержит конечное число элементов, то А называется конечным мноясеством, и часто пишут А= [а„а„... ..., а„), если а„..., а„— все элементы множества А и а; Фау для 1~1. Заметим, что порядок элементов не играет роли. Можно было бы, например, написать А = [а„, ..., а,). Мы резервируем символ )сз для Обозначения пустого множества, т.

е. множества, в котором нет элементов, Заметим, что атом тоже не имеет элементов, но пустое множество не атом и атом не является пустым множеством. Утверждение ЧР А = и означает, что множество А имеет и элементов. Пример 0.1. Пусть атомами будут неотрицательные целые числа.

Тогда А = (1,(2, 3), 4) †множест. Элемеитамн А служат 1, (2, 3) и 4. Элемент (2, 3) множества А сам является множеством, состоящим из атомов 2 и 3. Однако атомы 2 н 3 не принадлежат множеству А. Можно писать А==-(4, 1, (3, 2)), Заметим, что 4: А =3. () Один из полезных способов определения множества — определение с помощью предикота„т. е. утверждения, содержащего одно или несколько неизвестных и принимающего в зависимости от значений неизвестных одно из двух значений — истина или ложь, Множество, опрсделяемое с помощью предиката, состоит в точности из тех элементов, для которых предикат истннен.

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

е. У состоит в точности из тех множсств, которые не являются элементами самих себя. Так как большинство Обычных множеств не являются элементами самих себя, возникает искушение допустить, что множество У существует. Но если 1' существует, мы должны суметь ответить на вопрос; „Является ли ?' элементом самого себя?" Л это приводит к невозможной ситуации. Если У Е У, то Р (У) ложно, и У не является элементом самого себя по определению ?'. Отсюда невозможно, чтобы УЕ У. Допустим наоборот, что У( У. Тогда по определению У снова УЕ У, Мы видим, что У~У влечет У Е У, а УЕ 1' 12 влечет У~?'.

Так как либо 1" Е У, либо У(1' истинно, то оба эти утверждения истинны — ситуация, которую мы считаем невозможной. Единственный выход из положения состоит в том, чтобы предположить, что 1' не существует. Д Обычный способ избежать парадокса Рассела заключается в том, чтобы определять множества только с помощью предикатов Р(Х) вида „Х принадлежит А н Р, (Х)", где А — известное множество, а Р,— произвольный предикат. Если множество А подразумевается, то мы будем вместо „Х принадлежит А и Р, (Х)" писать просто Р,(Х). Если Р(Х) — предикат, будем обозначать множество объектов Х, для которых Р (Х) истинно, через ?Х(Р(Х)). Пример 0.3.

Пусть Р (Х) — предикат „Х вЂ” неотрицательное четное число", т. е. Р(Х) имеет вид „Х принадлежит множеству неотрицательных целых чисел и Р,(Х)", где Р, (Х) — предикат „Х четно". Тогда А =-(Х) Р (Х)) будет множеством, которое часто записывают так: (О, 2, 4, ... „2п, ...). Если по ходу дела ясно, что речь идет о множестве неотрицательных целых чисел, то можно писать А =-. (Х ) Х четно). Г') Мы нс останавливаемся здесь подробно на аксиоматической теории множеств. Интересующемуся читателю рекомендуем книги Халмоша [19601 и Суппеса [19601 (см.

список литературы). Определение. Говорят, что множество А содержилпся в множестве В, и пишут А~ В, если каждый элемент из А является элементом из В. Иногда в этом случае говорят, что В содержит (или включает) А, н пишут В о А. Говорят также, что А — подмножество В, а  — надмножествс А. Если В содержит') элемент, не принадлежащий А, и А с: — В„ то говорят, что А собственно содержится в В, и пишут А~~ В (нли что В собственно вклсочает А, и пишут В~~ А). Можно также сказать, что А — собственное подмножество В или что В— собственное надмножество А. Два множества А и В называются равными, если А с= В и В: — А.

Для того чтобы графически изобразить включение множеств, часто пользуются так называемыми диаграммами Венна. На рис. 0.1 показана диаграмма Венин для отношения А ~ В. ') Русский термин „содержит" (н его производные) обозначает н силу традиции дза разных понятня; множество В содержит ииожвсжво А, т. е. В ~ А, нлн А ~ В, н множество В содержит влвивнж Ь, т. е.

ЬЕВ. Из коитвкстз каждый ряз ясно, о чем идет речь, н можно недеяться, что у читателя трудностей по втой причине ое нозннкнет.— )?рии, ред. 15 гл. о. ИРадилритвльныв мятРмятическне свйдеиия ряс. 0.), Диаграмма Венка для включения множеств: А!=В. ОА.2. Операции ивд множествами Существует несколько основных операций над множествами, с помощью которых можно строить новые множества.

Определение. !!усть А и  — множества. Объединением множеств А и В (записывается А О В) называется множество, содержащее все элементы из А вместе со всеми элементами из В. Формально А О В= (х)хЕ А или хЕВ) '). Лересечением множеств А и В (записывается А П В) называется множество, состоящее из всех тех элементов, которые принадлежат обоим множествам А и В. Формально А ПВ==(х)хЕ А н хЕВ). Разностью множеств А и В (записывается А — В) называется множество тех элементов из А, которые не принадлежат В. Если А — множество всех элементов, рассматриваемых в данной ситуации (иногда его называют униеерсальным и обозначают через У), то разность (г' — В часто обозначается В и называется дополнением множества В.

Характеристики

Список файлов книги