Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 64
Текст из файла (страница 64)
Если можно обойтись одной выходной цепочкой, то, обнаружив первую последовательность тактов, оканчивающуюся заключительной конфигурацией, можно прекратить моделирование Р. Разумеется, если ни одна последовательность не оканчивается заключительной конфигурацией, придется перепробовать все. Синтаксический анализ с возвратами можно представлять себе в следующем виде, Последовательности тактов располагают обычно в таком порядке, чтобы к моделированию очередной последовательности можно было перейти, возвратившись по последннм сделанным тактам (т. е. прослеживая их) к конфигурации, в которой возможен еще не испытанный альтернативный такт. Этот такт и надо затем сделать, На практике для ускорения процесса возврата пользуются локальными критериями, позволяющими, пе моделируя всей последовательности, определить, может ли она привести к заключительной конфигурации.
В этом разделе мы опишем, как можно детерминированно моделировать недетерминированный МП-преобразователь, используя возвраты. Затем исследуем два специальных случая. Первый †нисходящ анализ с возвратами, при котором для входной цепочки строится левый разбор. Во втором случае восходящии анализ с возвратами дает правый разбор. ч4 Т. Модепироваиие МП-преобразователи Рассмотрим МП-преобразователь Р и лежащий в его основе МП-автомат М. Если дана входная цепочка ш, то нам было бы удобно знать, что, хотя А1 может недетерминированно перепро- ГЛ. Ь. ОБ ИЕ НЕТО Ы СИНТАКСИЧЕСКОГО АНАЛИЗА Ы.. СИНТАКСИЧЕСКИЙ АНАЛИЗ С ВОЗВГАТАМИ бовать много последовательностей тактов, каждая из них огра. ничена по длине.
Если это так, то последовательности можно перепробовать в некотором разумном порядке. Если для входа и возможны бесконечные последовательности тактов, то по крайней мере в одном смысле нельзя осуществить полное прямое моделирование МП-автомата М. Определение.
МП-автомат М=(>е, Х, Г, 6, д„Л„Ь) пазы вается яезациклиеиющимся, если для каждой цепочки и> Е Х' найдется такая константа й, что если (»„и>, хь) ! — "(>), х, у), то т й . МП-преобразователь назовем незациклиеа>ощи ся, если лежащий в его основе МП-автомат незацикливающийся. Интересно, при каких условиях, налагаемых на грамматику б, левый или правый анализатор для б будет незацикливающимся. Предоставляем читателю в качестве упражнений доказать, что левый анализатор пе зацикливается тогда и только тогда, когда грамматика В ие леварекурсивна, а правый анализатор не зацикливается тогда и только тогда, когда 6 не содержит циклов и е-правил.
Мы покажем далее, что именно при этих условиях работают общие нисходящие и восходящие алгоритмы разбора с возвратами, хотя более общие алгоритмы работают на грамматиках из более широкого класса. Заметим, что условие отсутствия циклов и е-правил на самом деле не очень ограничительно. Для каждого КС-языка существует грамматика, удовлетворяющая этим условиям, и, более того, ее можно получить из произвольной КС-грамматики, порождающей этот язык, с помощью простых преобразований (алгоритмы 2.
!О и 2.11). Далее, если исходная грамматика однозначна, то преобразованная грамматика лево- и правопокрывает ее. Отсутствие левой рекурсии в этом смысле более стеснительное условие. Хотя для каждого КС-языка существует грамматика без левой рекурсии (теорема 2.18), может не быть покрывающей грамматики, удовлетворяющей этому условию (см.
упр. 3.4.29). Для того чтобы продемонстрировать, что такое анализ с возвратами и вообще моделирование недетермипированного МП-преобразователя, рассмотрим грамматику б с правилами (!) 5 — а5ЬЬ' (2) 5 — а5 (3) Ь'- с Левым анализатором для 6 служит МП-преобразователь Т с функцией переходов, определяемой равенствами 6(д, а, Ь)=((>), 5Ь5, !), (>>, 5, 2)) 6 (д, с, 5) ((>>, е, 3)) б(>1, Ь, Ь)=~(>), е, е)) Допустим, чта нам надо разобрать входную цепочку аасЬс. На рис, 4.1 изображено дерево, представляющее возможные последовательности тактов, которые может сделать Т для этого входа. С С С>Ь Ь СЬ СЬ 1 Ст Ркс.
4.|. Последолательиостн тактов вналнзьто!>ь. Вершина С, представляет начальную конфигурацию (», аасЬс, 5, е). Правила, определяющие Т, показывают, что из С„ыожно перейти в две следующие конфигурации, а именно С, =(>>, асбс, 5ЬЬ', 1) н С,=(>>, асбс, 5, 2). (Упорядочение здесь произвольное.) Из С, анализатор Т может перейти в конфигу- рации С,=(>),сбс,56565, 11) и С,— (с>, сЬс, 565, 12). Из С, можно перейти в конфигурацииС„= (»,сЬс,565,2!) и С„=-(>>, сбс, Ь', 22). Остальные конфигурации определяются однозначно.
Один из способов нахождения всех разборов данной входной цепочки состоит в определении всех допускающих копфигураций, достижимых из С, в дереве конфигура>тий. Это можно сделать, прослеживая все возможные пути, начинающиеся в С, и заканчивающиеся в конфигурации, из которой дальнейший переход невозможен. Можно ввести порядок, в котором будут перебираться пути, упорядочив выборы очередных тактов, доступных анализатору Т, для каждой комбинации состояния, входного символа и верхнего символа магазина.
Например, в том случае, когда применимо правило 6 (», а, 5), возьмем (>), 565, 1) в качестве первого выбора и (д, 5, 2) — в качестве второго выбора. Посмотрим теперь, как можно определить все допускающие конфигурации анализатора Т, систематнчески прослеживая все возможные для Т последовательности тактов. Допустим, что из С, ., делая первый выбор, мы получаем С,. Из С„снова делая первый выбор, получаем С,.
Продолжая в том же духе, мы "Рослеживаем последовательность конфигураций С„, ффф С, Ст. Вершина С| представляет заключительную конфигурацию (», е, Ь5, 1133), которая не является допускающей. Чтобы Згэ ГЛ. 4. ОБЩИЕ МЕТОДЫ СИНТАКСИЧЕСКОГО АНАЛНЗА определить, существует ли другая заключительная коифигураг ция, можно вернуться (сделать <возврат») по дереву, пока не встретится конфигурация, для которой возможен другой, еще не рассмотренный выбор очередного такта.
Поэтому мы должны быть в состоянии восстановить конфигурацию С, по конфигурации С,. Возврат к С, из С, может включать обратный сдвиг головки на входе, восстановление предыдущего содержимого магазина и удаление выходных символов, выданных при пере. ходе от С, к С,. Восстановив С„мы должны сделать новый выбор очередного такта (если таковой возможен). Так как в вершине С, других выборов нет, мы продолжаем возврат к С, и далее к С» и С,. Из С, с помощью второго выбора такта для правила 6 (»г, и, 5) можно получить конфигурацию С,. Затем, переходя через конфигурации С„н С„можно получить конфигурацию С„=~ =(д, е, с, 1233), которая оказывается допускающей.
После этого можно выдать в качестве выхода левый разбор 1233. Если мы заинтересованы в получении только одного разбора входной цепочки, то можно остановиться. Но если нас интересуют все разборы, можно вернуться к конфигурации С» и затем испробовать все конфигурации, достижимые из С,.
Вершина С„представляет другую допускающую конфигураци!о, а имепно (д, е, е, 2!33). Мы остановимся после того, как рассмотрим все последовательности тактов, которые может сделать Т. Если входная цепочка построена синтаксически неправильно, то придется рассмотреть все возможные последовательности тактов. Если исчерпаны все последовательности тактов, а допускающая конфигурация пе обнаружена, надо выдать сообщение об ошибке. Описанный нами анализ иллюстрирует характерные черты алгоритма, который иногда называют недетерминироеаннь»м, т. е. на некоторых его шагах допускаются выборы и все их нужно перебрать' ).
На самом деле систематически порождаются все конфигурации, к которым могут привести данные, обрабатываемые алгоритмом, пока не встретится нужное решение или не исчерпаются все возможности. Понятие недетерминированного алгоритма применимо, таким образом, не только к моделированию недетерминированного автомата, но также и ко многим другим проблемам. Интересно отметить, что нечто аналогичное проблеме остановки для МП-преобразователей всегда приводит к вопросу о том, можно ли промоделировать недетермипированный алгоритм детерминированно. Конкретные приме. ры недетермннированиых алгоритмов даны в упражнениях.
') Лучше было бы на»неть такой алгоритм пер«берлын. Термин «перетер. миннронанный елгорнтм» обычно употребляют и том же смысле, что и «не' детерминированный автомат» (прои»польного типа). — Прим. перел, 320 4,1 СИПТАКСИЧЕСКИй АНАЛИЗ С ВОЭВРАТАМИ При синтаксическом анализе задается обычно грамматика, а не МП-преобразователь. Поэтому мы обсудим сейчас восходящий и нисходящий анализ прямо в терминах заданной грамматики, а не левого или правого анализатора для нее. Однако особ аботы соответствующих алгоритмов состоит именно в иной иапо следовательном моделировании анализатора с магази т" мятью. Но вместо обхода всевозможных последовательнос ей тактов анализатора мы будем обходить всевозможные выводы, совместимые с данным входом. йА.2. Нефорььвпьиое описание нисходящего разбора Происхождение названия нисходящего синтаксического анализа связано с тем, что дерево разбора входной цепочки строится сверху вниз, начиная с корня и нисходя к листьям.
Начнем с тог „ го что возьмем какую-нибудь грамматику н для каждого части нетерминала занумеруем в некотором порядке все правые ча правил, у которых левой частью является данный нетерминал (их называют альтернатиопмг! этого ндперминала), т. е. если А- а,!а, ~...)ан — все А-правила данной грамматики, то припишем некоторый порядок цепочкам а! (альтернативам нетерминала А). Например, рассмотрим грамматику, упомянутую в предыдущем разделе. Ее 5-правила 5 п5Ы! а5!с будем использовать в том порядке, как они написаны, т. е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
