Грамматики класса S (S-грамматики)
Грамматика строится по очень простому принципу:
правая часть каждого правила должна начинаться с терминального символа;
для двух любых правил, имеющих одинаковые левые части, начальные терминальные символы должны быть различны;
не допускаются правила с пустой правой частью.
Следующая грамматика является S-грамматикой:
.
T = {a,b}, N = {S,B}, N0 = S
S ::= aA
S ::= bSb
A ::= aA
A ::= b
Данная грамматика порождает цепочки вида aa…aaab и b..baaa..aaabb..b.
Для начала рассмотрим, как будет происходит нисходящий СА для такой грамматики:
дерево разбора строится сверху вниз;
на каждом шаге в полученной цепочке единственный нетерминальный символ должен быть заменен на правую часть одного из правил, в котором он присутствует в левой части;
принцип замены вытекает из самого определения S-грамматики. Для замены выбирается такое правило, у которого первый терминальный символ совпадает с очередным “незакрытым” символом в входной цепочке. Сказанное поясним примером:
.
b b a a b b b
| | | | |
| | | | b S ::=b
| | | | --
| | | a A b b S ::=aA
| | | ----
| | a A b b S ::=aA
| ----
| b S b b S ::=bSb
| -------
b S b
------- S ::=bSb
S
Начальный нетерминальный символ грамматики S. Поэтому он и является начальной цепочкой нисходящего вывода. Он может быть заменен на правую часть одного из двух правил S ::=aA или S::=bSb. Какое будет выбрано, определяется первым символом в распознаваемой цепочке. Поскольку это - b, то выбирается второе правило и цепочка примет вид bSb. Заметим, что первые символы в распознаваемой и выводимой цепочке совпадают, то есть перекрываются. Тогда второй символ распознаваемой цепочке оказывается “незакрытым” и соответствующим нетерминалу S в выводимой цепочке. Для этой пары такая процедура должна быть повторена.
Если использовать МА, то естественным местом для размещения выводимой цепочки является стек (магазин).
Тогда правила функционирования МА (пока еще не алгоритм, а перечень действий), можно определить так:
(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. Здесь рассмотрим его фрагменты.
char s[100]; char m[100]; int i,j;
void push(char *str) // поместить в стек “хвостом вперед”
{ char *q=str;
while (*q !=’\0’) q++;
q--; while (q >=str) { m[j++] = *q--; }
m[j]=’\0’; }
char *GR[]={ “S:aA”, “S:bSb”, “A:aA”, “A:b”, NULL };
int sintax()
{
int k; char *q;
i=0; j=1; m[0]=’S’; // Исходное состояние МА
while (1) // Завершение разбора
{ if ((s[i]==’\0’) && (j==0)) break;
if ((s[i]==’\0’) || (j==0)) return 1;
if ((s[i]==m[j-1])) // Совпадение символов
{ i++; j--; m[j]=’\0’; }
else
{ // Поиск правила (M)::=(I)xyz
for (k=0; GR[k]!=NULL; k++)
{
q=GR[k];
if ((*q==m[j-1]) && (*(q+2)==s[i])) break;
} //Нет правила
if (GR[k]==NULL) break;
else //Запись в стек “хвостом вперед”
{ j--; printf(“Правило: %s\n”,q);
push(q+2);}
}
printf(“Стек:%s Строка:%s \n”,m, s+i);
return 0;}}
