WI. p. rtjUFfliMbt РДЗБЦРД С ОГРАНИЧЕННЫМИ ВОЗВРАТАМИ

нельзя установить, является ли произвольная КС-грамматика грамматикой Колмерауэра, не зная заранее, что она однозначная.

Определение. Пусть G -(N, S, Р, S) -КС-грамматнка. Определим три новых отношения Х („слева"), \i. („смежность") и р („справа") на Nu2. Для всех X, KNuS и 4€N положим

(1) ЛХК. если в Р есть правило Л--Уа,

(2) Хц.К, если в Р есть правило Л-»-аХУр,

(3) ХрЛ, если в Р есть правило Л-«-аХ.

Как обычно, для каждого отношения R обозначим \} R

и - и R- Напомним, что и R* удобно вычислять с по-мощью алгоритма 0.2.

Заметим, что отношения предшествования Вирта - Вебера

и •> на N и 2 можно определить через ц и р:

(1) <=p?t .

(2)=L = fi,

(3) > = p+p?.»n(Nu2)x2.

Остальную часть этого раздела посвятим доказательству того, что однозначная приведенная КС-грамматика G обладает отношениями предшествования Колмерауэра тогда и только тогда, когда

(1) p + nnt4>-0.

(2) \хГ\р*ц%-=0.

Пример 6.15. Рассмотрим предыдущую грамматику

SaSA\bSAlb Л-а

Для нее

?. = {(5.о), (S, £>), (Л, А)} ji-{(a,5), (S, Л), {b,S)\ р-{(Л, 5), (6,5), (а, Л)] р-р = {(Л, Л), (&, Л), {а. А]}

рХ*-{(а, 5), (5. Л), (&, 5), (а, а), (а, ft), (S, а), (6, а), (К Ь)} р*цХ+ = {{а, а), {а, Ь), ф, а), (6, Ь), (5, а), (Л, а)}

Так как ррПр?* 0 и р*рХ+П р= 0, эта грамматика обладает отношениями предшествования Колмерауэра; мы их уже видели на рис. 4.3. П

Покажем теперь, что если грамматика G содержит такие символы X и У, что ХрУ и Хр*рХУ, то она не может быть

1) Заметим, что здесь X и К обозначают определенные вхождения этих символов в выводы, т. е. конкретные вершины дерева вывода. Мы надеемся, будет ясно, чтб именно имеется в виду.

Грамматикой Колмерауэра. Здесь X и К не обязаны быть различными.

Лемма 6.7. Пусть G -(N, 2, Р, S)-грамматика Колмерауэра с отношениями предшествования Колмерауэра Л, « •>. Если ХрУ, то ХУ.

Доказательство. Так как грамматика G приведенная, существует вывод,, в котором применяется правило Л-«-ссХУр. При разборе цепочки wL{G), в выводе которой встречается это правило, цепочка аХУр в какой-то момент окажется на верху первого магазина и свернется к Л. Это может произойти, только если X Л У- □

Лемма 6.8. Пусть G = (N, 2, Р, 5)-такая КС-грамматика, что Хр*р>.+У U ХрУ для некоторых X и У аз Nu 2. Тогда G не является грамматикой Колмерауэра.

Доказательсто. Предположим, что G-грамматика Колмерауэра. Пусть <•, и •> - отношения Колмерауэра для этой грамматики и Т-индуцированный ими двухмагазинный анализатор. Так как G предполагается приведенной, найдутся такие д; и у из 2*, что X и У=*у. Так как ХрУ, существуют правило Л->-аХУ)3 и такие цепочки w, w, и из 2*, что S=*-WyAWi=WyaXym*WyW.XywW/y=*WyWxyww Так как Хр*р?.+У, существует такое правило B~yZC6, что 2=*уХ, С Уб, и для некоторых г, га, и z

S =Ф* zBz =Ф zyZCbz =>* г1ууХУббг, ZyZXyzz =>* ZyZxyzz

