6. 5. Моделирование мп-преобразователей

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

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

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

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

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

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

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

(1) S  aSbS

(2) S  aS

(3) S  c

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

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

 (q, c, S) = {(q,  , 3)}

 (q, b, b) = {(q,  ,  )}

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

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

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

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

Упражнения

6.1. Найдите восходящие и нисходящие МП-автоматы для следующих грамматик:

(а)

S  aSb

(б)

S  ASb

A  SAa

(в)

S  SSA

A  0A1S01

6.2. Найдите грамматику, порождающую L(R), где

R = ({q₀, q₁, q₂}, {a, b}, {Z₀, A},  , q₀, Z₀, {q₂})

и  определяется равенствами

 (q₀, a, Z₀) = (q₁, AZ₀)

 (q₀, a, A) = (q₁, AA)

 (q₁, a, A) = (q₀, AA)

 (q₁,  , A) = (q₂, A)

 (q₂, b, A) = (q₂,  )

Для тупиковых нетерминалов строить правила не обязательно.

6.3. Постройте ДМП-автоматы, допускающие следующие языки:

(а) {0 ⁿ 1^m m  n},

(б) {  состоит из равного числа символов a и b,

(в) L(G₀), где G₀ - обычная грамматика простых арифметических выражений.

6.4. Покажите последовательности конфигураций МП-преобразователей из примеров 6.9, 6.10, которые они проходят допуская цепочку (a+a)a.

ЗАКЛЮЧЕНИЕ

Завершая пособие, отметим, что очень многие аспекты теории формальных языков остались за пределами предлагаемого материала. Это лишь введение в математическую лингвистику и основы вычислимости. Будем считать это первым знакомством с данной теорией и автор считал бы свою задачу выполненной, если хотя бы часть из Вас заинтересовалась ею и захотела просмотреть одну из монографий, предложенных в списке литературы.

Та часть теории формальных языков, которая изложена в пособии, имеет ярко выраженную практическую направленность. Рассмотренные вопросы позволят вам глубже понять и осмыслить алгоритмы, лежащие в основе синтаксического анализа и компиляции, которые автор предполагает осветить во второй части пособия - “Основы построения компиляторов”. Поэтому здесь мы не ставим точку

82