Курс Основы построения трансляторов


Восходящие методы анализа. Свертка-перенос


Восходящие методы синтаксического анализа состоят в том, что в цепочке (промежуточной или терминальной) ищется правая часть очередного правила, которое должно быть заменено своим нетерминалом. Очевидно, что не любая правая часть правила может быть свернута в любое время. Если посмотреть на дерево синтаксического разбора, то нетрудно заметить, что свертку необходимо производить регулярно, путем обхода дерева слева направо.


.

      Z

      |

      E

      |

      T

      -------------

      T     *     F

      |           --------

      F           (   E   )

                    -----

                    E + T

                    |   |

                    T   F

                    |

                    F

 

В данном дереве необходимо выполнить свертку по самому левому правилу T::=F в цепочке. Правая часть такого правила называется ОСНОВОЙ. Таким образом, основа - это полная правая часть первого правила при просмотре цепочки слева направо. Найденная в цепочке основа должна быть заменена на нетерминал из левой части соответствующего правила. Для более полного понимания принципа приведем последовательность основ цепочек при выполнении такого процесса свертки.

.

      F * (F + F)

      ---

      T * (F + F)

          ---

      T * (T + F)

          ---

      T * (E + F)

              ---

      T * (E + T)

           -----

       T * (E)

           ---

      T * F

      -----

        T

       ---

        E

       ---

        Z

       ---

 

Способ нахождения основы цепочки реализован в методе восходящего разбора "свертка-перенос":

В процессе анализа используется магазинный автомат (КА со стеком);

На каждом шаге работы автомата сравнивается пара символов - текущий символ входной цепочки (I) и текущий символ в стеке (М). По результату сравнения возможны два действия:

Перенос терминального символа из строки в стек: PUSH((I), NEXT(I) - в соответствии с принятыми для МА обозначениями.

Свертка правой части правила, которое в данный момент находится в стеке.


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