Пред.Страница   След.Страница   Раздел   Содержание

Процедуру построения автомата рассмотрим на примере грамматики:
 

Г_{1. 9}:        R={<E>  ®<E> + <T> | <T>,
<T>  ® <T> * <F> | <F>,
<F>  ® ( <E> ) | a}.

M₃:  P = {a, + , * , ) , ( },   H = {E , T , F , a , + , x , ) , h₀ , ( },   S = {s₀ },   F = {s₀}

Для всех правил грамматики строим команды типа (1):
 

(1)    f⁰ (s₀ , e , E) = {(s₀ , T+E) ; (s₀ , T)},
(2)    f⁰ (s₀ , e , T) = {(s₀ , F*T) ; (s₀ , F)},
(3)    f⁰ (s₀ , e , F) = {(s₀ , )E( ) ; (s₀ , a)},

(4)   f ( s₀, a, a ) = ( s₀, $ ),
(5)   f ( s₀ , + , + ) = (s₀ , $ ),
(6)   f ( s₀ , * , * ) = (s₀ , $ ),
(7)   f ( s₀ , ( , ( ) = (s₀ , $ ),
(8)   f ( s₀ , ) , ) ) = (s₀ , $ ),

(9)   f (s₀ , e , h₀) = ( s₀ , $ ).

(s₀ , a+a*a , h₀E)   |--   (s₀ , a+a*a , h₀T+E)   |--
(s₀ , a+a*a , h₀T+T)   |--   (s₀ , a+a*a , h₀T+F)   |--
(s₀ , a+a*a , h₀T+a)   |--   (s₀ , +a*a , h₀T+)   |--
(s₀ , a*a , h₀T)    |--    (s₀ , a*a , h₀F*T)    |--
 (s₀ , a*a , h₀F*F)    |--    (s₀ , a*a , h₀F*a)    |--
(s₀ , *a , h₀F* )    |--    (s₀ , a , h₀F)    |--
(s₀ , a , h₀a)    |--    (s₀ , $ , h₀)    |--
(s₀ , $ , $).

E Ю E+T  Ю   T+T  Ю F+T Ю a+T  Ю a+T*F  Ю a+F*F  Ю a+a*F  Ю  a+a*a.

Если по такому выводу строить дерево, то построение будет происходить
сверху вниз, т.е. от корня дерева к листьям.