Тестирование софта - статьи


Предварительные сведения - часть 3


На каждом шаге рассматривается символ на вершине стека X и текущий входной символ a. Действия анализатора определяются этими двумя символами:
  • если X = a = $, то анализатор прекращает работу и сообщает об успешном завершении разбора;
  • если X = a ? $, анализатор удаляет из стека символ X и переходит к следующему символу входного потока;
  • если X является нетерминалом, анализатор ищет такую альтернативу раскрытия символа X, для которой символ a является допустимым первым символом. После того, как требуемая альтернатива найдена, символ X в стеке заменяется обратной последовательностью символов альтернативы. Например, если искомая альтернатива X > ABC, то анализатор заменит X на вершине стека на последовательность CBA, т.е. на вершине стека окажется символ A. Конфликты, возникающие в процессе поиска альтернатив, могут разрешаться, например, с помощью “заглядывания вперед”, т.е. просмотра нескольких входных символов вместо одного.
Анализатор завершает работу, когда на вершине стека оказывается символ конца строки $.

Рассмотрим теперь LR-анализатор, построенный на основе стека. У такого LR-анализатора имеются две основные операции:

  • перенос символа из входного потока в стек;
  • свертка нескольких последовательных символов на вершине стека в некоторый нетерминал.
Работа анализатора происходит так, что в стеке все время находится активный префикс некоторой правосентенциальной формы. При переносе символа и свертке на вершину стека кладется символ состояния sj конечного автомата V, кодирующий текущий активный префикс. LR-анализатор принимает решение о переносе или свертке, исходя из пары (символ sj, текущий токен входного потока). Анализатор завершает работу, когда в стеке оказывается стартовый символ грамматики.


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



Книжный магазин