LR(k)-грамматики — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(См. также)
(Перенос-свертка)
Строка 37: Строка 37:
 
* не более <tex>k</tex> символов цепочки (англ. ''k-token lookahead'') используются для принятия решения.
 
* не более <tex>k</tex> символов цепочки (англ. ''k-token lookahead'') используются для принятия решения.
  
== Перенос-свертка ==
+
=== Структура LR-разборщика ===
 +
При LR(k)-анализе применяется метод '''перенос-свертка''' (англ. ''shift-reduce''). Этот метод использует:
 +
* Стек
 +
* Входная цепочка
 +
* Управляющая таблица
 +
* Автомат
  
При LR(k)-анализе применяется метод '''перенос-свертка''' (англ. ''shift-reduce''). Этот метод использует магазинный автомат. Суть метода сводится к следующему. Символы входной цепочки переносятся в магазин до тех пор, пока на вершине магазина не накопится цепочка, совпадающая с правой частью какого-нибудь из правил (операция '''перенос'''). Далее все символы этой цепочки извлекаются из магазина и на их место помещается нетерминал, находящийся в левой части этого правила (операция '''свертка'''). Входная цепочка допускается автоматом, если после переноса в автомат последнего символа входной цепочки и выполнения операции свертка, в магазине окажется только аксиома грамматики.
+
=== Принцип переноса-свёртки ===
 +
Суть метода сводится к следующему. Символы входной цепочки переносятся в магазин до тех пор, пока на вершине магазина не накопится цепочка, совпадающая с правой частью какого-нибудь из правил (операция '''перенос'''). Далее все символы этой цепочки извлекаются из магазина и на их место помещается нетерминал, находящийся в левой части этого правила (операция '''свертка'''). Входная цепочка допускается автоматом, если после переноса в автомат последнего символа входной цепочки и выполнения операции свертка, в магазине окажется только аксиома грамматики.
  
 
== Управляющая программа анализатора ==
 
== Управляющая программа анализатора ==

Версия 10:46, 29 августа 2015

Восходящий разбор (англ. 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]


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

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

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


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


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

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

// TODO end

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

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

Структура 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]action [s_m, a_i][/math], где

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

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

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

 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 [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 action [s, a] == accept 
             return success
         else 
             return error     

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

См. также

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