Моделирование МП-преобразователей

Большинство МП-преобразователей, рассмотренных в предыдущем разделе, были в общем случае недетерминированными. Во второй части пособия, посвященной построению компиляторов, будут рассмотрены детерминированные левые и правые анализаторы. Там же будут изложены строгие недетерминированные алгоритмы нисходящего и восходящего разбора. Остановимся здесь лишь на основных моментах моделирования недетерминированных МП-автоматов и преобразователей.

Рассмотрим недетерминированный МП-преобразователь P и лежащий в его основе МП-автомат M. Допустим, что все последовательности тактов, которые может сделать P для входной цепочки w ограничены по длине.Тогда общее число различных последовательностей тактов МП-преобразователя P тоже конечно, хотя, возможно, и экспоненциально зависит от длины цепочки w. Прямой способ детерминированного моделирования P состоит в том, чтобы каким-то образом линейно упорядочить последовательности тактов и затем в предписанном порядке промоделировать каждую последовательность.

Если необходимо получить все выходные цепочки для данной входной цепочки w, то моделируются все последовательности тактов. Если можно обойтись одной выходной цепочкой, то, обнаружив первую последовательность тактов, оканчивающуюся заключительной конфигурацией, можно прекратить моделирование P. Разумеется, если ни одна последовательность не заканчивается заключительной конфигурацией, прийдется перепробовать все.

Последовательности тактов располагают обычно в таком порядке, чтобы к моделированию очередной последовательности можно было перейти, возвратившись по последним сделанным тактам (т. е. прослеживая их) к конфигурации, в которой возможен еще не испытанный альтернативный такт. Этот такт и надо затем промоделировать. Не случайно алгоритмы в основе которых лежит рассмотренная схема, носят название алгоритмов синтаксического анализа с возвратами.

Основное требование этих алгоритмов - ограниченность по длине каждой из последовательностей тактов. Если для входа w возможны бесконечные последовательности тактов, то очевидно, что прямое моделирование преобразователя P невозможно. Интуитивно ясно, а в дальнейшем будет показано, что левый анализатор не зацикливается тогда и только тогда, когда грамматика, лежащая в его основе не леворекурсивна. Правый анализатор не зацикливается, когда соответствующая грамматика не содержит циклов и e -правил. Все перечисленные условия не очень ограничительны, так как всегда можно построить эквивалентную КС-грамматику, удовлетворяющую этим условиям.

Для того чтобы продемонстрировать, что такое анализ с возвратами и вообще моделирование недетерминированного преобразователя, рассмотрим пример.

Пример 6.11. Рассмотрим грамматику G с правилами

(1) S ® aSbS

(2) S ® aS

(3) S ® c

Левым анализатором для G служит преобразователь T со следующей функцией переходов:

d (q, a, S) = {(q, SbS, 1), (q, S, 2)}

d (q, c, S) = {(q, e, 3)}

d (q, b, b) = {(q, e, e)}

Допустим, что нам необходимо разобрать входную цепочку aacbc. На рис. 6.3 изображено дерево, представляющее возможные последовательности тактов, которые может сделать T для этого входа.

Вершина C₀ представляет начальную конфигурацию (q, aacbc, S, e). Правила, определяющие T показывают, что из C₀ можно перейти в две следующие конфигурации, а именно С₁ = (q, acbc, SbS, 1) и C₂ = (q, acbc, S, 2). (Упорядочение здесь произвольное.) Из C₁ анализатор T может перейти в конфигурации C₃ = (q, cbc, SbSbS, 11) и C₄ = (q, cbc, SbS, 12). Из C₂ можно перейти в конфигурации C₁₁ = (q, cbc, SbS, 21) и C₁₅ = (q, cbc, S, 22). Остальные конфигурации определяются однозначно.

Посмотрим теперь, как можно определить все допускающие конфигурации анализатора T, систематически прослеживая все возможные для T последовательности тактов. Допустим, что из C₀, делая первый выбор, мы получаем C₁. Из C₁, снова делая первый выбор, получаем C₃. Продолжая в том же духе, мы прослеживаем последовательность конфигураций C₀, C₁, C₃, C₅, C₆, C₇. Вершина C₇ представляет заключительную конфигурацию (q, e, bS, 1133), которая не является допускающей. Чтобы определить, существует ли другая заключительная конфигурация, можно вернуться (сделать “возврат”) по дереву, пока не встретится конфигурация, для которой возможен другой, еще не рассмотренный выбор очередного такта. Поэтому мы должны быть в состоянии восстановить конфигурацию C₆ по конфигурации C₇. Возврат к C₆ из C₇ может включать обратный сдвиг головки на входе, восстановление предыдущего содержимого магазина и удаление выходных символов, выданных при переходе от C₆ к C₇. Восстановив С₆, мы должны сделать новый выбор очередного такта (если он возможен). Так как в C₆ других альтернатив нет, мы продолжаем возврат к C₅ и далее к C₃ и C₁. Из C₁ с помощью второго выбора такта для правила d (q, a, S) можно получить конфигурацию C₄, а затем переходя через С₈ и С₉, можно получить конфигурацию С₁₀ = (q, e, e, 1233), которая оказывается допускающей. После этого можно выдать в качестве выхода левый разбор 1233 и завершить моделирование. Но если нас интересуют все разборы, можно вернуться к конфигурации С₀ и испробовать все конфигурации, достижимые из C₂. Вершина C₁₄ = (q, e, e, 2133) представляет другую допускающую конфигурацию.

Если входная цепочка построена синтаксически неверно, то необходимо рассмотреть все возможные последовательности тактов и если все они исчерпаны, а допускающая конфигурация не обнаружена, надо выдать сообщение об ошибке. 

Рассмотренный процесс анализа иллюстрирует характерные черты недетерминированного (переборного) алгоритма, допускающего на отдельных шагах альтернативы, которые нужно перебрать. Подробно эти алгоритмы и подходы к их реализации будут рассмотрены во второй части пособия.

Дата добавления: 2015-06-27