Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 69
Текст из файла (страница 69)
Как и раньше, алгоритм может находиться в одном из трех состояний д, Ь или Е В магазине Г.1 будет храниться цепочка терминалов и нетерминалов, из которой выводится часть входной цепочки, расположенная слева от входного указателя. В магазине (.2 будет храниться история переносов и сверток, необходимых для получения из входной цепочки содержимого магазина Г.!.
(3) Начальная конфигурация алгоритма — (д, !$, е). (4) Сам алгоритм работает так, Начинаем с попытки применить шаг 1. Шаг 1. Попытка свертки (д, |, ар, у) « — (д, 1, аА, )у) 340 при условии, что А — р †прави из Р с номером 1 и р †первая правая часть в линейном упорядочении, определенном в (1), которая является суффиксом цепочки а«).
Номер этого правила записывается в 52. Если шаг 1 применим, повторить его. В противном случае перейти к шагу 2. Шаг 2. Перенос (д, !', а, у) «-(|1, !'+1, аоо зу) при условии, что !'Фн-«-1. Перейти к шагу !. Если ! =- и+1, перейти к шагу 3. Г!ри выполнении шага 2 !'-й входной символ переносится в верхнюю часть магазина 51, позиция входного указателя увеличивается и в магазин Г.2 записывается з, чтобы указать, что сделан перенос. Шаг 3. Допускание (д, и+1, $5, у)« — (г, и+1, $5, у) Выдать Ь (у), где Ь вЂ” гомоморфизм, определенный равенствами Ь(в) =в, Ь ()) =1 для всех номеров правил, Ь(у) — обращенный правый разбор цепочки ц>.
После этого остановиться. Если шаг 3 неприменим, перейти к шагу 4. Шаг 4. Переход в состояние возврпо>а (д, и+1, а, у) « — (Ь, и+1, а, у) при условии, что аФ$5, Перейти к |пагу 5. Шаг 5. Возврат (а) (Ь, |, аА, (у) « — (>), |, а'В, йу) если А- () — правило из Р с номером 1', а следующим правилом в упорядочении (!), правая часть которого является суффиксом цепочки ар, является правило В- р' с номером Ь. (Заметим, что а()=а'р'.) Перейти к шагу 1. (Здесь происходит возврат к предыдущей свертке и делается попытка свертки с помощью следующей альтернативы.) (б) (Ь, и+1, аА, )у) «-(Ь, и+1, а«), у) если А р — правило из Р с номером 1' и для цепочки ар пе остается никакой другой свертки, Перейтп к шагу 5. (Если других сверток не существует, надо «взять назад» данную свертку н продолжать возврат, оставляя входной указатель на позиции и+ 1.) (в) (Ь, >, аА, 11!) « — (|1, !+1, ара, ву) если ! Фа+1, А — 5 — правило из Р с номером !' и для ар не остается никакой другой свертки.
Здесь символ а=-а; перено- Гл. 4. ОБщие методы синтАксическОГО АньлизА сится в магазин П, а символ з поступает в Е2. Перейти к шагу 1. (Мы вернулись к предыдущей свертке и„так как других сверток иет, попробуем сделать перенос,) (г) (Ь, 4, аа, зу) «-(Ь, ! — 1, а, у) если наверху магазина Е2 находится символ переноса з, (Здесь в позиции ! исчерпаны все альтернативы и надо «взять назад» операцию переноса.
Входной указатель сдвигается влево, терминальный символ устраняется из Е!, а символ переноса з— из Е2). Если этот шаг невыполним„объявить об ошибке. Пример 4.4. Применим описанный алгоритм восходящего разбора к грамматике С с правилами (!) Е- Е+ Т (2) Е- Т (3) Т вЂ” ТБР (4) Т- Р (б) Р- а Если наверху магазина Ы появится Е+ Т, то сначала попытаемся сделать свертку, используя Е -- Е+ Т, а потом — используя Š— Т. Если же появится Т ь Р, то сначала попробуем Т вЂ” ТБР, а потом Т вЂ” Р, Для входа а»а восходящий алгоритм пройдет через конфигурации 2, $а, 2, $Р, 2, $Т, 2, $Е, 3, $Е», Е» Зла (д, 1, $, е) «- (д, « — (ч «-(у'.
«-(4,' « — (ч « — (у «-(у,' «-(у', 'Г- (4 «- (ь, « — (Ь, « — (» 'à — (Ь ; — (ь, «-(Ь,' «-(у', (4 «-(4', «- (4 « — (ч «- (( 4, $ а, 4, $Е»Р, 4, $Е»Т, 4, $Е»Е, 4, $Е«Е, 4, $Е»Т, 4, $Е»Р, 4, $Е»а, 3, $ЕА, 2, $Е, 3, БТ», 4, $Таа, 4, $Т»Р, 4, $Т, 4, $Е, 4, $Е, з) Бз) 45з) 245з) з245з) зз245з) бзз245з) 45зз24бз) 245зз245з) 245зз245з) 45зз245з) 5зз24бз) зз245з) з245з) 245з) з45з) зз45з) 5зз45з) ЗБАБ45з) 235зз45з) 235зз4бз) (З 4.!, синтхкс!4'!ес!«Нн АнАлиз с ЕОЗВРАТАми Корректность алгоритма 4.2 можно доказать способом, аналогичным тому, которым было показано, что нисходящий алгоритм работает правильно.
Мы дадим здесь лишь набросок доказательства, оставляя ббльшую часть деталей в качестве упражнения. Определение. Пусть С=(х!«, Х, р, $) — КС-грамматика. Будем называть п частичным правым разбором, совместимым с «с, если существуют такие а Е (Ь) 0 Х)' и префикс х цепочки иц что а =>„я х. Лемма 4.5. Пусть С вЂ” КС-грамматика без циклов и без е-правил, Тогда найдется такая констан!па с, что ~«исло частичных правых разборов, совместимых с входной цепочкой длины и, не превосходит с". Д о к а з а т е л ь с т в о.
Упражнение. Теорема 4.4. Алгоритм 4.2 правильно находит правый разбор цепочки и!, если он су«цествует, и сигнализирует об ошибке в противном случае, До к аз а тел ь от в о. По лемме 4.5 число частичных правых разборов, совместимых с входной цепочкой, конечно. В качестве упражнения предлагаем показать, что пока алгоритм 4.2 не найдет разбор входной цепочки, он перебирает в естественном порядке все частичные правые разборы. А именно, каждый частичный правый разбор кодируется последовательностью индексов правил и символов переноса (з), и алгоритм 4,2 рассматривает все такие кодирующие последовательности в лексико- графическом порядке.
Зтот лексикографический порядок Определяется порядком символов, в котором з находится па последнем месте, а упорядочение индексов правил задается шагом 1 алгоритма 4,2. Заметим, что не каждая последовательное!ь таких символов будет кодом совместимого частичного правого разбора. [3 Так же, как для алгоритма 4.1, можно показать, что длины магазинных списков в конфигурациях алгоритма 4.2 линейно зависят от длины входной цепочки.
Теорема 4.5. Пусть для каждого символа из магазинных цепочек, участвую«цих в конфигурациях алгоршпма 4.2, требуется только одна ячейка, и пусть число влементирных операций, необходимых для вьыисления одного и!ага алгоритма 4.2, ограничено. Тогда для входной цепочки длины и алгоритму 4,2 требу!отся ся емкость па,ияти с,п и время с",, где с, и с,— некоторые константы. Доказательство. Упражнение. П ГЛ.
4, ОБЩИЕ МЕТОДЫ СИНТАКСИЧЕСКОГО АНАЛИЗА Известно несколько модификаций основного алгоритма восхоеящего разбора, ускоряющих его работу. (1) Можно добавить,,заглядьГвание вперед" так, что если збнаруживается, что следующие й символов справа от входного указателя не могут следовать за А ни в какой правовыводимой цепочке, то в этот момент не надо делать свертку, соответствуощую А-правилу. (2) Можно попытаться упорядочить сьэртки так, чтобы наиболее вероятные из них делались первыми.
(3) Можно добавить информацию, позволяющую определять, приведут ли некоторые свертки к успеху. Например, если первая свертка использует правило А- а, ... а„, где а,— первый входной символ, и мы знаем, что нет такой цепочки уЕХ'„что 5=О'Ау, то эту свертку можно сразу исклк>чить. Вообще мы хотим быть уверены в том, что если 8а — содержимое магазина Е1, то а — префикс правовыводимой цепочки.
Хотя проверить это, вообще говоря, сложно, некоторые понятия (такие, как предшествование, обсуждаемое в гл. 5), помогают исключить многие цепочки а, которые могли бы появиться в Е!. (4) Можно модифицировать алгоритм так, чтобы ускорить возвраты.
Например, можно записать информацию, позволяющую сразу восстановить предыдущую конфигурацию, в которой была сделана свертка. Некоторые из этих соображений изучаются в упр. 4.!.12— 4,!.14 и 4.1.25. Замечания по поводу обнаружения н исправления ошибок, относящиеся к нисходящему возвратному алгоритму, применимы и к восходящему алгоритму. эпэджнения 4.1.1, Пусть 6 определяется правилами 5 АЗ(а А- ЬЗА!Ь Какую последовательность шагов сделает алгоритм 4.1, если альтернативы рассматриваются в том порядке, как они записаны, а входной цепочкой является (а) Ьа? (б) ЬаЬа? Какие будут последовательности шагов, если альтернативы рассматриваются в обратном порядке? 4.1.2.
Пусть 6 состоит из правил 5- ЗА~А А- ЛА ~Ь 344 упРАжн е ния Какую последовательность шагов сделает алгоритм 4.2, если более длинная альтернатива считается первой, а входной цепочкой является (а) аЬ? (б) аЬЛЬ? Что будет, если первой считать более короткую альтернативу? 4.1.3. Покажнте, что каждая КС-грамматика без циклов, не порождающая пустой цепочки, правопокрывается грамматикой, для которой работает алгоритм 4.2, но может не левопокрываться грамматикой, для которой работает алгоритм 4.1.
*4.1.4. Покажите, что рекуррентные соотношения Е? (1) = 1 Е> (Г() = (Е! (~ — 1)')+ 1 определяют функцию 0 (Г() = ~ю (, где й — некоторое вещественное число, а 1х! — наименьшее целое число» х. Здесь й= 1,502837.... 4.1.6. Дополните доказательство следствия 2 леммы 4.4, 4.1.6. Модифицируйте алгоритм 4.1 так, чтобы можно было отказаться от использования альтернативы, если из левовыводимой цепочки, получающейся после ее применения, нельзя вывести Ь очередных входных символов, где Й вЂ” фиксированное число. 4.1.7. Модифицируйте алгоритм 4.1 так, чтобы он работал для произвольной грамматики, наложив ограничения на рост длин магазинов Е1 и Е2.
**4.1.8. Дайте необходимое н достаточное условие, которому должна удовлетворять входная грамматика для того, чтобы алгоритм 4.1 никогда не оказывался в состоянии возврата. 4.1.9. Докажите лемму 4.5. 4.1.10. Докажите теорему 4.5. 4.1.11, Моднфицируйте алгоритм 4.2 так, чтобы он работал для произвольной грамматики, наложив ограничения на длины магазинов Е! и Е2. быст 4 1.12. Модифицируйте алгоритм 4.2 так, чтобы он работал стрее, введя в него проверку того, что частичный правый Разбор вместе с частью входной цепочки, расположенной справа От указателя, не содержат ни одной из цепочек длины й,'котоРые не могут быть частью правовыводимой цепочки.
4,! 1 18. Модифицируйте алгоритмы 4.1 и 4.2 так, чтобы они могли ли возвращаться к любой специально выделенной конфнгу- ГЛ. 4, ОБЩИЕ МЕТОДЫ СИПТАКСИ'!ЕСКОГО АНАЛИЗА УПРАЖНЕИИЯ рации с помощью конечного числа разумно определенных элементарных Операций. "*4.1.14. Найдите необходимое и достаточное условие, которому должна удовлетворять грамматика, чтобы алгоритм 4.2 работал на ней без возвратов. То же для алгоритма, модифицированного, как в упр. 4.1.12. 4.1.15. Найдите грамматику без циклов и без е-правил, для которой алгоритм 4.2 тратит экспоненциальное время.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
