=== Принцип переноса-свёртки ===
При LR(k)-анализе применяется метод '''перенос-свертка''' (англ. ''shift-reduce''). Суть метода сводится к следующему.
* Рассматриваем по одному символу из Программа анализатора читает последовательно символы входной строки до тех пор, пока не накопится цепочка, совпадающая с правой частью какого-нибудь из правил. Рассмотренные символы переносим в стек (операция '''перенос'''). * Далее все символы совпадающей цепочки, которая совпала с каким-то правилом, извлекаются из стека и на их место помещается нетерминал, находящийся в левой части этого правила (операция '''свертка'''). Входная цепочка допускается, если после переноса в стек последнего символа входной строки и выполнения операции свертка, в магазине окажется S' (то есть нетерминал, который был добавлен при пополнении грамматики).
=== Структура ===
Метод '''перенос-свертка''' использует следующие компоненты:
* Стек (для хранение рассматриваемых запоминания рассмотренных символов)
* Входная строка
* Управляющая таблица (для определения, какое действие применить - перенос или свертку)
* Автомат (для построения управляющей таблицызапоминания информации о текущем состоянии стека)
=== Управляющая программа анализатора ===
Для определения, какую операцию применить(перенос-свертку), используем управляющую таблицу. Управляющая программа одинакова для всех LR-анализаторов, а таблица изменяется и автомат изменяются от одного анализатора к другому. Программа анализатора читает последовательно символы входной цепочки. Программа использует стек для запоминания строки следующего вида <tex>s_0X_1s_1X_2...X_ms_m</tex>, где <tex>s_m</tex> {{---}} вершина магазина. Каждый <tex>X_i</tex> {{---}} символ грамматики, а <tex>s_i</tex> {{---}} символ, называемый состоянием. Каждое состояние суммирует информацию, cодержащуюся в стеке перед ним.
Программа ведет себя следующим образомДля запоминания строки запись в стек имеет вид: <tex>s_0X_1s_1X_2...X_ms_m</tex>, где <tex>s_m</tex> {{---}} вершина стека. Каждый <tex>X_i</tex> {{---}} символ грамматики(терминал или нетерминал), а <tex>s_i</tex> {{---}} состояние автомата. Каждое состояние суммирует информацию, cодержащуюся в стеке перед ним. <tex>s_0</tex> {{---}} стартовае состояние автомата.
Происходит обращение Ображение к таблице: происходит по паре <tex>action [s_m, a_i]</tex>, где *<tex>s_m</tex> {{---}} текущее состояние на вершине магазина, каждое состояние суммирует информацию, cодержащуюся в стеке перед нимавтомата,
*<tex>a_i</tex> {{---}} текущий входной символ;
Результат может иметь одно из четырех значенийВ таблице информация отображается слудующим образом:*переход в стостояние <tex>s</tex>, <tex>(shift)</tex>*свертка по правилу <tex>A \to \beta</tex>, <tex>(reduce)</tex>,*допуск, <tex>(accept)</tex>,*ошибка, <tex>(error)</tex>. === Алгоритм ===# Программа читает символ из входной цепочки. # Обращается к утравляющей таблице# Совершает соответствующее действие.# Возвращается к первому пункту
{| border="0"
