Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 95
Текст из файла (страница 95)
Теорема непосредственно следует из теоремы 5.!4, свойства Обратимосте и конструкции алгоритма 5.! 2. Детали доказательства оставляем в качестве упражне. ния. Е) 442 )4нтсресно изучить классы языков, порождаемых грамматикамн предшествования и грамматиками простого предшествования. Оказывается, каждый КС-язык, пе содержащий пустой цепочки е, определяется грамматикой предшествования, но не каждый такой КС-язык определяется грамматикой простого пред- шествования. Кроме того, для каждого КС-языка, не содержащего е, можно найти обратимую КС-грамматику без е-правил.
Таким образом, если от грамматик требуется, чтобы они были обратимыми и грамматиками предшествования, то это уменьшает их порождающую способность. Каждая грамматика простого предшествования является )-К(!)-грамматикой, но Е)1(!)-язык (ибг1'(г~» 1) () (60!1!'(г~ )1) не определяется никакой грамматикой простого предшествовапня (это будет показано в равд. 8,3). $.З,З. Грамматики расширенного предшестаоаания Отношения нредшествования Вирта — Вебера, определенные для нар символов, можно расширить на пары цепочек. Опреде- лим расширенные отношения предшествовапия — между цепоч- ками из гп символов и цепочками из и символов. Наше опреде- ление ориентировано иа некоторый подразумеваемый алгоритм разбора тина „перенос — свертка", Для понимания мотивов введения расширенного предшество- вапия Вспомним две роли, которые играют отношения предше- ствования в алгоритме типа „перенос — свертка".
(1) Пусть аХ вЂ” это т верхних символов магазина (причем Х вЂ” самый верхний) и агв — следующие и входных символов. Если аХ< ° аиг или ггХ ' аге, то а надо перенести в магазин. Если аХЕ агв, то надо сделать свертку. (2) Допустим, что ХР...Х,Х,— цепочка в магазине и а, а — необработанная часть входной цепочки в тот момент, когда вызывается процедура свертки (т. е. Х ...Х,) а,...а„). Если основой является ХА...Х„то нам хочется, чтобы было Хь уХ „т „...Х,„' Х,Х,, Х,а,...а„ для й > 1.» 1 и Х А... Х„, ( Х ...Х,а,...
а„„') Таким образом, процедура разбора для обратимой грамма- тики расширенного предшествовапия аналогична процедуре, соот- ветствующей грамматике простого предшествования Вирта — Ве- бера, за исключением того, что отношение предшествования между символами Х и )' определяется цепочками оХ и )'р, где 1 ) Прелиолаггем, что Х Х -г...Хгв!...вл-г — — ХгХг-! ° Хг-гг!ь если г~п, 4ЬЗ ГЛ, З. ОДНОПРОХОДНЫЙ СИНТАКСИЧЕСКИЙ АНАЛИЗ ВЕЗ ВОЗВРАТОВ 5.3. ГРАММАТИКИ ПРЕДШЕСТВОВАНИЯ и состоит из т — 1 символов, расположенных слева от Х, а р — из и — ! символов, расположенных справа от Р. Символы переносятся в магазин до тех пор, пока между цепочкой наверху магазина и оставшейся необработанной частью входной цепочки не встретится отношение '~. Тогда возвращаемся по магазину назад, проходя отношения '., пока впервые не встретится (. Между ( ° н ) лежит основа.
Эти замечания мотивируют следующее определение. Определение. Пусть 6::.=(Я, г', Р, 5) †приведенн КС-грам. матика без е-правил. Определим отношения (т, и)-предшествования (, ° н на множестве (!х)(!з.!! ф) х(!Х()г'(1(Ц)". Пусть 5 53" ~*,ХРХр, ХА,,Аа,... а, — произвольный правый вывод. Тогда (1) сх(!4, если сс состоит из последних т символов цепочки Х Хр, ... ХА, и либо (а) 5 состоит нз первых и символов цепочки ХА ...
Х,а, ... а, либо (б) Х,— терминал и рЕ Р!КБТ„(ХА... Х,а,, а ); (2) ы р для всех таких )! > !') 1, что а состоит из йослед- них т символов цепочки Х Х , ...Х, , и либо (а) р состоит из первых и символов цепочки ХрХТ Г ... Х,а, ... аа, либо (б) Х вЂ” терминал и рЕ Р1КЗТ„(Х,ХЗ, ... Х,а, ...
а,); (3) Х„Х„, ... Х,) а, ... а„, Будем говорить, что С вЂ” грамматики (т, и)-иредшеетвования, если 6 — приведенная КС-грамматика без е-правил и отношения (, ' и ) попарно не пересекаются. Из леммы 5.3 с очевид- ностью следует, что 6 — грамматика предшествоваиия тогда и только тогда, когда она — грамматика (1,1)-предшествования. Детали, связанные с концевыми маркерами, легко восстанавли- ваются.
При и=-1 условия (1б) и (26) не дают ничего нового. Заметим также, что если пересечение отношений ( и — ' непусто только за счет условий (1б) и (2б), все равно для такой грамматики расширенного предшествования найдется алгоритм разбора типа „перенос — свертка". Можно было бы дать более сложное, по менее ограничительное определение, по мы предпо- читаем оставить читателю в виде упражнения разработку такого класса грамматик. Изложим теперь алгоритм, вычисляющий отношения расши- ренного предшествования. Его, очевидно, можно применять и для вычисления отношений предшсствования Вирта — Вебера. 464 А лгоритм 5.13.
Построение отношений (т, и)-пред- шествования, Вход. Приведенная КСграмматика 6= (!х), г, Р, 5) без еправил. Выход. Отношения (т„и)-предшествования < °, " и > для грамматики 6, Метод. Начнем с построении множества Ф всех подцепочек длины т+и, которые могут встретиться в такой цепочке ахи, что 5 5$" =!>,ТААШ=Ф, схбсв и и=. Р(КЗТ„(ш).
Это осуществляется так: (1) Положим д'=(ф 5й" ', $ '5$"). Эти две цепочки в у' считаются „нерассмотренными". (2) Если 6 — нерассмотренная цепочка ИЗ,У, „рассмотрим" ее, выполнив следующие две операции. (а) Если 6 не имеет вида ссАх, где !х((и, то ничего не делать. (б) Если 6 —.яАх, !х)«=.и и АЕ11, то добавить к г", если их еще нет там, цепочки у, для которых в Р найдется такое правило р1- (), что у — подцепочка длины т+и цепочки ссбх.
Заметим, что так как 6 — приведенная грамматика, то !сфх~)т+и. Добавленные к Х цепочки считаются нерассмотренными. (3) Повторять |наг (2), пока в р" не останется нерассмотрен- ных цепочек. По множеству д' построим отношения (, ° и ): (4) Для каждой цепочки ыАу из еУ, для которой ~сс~=т, и для каждого правила А — р из Р положим сс<'6, где 6— первые и символов цепочки ()у либо р начинается терминалом и 6 Е Р(КЗТ„(~у). (5) Для каждой цепочки аАу из р, для которой )сс!=т, и для каждого правила А — р,Х1'р, из Р положим 6, ' б„где 6,— последние т символов цепочки сф,Х, а 6,— первые и сим- волов цепочки У(1,у, либо !' — терминал, а 6,:.—.=Уш для некото- рой цепочки сеЕ Р1КЗТ„, (!З,у).
(5) Для каждой цепочки схАШ из У, для которой ~св~ — и, и для каждого правила А — р из Р положим 6 >се, где 6— последние т символов цепочки ыр. 1) Пример 5.36. Рассмотрим грамматнсу 6 с правилами 5 — 05! 1) 011 Отношения (1,!)-предшествования для нее приведены на рис. 5.12. Так как ! )! и 1 1, то 6 не является грамматикой (1,1)-пред- шествования. С помощью алгоритма 5.!3 вычислим для С отношения (2,!)-предшествования. Начнем с вычисления У. Вначале З.Я.
ГРАММАТИКИ ПРВДШВСТВОВАНИЯ О 1 Ф 08 ГЛ. О. ОДНОПРОХОДНЫЙ СИНТАКСИЧГСКИЙ АНАЛИЗ ВЕЗ ВОЗВРАТОВ У=-(555, 555). Рассмотрим $55, добавляя к У цепочки $05, 051, 511, П$ (зто все подцепочкн длины 3 цепочки $05115) и 501, 011 (подценочки длины 3 цепочки 50115). Рассмотрение цепочки 555 приводит к добавлению 550, рассмотрение 505 добавляет ЬАОО, 005 и 001, рассмотрение 051 добавляет 1!1, и, о. О 1 Ф Рис, В.!2, Отношения (Ч,!)-преяшестооояния.
наконец, рассмотрение 005 добавляет 000. Вот все элементы множества У. Чтобы построить ск, рассмотрим цепочки из з' с 5 па правом конце. Получим 55(0, 50(0 н 00(0. Для построения снова рассмотрим такие цепочки и найдем 50 ' 5, 05 '.1, 51 '.1, 50 ' 1, 01 '.1, 00 ' 5 и 00 ' 1. с!тобы построить ), рассмотрим цепочки из д', у которых 5 в середине. Из 555 получится 11 ) $, а из 051 получится 11) Отношения (2,!)-предшествования для грамматики 6 приведены на рис. 5,!3. Цепочки длины 2, не принадлежащие Области определения отношений ', ( и ЗР, здесь опущены. Рнс. З, !3. Отношения (2,!)-предшествоиапия. Так как конфликтов между отношениями (2,!)-предшествования нет, то 6 — грамматика (2,1)-прсдшествоваиия.
[) Теорема 5.16. Алгоритм 5.13 правильно вычисляет отношения <~ и ) Д о к а з а т е л ь с т в о. Сначала покажем, что правильно определяется множество Ф, т, е, что у Е У тогда и только тогда, когда (у ~. т+и и у — подцепочка цепочки ари, где у"55"=:А*„аАв=Ф,а()!в и и=р1РЬТ„(ш).
Необходимость. Доказательство проводится индукцней по порядку, в котором цепочки добавляются к множеству У. Базис, когда в У содержатся только первые два элемента, получается сразу. Для доказательства шага индукции допустим, что у добавляется к У потому, что аАхс У н А 5ЕР, т. е. у — надцепочка цепочки ирх.
Так как аАх содержится в Т, то по предположению индукции существует вывод 5 55" =!>'„а'А'ш =::>„я'р'ио, где и=)т(РЬТ„(ш) и а'р'и можно записать в виде б,аАхб, для некоторых б, и б, из (5(ОХ(5))". Так как 6 — приведенная грамматика, то найдется такая цепочка у Е (Е О (5))*, что б,=-л" ,у. Таким образом, 5"55" ~,*б,аАхуо=>„б,а()хуш Так как у — подцепочка длины т+и цепочки ябх, то опа, конечно, является подцепочкой цепочки ирг, где г= Р1)!ЬТ„(хуи). Достаточность. Индукцией по й можно показать, что если 5 5$"=>»иАш=>,и()!е, то каждая подцспочка длины т-1-и цепочки а(ти содержится в У', где и=-Р!НЬТ„(ш). Из определения отношений (, ' н ) непосредственно следует, что они правильно вычисляются на шагах (4) — (6).
П Докажем теорему, которая лежит в основе анализатора типа ,перенос — свертка" для обратимых грамматик (т, и)-предшествования, аналогичного алгоритму О.12. Теорема 5.17. Пусть 6=(Г),г., Р, 5) — произвольная приведенная КС-граммагпика, т и и — целю числа и (5.3.!) 5'АЬф"=>„"Х Х, ... Х»+,Аа, ... а ~,Х Х,...
Х„»,Х» ... Х,а, ... а (!) Пусть р — Гп) !' > я, а — последние т символов цепочки ХРХР, ... Х,, и р — первь!е и символов цепочки Х Х,, ... Х,а,, а,. Тогда если 5 Е (А. О (Я)*, то либо и ( Р, либо а (2) Х +»Х» т Х»„(е'р), где Р состоит из первых п символов цепочки Л'»... Х а,, а . лвт ГЛ. б.
ОДНОПРОХОДНЫЙ СИНТАКСИЧЕСКИЙ ЛНАЛИЗ БЕЗ ВОЗВРАТОВ б.б. ГРЛММАТИКИ ПРЕДШЕСТВОВЛИИЯ (3) Луста 'я > 7' 1, и — последние т символов цепочки ХрХ,, ... Хт, и 5 — первые и. символов цепочки ХтХ Х,а, ... ар. Тогда бб,хаР. (4) Х„Х, ... Х,)а, ... ари Доказательство. Утверждения (2) — (4) непосредственно следуют из определений. Чтобы доказать (1), заметим, что так как !' > я, р состоит не только нз символов $. Поэтому вывод (5.3.1) можно записать в виде (5.3.2) 5"'В$" =>',7ВШ :=:>„уй,б„бе где ! — наибольшее из чисел, для которых Ьб~е в правиле В- б,б„нз В выводятся Х,+, и Хе и уЬ,=-ХрХр, ...
Х,, Есля первый символ цепочки бб терминальный, скажем б,=аб„то по правилу (2б) определения отношения ' имеем Х,„„Х,,, ... Хр„, ' (1, где !) =ах и х Е Е!ЕВТь,(б,бе). Если первый символ цепочки б, петерминальный, положим бе=65,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
