Главная Промышленная автоматика.

Доказательство последнего утверждения оставляем в качестве упражнения. Надо заметить, что когда стирается (Kg, 0), входная головка должна вернутьсядо конца влево. Присутствие цепочки Wy не меняет дела, потому что тогда к числам, записываемым -в магазин выше (К,, 0), добавляется \ Wy \ (при построении последовательности шагов, соответствующей (6.1.12), по последовательности (6.1.11)) и, значит, входная головка ие может выйти иа цепочку Wy, не стерев [Уу, 0).

По определению Уу п У . ,

(6.1.13) (начало, fay, {Z, 0))Н (начало, \ w, {У у, 0)(Z, 0)) "

(6.1.14) (успех, оу f (Z, 0)) [-(начало, Wy \ w, [У, 0))

Объединяя (6.1.13). (6.1.10), (6.1.14) и (6.1.12), получаем (начало, f w, (Z, 0)) (неудача, \w, е).

Случай 2: /=:>"j ( tjy,/) и Kg (t ,/). Этот случай аналогичен предыдущему: оставляем его читателю.

Достаточность, .Эта часть доказательства проводится ана- логично; мы оставляем се в качестве упражнения.

Из утверждения (С. 1.3), в частности, следует, что Zj, (ш f, s), тогда и только тогда, когда (начало, \ w, (Z, 0)) I-+ (успех, f w, e), так что L{M)L(P). □

Лемма 6.6. Если L - L {Р) для некоторой OUPOS-программы Р, то L~L{M) для анализирующей машины М.

Доказательство, Пусть Р = (N, 2, R, S). Зададим М = (Q, 2, N, б, начало, S), где 6 определяется так;

(1) Если в R есть правило Л-5[С, £)], то 6 (начало, е,-А) = (начало, ВЛ), б (успех, е. Л) (начало, С) и б (неудача, е, А) = (начало. Г)).

(2) (а) Если в R есть Л-а, где a2u [е], то б (начало, а, Л)= (успех, е).

(б) Если в R есть Л -,/, то б (начало, е, Л) = (неудача, е).

Простое доказательство равенства Е(М) = Е{Р) оставляем в качестве упражнения. П

Теорема 6.5. L = L[M) для некоторой анализирующей машины М тогда и только тогда, когда E = L{P) для некоторой ОЯНРОВ-программы Р.

Доказательство. Получается непосредственно из лемм 6.5 и 6.6. □

УПРАЖНЕНИЯ

6.1.1. Постройте ЯНРОВ-программы, распознающие следующие языки:

(а) ЦС,),

(б) множество цепочек, содержащих одинаковое число символов а и Ь,

(в) {wcw I w{a-yb)*},