По лемме 6.7 можно считать, что X JY. Посмотрим, как анализатор Т обрабатывает две цепочки u - WyWxyww и v = ZyZxyzz. В частности, проследим за цепочками, к которым свертываются х и I/ в каждом разборе, и выясним, появляются эти цепочки в первом магазине, во втором или же они как-то разделены по магазинам. Пусть 6, б, ...-последовательность цепочек, к которым свертываетсяxi/ в цепочке м, ijj, lig,.---аналогичная последовательность для цепочки v. Мы знаем, что найдется такое число /, что Оу = ХУ, так как в силу предположенной однозначности грамматики X и У при свертке цепочки и должны свертываться одновременно. Если iljO,- для 1"/, то в тот момент, когда У подвергается свертке при обработке цепочки v, стоящий слева X тоже будет свернут, так как XХ.У• Но этого не может быть, так как С=> Уб для некоторого б в выводе

цепочки £7).

Поэтому Предположим, что для какого-то наименьшего </ либо 91>/, либо ij?,- не существует {потому что следующая свертка символа из затрагивает также символ вне il),). Мы знаем, что если / > 2, то точка, делящая цепочку на две части, расположенные в разных магазинах (назовем ее точкой разделения по магазинам), занимает одну и ту же позицию в G, i и Б после того, как-б,., и построены в результате свертки. Следовательно, если точка разделения по магазинам вышла из G,. i до того, как построена цепочка 6,-, то она вышла и из ,-1, причем в том же направлении. Принимая во внимание случай t=2, в котором ± = 1 = ху, получаем, что перед постро-етшем и точка разделения по магазинам находится либо

(1) внутри G и lj:,- (и в обеих цепочках в одном и том же месте), т. е. цепочки 6 i и% 1 захватывают оба магазина, либо

(2) справа от 8,- , и т. е. обе цепочки находятся в первом магазине.

Заметим, что не может быть так, чтобы точка разделения находилась слева от 6y i и и все же на следующем такте эти цепочки изменились. Кроме того, число тактов между появлением 0,. , ив, не может быть таким же, как между появлением г?, ] и Нас не заботит время, которое точка разделения проводит вне этих подцепочек: цепочки могут изменяться только тогда, когда точка разделения возвращается в них.

Отсюда следует, что так как 6,-4г?,., первая свертка, затрагивающая символ из ypi-i, должна также затрагивать хотя бы один символ вне Pi-i, т. е. \pi на самом деле не существует, ибо по определению цепочек Gj, Э, ... свертка 8,- i к Э, затрагивае только символы пзО, ,. Если бы очередная свертка, затрагиваю щая происходила целиком внутри i-i, то, согласно сде-

ланным выше замечаниям (1) и (2), цепочка ф,. в результате должна была бы свернуться к 6,.

Исследуем отдельно случаи, зависящие от того, была ли в 0, j свернута к X подцепочка х и/или к К подцепочка у.

Случай t: Сделаны обе свертки. Это невозможно, так как мы взяли tj.

С.1учай 2: Подцепочка у не была свернута к У, х была свернута к X. Здесь свертка цепочки затрагивает символы bi) i и вне i-i- Следовательно, точка разделения по магазинам находится вну.трн 9 з и и свертывается некоторый префикс обеих цепочек. Таким образом, для входной цепочки и анализатор Т свертывает X раньше У. Так как, по предположению, Г -корректный анализатор, то и имеет два разных дерева разбора, и, значит, грамматика G неоднозначная. На самом деле она однозначная, так что этот случай тоже можно отбросить.

Случай в: Подцепочка х не была свернута к X, а i/ была свернута к У. Тогда 8. = 6К для некоторой цепочки 8. Надо рассмотреть положение точки разделения по магазинам в двух подслучаях:

