Разработка компиляторов



         

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


LR(k) означает, что

  • входная цепочка обрабатывается слева направо (left-to-right parse);
  • выполняется правый вывод (rightmost derivation);
  • не более k символов цепочки (k-token lookahead) используются для принятия решения.

При LR(k)-анализе применяется метод "перенос-свертка" (shift-reduce) . Этот метод использует магазинный автомат. Суть метода сводится к следующему. Символы входной цепочки переносятся в магазин до тех пор, пока на вершине магазина не накопится цепочка, совпадающая с правой частью какого-нибудь из правил (операция "перенос", " shift"). Далее все символы этой цепочки извлекаются из магазина и на их место помещается нетерминал, находящийся в левой части этого правила (операция "свертка", " reduce"). Входная цепочка допускается автоматом, если после переноса в автомат последнего символа входной цепочки и выполнения операции свертка, в магазине окажется только аксиома грамматики.

Анализатор состоит из входной цепочки, выхода, магазина, управляющей программы и таблицы, которая имеет две части (действие и переход). Схема такого анализатора выглядит следующим образом:




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