*(г) {а"\п1} {Указание: Рассмотрите S->-aSa\aa.), (д) какое-нибудь бесконечное подмножество Фортрана.

6.1.2. Постройте ОЯНРОВ-программы, распознающие следующие языки:

(а) языки из упр. 6.1.1,

(б) язык, порождаемый грамматикой (с начальным символом £)

ЕЕТ\Т

F~{E)\I !a\a{L) La \ й, E

**(в) {а"\пЦ. *6.1.3, Покажите, что для каждого ЕЬ(1)-языка существует ОЯНРОВ-программа, распознающая его без возвратов, т, е. анализирующая машина, построенная в лемме 6.6, никогда не сдвигает входной указатель влево.

*6,1.4. Докажите неразрешимость следующих проблем: распознает ли ЯНРОВ-программа P-(N, 2, R, S)

(а) пустое множество 0?

(б) язык 2*?

6.1.5. Покажите, что каждая ЯНРОВ и ОЯНРОВ-программа эквивалента программе, в которой есть правило для каждого нетерминала. Указание: Покажите, что если для Л правила нет, то можно добавить правило Л-»-ЛЛ/Л (или соответственно А-*-Л [Л, Л]), НС изменив распознаваемого языка.

*6.1.6. Постройте обычную ЯНРОВ-црограмму, эквивалентную расширенной программе

5 -Л/В/С Л ~а B~SCA Сс

Какой язык она определяет? Каковы недостатки этой программы с практической точки зрения?



6.1.7. Дайте формальное доказательство леммы 6.3.

6.1.8. Докажите лемму 6.4.

6.1.9. Дайте формальное доказательство того, что програАш Р из примера 6.5 определяет язык j0l2" п 1}.

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

6.1.11. С помощью алгоритма 6.2 покажите, что цепочка содержится в языке t(P), где Р-программа из примера 6,6J

6.1.12. ОЯНРОВ.операторы можно расширить тем же споср« бом, что и ЯНРОВ-операторы. Например, можно разрешить! ОЯНРОВ-операторы вида .

где каждый символ X,--терминал или нетерминал, а каждый;; символ gi-либо е, либо пара вида [се,-, р,], в которой сс- и р,-- цепочки символов. Нетерминал А сообщает об успехе тогда и только тогда, когда каждая депочка Xgi приводит к успеху, а это определяется рекурсивно следующим образом. Цепочка Xi\oi-,i\ приводит к успеху тогда и только тогда, когда

(1) Х- и а,- приводят к успеху

(2) Х(- приводит к неудаче, а р-к успеху.

(а) Покажите, как заменить этот расширенный оператор эквивалентным множеством обычных ОЯНРОВ-операторов.

(б) Пoкaжитii, что каждый расширенный ЯНРОВ-опера-тор можно заменить эквивалентным множеством (расширенных) ОЯНРОВ-операторов.

6.1.13. Покажите, что существуют ЯНРОВ- и ОЯНРОВ-программы, для которых число операторов, выполняемых анализирующей машиной из леммы 6.6, экспоненциально зависит ot длины входной цепочки.

6.1.И. Постройте ОЯНРОВ-программу, моделирующую действия правила Л ->BC/(I>i, D), упомянутого в конце разд. 6.1.3.

6.1Л5. Найдите ОЯНРОВ-программу, определяющую язык L(M), где Л1 -анализирующая машина из примера 6.7.

6.1.16. Найдите анализирующие машины, распознающие языки из упр. 6.1.2.

Определение. ЯНРОВ-или 05IHPOB-nporpaMMaP=(N, 2, RS) приводит к неудаче с частичным распознаванием на цепочке оу, если w = uv, причем vфe и 5=" (и и, s). Программа Р вполне определена, если для каждой цепочки ecj из 2* либо 5=»" (tчг./)» либо 5=Ф+ {w t, s).

*6.1Л7. Покажите, что если -ЯНРОВ-язык (ОЯНРОВ-язык) и <ii-новый символ, то.Л$ определяется ЯНРОВ-программой (ОЯНРОВ-программой), не приводящей к неудаче с частичным распознаванием.

*6.1.18. Пусть определяется ЯНРОВ-программой (ОЯНРОВ-программой), а Z,a-вполне определенной программой того же типа. Покажите, что следующие языки являются ЯНРОВ-язы-ками (ОЯНРОВ-языками):

(а) Z,iUL„ .

(б) L„

(в) i-iOLa. (Г)

*6.1.19. Покажите, что каждая ОЯНРОВ-программа, не приводящая к неудаче с частичным распознаванием, эквивалентна некоторой вполне определенной ОЯНРОВ-программе. Указание. Достаточно обнаружить и устранить „левую рекурсию". Иными словами, если дана-обычная ОЯНРОВ-программа, построим КС-тршматшу, заменив правило вида Л->В\С, D\ правилами А~~ВС и Л-и сохрйтв правила Ли Л-Имеется в виду.,левая рекурсия" впостроенной КС-грамматике.

**6.1.20, Докажите, что проблема пустоты множества Z-(Р) для вполне onpejiQnenHux ЯНРОВ-программ Р неразрешима. Замечание-, Естественное моделирование проблемы соответствий Поста позволяет сделать упр. 6.1.4(a), но не ьсетд, дает вполне определенную программу.

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

6.1.22. Докажите лемму 6.6.

Открытые проблемы

6.1.23. Существует ли КС-яшк, который не является ОЯНРОБ-языком?

ел.24. Замкнут лн класс ЯНРОВ-языков относительно дополнения?

6.1.25. Эквивалентна ли каждая ЯНРОВ-программа некоторой вполне определенной ЯНРОВ-программе?

6.1.26.Эквивалентна ли каждая ОЯНРОВ-программа некоторой ЯНРОВ-программе? Мы выдвигаем гипотезу, что ОЯНРОВ-зык {а"\п\} не является ЯНРОВ-языком.

Упражнения на программирование

6.1-27. Постройте интерпретатор для анализирующих машин. Напишите программу,- которая по расширенной ОЯНРОВ-про-



грамме строит эквивалентную анализирующую машину, моделируемую далее интерпретатором.

6.J.28. На основе обобщенного или обычного языка ннсходя* щего разбора с ограниченными возвратами разработайте язык программирования, который можно использовать для задания трансляторов. Постройте компилятор для этого языка. Исходной программой для него будет описание транслятора, а объектной программой - фактический транслятор.

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

ЯНРОВ-это абстракция языка, использоваиного Мак-Клюром [1965]вего компиляторе компиляторов TMG, Анализируюи;ая машина изразд. 6.1.5 аналогична машине, рассмотренной Кнутом {1967, 1971]. Болъшинст излагаемых здесь теоретических результатов, связанных с ЯНРОВ и ОЯНРОВ, получено Бирманом и Ульманом [1970, 1973]. В их работах можно найти решения мио гих упражнений.

ОЯНРОВ - это модель семейства компиляторов компиляторов типа МЕТА [Шорре, 1964] и др.

6.2. ВОСХОДЯЩИЙ РАЗБОР С ОГРАНИЧЕННЫМИ ВОЗВРАТАМИ

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

6.2.1. Неканонический разбор

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

Пример 6.8. Рассмотрим грамматику G с правилами

S~Aa\Bb Л-0Л101 ВОВИ 0П

Эта грамматика порождает язык {0"1"а п> 1} U {0"12"Ь 1}, который не является детерминированным КС-языком. Однако разбор для грамматики G можно провести, сначала передвинув

входной указатель к концу входной цепочки, чтобы посмотреть, каков последний символ - а нли Ь, а затем, вернувшись к началу цепочки и продолжив разбор для цепочки 0"1" или 0"1" соответственно. □

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

Определение. Если G = (N, 2, Р, 5)-КС-грамматика и в ней есть вывод 5=>*аЛу =>сфу, то цепочка р называется составляющей выводимой цепочкн фу. Пусть X.-.Xj и Ху...Х/-составляющие выводимой цепочки Х.-.Х; будем говорить, что составляющая Х-... Xj расположена левее составляющей Х.. .Х, если (< / либо t -/ ий </. Таким образом, если грамматика однозначная, то основа -самая левая составляющая правовыводимой цепочки.

Пример 6.9. Рассмотрим грамматику G с правилами S-QABb\OaBc А-а B~Bi I 1

L{G)-это регулярное м1южество Ой!" (Ь-[-с), но G -не LR-грамг матика.: Однако для G возможен восходящий разбор, если .решение вопроса о том, является ли а составляющей, отложить до тех пор, пока не прочтем последний входной символ. Иными словами, входную цепочку вида Qal" можно свернуть к QaB независимо от того, следует за ней b илн с. В первом случае цепочка ОаВЬ сначала свертывается к QABb,. а затем к 5. Во втором случае цепочка ОаВс сразу свертывается к S. При этом, конечно, мы не получим ни левого, ни правого разбора. □ Пусть G = (N, 2, Р, S) -КС-грамматика, правила которой занумерованы числами от 1 до р, и пусть

(6.2.1) 5 = ао=?>а=>сСз=.. .=?>а„-ш

- вывод цепочки w из S. Для 0(<л пусть а,. = р,-Л;б- и Л,.-*управило с номером р, которое применялось к явно указанному вхождению А в а\Н дало ci.. =р,-у,-6,.. Шаг вывода a=»a ) j можно представить парой чисел (р,-, /,), где Таким образом, вывод (6.2Л) можно представить цепочкой, состоящей из п пар чисел

(6.2.2) (р«, /J(p„ /,)...(p„ i,

Если вывод правый или левый, то вторые компоненты пар цепочки (6.2.2), указывающие позицию нетерминала, развертываемого на очередном шаге вывода, можно не писать.





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 [89] 90 91 92 93 94 95 96 97 98 99 100 101

0.0035