(а) Если точка разделения лежит внутри G„j и, значит, внутри то -ф,- может отличаться от 6,-только тогда, когда при свертке цепочки 8, свертывается ее префикс, а символ слева от G,. i находится в отношении <• с самым левым символом цепочки G . Однако для выполняется отношение так что происходит другая свертка. Но тогда некоторые символы из которые уже должны быть свернуты к X, свертываются вместе с некоторыми символами вне Эта возможность исключается тем же рассуждением, что в случае 2.

(б) Если точка разделения лежит справа отб.., то префиксе может оказаться на верху первого магазина, только если У подвергается свертке, так как единственный способ уменьшить длину первого магазина -свернуть его верхние символы. Но тогда при обработке и к тому моменту, когда х свертывается к X, К уже будет свернут. Но X и К должны свертываться одновременно в единственном дереве вывода цепочки и. Итак, в этом случае мы тоже вынуждены заключить, что либо Т не корректный анализатор, либо G не однозначная грамматика.

Случай 4: х не свертывается к X и I/ не свертывается к У. Здесь надо применить одно из рассуждений, использованных в случаях 2 и 3.

Таким образом, мы исключили все возможности и можем сделать вывод, что для грамматики Колмерауэра множество цПр*р должно быть пустым. □ т

у Покажем, что если в КС-грамматике G есть символы X и К, лля которых Хр+К и XVy, то она не может быть грамматикой Колмерауэра.

Лемма 6.9. Пусть G==(N, 2, Р, S)-такая КС-грамматика, что Хр+рК и ХцХ*К для некоторых X и К мз Nu2. Тогда G не является грамматикой Колмерауэра.

Доказательство. Доказательство, аналогичное, к сожалению, доказательству леммы 6.8, оставляется в качестве упраж-иення. Так как Хр+лК, в Р найдется такое правило Л-ccZKp, что 2=>аХ. Так как X\iX*y, в Р найдется такое правило В - уХСб, что С=>*К6. Поскольку грамматика G приведенная, можно найти такие цепочки п и у из языка L{G), что каждый вывод цепочки и включает правило Л-»-ceZKp и вывод цепочки ссХ из Z, а каждый вывод цепочки v включает В-уХСЬ и вывод цепочки Кб из С. В любом случае из X выводится какая-то цепочка xS* и из К-какая-то цепочка

Как и в лемме 6.8, надо следить за тем, что произойдет с подцепочкой ху цепочек а и у. Для и окажется, что X придется свернуть раньше, чем К, а при обработке v либо X и У свертываются одновременно (если С =>* Уб-тривиальный вывод),, либо К свертывается раньше X (если С=>+Кб). С помощью: рассуждений, аналогичных проведенным в лемме 6.8, можно до--казать, что если цепочки, к которым свертывается ху в цепочках и и V, различны, то либо первый, либо второй вывод не может идти правильно. □

Итак, условия р П р>?+ = 0 я р+р п t?* 0 необходимы для того, чтобы G была грамматикой Колмерауэра. Перейдем теперь к доказательству того, что вместе с однозначностью, приведенностью и обратимостью эти условия также и достаточны.

Лемма 6.10. Пусть G-(N, 2, Р, S) -приведенная КС-грамматика. Тогда если аХУлюбая выводимая цепочка этой грамматики, то Хр*рХ*К.

Доказательство. Элементарная индукция по длине вывода цепочки аХКр. □

Лемма 6.11. Пусть G -{N, 2, Р, S)-однозначная приведенная КС-грамматика, причем р П р>?* = 0 w р+р П р?* = 0. Если аУХу ,.. XfjZ - выводимая цепочка этой грамматики, то из условий XipXa, ....Xfe ipXfe, Kp*pX + Xi и Xjp-iiXZследует, что Xj ... Xft-составляющая цепочки аУХ ... Х2р.

Доказательство. Если бы это было не так, то в аКХ ... XftZp нашлась бы другая составляющая, содержащая Xi.

