Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 109
Текст из файла (страница 109)
Так как мы взяли и> 1, то для Е есть правило 'У~1~ з 1з). Случай 1: в=в,вм У,~" (в, (в,х, з) и У,=!Р*(в, ! х, з), Тогда и, и и, меньше и и йо предположению индукции (6.1.5) (начало, !вх, (У„О))« — +(успех, в,«в,х, е) (6.1.6) (начало, ! в,х„(У„О)) «-,+туспех, в, 1х, е) Заметим, что если слева от входной головки машины М вставить какую-нибудь цепочку, в частности в„то М выполнит те же действия. Поэтому из (6.!.6) получаем (6.1.7) (начало, в, «в,х, (Ум 0))! — + (Успех, в ! х, е) Этот вывод требует, правда, доказательства, но мы оставим его в качестве упражнения.
Из определения )7 мы знаем, что 6(начало, е, 2)=-(начало, У,2) и 6(успех, е, 2) =(начало, У,). Поэтому (6.1.8) (начало, 7 вх, (2, 0)) « — (начало, Т вх, (1'„0) (2, О)) (6.1.9) (успех, в, «в,х, (Х, 0)) 'à — (начало, в,) в,х, (У„О)) Объединяя (6.1.9), (6.!.5), (6.!.8) и (6.1.7), получаем нужное утверждение: (начало, Т вх, (2, О)) «-+ (успех, в 7 х, е) Случай 2: У,=О'*(«вх,1) н У,=,>" (в ух, з). Доказательство аналогично доказательству в случае 1, и мы оставляем его читателю. Теперь проведем индукцию для (6,1.4).
Пусть 2=О" («в, )). С Л у Ч а й 1 У ~ ~ ~ ( В 1 «В ~ З ) И У а ~ и ~ ( ! В А ~ 1 ) Г ДЕ В 1 В ~ В Тогда пм а, < л и из (6.1.3) н (6.1.4) получаем (6,1.10) ' (начало, 7 в, (У„О)) «-' (успех, в, 1 в„е) (6.1.11) (начало, 7 в„(УН 0)) «-+ (неудача, Т в„е) Если в (6.1.11) слева от 7 вставить в„будет (6.1.12) (начало, в, 7 в„(У„О)) «-' (неудача, ( в,в„е) 5зт ГЛ. 6. АЛГОРИТМЫ РАЗБОРА С ОГРАНИЧЕННЪ|МИ ВОЗВРАТАМИ УПРАЖНЕНИЯ 53а Доказательство последнего утверждения оставляем в качестве „: упражнения. Надо заметить, что когда' стирается ()'„О), входная головка должна вернуться до конца влево. Присутствие цепоя-:,: ки и|, не меняет дела, потому что тогда к числам, записываемым -в магазин выше (!'„0), добавляется !в,((при построении после-., довательности шагов, соответствующей (6.1.12), по последователь- ', ности (6.1.11)) и, значит, входная головка пе может выйти .иа ' цепочку в„не стерев (Г„О).
По определению 1', и 1', (б.!.13) (начало, у в, (7., 0)) ) — (начало, т в, (Г'О О) (3', 0)) (6.!.!4) (успех, в, у в„(с, 0)) ! — (начало, в, 1в„(г „О)) Объединяя (6.!.13), (6,1.10), (6. 1,14) и (6.!. !2), получаем (начало, ( в, (2, 0)) )-" (неудача, ф в, е). Случай 2: 1',=>" (1 в, !) и 1;=.У" (! в, !). Этот случай анало. гичен предыдущему: оставляем его читателю. Достаточность..Эта часть доказательства проводится ана. логично; мы оставляем се в качестве упражнения. Из утверждения (6.1.3), в частности, следует, что 2, ~+ (в ), г), тогда и только тогда, когда (начало, ( в, (Еы О)) !--+ (успех, ( в, е), так что Е (М) = Е (Р).
( ) Лемма 6.6. Если Е = Е (Р) для некоторой ОЯН РОВ-программы Р, то Е = — Е(М) для анализиру|оп!ей машины М. Д о к а з а т е л ь с т в о. Пусть Р = (61, г,, В, 5). Зададим М = (|г, Х, Х, 6, начало, 5), где 6 определяется так: (!) Если в В-есть правило А — В[С, Щ), то 6(начало, е, А) = (начало, ВА), 6(успех, е, А)=(начало, С) и 6(неудача, е, А) ==(начало, 0). (2) (а) Если в 11 есть А — а, где а ц Х (! !'е), то 6 (начало, а, А)= (успех, е).
(б) Ясли в В есть А — 1, то 6 (начало, е, Л) = (неудача, е). Простое доказательство равенства Е(М)= Е(Р) оставляем в качестве упражнения. Теорема 6.6. Е = Е(М) для некоторой анализирунчией машины М тогда и только тогда, когда Е=Е(Р) для некоторой ОЯНРОВ- программы Р. Дон аз а тел ь ство. Получается непосредственно из лемм 6.б' и 6.6.
упРАжнения 6.1.1. Постройте ЯНРОВ-программы, распознающие следу- ющие языки: (а) Е(6,), (б) множество цепочек, содержащих одинаковое число симво- лов а и Ь, (в) (всв" ) в 6(а+6)*), *(г) (а'" ~п~)1) (Указание: Рассмотрите 5- а5а(аа.), (д) какою-нибудь бесконечное подмножество Фортрана. 6.1.2. Постройте ОЯНРОВ-программы, распознающие следу- ющие языки: (а) языки из упр.
6.1.1, (б) язык, порождаемый грамматикой (с начальным символом Е) Š— Е+Т(Т Т вЂ” Твр '!Р Р (Е) !1 1 а ! а (Е) Е а!а,Е "(в) (а" ( и ) '!). *6.1.3. Покажите, что для каждого ) 1(!)-языка существует ОЯНРОВ-программа, распознающая сго без возвратов, т. е. анализирующая машина, построенная в лемме 6.6, д 6.6 никог а не сдвигает входной указатель Влево. "6.1.4. Докажите неразрешимость следующих проблем: распознает ли ЯНРОВ-программа Р =. (Х, Х, )||, 5) (а) пустое множество 8? (б) язык Х'7 6.1.6. Покажите, что каждая ЯНРОВ и ОЯНРОВ-программа эквивалента программе, в которой есть правило для каждого цетерминала.
ка . Указание; Покажите что если для А правила нет, то можно добавить правило А — АА1А (или соответственно А— А !А, А1), нс изменив распознаваемого языка. Я6.1.6. Постройте обычную ЯНРОВ-программу, эквивалентную расширенной программе 5 А/В|С А — а В 5СА С с ой язык она определяет? Каковы недостатки этой программы с практической точки зрення7 539 ГЛ.
В. АЛГОРИТМЫ РАЗВОРА С ОГРАНИЧЕННЫМИ ВОЗВРАТАМИ УПРАЖНЕНИЯ 6.1.7, Дайте формальное доказательство леммы 6.3. 6.1.8. Докажите лемму 5.4. 6.1.9. Дайте формальное доказательство того, что программ Р из примера 6.5 определяет язык (О"!"2" ~ н) 1). 6.1.10. Дополните доказательство теоремы 6.2. 6.1.11. С помощью алгоритма 5.2 покажите, что цепочка ((а))+ содержится в языке Е(Р), где Р— программа из примера 6.6Г 6.1.12. ОЯНРОВ-операторы можно расширить тем же своей': бом, что и ЯНРОВ-операторы.
Например, можно разрешит ОЯНРОВ-операторы вида А -Х,д,х,д,,Х,д, где каждый символ Х,— терминал или нетермниал, а каждый' символ дà — либо е, лабо пара вида )ап 5Г1, в которой аГ и 5;~; цепочки символов. Нетерминал А сообщает об успехе тогда. и только тогда, когда каждан цепочка Х,.а,. приводит к успеху;- а это определяется рекурсивно следующим образом.
Цепочка Х;~аь ~!Г) приводит к успеху тогда и только тогда, когда (1) ХГ и а, приводят к успеху или (2) ХГ приводит к неудаче, а р, — к успеху, (а) Покажите, как заменить этот расширенный оператор эк- ', вивалентным множеством обычных ОЯНРОВ-операторов. (б) Покажите, что каждый расширенный ЯНРОВ-опера.' ': тор можно заменить эквивалентным множеством (расширенных): ОЯНРОВ-операторов. 6.1.13. Покажите, что существуют ЯНРОВ- и ОЯНРОВ-про- граммы, для которых число операторов, выполняемых анализи- .: рующей машиной из леммы 6.6, экспоненциально зависит от''': длины входной цепочки. ' 6.1.14.
Постройте ОЯНРОВ-программу, моделирующую дей- ',:,, ствия правила А — ВС/(7?О Р,), упомянутого в конце разд. б.!.3. " 6.1.15. Найдите ОЯНРОВ-программу, определяющую язык ":""+, Е(М), где М вЂ” анализирующая машина из примера 5.7. 6.1.16. Найдите аналнзнрующие машины, распознающие языки из упр. 6.1.2. '-:-Ф Определение. ЯНРОВ- или ОЯНРОВ-программа Р=(5), г, )?, 3) .::;Ф приводит к неудаче с частичным распознаванием на цепочке Гв, если ю=--ии, причем РФе н 3=,>+ (и ! О, з). Программа Р вполне определена, если для каждой цепочки Ги из Х* либо 5 =о+ (! Гв, !), либо 5 =:;>' (Гв (, з). если Š— ЯНРОВ-язык (ОЯНРОВ-язык) ЯНРОВ й н $ (ОЯНРОВ-программой), не приводящей к неу распознаванием.
-п ог аммой (ОЯНРОВ- "6.!.18. Пусть Е определяется ЯНРОВ-программо язык~ ~м~жы ЯНРОВ-ю~- типа. Покажите, что следующие языки яв ками (ОЯНРОВ-языками): (а) Е,ОЕ„ (б) Еы (в) Е,ПЕ„ (г) Е,'-Е,. *6,!.19."Покажите, что каждая ОЯНРОВ-программа, не прне аче с частичным распознаванием, эквивалентна водящая к неудаче с ч некоторой вполне определенной ОЯНРО -прогр Достаточно обнаружить и устранить „левую рекурсию". Иными словами, если дана обычная ОЯНРОВ-программа, построим г амматйку, заменив правило вида А — Г , ! р в виду „левая рекурсия" в построенной КС.грамматике. **6,1.20. Докажите, что проблема пустоты множества Г ( ) д вполне' определенных ЯНРОВ-программ Р неразрешима. Замечание: стественное мо : Е моделирование проблемы соответствий Поста ает вполне опрепозволяет сделать упр. 6.1.4(а), но не всегда дает вполне деленную программу.
6.1.21. Дополните доказательство леммы 6.5. 6.1.22. Докажите лемму б.б. Открытие проблемы 6.!.23. Существует ли КС-язык, который не является ОЯН ЯНРОВ- языком? 6.1.24. Замкнут ли класс ЯНРОВ-языков относительно дополнения? 6.1.25. Эквивалентна ли каждан ЯНРОВ-программа некоторой вполне определенной ЯНРОВ-программе? 6.!.26. Эквивалентна ли каждая ОЯНРОВ-программа некоторой ЯНРОВ-программе? Мы выдвигаем гипотезу, что ОЯНРОВ- язык (а" ~ и) !) не является ЯНРОВ-языком.
Упражнения на программирование 6.!.27. Постройте интерпретатор для анализирующих машин, Напишите программу; которая по расширенной ОЯНРОВ-про- ЗГИ ГЛ, 6. АЛГОРИТМЫ РАЗБОРА С ОГРАНИВ РННЫМИ ВОЗВРАТАМИ грамме строит эквивалентную анализирующую машину, модели-, руемую далее интерпретатором. 6.1.28. На основе обобщенного или Обычного языка нисходя- щего разбора с ограниченными возвратами разработайте язык ., программирования, который можно использовать для задания,' трансляторов. Постройте компилятор для этого языка. Исходной:; программой для него будет описание транслятора, а объектной 'ч' .
программой †фактическ транслятор, Замечании по литературе ЯНРО — это абстракция яэыка, нспольаонапногоМак-Клюром (!965!него компиляторе компиляторов ТМО. Анализирующая машина иэ 'разд. 6.1.5 аналогична машине, рассмотренной Кнутом !!967, 19711, Большинстаь излагаемых здесь теоретических результатов, связанных с ЯНРОВ н ОЯЬ!РОВ, получено Бирмаиом и Ульманом !1970, 1973!. В ик работах можно найти решения мио гик упражнений. иа ОЯНРО — эго модель ссмейстаа компилятороа компнлятороа типа МЕТА !Шорре, !964! н др. 6.2.
ВОСХОДЯЩИЙ РАЗБОР С ОГРАНИЧЕННЫМИ ВОЗВРАТАМИ Рассмотрим возможности восходящего детерминированного анализа, если допускается большая свобода в выборе средств. В частности, разрешим Ограниченные возвраты на входе и не будем требовать, чтобы разбор был, обязательно правым. Глав-' ный обсуждаемыи здесь метод — алгоритм Колмерауэра, основанный'на отношениях прсдшествования. х 6.2 ч. Немвноничрский разбор Существует несколько приемов, с помощью.которых можно провести детерминированный разбор для грамматик, не являющихся 1.К-грамматикаыи. Один из них заключается в том, чтобы.
разрешить заглядывать вперед на любое число символов, позволяя входному указателю передвигэться по входной цепочкевперед для разрешения встретившейся неопределенности. После тогм как решение принято, входной указатель находит. обратный путь в подходящее для свертки место. Пример 6,8. Рассмотрим грамматику 6 с правилами 5 Аа) ВЬ А- ОА1 ! 01  — ОВ11 ( 011 Эта грамматика порождает язык (Оч1ап ! и) 1) () (О"1'"Ь | и ~ 1), который не является детерминированным КС-языком. Однако ' разбор для грамматики 6 можно провести, сначала передвинув аз, ВОСХОДЯЩИ н Рдзвоэ с огндниченными возвратами к .кони входной цепочки, чтобы посмотреть, входной у~ымель к .к~ш~у в каков последний символ— л — а или Ь, а затем, верн 0" 1" 0"1аа соот- цепочки и продолжив разбор д.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
