Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 112
Текст из файла (страница 112)
Следовательно, если точка разделения по магазинам вышла нз 9,, до того, как построена цепочка ОО то она вышла и из фб „йрйчем в том же направлении. Принимая во внимание случай 1=2„в котором О,=ф, =-ху, получаем, что перед построением Ос и ф, точка разделения по магазинам находится либо (!) внутри О, и фс (н в обенх цепочках в одном и том же месте), т. е. цепочки О;, и фс, захватывают оба магазина, либо (2) справа от О,, и ф „ т. е.
Обе цепочки находятся в первом магазине. Заметим, что не может быть так, чтобы точка разделения находилась слева от О,, и ф, и все же на следующем такте эти цепочки изменились. Кроме того, число тактов между появ- леиием О,, и О, не может быть таким же, как между появлением ф,, н фо Нас не заботит время, которое точка разделения проводит вне этих подцепочек: цепочки могут изменяться только тогда, когда точка разделения возвращается в них. Отсюда следует, что так как О, ~~>,, первая свертка, затра- гивающая символ нз ф1 „должна также затрагивать хотя бы один снмвол вне ф, „т.
е. фб на самом деле не существует, нбо по определению цепочек О,„ 9„ ... свертка О; , к Ос затрагивае только символы из 9, , Если бы очередная свертка, затрагиваю щая ф, „ происходила целиком внутри ~р, „ то, согласно сде- ланным выше замечаниям (1) и (2), цепочка ф,, в результате должна была бы свернуться к О,, Исследуем отдельно случаи, зависящие от того, была ли а О,, свернута к Х подцепочка х НГили к Г" подцепочка у.
Случай 1." Сделаны обе свертки. Это невозможно, так как мы взяли 1«-.1'. Случай 2: Подцепочка у не была свернута к 1', х была свер- нута к Х. Здесь свертка кепочки фб, затрагивает символы в ф,, и вне ф,, Следовательно, точка разделения по магазинам на- ходится вйутрн О,, и ф, „и свертывается некоторый префикс обеих цепочек. Таким образом, для входной цепочки и анали- затор Т свертывает Х раньше К. Так как, по предположению, Т вЂ” корректный анализатор, то и имеет два разных дерева раз- бора, и, значит, грамматика 6 неоднозначная. На самом деле она однозначная, так что этот случай тоже можно отбросить.
бд. ВОСХОДЯЩИЙ РАЗВОР С ОГРАНИЧЕННЫМИ ВОЗВРАТАМИ Случай Зс Подцепочка х не была свернута к Х, а у была свернута к У. Тогда О,,=ОУ для некоторой цепочки О. Надо рассмотреть положение точки разделения по магазинам в двух подслучаях: (а) Если точка разделения лежит внутри 0;, и, значит, внутРи фс „ то Ф, может отличатьсЯ от Об только тогда, когда пРи свертке цепочки О;, свертывается ее префикс, а символ слева от О,, находится в отношении ~ с самым левым символом цепочки О,, Однако для ф,, выполняется отношение, так что происходит другая свертка.
Но тогда некоторые символы из ф, „которые уже должны быть свернуты к Х, свертываются вместе с некоторыми символами вне ф Р Эта возможность исключается тем же рассуждением, что в случае 2. (б) Если точка разделения лежит справа от О; „то префикс 8 может оказаться на верху первого магазина, только если )' подвергается свертке, так как единственный способ уменьшить длину первого магазина — свернуть его верхние символы. Но тогда прн обработке и к тому моменту, когда х свертывается к Х, 1' уже будет свернут.
Но Х н У должны свертываться одновременно в единственном дереве вывода цепочки и. Итак, в этом случае мы тоже вынуждены заключить, что либо Т не корректный анализатор, либо 6 не однозначная грамматика. Случай 4б х не свертывается к Х и у не свертывается к )'. Здесь надо применить одно из рассуждений, использованных в случаях 2 и 3.
Таким Образом, мы исключили все возможности и можем сделать вывод, что для грамматики Колмерауэра множество (А()р*р)+ должно быть пустым. [.] т Покажем, что если в КС-грамматике 6 есть символы Х и 1', Зля которых Хр+р)' и Х)б).*У", то она не может быть грамматикой Колмерауэра. Лемма 6.8.
Пусть 6=(Х, 2, Р, 5) — такал КС-грамматика, что Хр'р)' и Х)А)м) для некоторых Х и 1' из г) 02. Тогда 6 не является грамматикой Колмерауэра. Доказательство. Доказательство, аналогичное, к сожалению, доказательству леммы 0.8, оставляется в качестве упражнения. Так как Хр'р)', в Р найдется такое правило А- а2)'р, что 2=~'и'Х. Так как Хр),*У, в Р найдется такое правило  — ТХСб, что С=О* 1'б'. Поскольку грамматика 6 приведенная, можно найти такие цепочки и и О из языка 1.
(6), что каждый вывод цепочки и включает правило А — а2)7 и вывод цепочки и'Х из Я, а каждый вывод цепочки о включает  — ТХСЬ и вывод цепочки 1'б' иэ С. В любом случае из Х выводится какая-то цепочка хЕ 2* и из 1' — какая-то цепочка убей'. 18' азу Гл. 6. АДГОРитмы РАВБОРА с ОГРАниченными БозвРАТАми Как и в лемме 6.8, надо следить за тем, что произойдет с подцепочкой ху цепочек и и о. Для и окажется, что Х придется свернуть раньше, чем 1', а при обработке о либо Х и 1' свертываются одновременно (если С =ь" 3'6' — тривиальный вывод),.: либо 1' свертывается раньше Х (если С~' 1'6').
С помощью рассуждений, аналогичных проведенным в лемме 6.8, можно доказать, что если цепочки, и которым свертывается ху в цепочках . и и о, различны, то либо первый, либо второй вывод не может идти правильно. г) Итак, условия р й р'р)+ = 8 н р'рйрк*= гР1 необходимы для ' того, чтобы 6 была грамматикой Колмерауэра.
Перейдем теперь к доказательству того, что вместе с однозначностью, приведенностью и обратимостью эти условия также и достаточны. Лемма 6.10. Пусть 6=(1«, о, Р, 3) — приведенная КС-грамматика. Тогда если 66Х)'(3 — любая выводимая цепочка этой грамматики, то Хр'рк")г. Доказательство. Элементарная индукция по длине вывода цепочки МХЕ~3.
О Лемма 6.11. Пусть 6=(Р(, Е, Р, Б) — однозначная приведенная КС-грамматика, при«гм р й р*р) " = 1О и рзрй р1*= 8. Если и)'Х,... ХД3 — вьиодимая цепочка этой грамматики, то из условий Х,рХ„..., Хь,рХА, )'р*р1 +Х, и Хьр+р).'Я следует, что Х, ... ХА — составляющая цгпо«ки 66);Х, ... Хьор. Д о к а з а т е л ь с т в о. Если бы это было не так, то в а)'Х,... Х,Д1 нашлась бы другая составляющая, содержащая Х,.
Случай 1: Допустим, что все символы Х„..., Х, входят в эту другую составляющую. Тогда в нее входит либо 1', либо Х, так как она не совпадает с Х,...ХЗГ Пусть входит 3', Тогда 61. УрХ,. Но Ур'рк+Х, и потому рйр"рк+~ 8. Если входит 2 то Хэрру. Но по условию также Хьр'р),*У. Если Х" содержит хотя бы одно вхождение ), т. е. Хьр'рй'У, то рйр'р)."~Я. Если А* не содержит ни одного вхождения А, то Хьр+рЯ. Так нак Хэрру, то ХАр).*Я и потому р+р йр)*~ 8.
Случай 2: Х, для некоторого ! ( ~ <й входит в эту составляющую, а Х„, не входит. Пусть эта составляющая сверты- 1 вается к А. Тогда, применяя лемму 6.10 и выводимой цепочке, к которой свертывается и)гХ, ... ХД3, получаем Ар'рА*Хг„и, значит, Хгр+р1."Хг„. Но уже было ХгрХ6„, так что либо р й Р'р)" Ф 8* либо р р й р) *Ф Ы в зависимости от того, нуль Ь или более раз входит й в А' в выражении р~рА'. 1) Лемма 6.12. Пусть 6=(г(, г., Р, 5) — однозначная, приведенная и обратимая КС-грамматика, для которой р й р'р) '=1д' и р+ р й рк' = Яз. Тогда 6 — грамматика Колмграуэра.
1 6л. ВОсхОдящий РАВБОР с ОГРАниченными ВОВВРАтАми Дока з а тел ь ство. Зададим отношения предшествования Колмерауэра: (1) Х 1' тогда и только тогда, когда ХрУ, (2) Хчя У' тогда и только тогда, когда Хр),' 3' либо Х=$, 3'Ф$, (3) Х) У' тогда и только тогда, когда Х~8 и 3'=$ либо Хр'рХ") „но ХрА."3' не выполняется. Легко показать, что эти отношения не пересекаются. Если ° й(ФЕ1 или ' П)чьо, то р.йр*р) "Фо или рйр'р=о, и тогда рй'йрчр~ 8. Если (й~~ Яз, то Хрк~у'. Но Хр)+3" не выполняется. Ясно, что все три пересечения отношений пусты. Допустим, что индуцированный этими отношениями двухмагазиниый анализатор Т содержит правило (1'Х,... Х„, Х)— (3, АЯ).
Тогда 3'( Х, и потому 3'=- $ или Ур).'Хо Но Х; ' Х;„, для 1: ( < )6, так что ХгрХ„,. Наконец, ХА) Х, и поэтому Я=6 или ХАр'рА'с. Если )'Фб и ЯФ~, то, согласно лемме 6.11, если хранящаяся в двух магазинах цепочка выводима в грамматике 6, Х,... Х„будет ее составляющей. Со случаями К=6 и 2=$ справиться легко, и потому можно заключить, что каждая свертка, проделанная анализатором Т над выводимой цепочкой, дает выводимую цепочку. Таким образом, достаточно показать, что, начиная работать с цепочкой в из языка Е (6), анализатор Т будет продолжать делать свертки, пока не свернет го к 5.
По лемме 6.1(), если Х и 1 †смежн символы выводимой цепочки, то Хр'рк*)'. Поэтому верно какое-нибудь из соотношений ХрУ, Хр'р1, Хр) ~У или Хр+р) 63'. В любом случае Х и 1' находятся в одном из Отношений предшествования Колмерауэра. Индукцией по числу тактов анализатора Т можно показать, что если Х и Г' — смежные символы в первом магазине, то Х ( 1 или Х ' У. Доказательство по существу состоит в том, что Хи У могут оказаться смежными, только если 1 переносится в первый магазин в тот момент, когда Х вЂ” его верхний символ.
Но правила анализатора Т таковы, что Х( 1' или ХИВАМ. Так как й остается во втором магазине, в нем всегда есть пара смежных символов, находящихся в Отношении ). Таким образом, если анализатор Т еще не достиг конфигурации Ц, 85, и), он делает переносы до тех пор, пока верхние символы первого и второго магазинов не окажутся в отношении ). В этот момент становится возможной свертка, поскольку между символами первого магазина никогда не выполняется отношение >, Т делает ее и продолжает работу. () ГЛ Е АЛГОРИТМЪ| РАЗБОРА С ОГРАНИе|ВИНЫМИ ВОЗВРАТАМИ эиивживиии Теорема 6.6, Грамматика яглягтгя грамматикой Колмграуэра тогда и только тогда, когда она однозначная, приведенная, обра- тил|аЯ и !А ПР')А? + =Р+!АП~й'= З'. Д о к а з а т е л ь с т в о. Непосредственно следует из лемм 6.8, 6.9 и 6.12.
П а г ь л! Рнс. 6.4. Отношения предшествования Колмерауэра, Пример 6.!6. В примере 6.15 мы видели, что грамматика Я вЂ” аЯА ( ЬЯА ) Ь, А — а удовлетворяет нужным условиям. Лемма 5.12 подсказывает, что для этой грамматики отношения предшествования Колмерауэра определяются так„как показано на рнс. 6.4. УПРАЖНВНИЯ 6.2.1. Какие из следующих разборов являются нисходящими для грамматики бч? Какая выводится цепочка (если таковая существует)? (а) (1,0)(3,2) (5,4) (2,0)(4,2) (2,5) (4,0) (4,5)(6,5) (6,2) (6,0). (б) (2,0) (4,0) (5,0) (6,1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