Случай 1: Допустим, что все символы Хд, ..., Х входят в эту другую составляющую. Тогда в нее входит либо К, либо Z, так как она не совпадает с Xi...X. Пусть входит У. Тогда KpXj. Но Кр*рХ+Х, и потому рПр>?т0. Если входит Z, то XftpZ. Но по условию также Xftp + p?i*Z. Если X* содержит хотя бы одно вхождение \, т. е. Xp+pX+Z, то р П р*р?" =7 0. Если Х* не содержит ни одного вхождения %, то Xp+pZ. Так как XjpZ, то Xfep?.*Z и потому р+рПр>*0.

Случай 2: X,- для некоторого 1 г < й входит в эту составляющую, а Ху не входит. Пусть эта составляющая свертывается к А. Тогда, применяя лемму 6.10 к выводимой цепочке, к которой свертываетсяctKXi ... XftZp, получаем Лр*рЯ*Х1 и, значит, X,-p+pX*X,-+i. Но уже было X,-pX ,i, так что либо р П рр?" 0, либо р+рПр?*т0 в зависимости от того, нуль или более раз входит X в X* в выражении р+рХ*. □

Лемма 6.12. Пусть G = {H, 2, Р, S)-однозначная, приведенная и обратимая КС-грамматика, для которой рПр*р = 0 ррП(л*0. Тогда G-грамматика Колмерауэра,

Доказательство. Зададим отношения предшествования Колмерауэра:

(1) ХУ тогда и только тогда, когда ХрК,

(2) Х<»К тогда и только тогда, когда ХрХ"К либо Х==$,

Уф%.

(3) XJ>K тогда и только тогда, когда Х=$ и К = $ либо Хр+рХ*К, но Хр?.+ К не выполняется.

Легко показать, что эти отношения не пересекаются. Если П<$¥=0 или Л •> =7 0, то рЛр*1А?т0 или рПрМ = 0, и тогда к*{]{>\1ф0. Если <J П > =7 0, то ХрХ+К. Но Хр-К не выполняется. Ясно, что все три пересечения отношений пусты.

Допустим, что индуцированный этими отношениями двухмагазинный анализатор Т содержит правило (KXj ... Xj, Z) (К, ЛZ). Тогда K<Xi и потому К--$. или Ур+Х. Но X,-=Xj-+i для 1</<А, так что X,pX, ,i. Наконец, X>>Z, и поэтому Z = $ или XfcppX*Z. Если УФ% и Z, то, согласно лемме 6.11, если хранящаяся в двух магазинах цепочка выводима в грамматике G, Xi ... Х будет ее составляющей. Со случаями У = % и Z~% справиться легко, и потому можно заключить, что каждая свертка, проделанная анализатором Т над выводимой цепочкой, дает выводимую цепочку.

Таким образом, достаточно показать, что, начиная работать с цепочкой W из языка E{G), анализатор Т будет продолжать делать свертки, пока не свернет mj к 5.

По лемме 6.10, если X и К-смежные символы выводимой цепочки, то Xp*pi*K. Поэтому верно какое-нибудь из соотношений ХрК, Хр+рК, ХрХ+К ИЛИ Хр + рХ+К. В любом случае X и К находятся в одном из отношений предшествования Колмерауэра.

Индукцией по числу тактов анализатора Т можно показать, что если X И У-смежные символы в первом магазине, то X <• К или X К. Доказательство по существу состоит в том, что X и У могут оказаться смежными, только если У переносится в первый магазин в тот момент, когда X-его верхний символ. Но правила анализатора Т таковы, что Х<*К или ХУ.

Так как $ остается во втором магазине, в нем всегда есть пара смежных символов, находящихся в отношении •>. Таким образом, если анализатор Т еще не достиг конфигурации ($. 5$, 3t), он делает переносы до тех пор, пока верхние символы первого и второго магазинов не окажутся в отношении •>. В этот момент становится возможной свертка, поскольку между символами первого магазина никогда не выполняется отношение J>. Т делает ее и продолжает работу., □