Грамматики класса LL( (LL(-грамматики)
Следующий тип формальных грамматик уже может быть использован для практического применения. В дополнение к Q-грамматикам они могут содержать правила, правая часть которых начинается с нетерминального символа. Общий принцип функционирования МА в этом случае остается прежним. Единственное, что здесь необходимо, это определить выбирающие символы, по которым производится замена. Здесь нужно последовать уже опробованному методу. Если из правила A::=U…, начинающегося с нетерминала, можно построить цепочку A >> U... >> ... >> x..., которая начинается с теминального символа x, то такой символ можно считать выбирающим, поскольку он дает основания для применения правила A::=U.... Таким образом, множество выбирающих символов для правила, начинающегося с нетерминального символа, состоит из множества символов, которые являются первыми во всех возможных цепочках, выводимых из этого правила.
.
ВЫБ(A::=U…) = ПЕРВ(A::=U…)
Естественное требование к выбирающим символам остается прежним: для работоспособности метода необходимо, чтобы множества выбирающих символов для правил с одинаковой левой частью не пересекались. В качестве примера рассмотрим LL(1)-грамматику для четырех действий арифметики и скобок.
.
Правило Способ выбора Символы
E ::=TM ПЕРВ(T) a,(
M ::=-E - -
M ::=+E + +
M ::=e СЛЕД(M) ),#
T ::=FG ПЕРВ(F) a,(
G ::=*T * *
G ::=/T / /
G ::=e СЛЕД(G) ),+,-,#
F ::=a A a
F ::=(E) ( (
Множества выбирающих символов для правил, начинающихся с нетерминала и аннулирующих правил строятся в такой несложной грамматике путем простого перебора возможных цепочек синтаксического вывода:
.
Правило E ::= TM, способ построения ПЕРВ(T):
1. T >> FG >> a, выбирающий символ a
2. T >> FG >> (E), выбирающий символ (
.
Правило G ::= e, способ построения СЛЕД(G):
1. E >> TM >> FGM >> FG+E, символ +
2. E >> TM >> FGM >> FG-E, символ -
3. F >> (E) >> ™ >> (FGM) >> (FG), символ )
4. E# >> TM# >> FGM# >> FG#, символ #
Программа нисходящего разбора для LL(1)-грамматик с перечисленными выше правилами имеется в lgram1.cpp. Принципиально она не отличается от программы для Q-грамматик. Имеется массив указателей на строки-правила GR и массив указателей на строки выбирающих символов CH. Для S-правила выбирающие символы отсутствуют (NULL-указатель), поэтому производится сравнение с первым символом правой части правила, для остальных - последовательно проверяются все выбирающие символы в соответствующей строке.
char *GR[]=
{”E:TM”,”M:-E”,”M:+E”,”M:”,”T:FG”,”G:*T”,”G:/T”,”G:”,“F:a”,”F:(E)”,NULL };
char *CH[]=
{ “a(“,NULL,NULL,”)#”,”a(“,NULL,NULL,”+-)#”,NULL,NULL};
