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

                                                                        79
основа γ находится на вершине стека. После свертки γ в В синтаксический
анализатор может перенести строку ху для получения следующей основы у
на вершине стека:
                             Стек      Вход
                             $αBxy      z$
Теперь синтаксический анализатор свертывает у в А.
      В обоих случаях после свертки синтаксический анализатор для
получения очередной основы переносит нуль или несколько символов в стек.
Синтаксический анализатор никогда не заглядывает внутрь стека в поисках
правого края основы. Все это делает стек особенно удобным для
использования в реализации ПС-анализатора. Впрочем, мы все еще не
выяснили, каким образом осуществлять выбор очередного действия для
корректной работы синтаксического анализатора.


                          Активные префиксы


      Префиксы правосентенциальных форм, которые встречаются в стеке
ПС-анализатора, называются активными (viable prefixes). Эквивалентное
определение активного префикса заключается в том, что это – префикс
правосентенциальной формы, который не выходит за правый конец крайней
справа основы этой сентенциальной формы. Согласно этому определению, к
концу активного префикса всегда можно добавить терминальные символы
для    получения      правосентенциальной        формы.     Следовательно,
просканированная часть входного потока не содержит ошибок только в том
случае, когда она может быть свернута в активный префикс.


                    Конфликты в процессе ПС-анализа


      Существуют контекстно-свободные грамматики, для которых ПС-
анализ не применим. Любой ПС-анализатор для такой грамматики может