LR(k)-грамматики

Восходящий разбор (англ. Bottom-up parsing) предназначен для построения дерево разбора. Мы можем представить себе этот процесс как "свертку" исходной строки $w$ к правилу грамматики. Каждый шаг свертки заключается в сопоставлении некоторой подстроки $w$ и правой части какого-то правила грамматики, затем происходит замена этой подстроки на нетерминал, являющийся левой частью правила. Восходящий разбор менее интуитивный, чем нисходящий, но зато позволяет разбирать большее множество грамматик.

LR(k)-грамматика

Определение:

Пусть $\Gamma =\langle \Sigma, N, S, P \rangle$ — контекстно-свободная грамматика. Пополненной грамматикой (англ. augmented grammar), полученной из $\Gamma$, назовем грамматику $\Gamma' =\langle \Sigma', N', S', P' \rangle$, где $\Sigma' = \Sigma; N' = N \cup \{S'\}; S' \notin N; P' = P \cup \{S' \to S\}$

Использование в определении LR(k)-грамматики пополненной грамматики существенно для однозначного определения конца анализа. Действительно, если грамматика использует $S$ в правых частях правил, то свертка основы в $S$ не может служить сигналом приема входной цепочки. Свертка же в $S'$ в пополненной грамматике служит таким сигналом, поскольку $S'$ нигде, кроме начальной сентенциальной формы, не встречается.

// TODO сделать пример, когда нам точно нужно пополнять грамматику

// TODO написать нормальное определение LR(k)-грамматики

Определение:

Пусть $\Gamma' =\langle \Sigma', N', S', P' \rangle$ — пополненная грамматика для КС-грамматики $\Gamma$. Грамматика $\Gamma$ явяется LR(k)-грамматикой, если для любых двух правосторонних выводов вида: $S' \Rightarrow^* \alpha A w \Rightarrow \alpha \beta w$, $S' \Rightarrow^* \gamma B x \Rightarrow \alpha \beta y$, в которых $\mathrm{FIRST}_k(w) = \mathrm{FIRST}_k(y)$, должно быть $\alpha A y = \gamma B x$. Другими словами, $\alpha = \gamma, A=B, y=x$.

Говоря неформально, если согласно первому выводу $\beta$ — основа, сворачиваемая в нетерминал $A$, то и во втором выводе $\beta$ должна быть основой, сворачиваемой в нетерминал $A$. Из этого определения следует, что если имеется правовыводимая цепочка $\alpha_i = \alpha \beta w$, где $\beta$ — основа, полученная из $A$, и если $\alpha \beta = X_1 X_2 ... X_r$, то

• зная первые символы $X_1 X_2 ... X_j$ цепочки $\alpha \beta$ и не более, чем $k$ следующих символов цепочки $X_{j+1} X_{j+2} ... X_r w$, мы можем быть уверены, что правый конец основы не будет достигнут до тех пор, пока $j \ne r$;
• зная цепочку $\alpha \beta = X_1 X_2 ... X_r$ и не более $k$ символов цепочки $w$, мы можем быть уверены, что именно $\beta$ является основой, сворачиваемой в нетерминал $A$;
• если $\alpha_{i-1} = S'$, можно сигнализировать о выводимости исходной терминальной цепочки из $S'$ и, следовательно, из $S$.

// TODO end

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

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

LR-разборщик

Структура

При LR(k)-анализе применяется метод перенос-свертка (англ. shift-reduce). Этот метод использует:

• Стек
• Входная цепочка
• Управляющая таблица
• Автомат

Принцип переноса-свёртки

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

Управляющая программа анализатора

Для определения, какую операцию применить(перенос-свертку), используем управляющую таблицу. Управляющая программа одинакова для всех LR-анализаторов, а таблица изменяется от одного анализатора к другому. Программа анализатора читает последовательно символы входной цепочки. Программа использует магазин для запоминания строки следующего вида $s_0X_1s_1X_2...X_ms_m$, где $s_m$ — вершина магазина. Каждый $X_i$ — символ грамматики, а $s_i$ — символ, называемый состоянием. Каждое состояние суммирует информацию, cодержащуюся в стеке перед ним.

Программа ведет себя следующим образом:

Происходит обращение к таблице: $action [s_m, a_i]$, где

• $s_m$ — текущее состояние на вершине магазина, каждое состояние суммирует информацию, cодержащуюся в стеке перед ним,
• $a_i$ — текущий входной символ;

Результат может иметь одно из четырех значений:

• переход в стостояние $s$, $(shift)$
• свертка по правилу $A \to \beta$, $(reduce)$,
• допуск, $(accept)$,
• ошибка, $(error)$.

bool algorithmLR(w: string) ip — указатель на перый символ в строке w while цепочка не закончилась s = top() a = w[ip] if action [s, a] == shift s’ push(a) push(s’) ip++ else if action [s, a] == reduce A $\to \beta$ for j = 1 to $|\beta |$ pop() pop() s’ = top() push(A) push(goto [s’, A]) Вывод правила (A $\to \beta$) else if action [s, a] == accept return success else return error

Функция $goto$ получает состояние и символ грамматики и выдает состояние. Функция $goto$, строящаяся по грамматике $\Gamma$, есть функция переходов детерминированного магазинного автомата, который распознает язык, порождаемый грамматикой $\Gamma$.

См. также

• Предиктивный синтаксический анализ
• LL(k)-грамматики, множества FIRST и FOLLOW

Источники информации

• Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс, 2003. Стр. 301 - 326.
• Терехов Ан.А., Вояковская Н., Булычев Д., Москаль А. - Разработка компиляторов на платформе .NET - Восходящие анализаторы
• Б.К.Мартыненко. Языки и трансляции. Стр. 198 - 223