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

Асрйео ч. дно Вся Тсгерропе Са»огауоигя гпе. Ипггау рнн, Н. !. Компиляция уерраеу о. пссидн Под редакцией В. М. Курочкина РгепНсе-На11, 1пс. Епя1есчоос1 С1Н12, М. 3. 1973 ТНЕ ТНЕОКУ ОГ РАМ$1ЯО, ТРА!»1$1АТ101»! АХО СОМРН.!уч!О чо!пепе ги СО!ПР!С!Исг Оерагспгеп! о! Егесрнса! Епфпеег!пр рггпсеоп оп!гогену А. АХО, ДЖ. УЛЬМАН ТЕОРИЯ СИНТАКСИЧЕСКОГО АНАЛИЗА, ПЕРЕВОДА И КОМПИЛЯЦИИ Том 2 Перевод с английского А.

Н. Бирюкова и В. А. Серебрякова ИЗДАТЕЛЬСТВО «МИР» МОСКВА 1978 УДЦ Ы6.662.!+66!.з42.2 ПРЕДИСЛОВИЕ О лользозаиии книгой Второй том фундэмеитзльной монографии известнмх вмери. кансках ученик посвящен мегодэм оптнмизз»гик синтаксических вввлизэторов, »сории сиитвкснчесии улрлвляемого переводе, в глюке способам орг'випээнии пэинти при переводе.

Большое виимэиие уделяется мстадэм оптнннвэпии объектной прсгрзммм. Автори проделали зиэчишльиую работу по отбору и системз»иванн многачислсинмх результатов, получеиемк з последние годм; оии сц»оят изложение оэ епипом подкоде к зла»чем перевода и зэдэчвм оптимизации прогрвммм Ци реднээнвченв тем, кто рэбответ в сблэсги сис»сивого и теоретического «рогрвммироввннн, преподаст илн нзучэет эти ди ю и и, а также рвэрвботчиивм мвтечэтвческого сбеспече. ния ЭВМ. Рмтоеиил литератррм ло ллтеллтммским павкам 26266-6!7 А, э7-76 ь! Перевод пв русский язык, *Мир», !буй Копструирооаигэе компиляторов — один из первых больших разделов системного программирования, которые получают сейчас строгое теоретическое обоснование.

В т. 1 этой книги изложены необходимые для такого обоснования сведения из математики и теории языков и основные методы проведения быстрого синтаксического анализа. Том 2 служит продолжением т. 1,но, эа исключением гл. 7 н 8, ои ориентирован на несинтаксические аспекты в конструировании компиляторов. Материал в т. 2 излагается в оснонном так же, как и в т. 1, ио доиазательства здес~ несколько более схематичны. Мы попыталась по возможности облегчить чтение, включив а книгу много првмеров, каждый из которых иллгострирует одно или два понятия.

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

Книга возникла на основе записей лекций, прочитанных на старших курсах Принстонского университета и Стивепсовского технологического института. Материал т. 2 использовался в Стивенсовском институтекак селгестровый курс конструирования компиляторов, следующий за семестровым курсом, основанным па т. 1, С точки зрения изучения конструирования компнлнторов одни разделы кяиги, как мы полагаем, важнее других.

Г1ри первом пьвдислознг Благадарнасши Альфред В. Ало Джефри Л, Улыбин чтении можно пропустить все доказательства, а также гл. 3 и равд. 7,4,3, 7.3,3, 9.3.3, 10.2.3 и 10.2.4. Как и в т. 1, в конце каждого раздела помещены задачи и замечания по литературе. Задачи, не являющиеся ни проблемами для исследования, пи открытыми проблемами, мы приблизительно упорядочили в соответствии с уровнем их сложности. Для этого пспользонали звездочки: упражнения, не помеченные звездочкой, служат для проверки понимания основных определений; лля решения упражнений с одной звездочкой требуется Одна существенная догадка, а упракчцеиия с двумя звездочками значительно сложнее.

В дополнение к благодарностям, выраженным в предисловии к т, 1, мы хотели бы иоблагодарнгь Карела Чулнка, Амелию Фонт, Майка Хаммера н Стива Джонсона за полезные замечания. МЕТОДЫ ОПТИМИЗАЦИИ 7 СИНТАКСИЧЕСКИХ АНАЛИЗАТОРОВ В щой главе ыы рассмотрим различные методы, с помощью которых можно уменьшать размер кении повышать скорость работы синтаксических анализаторов. Сначала исследуем вопрос об ул1еиьшенин объема памяти, требующейся для матриц предпчествоаания. Мы увидим, что в определенных случаях, среди когорых многие представляют практический интерес, матрицу предшествования размера тчен удается заменить двумя нектарами длины и и и соответственно.

Кроме того, покажем, как видоизменять матрицу прсдшествова. ния, не затрагивая построенный по ней алгоритм разбора типа „перенос †сверт". дателе мы опишем, как по грамыатике слабого предшсствоваиия можно механически получить синтаксический анализатор на языке Флойда †Эван, а потом рассмотрим различные, приемы, примекяемые для уменьшения размера полученного анализатора.

Наконец, подробно изучим различные преобразования, с помощью которых можно уменьшать размер С!Ваналнзатора без ослабления его способности обнаруживать ошибка. Детально исследуются метод „простых 1!!" Де Ремера и метод расщепления грамматики Кореньяка. Методы, описанные в этой главе, показывают, какие типы оптимизации возможны для а!гализаторов, построенкых с помощью приемов гл. 5 тома !. Возможны и многие другие типы оптимизации, по законченного „каталога" их не сушествуег Читателям, желающим получить только общее представление о методах оптимизации синтаксических анализаторОв, рекомендуем помещенный в канне главы обзор ее содержания. 7.1.

