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


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


(3) ВЫБОР(<B>  ®

<C>) = ПЕРВ(<A><C>) = {x,(}

(4) ВЫБОР(<C>  ®

+<A><C>) = ПЕРВ(+<A><C>) = {+}

(5) ВЫБОР(<C>  ®

$) = СЛЕД(<C>)  = СЛЕД(<B>) = { ) }.

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

      ( 1 ) f ( s0 , x , <A>) = ( s0 , $ ) ,

      ( 2 ) f( s0 , ( , <A> ) = ( s0 , )<B> ) ,

      ( 3 ) f* ( s0 , ( , <B> ) = ( s0 , <C><A>

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

      ( 4 ) f ( s0 , + , <C> ) = ( s0 , <C><A>

      ) ,

      ( 5 ) f* ( s0 , ) , <C> ) = ( s0 , $ ).

Учитывая, что закрывающиеся скобки расположены на последнем месте правила (2), построим команду

        f ( s0 ,  ),  ) ) = ( s0 , $ ) .

Кроме того, построим команду для перехода в заключительное состояние:

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

Работу построенного автомата проверим на примере входной цепочки ( x + x ). При этом получаем следующую последовательность конфигураций:

    ( s0 , (x+x) , h0<A> ) |--- ( s0

    , x+x ) , h0)<B> ) |--- ( s0 , x+x) , h0)<C><A>

    ) |---
    ( s0 , +x ) , h0)<C>) |--- ( s0 , x) , h0)<C><A> )  |--- ( s0 , ) , h0)<C>)|---
    ( s0 , $ , h0 ) |--- ( s0 , $ , $ ) ,

которая показывает, что входная цепочка допускается построенным автоматом.
 

 

  • Пред.Страница 

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




- Начало -  - Назад -  - Вперед -