Курс Основы построения трансляторов


Грамматики класса S (S-грамматики) - часть 2


Тогда правила функционирования МА (пока еще не алгоритм, а перечень действий), можно определить так:

(I)=(M)  ==> pop(M), next(I),  если текущий символ строки совпадает с символом в вершине стека, то исключить его из стека и продвинуться в строке к следующему (совпадающие символы в начале выводимой и распознаваемой цепочек взаимно уничтожаются);

(M) # (I) && (M) in T =>> Error, если текущий символ строки и символ в вершине стека не совпадают, и при этом символ в стеке является терминальным, то это синтаксическая ошибка

(M) in N, если в вершине стека находится нетерминальный символ, то ищется правило, которое в левой части имеет этот символ, а его правая часть начинается с очередного символа в распознаваемой строке, то есть по нашим обозначениям имеет вид  (М)::=(I)xyz , тогда в стеке левая часть правила заменяется на правую, то есть по нашим обозначениям выполняются действия pop(M), push(M,”(I)xyz”);

распознавание выполнено успешно, когда и стек и строка одновременно становятся пустыми, то есть I=0 && S=0, в противном случае - синтаксическая ошибка;

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

Перечисленные правила могут быть использованы для представления поведения конкретного КА в виде таблицы. Заметим, что такой МА имеет единственное состояние. Таблица определяет реакцию МА на любую комбинацию символов в стеке и строке. Дополнив множество терминальных символов  символом конца строки (цепочки) “#”, получим полную картину поведения МА. Для нашего примера она будет иметь вид:


.

(M)\(I) a               b                #

a       pop(M),next(I)  Error            Error

b       Error           pop(M),next(I)   Error

A       pop(M),push(aA) pop(M),push(b)   Error

S       pop(M),push(aA) pop(M),push(bSb) Error

#       Error           Error            Success

 

Алгоритм нисходящего разбора для S-грамматик с произвольным набором правил приведен в sgram2.cpp. Здесь рассмотрим его фрагменты.

 




Начало  Назад  Вперед