Формальные языки


Построение магазинного автомата - часть 2


' является зеркальным
    отображением цепочки a

.
Количество команд, которые необходимо построить для заданного   правила, определяется числом элементов множества ВЫБОР.
Команды магазинного автомата, работающие без сдвига входной головки, выполняют замену нетерминаала, соответствующего   левой части правила, цепочкой,  соответствующей правой части   этого правила. В этом случае сопоставление терминального символа, получаемого при выводе, и очередного символа входной цепочки не производится, поэтому для таких команд сдвиг входной  головки не нужен.
3)  Для каждого аннулирующего правила грамматики вида
      <A>

® $

построим команды автомата

     

        f* ( s0 , x , <A> ) = ( s0

        , $ )

     

 для каждого элемента x из множества ВЫБОР(<A> 

® $). Количество таких команд  определяется числом элементов множества    ВЫБОР.
4)  Для каждого терминального символа b, расположенного в   середине или на конце правых
     частей правил грамматики, построим команду
 

        f ( s0 , b , b ) = ( s0

        , $ ).

     

5) Для перехода в заключительное состояние построим команду

     

        f* ( s0 , e

        , h0 ) = ( s0 , $ , $ ).

     

В качестве начальной конфигурации автомата условимся использовать следующее выражение с заданной входной цепочкой µ :
 

          (s0,µ,h0<I>).

Пользуясь приведенными правилами, построим магазинный автомат для грамматики Г12, схема которой в символических  обозначениях может быть записана так

          Г3. 5

          :    R = {<A> 

          ® x | (<B>),

              <B> 

              ® <A> <C>,


              <C> 

              ® +<A> <C>

              | $}.

    Вначале построим множества ВЫБОР для каждого из правил и проверим, является ли эта грамматика LL(1) грамматикой.