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




LR(1)-анализаторы


В названии LR(1) символ L указывает на то, что входная цепочка читается слева-направо, R - на то, что строится правый вывод, наконец, 1 указывает на то, что анализатор видит один символ непрочитанной части входной цепочки.

LR(1)-анализ привлекателен по нескольким причинам:

  • LR(1)-анализ - наиболее мощный метод анализа без возвратов типа сдвиг-свертка;
  • LR(1)-анализ может быть реализован довольно эффективно;
  • LR(1)-анализаторы могут быть построены для практически всех конструкций языков программирования;
  • класс грамматик, которые могут быть проанализированы LR(1)-методом, строго включает класс грамматик, которые могут быть проанализированы предсказывающими анализаторами (сверху-вниз типа LL(1)).

Схематически структура LR(1)-анализатора изображена на рис. 4.4. Анализатор состоит из входной ленты, выходной ленты, магазина, управляющей программы и таблицы анализа (LR(1)-таблицы), которая имеет две части - функцию действий (Action) и функцию переходов (Goto). Управляющая программа одна и та же для всех LR(1)-анализаторов, разные анализаторы отличаются только таблицами анализа.

Анализатор читает символы на входной ленте по одному за шаг. В процессе анализа используется магазин, в котором хранятся строки вида S0X1S1X2S2 ... XmSm (Sm - верхушка магазина). Каждый Xi - символ грамматики (терминальный или нетерминальный), а Si - символ состояния.

Заметим, что символы грамматики (либо символы состояний) не обязательно должны размещаться в магазине. Однако, их использование облегчает понимание поведения LR-анализатора.

Элемент функции действий Action[Sm; ai] для символа состояния Sm и входа

a_i \in T \cup \{$\}
, может иметь одно из четырех значений:

  1. shift S (сдвиг), где S - символ состояния,
  2. reduce A
    ? (свертка по правилу грамматики A
    ?),
  3. accept (допуск),
  4. error (ошибка).

Элемент функции переходов Goto[Sm; A] для символа состояния Smи входа

A \in N
, может иметь одно из двух значений:


Рис. 4.6. 

  1. S, где S - символ состояния,
  2. error (ошибка).

Конфигурацией LR(1)-анализатора называется пара, первая компонента которой - содержимое магазина, а вторая - непросмотренный вход:




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