![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
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. по обнаружению несоответствия размерности данных в строке и стеке.
В заключение еще раз отметим основные свойства нисходящего распознавателя на основе МА: · В стеке МА хранится недостроенная часть синтаксического дерева в виде последовательности незакрытых терминальных и нетерминальных вершин; · Иначе говоря, в стеке хранится «будущий» или «ожидаемый» синтаксис определенный начальными (ключевыми) терминалами недоразобранных правых частей правил; · Иначе говоря, в стеке хранятся «хвосты» выбранных, но недоразобранных правил; · Синтаксическое дерево не строится распознавателем, но последовательность замен в стеке левых частей на правые соответствует обходу дерева справа-налево и сверху-вниз; · Отсутствие подходящего правила для подстановки свидетельствует о синтаксической ошибке, а «незакрытая» часть входной строки – о месте ее возникновения.
|