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

Пример построения преобразователя


   Применение правил построения команд преобразователя рассмотрим на примере транслирующей грамматики Г, которая описывает перевод инфиксных выражений, состоящих из идентификаторов и знаков + и *, в постфиксные польские выражения. Эта грамматика имеет следующую схему:

     Г 4. 1 :    R = {<E> Ю +<E><E>{+},
                           <E> Ю x<E><E>{x},
                           <E> Ю a{a}}

  Используя правило построения команд преобразователя (1) для правил грамматики, начинающихся входным терминальным символом, получаем команды преобразователя Мп1:
 

      q(s0, +, <E>) = (s0, {+}<E><E>, $),
      q(s0, *, <E>) = (s0, {*}<E><E>, $),
      q(s0, a, <E>) = (s0, {a}, $)

    Правила построения команд вида (2),(3),(4) к заданной грамматике неприменимы, поэтому с помощью правил вида (5) построим команды, обеспечивающие передачу выходных символов на выход. Эти команды имеют вид:


     

        q*(s0, +, {+}) = (s0, $, +), q*(s0, *, {+}) = (s0, $, +),
        q*(s0, a, {+}) = (s0, $, +), q*(s0, $', {+}) = (s0, $, +),
        q*(s0, *, {*}) = (s0, $, *), q*(s0, +, {*}) = (s0, $, *),
        q*(s0, *, {a}) = (s0, $, *), q*(s0, $', {*}) = (s0, $, *),
        q*(s0, a, {a}) = (s0, $, a), q*(s0, +{a}) = (s0, $, a),
        q*(s0, *, {a}) = (s0, $, a), q*(s0, $', {a}) = (s0, $, a)

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

      в соответствии с правилом (6) построим команду:


       

          q(s0, $', h0) = (s1, $, $)

           Чтобы посмотреть как работает построенный преобразователь, рассмотрим построение выходной цепочки для входа +a*aa. Последовательность конфигураций, получаемых с помощью команд преобразователя имеет вид:


         

            (s0, +a*aa, h0E, $) |-- (s0, a*aah0{+}EE, $) |--
            (s0, *aa, h0{+}T{a}, $) |--
            (s0, *aa, h0{+}E, a) |--
            (s0, aa, h0{+}{*}T{a}, a) |--
            (s0, a, h0{+}{*}E, aa) |--
            (s0, $, h0{+}{*}{a}, aa) |--
            (s0, $, h0{+}{*}, aaa) |--
            (s0, $, h0{+}, aaa*) |--
            (s0, $, h0, aaa*+) |--
            (s0, $, $, aaa*+).

             Результатом работы преобразователя

          является выходная цепочка aaa*+, представляющая постфиксную запись заданной входной цепочки.


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



          Содержание раздела