297
правок
Изменения
Новая страница: «'''Восходящий разбор '''(англ. ''Bottom-up parsing)'' предназначен для построения дерева разбора, нач...»
'''Восходящий разбор '''(англ. ''Bottom-up parsing)'' предназначен для построения дерева разбора, начиная с листьев и двигаясь вверх к корню дерева разбора. Мы можем представить себе этот процесс как "свертку" исходной строки <tex>w</tex> к аксиоме грамматики. Каждый шаг свертки заключается в сопоставлении некоторой подстроки <tex>w</tex> и правой части какого-то правила грамматики и замене этой подстроки на нетерминал, являющийся левой частью правила. Если на каждом шаге подстрока выбирается правильно, то в результате мы получим правый вывод строки <tex>w</tex>.
== LR(k)-Грамматика ==
{{Определение
|id=def_augmented_grammar)
|definition=
Пусть <tex>\Gamma =\langle \Sigma, N, S, P \rangle</tex> {{---}} КС-грамматика. '''Пополненной грамматикой''' (англ. ''augmented grammar''), полученной из <tex>\Gamma</tex>, назовем грамматику <tex>\Gamma' =\langle \Sigma', N', S', P' \rangle</tex>, где <tex>\Sigma' = \Sigma; N' = N \cup \{S'\}; S' \notin N; P' = P \cup \{S' \to S\}</tex>
}}
{{Определение
|id=def_LR_K
|definition=
Пусть <tex>\Gamma' =\langle \Sigma', N', S', P' \rangle</tex> {{---}} пополненная грамматика для КС-грамматики <tex>\Gamma</tex>. Грамматика <tex>\Gamma</tex> явяется '''LR(k)-грамматикой''', если для любых двух правосторонних выводов вида:
* <tex>S' \Rightarrow^* \alpha A w \Rightarrow \alpha \beta w </tex>,
* <tex>S' \Rightarrow^* \gamma B x \Rightarrow \alpha \beta y </tex>,
в которых <tex> \mathrm{FIRST}_k(w) = \mathrm{FIRST}_k(y)</tex>, должно быть <tex>\alpha A y = \gamma B x</tex>. Другими словами, <tex>\alpha = \gamma, A=B, y=x </tex>.
}}
Говоря неформально, если согласно первому выводу <tex>\beta</tex> {{---}} основа, сворачиваемая в нетерминал <tex>A</tex>, то и во втором выводе <tex>\beta</tex> должна быть основой, сворачиваемой в нетерминал <tex>A</tex>.
Из этого определения следует, что если имеется правовыводимая цепочка <tex>\alpha_i = \alpha \beta w</tex>, где <tex>\beta</tex> {{---}} основа, полученная из <tex>A</tex>, и если <tex>\alpha \beta = X_1 X_2 ... X_r</tex>, то
* зная первые символы <tex>X_1 X_2 ... X_j</tex> цепочки <tex>\alpha \beta</tex> и не более, чем <tex>k</tex> следующих символов цепочки <tex>X_{j+1} X_{j+2} ... X_r w</tex>, мы можем быть уверены, что правый конец основы не будет достигнут до тех пор, пока <tex> j \ne r</tex>;
* зная цепочку <tex>\alpha \beta = X_1 X_2 ... X_r</tex> и не более <tex>k</tex> символов цепочки <tex>w</tex>, мы можем быть уверены, что именно <tex>\beta</tex> является основой, сворачиваемой в нетерминал <tex>A</tex>;
* если <tex>\alpha_{i-1} = S'</tex>, можно сигнализировать о выводимости исходной терминальной цепочки из <tex>S'</tex> и, следовательно, из <tex>S</tex>.
Использование в определении LR(k)-грамматики пополненной грамматики существенно для однозначного определения конца анализа. Действительно, если грамматика использует <tex>S</tex> в правых частях правил, то свертка основы в <tex>S</tex> не может служить сигналом приема входной цепочки. Свертка же в <tex>S'</tex> в пополненной грамматике служит таким сигналом, поскольку <tex>S'</tex> нигде, кроме начальной сентенциальной формы, не встречается.
== LR(k)-Разбор ==
LR(k) означает, что
* входная цепочка обрабатывается слева направо (англ. ''left-to-right parse'');
* выполняется правый вывод (англ. ''rightmost derivation'');
* не более <tex>k</tex> символов цепочки (англ. ''k-token lookahead'') используются для принятия решения.
== Перенос-свертка ==
При LR(k)-анализе применяется метод ''"перенос-свертка"'' (англ. ''shift-reduce''). Этот метод использует магазинный автомат. Суть метода сводится к следующему. Символы входной цепочки переносятся в магазин до тех пор, пока на вершине магазина не накопится цепочка, совпадающая с правой частью какого-нибудь из правил (операция ''"перенос"''). Далее все символы этой цепочки извлекаются из магазина и на их место помещается нетерминал, находящийся в левой части этого правила (операция ''"свертка"''). Входная цепочка допускается автоматом, если после переноса в автомат последнего символа входной цепочки и выполнения операции свертка, в магазине окажется только аксиома грамматики.
== Управляющая программа анализатора ==
Для определения, какую операцию применить(перенос-свертку), используем управляющую таблицу, о которой будет рассказано подробнее позже. Управляющая программа одинакова для всех 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>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"
|align="left" colspan="4"|
<font size=2>
'''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 <tex> \to \beta</tex>
'''for''' j = 1 '''to''' <tex>|\beta |</tex>
pop ()
pop ()
s’ = top()
push (A)
push (goto [s’, A])
Вывод правила (A <tex> \to \beta</tex>)
'''else''' '''if''' action [s, a] == accept
'''return''' success
'''else'''
'''return''' error
</font>
|}
Функция <tex>goto</tex> получает состояние и символ грамматики и выдает состояние. Функция <tex>goto</tex>, строящаяся по грамматике <tex>\Gamma</tex>, есть функция переходов детерминированного магазинного автомата, который распознает язык,
порождаемый грамматикой <tex>\Gamma</tex>.
== См. также ==
* [[Предиктивный синтаксический анализ]]
== Источники информации ==
* Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс, 2003. Стр. 301 - 326.
* [http://ict.edu.ru/ft/005128//ch7.pdf Терехов Ан.А., Вояковская Н., Булычев Д., Москаль А. - Разработка компиляторов на платформе .NET - Восходящие анализаторы]
* [http://window.edu.ru/resource/974/69974/files/lang_trans.pdf Б.К.Мартыненко. Языки и трансляции. Стр. 198 - 223]
[[Категория: Методы трансляции]]
[[Категория: Восходящий разбор]]
== LR(k)-Грамматика ==
{{Определение
|id=def_augmented_grammar)
|definition=
Пусть <tex>\Gamma =\langle \Sigma, N, S, P \rangle</tex> {{---}} КС-грамматика. '''Пополненной грамматикой''' (англ. ''augmented grammar''), полученной из <tex>\Gamma</tex>, назовем грамматику <tex>\Gamma' =\langle \Sigma', N', S', P' \rangle</tex>, где <tex>\Sigma' = \Sigma; N' = N \cup \{S'\}; S' \notin N; P' = P \cup \{S' \to S\}</tex>
}}
{{Определение
|id=def_LR_K
|definition=
Пусть <tex>\Gamma' =\langle \Sigma', N', S', P' \rangle</tex> {{---}} пополненная грамматика для КС-грамматики <tex>\Gamma</tex>. Грамматика <tex>\Gamma</tex> явяется '''LR(k)-грамматикой''', если для любых двух правосторонних выводов вида:
* <tex>S' \Rightarrow^* \alpha A w \Rightarrow \alpha \beta w </tex>,
* <tex>S' \Rightarrow^* \gamma B x \Rightarrow \alpha \beta y </tex>,
в которых <tex> \mathrm{FIRST}_k(w) = \mathrm{FIRST}_k(y)</tex>, должно быть <tex>\alpha A y = \gamma B x</tex>. Другими словами, <tex>\alpha = \gamma, A=B, y=x </tex>.
}}
Говоря неформально, если согласно первому выводу <tex>\beta</tex> {{---}} основа, сворачиваемая в нетерминал <tex>A</tex>, то и во втором выводе <tex>\beta</tex> должна быть основой, сворачиваемой в нетерминал <tex>A</tex>.
Из этого определения следует, что если имеется правовыводимая цепочка <tex>\alpha_i = \alpha \beta w</tex>, где <tex>\beta</tex> {{---}} основа, полученная из <tex>A</tex>, и если <tex>\alpha \beta = X_1 X_2 ... X_r</tex>, то
* зная первые символы <tex>X_1 X_2 ... X_j</tex> цепочки <tex>\alpha \beta</tex> и не более, чем <tex>k</tex> следующих символов цепочки <tex>X_{j+1} X_{j+2} ... X_r w</tex>, мы можем быть уверены, что правый конец основы не будет достигнут до тех пор, пока <tex> j \ne r</tex>;
* зная цепочку <tex>\alpha \beta = X_1 X_2 ... X_r</tex> и не более <tex>k</tex> символов цепочки <tex>w</tex>, мы можем быть уверены, что именно <tex>\beta</tex> является основой, сворачиваемой в нетерминал <tex>A</tex>;
* если <tex>\alpha_{i-1} = S'</tex>, можно сигнализировать о выводимости исходной терминальной цепочки из <tex>S'</tex> и, следовательно, из <tex>S</tex>.
Использование в определении LR(k)-грамматики пополненной грамматики существенно для однозначного определения конца анализа. Действительно, если грамматика использует <tex>S</tex> в правых частях правил, то свертка основы в <tex>S</tex> не может служить сигналом приема входной цепочки. Свертка же в <tex>S'</tex> в пополненной грамматике служит таким сигналом, поскольку <tex>S'</tex> нигде, кроме начальной сентенциальной формы, не встречается.
== LR(k)-Разбор ==
LR(k) означает, что
* входная цепочка обрабатывается слева направо (англ. ''left-to-right parse'');
* выполняется правый вывод (англ. ''rightmost derivation'');
* не более <tex>k</tex> символов цепочки (англ. ''k-token lookahead'') используются для принятия решения.
== Перенос-свертка ==
При LR(k)-анализе применяется метод ''"перенос-свертка"'' (англ. ''shift-reduce''). Этот метод использует магазинный автомат. Суть метода сводится к следующему. Символы входной цепочки переносятся в магазин до тех пор, пока на вершине магазина не накопится цепочка, совпадающая с правой частью какого-нибудь из правил (операция ''"перенос"''). Далее все символы этой цепочки извлекаются из магазина и на их место помещается нетерминал, находящийся в левой части этого правила (операция ''"свертка"''). Входная цепочка допускается автоматом, если после переноса в автомат последнего символа входной цепочки и выполнения операции свертка, в магазине окажется только аксиома грамматики.
== Управляющая программа анализатора ==
Для определения, какую операцию применить(перенос-свертку), используем управляющую таблицу, о которой будет рассказано подробнее позже. Управляющая программа одинакова для всех 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>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"
|align="left" colspan="4"|
<font size=2>
'''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 <tex> \to \beta</tex>
'''for''' j = 1 '''to''' <tex>|\beta |</tex>
pop ()
pop ()
s’ = top()
push (A)
push (goto [s’, A])
Вывод правила (A <tex> \to \beta</tex>)
'''else''' '''if''' action [s, a] == accept
'''return''' success
'''else'''
'''return''' error
</font>
|}
Функция <tex>goto</tex> получает состояние и символ грамматики и выдает состояние. Функция <tex>goto</tex>, строящаяся по грамматике <tex>\Gamma</tex>, есть функция переходов детерминированного магазинного автомата, который распознает язык,
порождаемый грамматикой <tex>\Gamma</tex>.
== См. также ==
* [[Предиктивный синтаксический анализ]]
== Источники информации ==
* Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс, 2003. Стр. 301 - 326.
* [http://ict.edu.ru/ft/005128//ch7.pdf Терехов Ан.А., Вояковская Н., Булычев Д., Москаль А. - Разработка компиляторов на платформе .NET - Восходящие анализаторы]
* [http://window.edu.ru/resource/974/69974/files/lang_trans.pdf Б.К.Мартыненко. Языки и трансляции. Стр. 198 - 223]
[[Категория: Методы трансляции]]
[[Категория: Восходящий разбор]]
