Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 57
Текст из файла (страница 57)
Затем во внутреннем блоке идентификатор 1 по. средством сил!волов (аЬе( [1:2] и йо!о [1:4] соответственно объявлен и используется как метка (что законно), а ндензнфикатор 2 посредством символа а [2:3] используется как переменная. На рис. 10.9 приведено дерева разбора с таблицами, связанными с каждой вершиной. Т) Понятие грамматики свойств можно обобщить. Например, (1) отображение р можно сделать иедетерминированиым, т.
е. дапуститзм что р (р, ю) — аодмножество множества У, (2) можно не предполагать наличия нейтрального свойства, (3) можно наложить ограничения на класс таблиц, связаниык с символами; например, можно ие допускать наличии полностью нейтральных таблиц. Некоторые теоремы о грамматиках свойств в этой более Общей формулировке изложены в упражнениях. Объявленные идентификаторы передаются в (список Объявлений>. (11) (список объявлений) е Р (25, 5! Здесь та же ситуашзя, что и в правиле (9).
Теперь приведем пример построения таблиц снизу Вверх на дереве разбора. Таблицу, которая индексу 1, присваивает свойство о для 1щ ]щ и, а всем остальным ийдексалз--нейтральное свойство, будем обозначать [Г,:ом г„:ом ..., („:Р„]. 303 19.3.3. Ревннзацня грамматик свойств Рассмотрим реализацию грамматики свойств для случая, когда входная К<)грамматика допускает детерминированный восходящий разбор с помощью алгорнтматипа „перенос — свертка", Нисходящий разбор или применение других алгоритмов раабора, Изложенных а зтай книге, приводит к тем же проблемам согласования при конструировании таблиц, что и при построении цепочек переводов в ОУ-переводе.
Поскольку их решение а основном то же, чта и в гл. 9, мы рассмотрим только восходящий разбор. В нашей модели компилятора вход для лексического анализатора не имеет таблиц, связанных с его терминалами. Будем предполагать, что лексический анализатор сигнализирует о том, является ли выбранная лексема идентификатором или зв !О э гп»мм»тики сВОйстВ «ряен > беде и < епиепя ерэпрпенки" ~! . Еее!в »покоя пбъяряпное> <еппопя опероюорор> <опере ор> [гиЯ [из) ! ! соперопюр.. епипоя переменюю. [2:2! [1'х! с еэон> с опиши мромоннмк.
а Ьп~рю <оппоон олопляояео> <щоео» ыороюоргл мюг е р:г,г;з[ Б:г,г:21 Н:4) ! ! <опере<яр -"О)'О !эЬе! сспимнппремеяими. селищ»перемен»и». и Пм! Ьючй <епнооя око»ляпкин> < оппппн пперпюорм> е и [1'1, 2:11 П:3, 2'3) е сгппщн опероюорпи опере»юр. Рюс. !0.9. Дерееп Эеэблра с гпбпияаюя. нет. Таким образом, каждая лексема, будучи входом прн раз. боре, имеет одну нз двух таблиц — либо полностью нейтральную, либо таблицу, в которой один индекс обладает не иейтральпым свойством. Поэтому мы будем считать, что еще необработанный вход вообще не имеет таблиц, и онн строятся, когда символ передается в магазин.
Будем также предполагать, чта таблицы не влияют на разбор, пе считая случая ошибки, когда разбор надо прервать. Таким образом, механизмом разбора будет нормальный механизм типа „перенос †сверт", причем к каждому символу магазина будет добавляться указатель на таблицу свойств этого элемента. Пусть в верхушке магазина находится [В, Т,1[С, Те[ и выполняется свертка в соответствии с правилом А ВС.
Наша задача заключается в том, чтобы быстро и проста по Т, и Т, построить таблицу, связанную с А. Поскольку бзльш!!яство индексов в таблице отображается в нейтральное свойс!во, желательна помещать в нее только те индексы, которые обладают не нейтральным свойством. Схема обработки таблиц будет реализована так, чтобы все операции по обработке таблиц и запросы о свойстве данного индекса можно было выполнить эа время, фактически пропорциональное числу операций н запросов. Естественно предположи!ь, что число запросов в таблицы пропорциональна длине входа. Предположение корректно, если разбор детерминированный, поскольку число выполняемых сверток (а следавател!и!о, и число слияний таблиц) в этом случае пропорционально длине входа. Б то же время разумный алгоритм перевода нс дошкен осуществлять запросы свойств более чем фиксированное число раз на одну свертку.
1[алее мы будем считать, что в нашей грамматике свойств входная КС-грамматика имеет нормальную форму Хамского. Обобщения алгоритма вынесены в упражнения. Будем предпо. лагать, что в любой таблице свойств каждый индекс (идентификатор), обладающий не нейтральным свойствам, занимает позицию в таблице расстановки, и что можно создавать структуры данных иа элементарных единиц, называемых ячейками. Каждая ячейка имев! форму ДАННОЕ! .. ДАННОЕт ... УКАЗАТЕЛЕИ ... УКАЗАТЕЛЬ» т.
е. состоит из одного или более полей, каждое иэ которых может содержать некоторые данные илн указатель на друг)ю ячейиу. Я чейки понадобятся при построении связных списков ГЛ. 1 ° . ОРГАНИЗАЦИЯ ИНФОРМАЦИИ 10 т. ГРАИИАтики сэоистэ Предположим, что У состоит из й свойств. Таблица свойств, связаиаая с символам грамматики, расположенным в магазине, представляется структурой данных, состоящей не более чем из А снискал свойств и из списка пересечений. Каждый список свойств начинается с заголовка слиасо свойств. Список пересечений начинается с зпголоело списка лересечеиий.
Эти заголовки связаны так, как зто показано иа рис. !0.10. 3 темене могпгнне Унпгпае в дпгонодон епщнп пелеещеннр Зогонодно слоеной едонсмд Рпс. 10.10, Элеие«п иагплппа сп с«руктурпй, прело«леле~лжей тлблппу свойств. Заголовок списка свойств имеет три поля: СВОЙСТВО РАЗМЕР СЛЕДУКУШИЙ ЗАГОЛОВОК Заголовок списка пересечений абдер«кит только указатель на первую ячейку списка пересечеаий. Каждая ячейка синопов свойств и списков пересечений называется индексной ячеикой. Итщексиая ячейка состоит из четырех полей с указателями: Предположим, что Т вЂ” таблица свойств, связанная с символом в магазине.
Тогда Т будет представляться р списками свойств, где у — число различных свойств в Т, и одним списком пересечений. Для каждого индекса в Т, обладающего не нейтральным свойством /, есть одна вндексная ячейка в списке свойств, на. чинающемся с заготовка списиа свойств для свойства 1.
Индексные ячейки, обладающие одинаковым свойством, объ. еш1нецы в дерево'1, корнем которого служит заголовок для этого свойства. Первый укаватель в индексной ячейке †э указатель па ее прямого предка в этом дереве. Если индексная ячейка принадлежит списку пересечений, то вторым указателем в ней является указатель на следующую ячейку списка пересечений. Если ячейка не принадлежит списку пересечений, то этот указатегш пуст. Два остальных указателя связывают индексные ячейка, представляющие один и тот же индекс, но в различных таблипал свойств. Предположим, что ЗТеуТ«ВТ«п прелставляет такую цепочку таблиц я магазине, что каждая из таблиц Т„Т, и Т, содержит индекс «с ие нейтральным свойством и все таблицы в а, В, у и б дают индексу ! нейтральное свойство.
Если ближе всех к верхушке магазина расположена таблица То то индексная ячейка С„предсгавлшощая 1' в Т„будет содержать в третьем поле указатель на позицию таблицы имен для «. Четвертое поле в С, содержит указатель на ячейку С, в Т„представляющую !. В С, третье поле содержит указатель на С„а четвертое поле содержит указатель на ячейку в Т„ представлявшую !. Таким образом, на индексные ячейки налагается дополнительная структура: все индексные ячейки, предстаоля«ощие один и тот же индекс во всех таблицах в магазине, помещаются в двунаправленный списан, пачииающийся с элемента таблицы расстановки для этого индекса Ячейка размещается в списке пересечений таблип тогда и только тогда, когда какая-нибудь таблица, расположенная над ней в магазине, ииеет индексаую ячейку, представляющую тот же индекс. В приведенном выше примере ячейка С, будет в списке пересечение для Т,.
Пример 1О.!О. Предположим, что в магазине находится символы грамматики В и С, причем С вЂ” в верхушке магазина. Пус«ь с этими злементамм связаны соответственно таблицы Т,.— !! о,, 2'о„б:о„, 6:о,, В:о«Д Т, =2«о„З; о„й«о„б«о„у: о„й«о,1 Возможная реализация этих таблиц показана иа рис. 10.11. Кружочка««и указаны инлексные ячейки. Чнсло внутри кружочка — это индекс, представляемый ячейкой. Связи списка пересечений указаны пунктиром. Отметим, что список пересечений самой нервней таблипы пуст по определению, а список пересечений таблицы Т, состоит из иидексныл ячеек для индексов 2, «! Структур» этого дерева будет ясзл ип ачгпритил 1О.З. — Прим лонго. зау ГЛ М, ОГГЛНИЗЛЦИЯ ИНЕОРМЛЦНИ м г гелммлтнки сзапств 5 н 8.
Ссылки на таблицу расстановки и на вчейкн, предсгап. лающие одни н тот же индекс в прутик таблицах, указаны шгриховымн линиями. Во избежание путаницы оип показаны только для индексов 2 и 3. Е) мигигй )айииеи имен Ряс гп.г!. Рлллизлпия тлблнп свойств. 1(рсдположим, что в процессе разбора нада в магаанне свериугь ВС в Л. Надо вычислить таблицу Т для г) по таблицам 7', и Т, для В и С соответственно.
Поскольку С вЂ” верхний силгвол магазина, список пересечений таблицы Т, содержит в точности те гшдексы, которые обладают ое цейтральаым свойствам в сбспх таблипах Т, и Т, (отсюда и название „список пересечений"). Эти индексы мы рассмотриы позднее. Индексы, не принадлежащие списку пересечений 7'„обладают нейтральным свойствам по крайней мере в одной из таблип Т, или Т„. Таким образом, ик свойство в Т есть функция только зов их одного не нейтрального свойства.
Если отвлечься от индексов из списка пересечений, то структуру данных, представляюгцую таблицу Т, можно построить, комбинируя различные леревья из Т, и Т,, После того как это сделано, каждый элемент списка пересечений для Т, рассматривается отделы!о, и из пего делается ссылка на спответствующую ячейку таблицы Т. !!режде чем формализовать эти адси, отметим, что хотелось бы, чтобы на практике свойства можно было разбить на непересекающиеся подмножества так, чтобы (г могкпо было представить в виде ))г Х р, Х ... Х ри для некоторого относительно большого и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