ФУНКЦИИ ПРЕДШЕСТВОЯДНИЯ Матрицу с элементами — 1, О, +1 или „пусто" будем называть мшприцзд лредшествоаания. Матрицы предшествования очеаилным образом применяются при построении алгоритмов т.ь еункиии прядшвствовани я — ! 0 '1 пусто с се с с ) с ошибкой а С с Ф ч С с 1 — 1 с переносом 0 с ошибкой +1 с сверткой 5 а Рвс. 7 э Матраиз ирчашество- эзиаа т. Рас 7.!. Ма~рииаотаачеыизареа- шестврваиия Вирте — Вебера. гл.

т.мктоды оптимизации синтлксичвских анализаторов разбора, используюших технику предшествования Например, можно применить матрипу предшествовання для представления отношений предшесгаования Вирта — Вебера для грамматики предшествоваиия, сопоставив Матрицей предшествования можно также воспольэоиаться для того, чтобы представить шаги алгоритма разбора типа „перенос †сверт". Одно из таких представлений можно получить, сопоставив В этом разделе мы покажем, как матрицу предшествоваиня часто удается представить в сжатой форме парой векторов, называемых функциями предшествоаания. 7.1.1. Теорема о прействвнеими матрицы Пусть М вЂ” матрица предшествоваиия размера тхгг.

Будем говорить, что пара (П д) вектороа с целочисленными компонен- талги прсдстааллет Л(, если (1) )=()» )„..., !.), (2) й=(йм йм "., й„), (3) )7(йг, если Мг — — — 1, )г=д, если М;7 — — О, )7) дг, если М,г — — -1-1. Можно испольэовать ) и д вместо М следующим обрааом. Для того чгобы опРеделить Мгм отыщем 7, и йм Если У, <йм П 7йт или ),)ди, положим Мгг — — — 1, 0 или и,-1 соответственно.

За. метим, что при таком использовании ) я й вместо М у матршгы ие будет пустых элементов, потому что между 77 н й, всегда выполняется одно из отношений (, —.= или ). Векторы ) в д будем называть функциями яредшествоааиил для М. Используя ) н й дтя представления М, можно сокра- тить объем памяти, требуюшейся для матрицы предшествования, с т Сся до т +а элементов.

Следует, однако, отметить, что не для всякой матрицы предшествования функции предшествования сугцествуют. Пример 7.1. Рассмотрим грамматику простого предшествования О с правилами 5 а5с(С5с)с Отношения предшествования Вирта — Вебера для атрипу нз брзжени ю на рис 71 Л(ыб)демначывзтьтмат рицед отяаимнгш' прсдигсствозаиия Вирта — Вебера, чтобы избежать путаницы с гермином „матрица предшествованая". Отношения иредшествовапня, показанные на рис. 7. 1, можно представить также в виде матрипы предшествования (рис.

7.2). Можно далее ! 7 3 4 С представить эту матрицу предшествования функциями предшествования 7'=(1, О, О, 2, 0) й = (О, 1, 1, 1, 0) Нетрудно убедиться, что шо действительно функции предшествования для М. Например, 7, =-2, й, =. 0 и, значит, поскольку (, ) йм ) и д действгтельпо представляют элемент Мм со значеннеы +!. Элемент Мм матрицы предшествованиа имеет значение „пусто". Однако (,=-.2, а й,=О. Таким образам, если мы будем использовать ) и й для представления М, надо будет заменить значение Ми на .1-1 (так как ), ) и).

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

шествоваиия. Но этв ошибка все равно выявится при попытке ГЛ. 7. МЕТОДЫ ОПТИМИЗЛЦИИ СИНТЛКСИЧССКИХ ЛНЛЛИЗЛТОРОВ выполнить свертку, когда окажется, что нет правила с такой правой частью, которая находится в верхушке магазина. Тем ие менее такая задержка в обнаружении Ошибки может окаааться неприемлемо дорогой платой за удобство использования функций предшествовання вместо матриц предшествоеания; это зависит от того, насколько важно раннее обиаружсние ошибки в коякретном компиляторе. С) Пример 7.2. Потерю возможностн своевременно обнаруживать ошибки можно в значительной степени компенсировать,построив дяя грамматики предшествоваиия алгоритм разбора типа „иеренос †сверт", в котором с отношениями су и ' будет связана г з а Ь с г а 3 а 4 с Рис.

7.3. Матраца арслшесглсзанаа ЫК операция перенос, а с отношением ) — операция свертка. Кроме того, для построения функции действия алгоритма разбора типа „перенос †сверт" требуются только отношения предшествовання с областью определеияя Х В 2 6(3) и множеством значений 26(3). Например, можно сопоставить се и с — 1, йл с ль! и получить из матрицы, приведенной на рис. 7.1, матрипу пред- шествования М'(рис. 7.3).

Пустые элементы обоэнача1от ошибочные ситуации. Можно показать, что векторы / = (О, О, О, 2, 0) и й = (1, 1, 1, 0] — функции предшествоваиня для М'. Э1и функции предшестаования обладают тем пренму7цеством, что для пустых элементов Мм, М„„М„И Мм обе имеют эначеняе 0 (/, -/,.:=/,=- =./7=27=0). Поэтому, обозначая нулем ошибочную ситуацию, мы сохраняем возможность обнаружения ошибки, заложенную в исходной матрице МС Подробнее мы рассмотрим зту проблему а равд.