Построение команд синтаксического анализатора

1. A -> aj
   Певр(A -> aj) = {a}
   f(S,a,A) = (S,j*)
2. A -> $
   f*(S,x,A) = (S,$)
   x принадлежит Выбор( A -> $)
3. A -> Bj
   f*(S,x,A) = (S,j*B)
   x принадлежит Выбор( A -> Bj)
4. f(s,a,a) = (S,$)
5. f*(S,$,h0) = (S,$)

Пример:

Int *a[] … [];
Char $b , …;

Int a, *b[][];
Char *b, *a, *b[];

Правила грамматики:

1. I -> TS;
2. T -> int | char
3. S -> ABCR
4. A -> * | $
5. B -> a | b
6. C -> []C | $
7. R -> ,ABCR

Перв(1) = {int, char}
Перв(2.1) = {int}
Перв(2.2) = {char}
Перв(3) = {*,a, b}
Перв(4.1) = {*}
Перв(4.2) = {$}
Перв(5.1) = {a}
Перв(5.2) = {b}
Перв(6.1) = {[}
Перв(6.2) = {$}
Перв(7.1) = {,}
Перв(7.2) = {$}
След(T) = Перв(S) = Перв(A) & Перв(B) = {*,a, b}
След(S) = {;}
След(A) = Перв(B) = {a,b}
След(B) = Перв(C) & Перв(R) & Перв(S) = {[, , ,;}}
След(C) = Перв(R) & След(S)   = {, , ;}
След(R) = Перв(S) & След(S)  = {;}
Выбор(1) = {int, char}
Выбор(2.1) = {int}
Выбор(2.2) = {char}
Выбор(3) = {*,a,b}
Выбор(4.1) = {*}
Выбор(4.2) = След(A) = {a,b}
Выбор(5.1) = {a}
Выбор(5.2) = {b}
Выбор(6.1) = {[}
Выбор(6.2) = След(C) = {, , ;}
Выбор(7.1) = {,}
Выбор(7.2) = След(R) = {;}

Проверка LL1 грамматики.

Данная грамматика является LL1 грамматикой, так как элементы множества Выбор для правил с одинаковым левым нетерминалом не пересекаются.

Строим команды распознавания:

1. f*(S, int, I) = (S, ;ST)
2. f*(S, char, I) = (S, ; ST)
3. f(S, int, T) = (S, $)
4. f(S, char, T) = (S, $)
5. f*(S, *, S) = (S, RCBA)
6. f*(S, a, S) = (S, RCBA)
7. f*(S, b, S) = (S, RCBA)
8. f(S, *, A) = (S, $)
9. f*(S, a, A) = (S, $)
10. f*(S, b, A) = (S, $)
11. f(S, a, B) = (S, $)
12. f(S, b, B) = (S, $)
13. f(S, [, C) = (S, C])
14. f*(S, ;, B) = (S, $)
15. f*(S, , , B) = (S, $)
16. f(S, , , B) = (S, RCBA)
17. f(S, ;, R) = (S, $)
18. f(S, ;, ;) = (S, $)
19. f(S, ], ]) = (S, $)
20. f(S, $, h0) = (S, $)

Пример распознавания:

(S, int *a[], b; h0I) ->(1) -> (S, int *a[], b; h0;ST) ->(3) -> (S,  *a[], b; h0;S  ) -> (5)->
(S,   *a[], b; h0;RCBA) ->(8) -> (S,    a[], b; h0;RCB ) ->(11) -> (S,   [], b; h0;RC  ) ->(13) ->
(S,   ], b; h0;RC] ) ->(19) -> (S,    , b; h0;RC ) ->(15) -> (S,     b; h0;RCBA  ) ->(10) ->
(S,    b; h0;RCB ) ->(12) -> (S,    ; h0;RC ) ->(14) -> (S,    ; h0;R  ) ->(17) ->
(S,    ; h0; ) ->(18) -> (S,     h0 )  -> (S,    $,  $  )