Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 55
Текст из файла (страница 55)
10.1.27. Запрограммируйте систему расстановки, использующую для разрешения конфликтов метод цепочек. Сравните понедеине этой системы и системы из упр. !0.1.26. Замечания по литературе Тэбээцы рэсстэээээ э>вест ы >в«ж эээ ~эйээцы с ?эсэрээюэээай пэцэыю, ключевые трвэсфэрмэцнаээыэ тэсллцы, случайные >вол цы э ~аолицы с э~лчэсээеыыцэ лэеысэтэыэ. Твйээпы расстановки эримеээлясь эрогрэымэстэыэ с эвчэээ 80-х голов. Сэцэя рвээлш гэботэ па вэрссэ» рэс. стээовээ ню>эсвэв 1!етерсоэом (1957). Хороший аоэор методов рвссыэовкэ эрээгдгя Моррисам (И081. У эсга же можэо найти ответ эв гэр. !О ! 7.
Методы эю>эсээээя зшрэчныэ фуээцэй тля гмээывеэиэ а>кяээемэго чэслэ эоэфлэк авоосгжэвютс» Мэгрср и !19081, Рээ э 1>97Щ э И .. (И701. Огэст эв Тэр. 10.1.10 мо>кэа найти 7 Рэдкэ 1!970!. В рзоо>е Ульыввв 119791 ээучээпсэ Ьрввэаыерэые сэс>емы гесс>ээоээи.
Харошэм сэрээочээкам ео эегезьяы эзанэцаго поиска н тволэцэы ?эсстэгюэээ яээяе>сэ гэбэ>э Кнута ! И731. 90.2. ГРАММАТИКИ СВОЙСТВ Интересный конструктивный метод присваивания свойств идентификаторам з яаыке программирования основан па формализме „грамматик свойств".
Это контекстно-свободные грамматики с дополнительными механизмами передачи информации >Л Э. ГЕЭММАТИКИ СВОЙСТВ об идентификаторах и обработки некоторых не контекстно-свободных аспектов синтаксиса языков программирования (такнл, как требование, чтобы идентификаторы были описаны раньше их >гсиользаяаиня). В этом разделе мы ладим зиедепис з теорию грамматик свойств и покажем, как с помощью грамматики сзоистн смоделировать синтаксическин анализатор, соединяющий з себе ргыбор с некоторыми аспектами сел>антнческаго анализа. тб.ТЗ. Мотипироака Попробуем понять сначала, почему не всегда бывает достаточно объзолсния идентификатора для того, чгобы установи> Все его свойства и поместить нх з ячейки таблицы имен, отведенные для этого идентификатора.
Если мы рассмотрим язык ввгвээ уэавв ! с блочной структу'рой (например, Алгол или ПЛ(1), то увидим, что своистза иден вювж Уэээв 2 тификатора могут многократно меняться, Дшл 1 Ээввц Выло 2 эвш>ю б>жв 4 ээээ 3 ! юлжг б>ээв 4 энэк гтввээ ! О Р эг 107 Пэ эээ ° гуэ- р . 10.8. Преэстэвээ.ээ О.„чэай структуры в >урэ эрогрэчцы эээе жгезэ.
погкальку его можно определить о охватывающем блоке н пер«определить Во внутреннем. Когда внутренний блок заканчивается, свойства становятся снова такими, какими оии быяи а охватывающем блоке. Рассмотрим, наприлгер, диаграмму на рис. !0.7, нзображаюплую блочную структуру программы. Буквы обозначают области действия в программе. Эту блочную структуру можно представить дерезолл на рис. 10.8. Предположим, что идентификатор 1 определен з блоке 1 этой программы и помещен з >аблицу' имен сразу, как только Встретился. Предположим, что после этого ! переопределен 293 гл ~ю. огглнизлция инеагмлции ыл гглммлтикгт свойств в блоке 2. В областях В, С н 0 этой программы для ! действует новое определение. Таким образом, встретив определение ! в блоке 2, надо внести это новое определение в таблицу имен. Однако нельзя просто заменить определение, которое была у 1 в блоке 1, назым определением в блоке 2, поскольку з области Е нада будет вернуться к первоначальному определению 1, Один из путей решения этой проблемы занлючается в том, что с каждыч определеаием идег!тификатора связываются два числа: номер уровня и индекс.
Номер уровня †э глубина вло. жеиности, н всем блокам с одним и тем же номером уровня даются различные индексы. Например, идентификаторы в аб. ластнх В и [) блока 2 имеют номер уровня 2 и индекс !. Идентификаторы з области Р блока 4 имеют номер уровня 2 и индекс 2. Если ссылна на идентификатор осуществляется в блока с уровнем ! и индексом /, то в таблице имен разыскивается определение этого идентификатора с тем же номером уровня и тем же индеисоч, Если, однако, в блоке с номерам уровня г идентификатор ие определен, то его определение надо искать в блоке с номером уровня ! — 1, содержащем блок с номером уровня г н индексом 1, и т.
д, Если определение появлялось на нужном уровне, но индекс слишком мзл,можно отбросить апре. деление, так как оно уже больше неприменима. Таким образом, для запоминания определений каждого идентификатора по мере нх появлений полезен магазин. Описанный поиск облегчается, если индекс текущего активного блока доступен на каждом уровне. Например, если идентификатор К встречается в области С но его определения там нет, надо взять его определение в нли [), если допускаются объявления после использования). сли же определения К нет ии в В, ни в Тг, надо взять'его в областях А, Е или 6.
Но нельзя искать определение К в об. лас~гг Р. Метод „уровень — индекс" работы с определениями годится для языков с принципом строгой вложенности областей действия определений (например, для Длгола н ПЛ)1). В этом рладеле, однако, иы изуч|ш более общий формализм, называемый грамматиками свойств, допускающий произвольные соглашения об области действия определений. Грамматикам свойств присущи общность н элегантность, вытекающае из единообразной трактовки идентификаторов и их свойств. Кроме того, обработку с их помощью можно осуществить за время, линейное относительно длины входного потока.
Константа пропорциональности может быть велика, но чы излагаем зту концепцию в надежде на то, что будущие исследования сделают использование грамматик свойств практически приемлемым. ?эл 10.?.2. Опредепенне грамматики свойств Неформально грамматику свойств лгожно определить как входную КС-грамматику, негерминальным и терлиинальным сии. валам котороа приписываются „таблицы свойств". Таблицу свойств можно рассматривать как абстракцию таблицы имен. Прн разборе снизу вверх в соответствии с входной грамма. тикай таблицы свойств, приписанные нстерииналам, представляют в данной точке разбора информапию, хранящуюся обычно в таблице имен Таблица свойств Т вЂ э отображение множества нндексов г' в множество свойств )Г, Множсством индексов у нас будет мно.
жсство неотрицательных целых чисел. Каждое целое число в множестве индексов можно интерпретиронать как указатель на таблицу имен. Таким образом, сели указываемый элемент таблицы имен представляет идентификатор, то целое можно трактовать как ния этого идентификатора. Множество )г †э множество „свойств", или „значений", н им у пас будет конечное множество пелых чисел. Одно из них (обычно 0) выделяется как „нейтральное" свойство. Остальные можно связать с различными свойствами, представляющими инте. рос. Например, число 1 можно связать со свойством „на этот идентификатор была ссылка", 2 — со свойством „обьязлеяное вещественное" и т д.
В таблицах, связанных с терминалами, все индексы, кроме одного, отображаются в нейтральное свойство. Этот один индекс мажет отображаться в любое свойство (в том числе н цейтраль. нос). Однако если терминалом является лексема <идентификаторы то ивдекс, представляющий имя конкретной лексемы (а именно, компонента данных этой лексемы), должен отображаться на свойстзо типа „это идентифииатор, >поминаемый здесь".
Например, если в программе встретилось объявленае геа) В, то эту цепо чку можно разобрать так: «збззйлсллгм [г:2] геа! «сьсэтввлгзягрьд1] где компонента данных лексемы <идентификатор) ссылается иа цепочку В. С терминалом <г!дентнфикатор> связана таблица [1; 1], отображающая индекс 1 (который соответствуег теперь цепочке В) в свойство 1 [возможна, „упомннаеьгый"), а остальные индексы в нейтральное свойство. Терминальная лексема геа! связана с таблицеи, отображающей все инденсы в нейтральное свойство.
Обычно гакая таблица явно не представлена. ГЛ 1О ОРГАНИЗАЦИЯ ИНФОРМАЦИИ С нетерминалом <объявление> в дереве разброса связывается таблица, получаемая слиянием по некоторому правилу таблиц прямых потомков этого нетермвнала. Н приведенном примере это твблица (1:2], отобража1ощая индекс 1 в свойство 2, а все другие индексы-в нейтральное свойство.
Тогда ее можно трантовать так, что идентификатор, связанный с индексом 1 (а именно, В), обладает свойством „объявленное вещественное". Вообще говоря, если в дереяе разбора есть структура А г ~сз. Г АммАтики свойств Вызсдимой Пеггочкой в 6 называется цепочка Х,Т,Х,Т,,Х„Т„, Где символы Х принадлежат М 02, а Т вЂ” таблицы свойств, Предполагается, что каждая таблица связана с символом непосред.
отвеяно слева от иее и представляет собой такое отображение множества индексов в У, чта все индексы, кроме конечного числа, отображаются в о,. Определим на выводимых цепочнах отношение ~о (или ~, если ясно, о какой грамматике идеть речь). Пусть ИАТЬ— выводимая цепочка в 6 и А Х, ... Х» — правило вывода р бр. Тогда ОАТб=зиХ,Т,... Х»Т»й, если для всех индексов г р (р, ТГ(!) Т,(1)... Т»(1)) =Т(1) д,х, «» т, Г, ... Г„ то свойство индекса 1 в таблице Т является функ цией только свойства индекса 1 в таблицах Тч Т„ .
.., Т», Иными словами, каждый индекс трактуетс я незя вйсг!мо от всех осталы1ых . Дадим теперь формальное оо ределение грамматики свойств . Определение . Грамматикой свойств вазывается восьмерка 6 = ( А, 2, Р , В, У, Оч Р, р), где (1) (М, 2, Р, В) — зходиая КС-грамматика, (2) У вЂ” конечное множество сзойстз, (3) О, Е У вЂ” я»утра»»ног свойство, (4) Рту — множество доиугтииат гзоште, о„всегда принадлежит Р, (5) р — такое отображение из Рху' в У, что (а) если значение р(р, А] определено, то длина правой части правила нывода р та же, что и у з, где з — цепочка свойств; (б) зиачеиве р(р, О»о» ... о,) равноо„ если длина цепочки нз нейтральных свойств а, та же, что и у правой части правила выпада р, и не определено в противном случае. Функция р говорит о том, каи выбирать свойства в таблицах, связанных с внутренними вершинами дерева разбора. В зависимости от правила вывода, использованного в этой вершине, свойство, связанное с каждым целым числом, вычисляется независимо от свойств всех других пелых чисел.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
