Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 104
Текст из файла (страница 104)
Тзк как нетерминал А сообщил об успехе своего первого вызова, он уже не будет вызываться для проверки второй а.чьтернативы. Заметим, что этой трудности можно избежать, записав А-альтернативы в обратном йорядке А аЬ)а Теперь изложим язык нисходящего разбора с ограниченными возвратами (сокращенно ЯНРОВ), который можно использовать для описания процедур разбора указанного типа. Операторсд! (нли правилож) этого языка называется цепочка одного нз видов А — ВС!'17 илн А а ') Здесь снова вовнкквет нетст»укндей гремматнке 6, в рввд. 5.4Л.
— Прил. перев. проблема вдекввтносгн распознавателя А«о соог. уяомнявна!анен к дополненнк к равд. 5.1 н ! 7 А. Ако. Дм. Ульм»в, г. ! 5!3 Различие между таким алгоритмом н алгоритмом 4.1 состоит, в том, что если последний потерпит неудачу при попытке найтй полный разбор, в котором из ау выводится а!...а„, то он вернется назад, станет испытывать выводы, начинающиеся правилами А а „„А а,, и т. д., и при этом, возможно, получит другой префикс цепочки а,...а„, выводимый из А. Наш новый алгоритм так ие делает.
Если уж ои обнаружил, что нз ау выводится префикс входной цепочки и что полученнын после этого вывод неудачен, т. е. не дает цепочки, совпадающей с входной цепочкой, то он возвращается к процедуре, вызвавшей Л, н сообщает О неудаче. Алгоритм будет вести себя так, как будто из А не выводится никакой префикс цепочки а!...а„. Таким образом, этот алгоритм может не обнаружить некоторые разборы и даже может распознать не тот язык, который определяет лежащая в его основе КС-грамматика' ).
Мы ие будем, следова. тельно, связывать такой алгоритм с конкретной КС-грамматикой, а будем трактовать его сам по себе как формализм, предназначенный для определения и синтаксического анализа языка. Возьмем конкретный пример. Если правила 5- Ас Л вЂ” а(аЬ Гл. 6, АлГОРитмы РА3БОРА с ОГРАиичгииыми возвРАТАми где Л, В, С и Р— нетерминалы, а а — терминал, пустая цепочка или специальный символ 7 (обозначающий неудачу). Определение. ЯНРОВ-программой Р называется четверка (г), Х, 77, В), где (1) )л( и Х вЂ” конечные непересекающиеся множества иетерминалвв и терминалов, (2)  — последовательность ЯНРОВ-операторов, содержащая для каждого Л Е)л) пе более одного оператора с левой частью А (слева от стрелки), (3) 3 б М вЂ” начальный символ.
ЯНРОВ-программу можно связать с грамматикой в специальной нормальной форме. Оператор вида А — ВС!Р соответствует двум правилам А ВС и А — Р, из которых первое всегда испытывается первым. Оператор вида А-- а соответствует правилу А — а, когда аЕХ или а=-е. Если а=7, то нетерминал А имеет специальный смысл, который мы разъясним позже.
ЯНРОВ-программу можно описать иначе как множество процедур (нетермииалов), вызываемых рекурсивно для некоторых входных цепочек в качестве аргументов. Выходом, или результатом, вызова нетермииала будет либо неудача (ии один префикс входной цепочки не подходит даииол!у нетермииалу), либо успех (некоторый префикс входной цепочки подходит ему). Результатом вызова оператора вида Л вЂ” ВС/Р для входной цепочки 6е будет следующая последовательность вызовов процедур: (!) Сначала Л вызывает В для входной цепочки и!.
Если и!--хх' и цепочка х подходит нетерминалу В, то В сообщает об успехе, т. е. результатом вызова В будет успех. После этого А вызывает С для цепочки х'. (а) Если х'=уг и д подходит С, то С сообщает об успехе. Тогда Л тоже сообщает об успехе и о том, что ему подходит префикс ху цепочки и!. (б) Если никакой префикс цепочки х' не подходит С,.то С ссюбщает о неудаче. Тогда А вызывает Р для цепочки 6е. Заметим, что в этом случае успех вызова В аннулируется. (2) Если А вызывает В для цепочки и и оказывается, что никакой префикс цепочки и! Ие подходит В, то В сообщает о неудаче. Тогда А вызывает Р для цепочки и!.
(3) Если Р был вызван для 6е= ио и цепочка и подходит Р, то й сообщает об успехе. Тогда А тоже сообщает об успехе и о том, что ему подходит префикс и цепочки 6е. (4) Если Р был вызван для цепочки ш и никакой префикс цепочки ш ему не подходит, то Р сообщает о неудаче. Тогда А тоже сообщает о неудаче. 6. !. нисходящий ~лзвоР с Огялничзнными возБРАтлми Заметим, что Р вызывается, когда не оба вызова В и С оказались успешными.
В дальнейшем мы исследуем другую систему разбора, в которой Р вызывается только тогда, когда вызов В оканчивается неудачей. Заметим, что если В и С привели к успеху, то альтернатива Р не вызывается. Зта особенность отличает ЯНРОВ-программу от общего алгоритма нисходящего разбора из гл. 4. С операторами вида А - а, А =е и А = 7 обращаются так: (1) Если есть правило А — а, в котором ОЕАР, и А вызывается для цепочки, начинающейся символом а, та цепочка а подходит А, и А сообщает об успехе.
В противном случае А сообщает о неудаче. (2) Если есть правило А- е, то вызов А всегда успешен и пустая цепочка всегда подходит А. (3) Если есть правило А 7, то вызов А всегда оканчивается неудачей. Определим формально, как иетерминал «действует на входную цепочку». Определение, Пусть Р = (Х, Т, В, В) — ЯНРОВ-программа. Зададим отношения =>Р между нетерминалами и парами вида (х)у, г), где х и у — цепочки из Х', а г — либо в (обозначает успех), либо 7 (обозначает неудачу). Метасимвол 1 используется, для указания позиции текущего входного символа. Индекс Р будем опускать всюду, где можно. (1) Если А — еЕ В, то А =>! ()и!, З) для всех и!~ Х'.
(2) Если А !'ЕВ, то А '=>'(1щ 7) для всех и!йХ'. (3) Если А а~)г и аЕХ, то (а) А =Зл(а1х, в) для всех хЕХ', (б) А ~»()у, )!) для всех у ЕЕ' (включая е), не начинающихся с а. (4) Пусть А- ВС/Р~)Г. Тогда (а) А =э"+"+" (ху)г, в), если (1) В=>'"(х)уг, з), (й) С~" (д(г, з); (б) А ~!(И!о, з) для 1'=и+и+р+1, если (!) В~ (х1у, з), (!!) С=~" ()д, й. ' (ш) Р=ьв(и!и, з), где ии ку; (в) А =->6()ху, 7) для (=т+и+р+1, если (1) В =>и (х ! у, в), (!!) С=э" ()у В (!!1) Р=ьв((ху, 7); 17» 515 Гл.
6. Алгогитмы РАВВОРА с ОГРАниченными ВОВВРАтлми (г) А ~ ""(х)у, з), если (1) В=> ()ху, 1), (П) 17 =Э" (х 1 у, з); (д) А => ""()х, 1), если (!) В «'" (1 х, )'), (П) 17 ~в (1 х, 1). (6) ОТНОШЕНИЕ =>в ВЫПОЛНяЕтСя ТОЛЬКО В СЛуЧаяХ, ОГОВОрги- ных в (1) — (4). Пункт (4а) учитывает тот случай, когда В и С оба приводят к успеху. В (4б) и (4в) В успешен, но С неудачен.
В последних четырех случаях вызывается 17, и это оканчивается либо успе. хом, либо неудачей. Заметим, что число у стрелки указывает количество ввызовов», сделанных до того, как получен,результат. Еще отметим, что если А ~в(х1у. Г), то х=е, т. е. в случае неудачного вызова входной указатель переставляется туда, где ои находился перед вызовом. Положим А.-4 (х1у, Г) тогда и только тогда, когда А «л(х)у, Г) для некоторого п 1. Язьском, определяемым программой Р, назовем множество Б(Р) =(нс)5 М(ис1, з) и исЕХв).
Пример 6.1. Пусть Р =((5, А, В, С), (а, Ь), Р, 5) — ЯНРОВ- программа, где )лс состоит из операторов 5 АВ1С А — а В СВ1А С Ь Исследуем поведение программы Р на входной цепочке аЬа, используя введенные выше обозначения. Вначале„благодаря правилу 5- АВ1С, 5 вызывает А для цепочки ада.~А распознает первый входной символ и сообщает об успехе. Учитывая (3) предыдущего определения, можно писать А =>с (а', Ьа, з). Далее 5 вызывает В для цепочки Ьа. Так как для В есть правило В- СВ1А, нужно заняться поведением С на цепочке Ьа, Оказывается, что Ь подходит С, так что С сообщает об успехе. В соответствии с (3) пишем С =>с(Ь) а, з).
Затем В рекурсивно вызывает себя для цепочки а. Однако С терпит неудачу на а, и потому С =>с(1а, 1). Тогда В вызывает А для цепочки а. Так как а подходит А, то А =Рс(а 1, з). Так как вызов А успешеи, то второй вызов В тоже успешен. В соответствии с (4г) пишем В =>в (а1, з). Возвращаясь к первому вызову В для цепочки Ьа, замечаем, что, так как вызовы С и В успешны, этот вызов В тоже успешен, н в соответствии с (4а) пишем ВсЭ»(Ьа), з). 516 В.с. нисходящий РА3БОР с ОГРАниченными ВОВВРАтлми Возвращаясь теперь к вызову 5, видим, что оба вызова А и В успешны.
Таким образом, цепочка аЬа подходит 5, и 5 сообсцает об успехе. Учитывая (4а), пишем 5 ~с (аЬа), з). Поэтому аЬа б Б (Р). Нетрудно показать, что 1. (Р) = аЬва-(-Ь. Каждая ЯНРОВ-программа Обладает одним важным свойством, а именно: ее результат для данного входа однозначен. Это до.
казывает следующая лемма. Лемма 6.1, Пусть Р=(Ь), Х, К 5) — ЯНРОВ-программа, для которой А =Э" (х,)у„г„) и А =Э»*(х,)у„гл), где А Е)л(, х,у, = х,у,=тЕХ», Тогда х,=х„у,=у, и Г,=Г,. До к а з а тел ьст во. Доказательство проводится простой индукцней по меньшему из чисел пс и и,.
Вез потери общности будем считать, что и, <п,с Базис, п,=1. Применяется Одно из правил А-ва, А — е или А- ). Отсюда сразу получаем нужное утверждение. Шаг индУкс(исс. ДОНУстнм, что УтвеРждение ВеРно длн п < пс, причем и, > 1. Пусть для А есть правило А — ВС117. Допустим, что А~"с(хсту„гс) для с=1 и 1=2 получено в силу (4) нз В=Э с(ис) ос, Ес) и (возможно) С==;»лс,(и,) В;, С,) И1нли с)=С»~с (ис) Вс, Сс), Тогда т, < пс,.
так что, йрименяя предположение индУкции, заключаем, что и,=и„ос=о, и 11=1». РассмотРим отдельно два случая, зависящие от значейия 11. Случай 1: 11=1,=1. Так как 11<-пс, то и",=и,", Всв ов" и 1,"= 1;. ПосколькУ в Данном слУчае хс=ио Ус=-Рс" и ге=-17 ДлЯ 1 =1 и 1 =2, получаелс нужный результат. Случай 2: 11 —— 1,=з. Тогда исо;Г-Вс для 1=1 и с=2.
Так в Ф КаК йС < и,, та и;=-и.,', О,'=-Рв . И С;=1, ЕСЛИ 1,=З, то х,=и;ис, ус=о; и Г,=з для 1 =1 и с==-2; нужное заключение, таКИМ ОбРаЗОМ, ПОЛУЧЕНО. ПРИ Сс'=1 РаССУжДаЕМ ДЛЯ йс И О,"таК же, как в случае 1. ГЗ Отметим, что ЯНРОВ-программа не обязана давать результат для каждой входной цепочки. Например, каждая программа, содержащая правило 5 — 55/5, где 5 — начальный символ, не распознает ни одной цепочки (точнее, для нее отношение ~+ пусто). Представление ЯНРОВ-программ, которым мы пользовались до сих пор, выбрано для удобства изложения. На практике желательно иметь правила более общего вида.
Для этого введем расширенные ЯНРОВ-правила и определим их смысл в терминах прежних правил: 17. А. Алв, Длв. Улвмвл. т. С 517 Гл. Б. АлгоРитмы РАзвОРА с ОГРАниченнь[ми БозВРАтхми ( ) Правило А ВС заменяет два правила А — ВС(Р и 1 '6 Р (, где Р— новый символ. (2) Правило А — В(С заменяет правила А- ВР(С и Р— е. (3) Правило А — В заменяет правила А ВС и С вЂ” е. (4) Правило А- А,Аи . А„для п > 2 заменяет множество правил А — А,В„В,— А,в„..., В„,— А„,В, „В„,— и-1 и' (6) Правило А — а,/а,/.../а„, где и,— цепочка нетермнналов, В С заменяет множество правил А — В /С, С вЂ” В (С ..., С -и/ и >, Си,— Ви,/Ви н В,— и„ВТ вЂ” а„..., В„а„.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
