Формальные языки, грамматики и основы построения трансляторов. Кревский И.Г - 78 стр.

                                                                          78
     Рассмотрим очень важный факт, который поясняет использование
стека в ПС-анализаторе: основа всегда находится на вершине стека и никогда
– внутри него. Это становится очевидным при рассмотрении возможных
видов двух последовательных шагов в любом правом порождении. Эта два
шага могут быть следующими:
           *     *         *
      (1) S ⇒αAz ⇒ αβByz ⇒ αβγyz
           rm    rm        rm
           *          *         *
      (2) S ⇒α Bx Az ⇒αB x yz ⇒αγ x yz
           rm         rm        rm


     В случае (1) А заменяется на βВу, а затем крайний справа нетерминал В
в правой части – на γ. В случае (2) А также заменяется первым, но в этот раз
правая часть представляет собой строку γ, состоящую только из терминалов.
Следующий крайний справа нетерминал В находится слева от γ.
     Рассмотрим случай (1) в обратном порядке, начиная с момента, когда
ПС-анализатор достиг конфигурации
                                     Стек    Вход
                                     $αβγ     yz$
     Теперь синтаксический анализатор свертывает основу γ в В и
переходит в конфигурацию
                                     Стек    Вход
                                     $αβB     yz$
     Поскольку B является крайним справа нетерминалом в αβByz, правый
конец основы строки αβByz не может находиться внутри стека. Таким
образом, синтаксический анализатор может перенести строку y в стек для
получения конфигурации
                                     Стек    Вход
                                     $αβBy   z$
в которой βВу является основой и свертывается в А.
     В случае (2) в конфигураций
                                     Стек    Вход
                                     $αγ     xyz$