S – грамматики и построение распознающих МА на их основе

Принципы работы распознавателя рассмотрим на примере весьма ограниченной грамматики – S-грамматики. Распространение этих идей на грамматики более общего вида позволяет строить распознаватели для синтаксиса реальных языков программирования. Перечислим ограничения S-грамматики:

· правая часть каждого правила должна начинаться с терминального символа;

· для двух любых правил, имеющих одинаковые левые части, начальные терминальные символы должны быть различны;

· не допускаются правила с пустой правой частью.

Следующая грамматика является S-грамматикой:

.

T = {a, b}, N = {Z, S, B}

Z:: bS#

S:: aA

S:: bSb

A:: aA

A:: b

Грамматика производит цепочки вида bbbaaaaabbb, где символ a повторяется не менее одного раза, а количество символов b справа и слева равны:

Z => bS# => bbSb# => bbbSbb# => bbbaAbb# => bbbaabbb#

Z => bS# => baA# => baaA# => baaaA# => baaab#

Сначала попробуем построить синтаксическое дерево «интуитивно», но в соответствии с принципами нисходящего разбора, изложенными в п.3.4:

· синтаксическое дерево строится сверху-вниз и справа-налево;

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

· выбор правила происходит на основе очередного «незакрытого» символа входной строки. Для S-грамматики принцип выбора очевиден: выбирается правило с правой частью, первый символ которой совпадает с очередным «незакрытым» - он его и закрывает.

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

· одновременное «закрытие» одинаковых символов в строке (очередной терминал) и символа в вершине стека - pop, next;

· замена в стеке нетерминала левой части правила на его правую часть, т.е. для правила вида S:: ab - действия pop, push(ab).

После определения роли и места стека в процессе функционирования магазинного автомата алгоритм его работы содержит вполне очевидную последовательность шагов:

1. в исходном состоянии в стек записывается начальный нетерминал, push(" Z");

2. если одновременно пусты стек и входная строка, т.е. M=0 & & I=0, то распознавание считается выполненным успешно;

3. если один из них пуст, а другой – нет, т.е. M=0 xor I=0, то распознаватель обнаруживает синтаксическую ошибку;

4. если в вершине стека находится терминальный символ, совпадающий с очередным символом входной строки, т.е. (I)=(M), то оба они исключаются из стека и строки соответственно, т.е. pop(M), next(I);

5. если в вершине стека находится терминальный символ, совпадающий с очередным символом входной строки, т.е. (I)< > (M) & & (M) Î T, то распознаватель обнаруживает синтаксическую ошибку;

6. если в вершине стека находится нетерминальный символ, то ищется правило, у которого левая часть совпадает с этим нетерминалом, а очередной символ строки совпадает с первым символом правой части правила, т.е. правило вида (M):: (I)b. В этом случае в стеке производится замена нетерминала левой части правила на правую часть, т.е. pop(M), push(M, (I)b).

Отметим, что алгоритм не строит синтаксическое дерево, т.е. не создает в памяти древовидную структуру данных. Дерево создается не «в пространстве», а разворачивается «во времени». Аналогичная картина имеет место в любой рекурсивной функции, там дерево рекурсивных вызовов также имеет временную, а не пространственную природу. Поэтому вопрос результата трансляции здесь остается открытым. Например, возможен такой способ построения синтаксического дерева в памяти:

· с каждым нетерминалом в стеке связан указатель на соответствующую вершину синтаксического дерева в памяти;

· замена в стеке левой части правила на правую сопровождается достраиванием поддерева, соответствующего правой части правила, помещаемой в стек.

Алгоритм работы МА можно представить и в табличной форме – таблице, описывающей реакцию автомата на каждую пару символов – «стек – входная строка». Заметим, что такой МА имеет единственное состояние. Ячейки таблицы заполняются в соответствии с действиями МА:

1. по замене левых частей правил на правые в соответствующих контекстах их выбора (сочетание пар символов – стек – строка);

2. по удалению пар идентичных символов из стека и строки;

3. по обнаружению ошибок при несовпадении пар терминальных символов в стеке и строке;

4. по обнаружению ошибок во всех остальных незаполненных ячейках;

5. по обнаружению несоответствия размерности данных в строке и стеке.

В заключение еще раз отметим основные свойства нисходящего распознавателя на основе МА:

· В стеке МА хранится недостроенная часть синтаксического дерева в виде последовательности незакрытых терминальных и нетерминальных вершин;

· Иначе говоря, в стеке хранится «будущий» или «ожидаемый» синтаксис определенный начальными (ключевыми) терминалами недоразобранных правых частей правил;

· Иначе говоря, в стеке хранятся «хвосты» выбранных, но недоразобранных правил;

· Синтаксическое дерево не строится распознавателем, но последовательность замен в стеке левых частей на правые соответствует обходу дерева справа-налево и сверху-вниз;

· Отсутствие подходящего правила для подстановки свидетельствует о синтаксической ошибке, а «незакрытая» часть входной строки – о месте ее возникновения.