Теория и реализация языков программирования

         

Эта конфигурация соответствует правой сентенциальной


(S0X1S1X2S2 ... XmSm, aiai+1 ... an$)

Эта конфигурация соответствует правой сентенциальной форме

X1X2 ... Xmaiai+1 ... an

Префиксы правых сентенциальных форм, которые могут появиться в магазине анализатора, называются активными префиксами. Основа сентенциальной формы всегда располагается на верхушке магазина. Таким образом, активный префикс - это такой префикс правой сентенциальной формы, который не переходит правую границу основы этой формы.

Когда анализатор начинает работу, в магазине находится только символ начального состояния S0, на входной ленте - анализируемая цепочка с маркером конца.

Каждый очередной шаг анализатора определяется текущим входным символом ai и символом состояния на верхушке магазина Sm следующим ниже образом.

Пусть LR(1)-анализатор находится в конфигурации

(S0X1S1X2S2 ... XmSm, aiai+1 ... an$)

Анализатор может проделать один из следующих шагов:

  1. Если Action[Sm, ai] = shift S, то анализатор выполняет сдвиг, переходя в конфигурацию
    То есть, в магазин помещаются входной символ ai

    и символ состояния S, определяемый Action[Sm, ai]. Текущим входным символом становится ai+1.
  2. Если Action[Sm, ai] = reduce A
    ?, то анализатор выполняет свертку, переходя в конфигурацию
    где S = Goto[Sm-r; A] и r - длина ?, правой части правила вывода.

    Анализатор сначала удаляет из магазина 2r символов (r символов состояния и r символов грамматики), так что на верхушке оказывается состояние Sm-r. Затем анализатор помещает в магазин A - левую часть правила вывода, и S - символ состояния, определяемый Goto[Sm-r, A]. На шаге свертки текущий входной символ не меняется. Для LR(1)- анализаторов последовательность символов грамматики Xm-r+1 ... Xm, удаляемых из магазина , всегда соответствует ? - правой части правила вывода, по которому делается свертка.

    После осуществления шага свертки генерируется выход LR(1)-анализатора, то есть исполняются семантические действия, связанные с правилом, по которому делается свертка, например, печатаются номера правил, по которым делается свертка.


    Содержание  Назад  Вперед







    Forekc.ru
    Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий