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

золотой софт

Построение магазинного автомата


    Для грамматик, удовлетворяющих условиям LL(1) грамматик,  справедливо следующее утверждение.

     

    Утверждение. Для каждой LL(1) грамматики Г можно построить детерминированный 
                               магазинный автомат М , допускающий   язык,  порождаемый  заданной 
                               грамматикой:    L ( Г ) = L ( М ).

    Задача построения магазинного автомата для заданной LL(1)  грамматики формулируется следующим образом.
    Задана грамматика Г = {Vт,Va, I, R}, и требуется определить
    об'екты, определяющие автомат М = { P , S , s0

    , F , H , h0 , f }.
    Учитывая, что автомат должен допускать цепочки языка, порождаемого заданной грамматикой, примем    P = Vт. Чтобы упростить описание автомата, допустим, что он имеет одно состояние s0,     которое является и начальным и заключительным, то есть - S = {s0}и  F = {s0}.
    В качестве магазинного алфавита примем следующее объединение:  H = {Vт И

    Va И

    {h0}}.
    Построение функции переходов выполним с использованием  множеств ВЫБОР правил заданной грамматики следующим образом:
    1 ) Для каждого правила грамматики, начинающегося терминальным символом вида
         <A> ®

    b a,    построим команду автомата

       

          f ( s0 , b , <A> ) = ( s0

          , a

          ' ) ,

     
         где a

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

    a .
    2) Для каждого правила грамматики, начинающегося нетерминальным символом вида
         <A> 

    ® <B>

    a, построим команду автомата

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

        , <B> a

        ' )

      


        где f* - команда автомата без сдвига входной головки,   а a




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