Множество выбор в правилах грамматики

Пример:

A -> BCc
A -> gDB
B -> $
B -> bCDE
C -> DaB
C -> ca
D -> $
D -> dD
E -> gAf
E -> c

Функция Перв.

Перв(Перв(10) = {c}
Перв(9) = {g}
Перв(8) = {d}
Перв(Перв(7) = {$}
Перв(6) = {c}
Перв(E) = {c,g}
Перв(D) = {d}
Перв(5) = Перв(D) & Перв(a)  = {d,a}
Перв(4) = {b}
Перв(3) = {$}
Перв(2) = {g}
Перв(1) = Перв(B) & Перв(C) = {b,c,d,a}

Функция След.

След(A) = {f}
След(C) = {c} & Перв(D) & Перв(E) = {c,d,g}
След(B) = Перв(С) & След(A) & След(C)= {a,d,c,f,g}
След(D) = Перв(B) & След(A) & Перв(E) &{a} = {b,f,g,c,a}
След(E) = След(B) = {a,d,c,f,g}      

Множество выбор:

Если:

1. A -> i
   i  не равно $
   Выбор(A -> i) = Перв(i)
2. A -> $
   Выбор(A -> $) = След(A)
3. A -> i
   i  равно $
   Выбор(A -> i) = Перв(i) & След(A) & {$}

Определение:

Контекстно-свободная грамматика, называется LL(1) грамматикой, если множество выбор построен для правил с одинаковым левым нетерминалом не содержит одинаковых элементов. Под классом LL(1) грамматики является простая грамматика и слаборазделенная грамматика.

Пример: Построить правило грамматики для арифметического выражения. В правой части находятся идентификаторы A,B. В левой части операции +/-. Идентификаторы i,j. Выражение может содержать вложенные скобки.

a,b = (i+/- j) + (i+/-i+/- j …) или a,b = i+/- j + i+/-i+/- j …

Решение:

I -> A = S;
S -> BR | (SR)R
R -> DBR | $
B -> i | j
D -> + | -

Перв(1) = Перв(A) = {a,b}
Перв(2.1) = {i,j}
Перв(2.2) = {(}
Перв(3.1) = {+,-}                         
Перв(3.2) = $
Перв(4.1) = {i}
Перв(4.2) = {j}
Перв(5.1) = {+}
Перв(5.2) = {-}
Перв(6.1) = (a)
Перв(6.2) = {b}
След(A)  = {=}
След(S) = {;} & Перв(R) = {;,+,-}
След(B) = Перв(R) & След(S) = {+,-,;}
След(D) = Перв(B) = {i,j}
След(R) = След(S) & {)} = {;,)}

Выбор:

Выбор(1) = Перв(A) = {a,b}
Выбор(2.1) = Перв(B) = {i,j}
Выбор(2.2) = {(}
Выбор(3.1) = Перв(D) = {+,-}
Выбор(3.2) = След(R) = {;,),+,-}
Выбор(4.1) = {i}
Выбор(4.2) = {j}
Выбор(5.1) = {+}
Выбор(5.1) = {-}
Выбор(6.1) = {a}
Выбор(6.1) = {b}

Так как правило 3.1 и 3.2 содержит элементы, которые пересекаются (+,-), то данная грамматика не является LL(1) грамматикой, а грамматика нуждается в преобразовании.

Преобразование грамматики заключается в том, чтобы после буквы S необходимо удалить букву R в правиле 2.2. Тогда из множества выбор для правила 3.2 уйдут знаки +,-. Следовательно множество выбор для правил 3.1 и 3.2 не будет содержать одинаковых элементов.