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