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



ветеринарный гематологический анализатор цена. | Компании по аренде спецтехники по материалам http://greenstroy36.ru. |

LR(1)-анализаторы - часть 2


(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, то анализатор выполняет сдвиг, переходя в конфигурацию
    (S_0X_1S_1X_2S_2 \ldots X_mS_ma_iS, a_{i+1} \ldots a_n\$)
    То есть, в магазин помещаются входной символ ai

    и символ состояния S, определяемый Action[Sm, ai]. Текущим входным символом становится ai+1.

  2. Если Action[Sm, ai] = reduce A
    ?, то анализатор выполняет свертку, переходя в конфигурацию
    (S_0X_1S_1X_2S_2 \ldots X_{m-r}S_{m-r}AS, a_ia_{i+1} \ldots a_n\$)
    где 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)-анализатора, то есть исполняются семантические действия, связанные с правилом, по которому делается свертка, например, печатаются номера правил, по которым делается свертка.




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