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

                                                                      76
                   Стековая реализация ПС-анализа


     Существует две проблемы при синтаксическом анализе методом
обрезки основ. Первая заключается в обнаружении подстроки для свертки в
правосентенциальной форме, а вторая – в определении, какая именно
продукция должна быть выбрана, если имеется несколько продукций с
соответствующей подстрокой в правой части. Перед тем как ответить на эти
вопросы, сначала рассмотрим структуры данных, используемые в ПС-
анализаторе.
     Достаточно удобный путь реализации ПС-анализатора состоит в
использовании стека для хранения символов грамматики и входного буфера
для хранения анализируемой строки. В качестве маркера дна стека мы
используем $, и этот же символ является маркером правого конца входной
строки. Изначально стек пуст, а входной буфер содержит строку w:
                            Cтек          Вход
                              $           w$
     Синтаксический анализатор работает путем переноса нуля или
нескольких символов в стек до тех пор, пока на вершине стека не окажется
основа β. Затем он свертывает β к левой части соответствующей продукции.
Синтаксический анализатор повторяет этот цикл, пока не будет обнаружена
ошибка или он не придет в конфигурацию, когда в стеке находится только
стартовый символ, а входной буфер пуст:
                            Стек          Вход
                              $S           $
     Попав в эту конфигурацию, синтаксический анализатор прекращает
работу и сообщает об успешном разборе входной строки.
Пример 13.c
     Пройдем пошагово все действия, выполняемые синтаксическим
анализатором при разборе входной строки id1+id2*id3 грамматики (13.1),
используя первое порождение из примера 13.a. Последовательность действий