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


Синтаксический разбор


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

 

Определение.  Последовательность номеров правил грамматики Г, применение которых позволяет построить вывод рассматриваемой цепочки s из начального символа грамматики, называется синтаксическим разбором s.

 

    Например, в следующей грамматике

        Г1. 9:

            Vт = { i, +, * , (, ) }, Va = {<E>, <T>, <P>}

              R ={ (1) <E> ®<E>

              +<T>,

                (2) <E> ®<T>,


                (3) <T> ®<T>

                *<P>,


                (4) <T> ®<P>,


                (5) <P> ®(E),


                (6) <P> ® i },

    правила которой пронумерованы, вывод
     

        <E> Ю <E>

        +<T> Ю <T> +<T>

        Ю <T> *<P> +<T> Ю

          <P> *<P> +<T>

          Ю i * <P> +<T> Ю i * i +<T>

          Ю


          i * i +<P> Ю

          i * i + i

         

    имеет синтаксический разбор [1,2,3,4,6,6,4,6].

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

    Например, вывод цепочки i + i в грамматике Г1. 9 может быть получен десятью различными способами.
     

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


  •  




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