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