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

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

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

Определение

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

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

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

Пусть [math]\Gamma' =\langle \Sigma', N', S', P' \rangle[/math] — пополненная грамматика для КС-грамматики [math]\Gamma[/math]. Грамматика [math]\Gamma[/math] является LR(k)-грамматикой, если для любых двух правосторонних выводов: [math]S' \Rightarrow^* \beta A t z \Rightarrow \beta \alpha t z \Rightarrow^* w, [/math] если [math]|t|=k[/math] или [math]|t|\lt k, |z|=0 (z = \varepsilon)[/math] [math]S' \Rightarrow^* \gamma B t z' \Rightarrow \gamma \xi t z' \Rightarrow^* w', [/math] если [math]|t|=k[/math] или [math]|t|\lt k, |z'|=0 (z' = \varepsilon)[/math] верно, что [math]\beta \alpha = \gamma \xi[/math], следует, что [math]\beta = \gamma[/math] и [math]A = B[/math]

Говоря неформально, мы делаем правостороннюю свёртку нашей строки в стартовый нетерминал. Если по не более чем [math]k[/math] символам неразобранной строки мы можем однозначно определить, во что сворачивается хвост выведенного правила, то грамматика будет LR(k).

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

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

Замечание о пополненной грамматике

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

Существенность использования пополненной грамматики в определении LR(k)-грамматик продемонстрируем на следующем конкретном примере. Пусть пополненная грамматика имеет следующие правила:

[math] (0)\ S' \to S \\ (1)\ S \to Sa \\ (2)\ S \to a \\ [/math]

Если игнорировать [math]0[/math]-е правило, то, не заглядывая в правый контекст основы [math]Sa[/math], можно сказать, что она должна сворачиваться в [math]S[/math]. Аналогично основа [math]a[/math] безусловно должна сворачиваться в [math]S[/math]. Создается впечатление, что данная грамматика без [math]0[/math]-го правила есть LR(0)-грамматика. С учетом же [math]0[/math]-го правила, после свертки в [math]S[/math], просматривая [math]k=0[/math] символов, нельзя определить, делать ли свертку в [math]S'[/math], следовательно это не LR(0)-грамматика. Получили противоречие.

---

TODO тут надо либо дать более формальное объяснение, либо объяснить почему k не должно меняться от пополнения грамматики.

---

LR-разборщик

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

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

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

Структура

Метод перенос-свертка использует следующие компоненты:

• Входная строка
• Стек (для запоминания рассмотренных символов)
• Управляющая таблица (для определения, какое действие применить - перенос или свертку)
• Автомат (для запоминания информации о текущем состоянии стека)

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

Управляющая программа одинакова для всех LR-анализаторов, а таблица и автомат изменяются от одного анализатора к другому.

Для запоминания строки запись в стек имеет вид: [math]s_0X_1s_1X_2...X_ms_m[/math], где [math]s_m[/math] — вершина стека. Каждый [math]X_i[/math] — символ грамматики(терминал или нетерминал), а [math]s_i[/math] — состояние автомата. Каждое состояние суммирует информацию, cодержащуюся в стеке перед ним. [math]s_0[/math] — стартовое состояние автомата.

Обращение к таблице происходит следующим образом [math]\mathtt{T[state, token]}[/math], где

• [math]\mathtt{state}[/math] — состояние автомата,
• [math]\mathtt{token}[/math] — входной символ;

В таблице информация имеет следующий вид:

struct Cell
   enum: 
       Shift 
       Reduce 
       Accept   // допуск 
       Error    // ошибка
struct Shift 
    state: int  // переход в стостояние state
struct Reduce 
    rule: int   // свертка по правилу rule

Рузультатом работы управляющей программы будет:

struct Result
   enum:  
       Accept   // допуск 
       Error    // ошибка

Алгоритм

1. Программа читает символ из входной цепочки.
2. Обращается к управляющей таблице.
3. Совершает соответствующее действие.
4. Возвращается к первому пункту, пока входная цепочка не закончится.

Result algorithmLR(w: string) curToken — указатель на первый символ в строке w while haveToken() curState = top() if [math]\mathtt{T}[/math][curState, curToken] == Shift s push(curToken) push(s) nextToken() else if [math]\mathtt{T}[/math][curState, curToken] == Reduce A [math] \to \beta[/math] for j = 1 to [math]|\beta |[/math] pop() pop() s = top() push(A) push(goto [s, A]) Вывод правила (A [math] \to \beta[/math]) else if [math]\mathtt{T}[/math][curState, curToken] == Accept return Accept else return Error

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

См. также

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

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

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