Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 94
Текст из файла (страница 94)
Чтобы вычислить отношение (а, будем искать в правых частях правил пары смежных символов ХС. Тогда Х находится '1 Напомннм, что КС-грамматика С называегсн прнведепной, если в ней нег выводов вида А ~+ А, бесполезных снмволов н е-правнл, за нсключеннем, быть может, 3 — е, причем в атом случае 3 не встречается в правых частзх правая. ГЛ. 6. ОДНОПРОХОДНЫЙ СИНТАКСИЧЕСКИЙ АНАЛИЗ БЕЗ ВОЗВРАТОВ 6.6. ГРАММАТИКИ ПРЕДШЕСТВОВАНИЯ в отношении ( с каждым самым левым символом цепочки, не. тривиально выводимой из С.
(Читателю предоставляем разрабо. тать алгоритм для нахождения всех таких символов.) В нашем примере будут рассмотрены пары аВ и ВВ. В обоих случаях 8 а Ь в Ф Рнс. ос.11. Отношения предшестнонання. роль С играет В, причем нз В выводятся цепочки, начинающиеся символом а нли с. Поэтому Х()', где ХЕ(а, В) и !'Е а, с), тобы вычислить >, снова ищем в правых частях правил пары смежных символов, на этот раз вида СХ. Затем ищем символы )', которые могут оказаться на правом конце цепочки, выводимой из С за один или более шагов, и терминалы д, которые могут находиться в начале цепочки, выводимой из Х за нуль или более шагов. Если Х вЂ” терминал, то единственная возможность: Х =61. В данном примере парами такого вида будут $$ и ВЬ.
Поэтому У')д, где )'Е(Ь, с) и дЕ(а, с) для первого правила, 6( --Ь вЂ д второго. Подчеркнем, что атно!пения , ( н ) не обладают свойствами, которые обычно приписываются отношениям =-, ( и >, заданным на вещественных числах, целых и т. и. Например, обычно не является о|ношением эквивалентности, с и ), вообще говоря, не транзитивны, иа могут быть симметричными или рефлекснвными.
Так как в каждой ячейке матрицы на рис. 5.11 записано не более одного отншпения предшествования, то 6 — грамматика предшествования. Кроме того, правые части всех правил в 6 различны, так что 6 — грамматика простого предшествования, а Е (6) — язык простого предшествования. Рассмотрим праеовыводимую цепочку $ассЬ$ грамматики 6, ограниченную концевыми маркерами. Имеем з(а, а ° с и с)с. Основой цепочки ассЬ служит первый символ с, а отношения предшествования как раз и выделяют эту основу.
С) Всю существенную информацию, содержащуюся в матрице предшествования пхп, часто можно представить в виде двух п-мерных векторов, Такие представления матриц предшествования будут изучаться в разд. 7.1. Теорема 5.14, сформулированная ниже, показывает, что отношение с встречается в начале основы правовыводимой цепочки, отношение ' — между смежными символамн основы, а отношение ) — на правом конце основы. Это верно для любой грамматики без е-правил, но только в грамматиках предшествования любые два смежных символа активного префикса правовыводимой цепочки связаны ие более чем одним отношением предшествования.
Сначала выведем одно следствие из существования отношения предшествования для двух данных символов. Лемма 5.3. Пусть 6 =151, В, Р, В) — приведенная КС-граллатика без е-правил. (1) Если Х<~А или Х ' А и А — 1'а содержится в Р, п1о Х ° Г (2) Если А(а, А ' а или А)а и А — аУ содержится вР, то Уя)а. До к аз а тел ь ство. Мы докажем (2), а (1) оставим в качестве упражнения. Если А (а, то существует такая правая часть (5,АВ!о„что В ье ау для некоторой цепочки у. Так как А ~+ аК, то отсюда сразу получаем К >а. Если А ' а, то существует правая часть ~,Аале Поскольку а=>*а и А =>+ 661, отсюда снова получаем У'.>а.
Если А >а, то существует правая часть й,ВХй„ где В =О' уА и Х==,>*ад для некоторых у и д. Так как В=!> еуаК, то опять получаем нужное заключение. Теорема 5.14. Пусть 6=-(1ч, В, Р, Б) — приведенная КС-граго латика без е-правил. Если $$$ =:~„" ХРХр,... ХА„Аа,... ае =Ф„ХрХр,...ХАе,ХА...Х а,...а, (1) Х6„, (Х1 или Х,,е ' Х6 для р ( ! < й, (2) Х,, (Х, (3) Х;,, ' Х; для й > 1) 1„ (4) Х,я) а,.
Д о к а з а т е л ь с т в о. Доказательство проведем индукцией по п, Для п =-0 имеем $$$=ь,$ХА...Х $. По определению отношений предшествовання $(ХА, Х;, ' Х, для й) !)1 н Хе) $. Заметим, что Х„...Х, йе может быть пустой цепочкой, так как по условию в 6 нет е-правил. 459 ГЛ, З. ОДНОПРОХОДНЫЙ СИНТАКСИЧЕСКИЙ АНАЛИЗ БЕЗ ВОЗВРАТОВ З 3. ГРАММАТИКИ ПРЕДШЕСТВОВАН5555 Для доказательства шага индукции предположим, что тео рема верна для п. Рассмотрим вывод 555 =15," хр... х„,,Аа,, а Хр ХА.~.
ТХА Х 5а5 ач =Р,ХР Х,,);...);Х~ Г...Х,ат...а 5в котором на последнем шаге Х; заменяется цепочкой У;...)'о Поэтому ХГ „..., Х,— термийалы, причем случай 1=-1 не исключается. По предположению индукции Х, „,(ХГ или Х „' Х,. Поэтому ХГ„< ° )'„в силу леммы 5.3(1). К тому же Х~ находится в одном из трех отношений с символом справа от него (которым может быть и,).
Таким образом, 1',) Х,, либо )',)а; прп 1' =-!. Так как У,... !',— правая часть правила, то 1; ' 1;, ' ... ... ° 1;. Наконец, Хс„(Х; нли Х; „' Х, для р 5 ! по предположению индукции. Теорема доказана. Д Следствие 1. Если 6 — грамматика предшествования, то утверждение (!) теоремы 5.14 можно усилить„добавив слова „точно одно из отнои5ений ( или ' ".
Утверждения (1) — (4) можно усилить„добавив слова „и не выполняются никакие другие отношения", Доказательство. Непосредственно следует из определения грамматики предшествовання. Г Следствие 2. Каждая грамматика простого предшествования однозначна. Доказательство. Надо лишь заметить, что для любой отличной от 5 правовыводнмой цепочки р предыдущая право- выводимая цепочка а, для которой 5х=>,5, определяется Однозначно. из следствия 1 вытекает, что основу цепочки 5 можно однозначно определить, просматривая эту цепочку (ограниченную концевыми маркерами) слева направо, пока впервые не обнаружится отношение ЗР, а затем возвращаясь назад до ближайшего (, Основа лежит между ними, Так как грамматика простого иредшествования обратима, то нетерминал, к которому надо свернуть основу, находится однозначно.
Таким образом, и определяется по () однозначно. Гз Заметим, что так как мы оперируем с приведенными грамматиками, нетрудно доказать, что этот и последующие алгоритмь' тратят на разбор линейное время. Доказательства оставляем в качестве упражнений. Теперь опишем, как по грамматике простого предшествования строить детерминированный правый анализатор.
длго ритм 5.12. Построение алгоритма типа „перенос--свертка" для грамматик простого п р едГпествования. Вход. Грамматика простого предшествования 6=-(!А), л, Р, 5), в которой правила занумерованы числами от 1 до р. Выход. 4 =(1, у), алгоритм разбора типа „перенос — свертка" для грлммагики 6 Метод. (1) Алгоритм .4 использует символ 3 в качестве марксра дна магазина и правого концевого маркера входной цепочки. (2) Функция переноса 5' зависит только от верхнего символа магазина и самого левого символа необработанной части вход- ной цепочки. Поэтому зададим 5' только на (5) 0 г.
0 (5)) К(2 0 (5)), за исключением одного случая (правило (в)): (а) 1(Х, а) =перенос, если Х ° а или Х.'..а, (б) !" (Х, и) — --свертка, если Х) а, (в) 1(55, 5) =допуск' ), (г) ) (Х, а) =--ошибка в остальных случаях. (Правила реализуются с помощью матрицы предшествования.) (3) Функция свертки д зависит только от верхней части магазинной цепочки, вкл5очающей основу и еще один символ пнже нее. Оставшаяся необработанной часть входной цепочки иа д не влияет. Поэтому зададим у только на (!А)() 2 !1(3))*: (а) 3(Х „ХАХА,...Х„е) =5, если Хее,( ХА, Ху, ' Хг для к > 1) 1 и А — ХАХ„,...
Х,— правило с номером !. (Заметим, что функц55я и участвует только тогда, когда Х, ) а, где а — текущий входной символ.) (б) у(се, е)=ошибка в остальных случаях. Гз Пример 5,35. Построим алгоритм разбора типа „перснос— свертка" с1=-(Г, ф для грамматики 6 с правилами (1) 5 а555 (2) 5- с Отношения предшсствования для грамматики 6 приведены на рис. 5.1!. Функцию переноса !' можно вычислить с помощью матрицы предшествования.
Функция свертки у определяется так: (1) д(Ха555) =-1, если Х~ (5, а, 5), (2) 3(Хс) =2, если ХЕ (5, а, ф). (3) к (и) =ошибка в осталы5ых случаях. ') Заметим, что зте правило имеет приоритет иад правилами (2а) и (2О), когда Х=д и о=3 лв1 ГЛ. З. ОДНОПРОХОДНЫЙ СИНТАКСИг!ЕСКИЙ АНАЛИЗ БЕЗ ВОЗВРАТОВ З,З.
ГРАММАТИКИ ПРЕДВ!ЕСТВОВАНИЯ Для входной цепочки ассЬ алгоритм Л сделает такую последовательность шагов: ($, аалг$, е)) — '($а, ссЬ$, е) )-'($ас, с6$, е) ) — г($а5, с6$, 2) ) — *($а5с, 6$, 2) ! — '($а55, 6$, 22) ! — '($а556, $, 22) г ($5 $221) В конфигурации ($ас, с6$, е), например, будет 1(с, с) =свертка и д (ас, е) = 2. Поэтому ($ас, сЬ$, е)) — ($а5, с6$, 2) Посмотрим, как ведет себя А па цепочке асЬ, не принадлежащей языку С (6). Для этой цепочки алгоритм 2 сделает последовательность н!агов ($, ас6$, е) ! — '($а, с6$, е) г-'($ас, 6$, е) )-г($а5, 6$, 2) ( — ' ($656 $2) ! — ошибка В конфигурации ($а56, $, 2) будет 1(6, $)=свертка. Так как $< а и и ' 5 Ь, то свертку могкио сделать только, если а56 — правая часть какого-нибудь правила.
Однако такого правила пет, и поэтому д (а56, е) =-ошибка. На практике мы могли бы завести список „ошибочных правил", и всякий раз, когда с помощью функции д обнаруживается огпебка, можно было бы справиться в этом списке, нельзя ли сделать свертку с помощью ошибочного правила. Другие приемы исправления ошибок, ориентированные на разбор методом предшествовання, указаны в замечаниях но литературе в конце этого раздела, ( ) Теорема 5,15. Агггоритм 5.12 строит корректный алгоритм разбора типа „перенос — свертка" д гя грамматики простого пред- шествования. Доказательство.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
