Грамматики класса Q (Q-грамматики)
Данная грамматика отличается от S-грамматики наличие дополнительных аннулирующих правил вида:
.
A ::= e, где ? - пустая строка
Такое правило будем так и называть q-правилом. Приведенную выше S-грамматику можно превратить в Q-грамматику.
T = {a,b}, N = {S,B}, N0 = S
S ::= aA
S ::= bSb
A ::= aA
A ::= e
Данная грамматика порождает цепочки вида aa…aaa и b..baaa..aaab..b. Нетрудно заметить, что аннулирующее правило используется для порождения цепочек, которые могут включать повторяющиеся произвольное число раз фрагменты без явного признака их окончания. В данном примере это имеет отношение к последовательности символов a..a , порождаемых двумя последними правилами.
Для Q-грамматик может быть использован тот же метод разбора с применением МА, однако сам принцип необходимо расширить для аннулирующих правил. Заметим, что при замене нетерминального символа правой частью одного из правил мы руководствовались первым терминальным символом правил, которой можно назвать ВЫБИРАЮЩИМ. Тогда для обычного S-правила условием замены является совпадение текущего “незакрытого” символа в распознаваемой цепочке с ВЫБИРАЮЩИМ символом правила. Для Q-правила аналогично можно ввести понятие выбирающего символа. Рассмотрим, на каком основании тот или иной символ можно назвать выбирающим. Пусть в процессе вывода произвольной цепочки из начального нетерминала S мы получаем цепочку с последовательностью символов Ab в некотором контексте. Если при этом A является левой частью аннулирующего правила, то мы имеем все основания его применить. Тогда символ b, следующий за A в любом другом контексте синтаксического разбора является определяет возможность применения такого правила. Сказанное поясним примером.
S >> bSb >> baAb >> ba(A::= e)b >> baeb >> bab
Таким образом, множество выбирающих символов для применения аннулирующего правила A::=?
состоит из множества всех символов, которые могут следовать за A в любой промежуточной цепочке, выводимой из S.
.
ВЫБ(A::=e) = СЛЕД(A)
Построить множество символов, следующих за данным нетерминалом можно для простых грамматик и неформально, рассматривая возможные варианты порождения цепочек. В рассматриваемой грамматике приведенный выше вариант является одним из двух случаев. Второй случай предполагает, что в распознавании должен участвовать символ конца цепочки.
S# >> aA# >> … >> a…aA# >> a…a(A::=e)# >> a…a#
Однако применить принцип работы МА для S-грамматик к Q-грамматикам можно только в том случае, если множества выбирающих символов для аннулирующих правил и для обычных Q-правил не будут пересекаться. Иначе в работе МА возникает неоднозначность, которая исключает гарантированное распознавание. Таблица выбирающих символов для нашей грамматики будет выглядеть так:
.
Правило Выбирающие символы
S ::= aA a
S ::= bSb b
A ::= aA a
A ::= e СЛЕД(A)={b,#}
Поскольку аннулирующее правило имеет пустую правую часть, то его применение в алгоритме распознавания в МА сопровождается выталкиванием из стека текущего нетермиального символа. Таблица действий МА с учетом Q-правила будет иметь вид:
.
(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) pop(M)
S pop(M),push(aA) pop(M),push(bSb) Error
# Error Error Success
Алгоритм нисходящего разбора для S-грамматик с произвольным набором правил приведен в qgram1.cpp. Здесь рассмотрим только его отличия от предыдущего. При поиске необходимого правила проверяется, не является ли оно аннулирующим (пустым). В этом случае производится сравнение текущего символа строки (распознаваемой цепочки) с выбирающими символами из строковой константы CH[k]:
char *GR[]={ “S:aA”, “S:bSb”, “A:aA”, “A:”, NULL };
char CH[]={ NULL,NULL,NULL,”b”};
for (k=0; GR[k]!=NULL; k++) // Поиск правила
{ q=GR[k];if(*q==m[j-1]) // Левая часть ???
{ if (*(q+2)!=’\0’) // S-правило
{ if (*(q+2)==s[i]) break; }
else // Q-правило
{ // Выбирающий символ
for (f=CH[k]; *f !=’\0’; f++)
{ if (s[i]==*f) break;
if ((s[i]==’\0’) && (*f==’*’)) break;
}
if (*f != ‘\0’) break;
}}}
