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


Газобаллонная установка на сайте http://www.chelgas.ru. | доставка цветов в геленджике всегда свежие цветы. |

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


    Для грамматик, удовлетворяющих условиям 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, построим команду автомата