гл. 3. ТЕОРИЯ ПЕРЕВОДА

Привлечь и другие, более сильные, отображения; некоторые из них рассматриваются в упражнениях.

Определение. Пусть = (N, 2, Р,, S,) и = (N, 2, Р„ S,) КС-грамматики и L{Gy)=L{G). Будем говорить, что G левопо-крывает G, если найдется такой гомоморфизм h, отображающий

в Pj, что

(1) если алоу, то Syf,jy=w,

(2) для каждого л, для которого 8уп-=хю, существует такой разбор л, что S.w и /i(jt)jt.

Будем говорить, что Gg правопокрывает G, если найдется такой гомоморфизм h, отображающий Р в Р, что

(1) если S-=nW, то =Ф/,(п)tc,

(2) для каждого л, для которого Sjw, существует такой разбор л, что 5з=Фла и /1(я) = л.

Пример 3.28. Пусть Gi - грамматика с правилами

(1) S-OSl (2)

а (5 - эквивалентная ей грамматика в нормальной форме Хомского с правилами

SAC BSC АО

УПРАЖНЕНИЯ

(2) (3) (4) (5)

Мы видим, что Gg левопокрывает Gj; соответствующий гомоморфизм определяется равенствами h{2) = 2, h{3) h(4)=h(S) = e. Например,

5i432..5=>g.00U, /1(1432455)-12 и 5,,=>с,0011

Ga также и правопокрывает Gj, причем подходит тот же гомоморфизм h. Например,

S,35..4.a.0011, /1(1352544) = 12 и 5==>, 00П

Грамматика Gj не лево- и не правопокрывает G. Так как обе грамматики однозначные, то соответствие между разборами фиксировано. Поэтому гомоморфизм g, доказывающий, что G левопокрывает Gg, должен отображать 1"2 в (143)"24(5)"+\ а это, как легко показать, невозможно. □

Можно показать, что многие из конструкций разд. 2.4, преобразующих грамматики к нормальным формам, дают грамматики, лево- или правопокрывающие исходные грамматики.

Пример 3.29. Ключевой шаг при построении нормальной (Ьормы Хомского (алгоритм 2.12) состоит в замене правила JLX, X, {п>2) правилами Л-ХВ,, В,-. Х,В, ..., B.n-n-in: Можно показать, что в результате получается грамматика, левопокрывающая исходную: достаточно отобразить правило Л-Xii в Л->Х...Х„, а каждое из правил 5,-Хаз, •S„-2--X„ iX„ в пустую цепочку. Если мы хотим получить правое покрытие, то Л Х... Х„ мо.жно заменить пг А->-ВуХ, Ву-ВХ-у, ..В -~уХуХ. □

Другие результаты о покрытии оставляем в качестве упражнений.

УПРАЖНЕНИЯ

3.4.1. Дайте алгоритм построения дерева вывода по левому или правому разбору.

3.4.2. Пусть G -КС-грамматика. Покажите, что Lf-детерминированный КС-язык.

3.4.3. Всегда ли -детерминированный КС-язык?

*3.4.4. Постройте детерминированный МП-прсобразователь Р для которого т(Р) = {(я, л)л и л-правый разбор для

того же дерева вывода}.

*3.4.5. Можете ли Вы построить такой детерминированный МП-пршбразователь Р, что х {Р) = {(п, и л-соот-

ветствующий левый разбор}.

3.4.6. Постройте левые и правые разборы в грамматике G для цепочек "

(а)(()),

(6)a + (ct + a),

(B)fif*a » а.

3.4.7, Пусть КС-грамматика G определяется следующими занумерованными правилами:

(1) S-bits then Seise S

(2) S~s

(3) B~BAB

(4) BB\/B

(5) Bb

Постройте СУ-схемы, определяющие Т? и Г?.

йчя гройте МП-преобразователи, определяющие Г? и Г? я грамматики G из упр 3.4.7,

гл. 3. ТЕОРИЯ ПЕРЕВОДА

УПРАЖНЕНИЯ

3.4.9. Докажите теорему 3.10.

3.4.10. Докажите теорему 3.11.

3.4.11. Дайте определение СУ-схемы и докажите, что Ваша схема отображает цепочки нз L{G) в их правые разборы.

3.4.12. Дайте алгоритм, превращаюш,ий расширенный МП-преобразователь в эквивалентный МП-преобразователь. Ваш алгоритм должен быть таким, чтобы при применении его к детерминированному расширенному МП-преобразователю получался ДМП-преобразователь. Докажите, что Ваш алгоритм делает это.

3.4.13. Докажите теорему 3.12.

*3.4.И. Постройте детерминированные правые анализаторы для грамматик

S-e SAB АМХ А~е В-ВХ В-е

*3.4.(5. Постройте детерминированные левые анализаторы для грамматик

(1) (2) (3)

(1) (2) (3) (4) (5)

*3.4.16. Какие из грамматик в упр. 3.4.14 имеют детерминированные левые анализаторы? Какие в упр. 3.4.15 имеют детерминированные правые анализаторы?

*3.4.17, Дайте детальное доказательство того, что грамматика из примера 3.26 (3.27) право- (лево-)анализируема, но не лево- (право-)анализируема.

3.4.18. Дополните доказательство теоремы 3.14.

3.4.19. Дополните доказательство леммы 3.15.

3.4.20. Дополните доказательство теоремы 3.15.

Определение. Левым участком правила с непустой правой частью назовем самый левый символ (терминал или нетерминал) его правой части. Анализом (или разбором) цепочки по левому участку называется последовательность правил, соответствующих внутренним вершинам дерева разбора этой цепочки, в котором все вершины упорядочены следующим образом. Если вершина п имеет р прямых потомков п, п, . .п, то все вершины поддерева с корнем п предшествуют п. Вершина/г предшествует всем другим ее потомкам. Потомки вершины п предшествуют потомкам вершины которые в свою очередь предшествуют потомкам вершины п и т. д.

Грубо говоря, при анализе по левому участку левый участок правила распознается снизу вверх, а остальная часть правила-сверху вниз.

Пример 3.30. На рис. 3.11 показано дерево разбора цепочки ЬЬаааЪ, порожденной грамматикой с правилами

(1) S-AS (2) S~BB (3) A~bAA (4) А~а (5) ВЬ (6) В-е

Упорядочение вершин, о котором идет речь в определении анализа по левому участку, таково, что вершина п и ее по-

®ffB фпа

Т I I

0Щ (2)iio ®f*n

©15 @mi

Рис. 3.П. Дерево разбора.

ТОМКИ Предшествуют вершине п, за которой следуют п и ее потомки. Вершина п предшествует вершине п, за которой следуют п, и их потомки. Вершина п предшествует вершине п, за которой следуют п, n-i и их потомки. Продолжая в том же духе, получаем упорядочение вершин

ппппппппппппщпПуп

гл. 3. ТЕОРИЯ ПЕРЕВОДА

Разбором по левому участку является последовательность правил, соответствующих внутренним вершинам в этом упорядочении. Таким образом, разбором цепочки ЪЪаааЬ по левому участку будет последовательность 334441625. П

Другой метод определения разбора по левому участку для цепочки, порождаемой грамматикой G, заключается в использовании следующей простой СУ-схемы, ассоциируемой с G.

Определение. Пусть G = (N, 2, Р, S) -КС-грамматика, в которой правила занумерованы от 1 до р. Пусть Tf - простая СУ-схема (N, 2, jl, . . ., pj-, S), где для каждого правила из Р в множество R включается правило, определяемое так: если i-e правило из Р имеет вид Л-Ва или Л-аа, или Л-eroR содержит правило вида ЛВа, Bia. ,или Л-аа, ia, или А-t-e, i соответственно, где а получается из а удалением всех терминальных символов. Тогда если (ш, л) £т(7£), то л -разбор по левому участку цепочки w.

Пример 3.31. Для грамматики из предыдущего примера схема Т% такова:

S->Л5, A\S S-BB, В2В

A~bAA,, ЗАА Аа, 4 B~b, 5 В-е, б

Можно убедиться, что (bbaaab, 334441625) 6т(Г). □

3.4.21. Докажите, что {w, л)т(7£) тогда и только тогда, когда л -разбор по левому участку цепочки w.

3.4.22. Покажите, что для каждой КС-грамматики существует (недетерминированный) МП-преобразователь, отображающий цепочки языка, порождаемого этой грамматикой, в нх разборы по левому участку.

3.4.23. Разработайте алгоритмы, отображающие разборы по левому участку в (1) соответствующие левые разборы, (2) соответствующие правые разборы, и -обратно.

3.4.24. Покажите, что ec.;iH Gg лево- (право-)покрывает Gg и Gj, лево- (право-)покрывает G, то Gy лево- (право-)покрывает Gj.

3.4.25. Пусть Gj -грамматика без циклов, Покажите, что Gi лево- и правопокрывается грамматиками, не содержащими цепных правил.

3.4.26. Покажите, что каждая грамматика без циклов лево-и правопокрывается грамматиками в нормальной форме Хомского.

*3.4.27. Покажите, что не каждая КС-грамматика покрывается грамматикой, не содержащей е-правил.

ЗАМЕЧАНИЯ по ЛИТЕРАТУРЕ

3.4.28. Покажите, что алгоритм 2.9, устраняющий бесполезные символы, дает грамматику, лево- и правопокрывающую исходную.

**3.4.29. Покажите, что не каждая приведенная грамматика лево- или правопокрывается грамматикой в нормальной форме Грейбах. Указание: Рассмотрите грамматику S->501 S11011.

**3.4.30. Покажите, что утверждение из упр. 3.4.29 остается верным, если в определении покрытия заменить гомоморфизм конечным преобразованием.

*3.4.31. Останется ли верным утверждение из упр. 3.4.29, если заменить гомоморфизм МП-преобразованием.

Проблема для исследования

3.4.32. Было бы хорошо, если бы всегда, когда G лево-или правопокрывает G, каждая СУ-схема с G в качестве входной грамматики была эквивалентна некоторой СУ-схеме, входной грамматикой которой служит Gg. К сожалению, это не так. Можете ли Вы найти условия, связывающие G и G, при которых СУ-схемы с входной грамматикой G образуют подмножество СУ-схем с входной грамматикой Gg?

Замечания по литературе

Дополнительные подробности, касающиеся грамматического покрытия, можно найти б работах Рейнольдса и Хаскела [1970], Грэя [1969] и Грэя и Харрисона [1969]. В некоторых ранних статьях анализ по левому участку назывался восходящим анализом. Более полное изложение метода анализа по левому участку содержится в монографии Читэма [1967J.