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