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