Изменения

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

== LR(k)-Грамматика грамматика ===== Определение ===

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

Пусть <tex>\Gamma' =\langle \Sigma', N', S'E_0, P' \rangle</tex> {{---}} пополненная грамматика для КС-грамматики <tex>\Gamma</tex>. Грамматика <tex>\Gamma</tex> явяется является '''LR(k)-грамматикой''', если из того, что для любых двух [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора#Лево-_и_правосторонний_вывод_слова|правосторонних выводов вида]] верно, что:* <tex>S' E_0 \Rightarrow^* \alpha beta A w t z \Rightarrow \beta \alpha t z \beta Rightarrow^* w , </tex>если <tex>|t|=k</tex> или <tex>|t|<k,|z|=0 (z = \varepsilon)</tex>* <tex>S' E_0 \Rightarrow^* \gamma B x t z' \Rightarrow \alpha gamma \xi t z' \beta y Rightarrow^* w', </tex> если <tex>|t|=k</tex>,в которых или <tex> \mathrm{FIRST}_k|t|<k, |z'|=0 (w) z' = \mathrm{FIRST}_k(yvarepsilon)</tex> следует, должно быть что <tex>\beta \alpha A y = \gamma B x\xi</tex>. Другими словами,  тогда <tex>\alpha beta = \gamma, </tex> и <tex>A=B, y=x </tex>.

Говоря неформально, если согласно первому выводу Если игнорировать <tex>\beta0</tex> {{---}} основае правило, то, сворачиваемая не заглядывая в нетерминал правый контекст основы <tex>AEa</tex>, то и во втором выводе <tex>\beta</tex> можно сказать, что она должна быть основой, сворачиваемой сворачиваться в нетерминал <tex>AE</tex>.Из этого определения следует, что если имеется правовыводимая цепочка <tex>\alpha_i = \alpha \beta w</tex>, где <tex>\beta</tex> {{---}} Аналогично основа, полученная из <tex>Aa</tex>, и если <tex>\alpha \beta = X_1 X_2 ... X_r</tex>, то* зная первые символы <tex>X_1 X_2 ... X_jбезусловно должна сворачиваться в </tex> цепочки <tex>\alpha \betaE</tex> и не более, чем <tex>k</tex> следующих символов цепочки <tex>X_{j+1} X_{j+2} ... X_r w</tex>, мы можем быть увереныСоздается впечатление, что правый конец основы не будет достигнут до тех пор, пока данная грамматика без <tex> j \ne r0</tex>;* зная цепочку <tex>\alpha \beta = X_1 X_2 -го правила есть LR(0)-грамматика... 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(0)-разбор|LR(k0)-грамматики пополненной грамматики существенно для однозначного определения конца анализа. Действительно, если грамматика использует <tex>S</tex> в правых частях правил, то свертка основы в <tex>S</tex> не может служить сигналом приема входной цепочки. Свертка же в <tex>S'</tex> в пополненной грамматике служит таким сигналом, поскольку <tex>S'</tex> нигде, кроме начальной сентенциальной формы, не встречаетсяразбора]].

== LR(k)-Разбор разборщик ==

=== Принцип переноса-свёртки ===При LR(k) означает, что * входная цепочка обрабатывается слева направо -анализе применяется метод '''перенос-свертка''' (англ. ''leftshift-to-right parsereduce'');. Суть метода сводится к следующему:* выполняется правый вывод # Программа анализатора читает последовательно символы входной строки до тех пор, пока не накопится цепочка, совпадающая с правой частью какого-нибудь из правил. Рассмотренные символы переносим в стек (англ. операция '''перенос'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>s_0</tex> {{---}} стартовое состояние автомата.Комбинация символа состояния на вершине стека и текущего входного символа используется для индексирования управляющей таблицы и определения операции переноса-свертки. При реализации грамматические символы не обязательно располагаются в стеке, однако, мы будем использовать их при обсуждении для лучшего понимания поведения LR-анализатора.

Программа ведет себя Обращение к таблице происходит следующим образом<tex>\mathtt{T[state, token]}</tex>, где *<tex>\mathtt{state}</tex> {{---}} состояние автомата, *<tex>\mathtt{token}</tex> {{---}} входной символ. Полученное значение в таблице должно информировать о текущем действии, то есть о переносе или свертке. В этих двух случаях необходима дополнительная информация: к какому состоянию происходит переход (при переносе) и по какому правилу происходит свертка. Если входной символ некорректен, то происходит ошибка, а свертка в стартовое состояние идентифицируется как допуск: '''struct''' Shift { state: '''int''' } <font color="green">// переход в состояние с номером state</font> '''struct''' Reduce { rule: '''int''' } <font color="green">// свертка по правилу с номером rule</font> '''enum''' Result = Accept <font color="green">// допуск </font> | Error <font color="green">// ошибка</font> '''enum''' Cell = Shift | Reduce | Result

Происходит обращение к таблице: <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> '''boolResult''' algorithmLR(w: '''string''') ip <font color=green>// curToken {{---}} указатель на перый первый символ в строке w</font> '''while''' цепочка не закончиласьhasTokens() s curState = top() a = w[ip] '''ifwhen''' action (<tex>\mathtt{T}</tex>[scurState, acurToken] == shift s’ push (a) push Shift(s’s) ip++ '''else if->''' action [ push(curToken) push(s, a] == reduce A ) nextToken() Reduce(<tex> A \to \beta</tex> ) '''->''' '''for''' j = 1 '''to''' <tex>|\beta |</tex> pop () pop () s’ s = top() push (<tex>A</tex>) push (goto [s’(s, <tex>A]</tex>)) Вывод правила (A : <tex> A \to \beta</tex>) Accept '''else->''' '''ifreturn''' action [s, a] == accept Accept Error '''return->''' success '''else''' '''return''' error </font>|}Error

* Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс, 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]* [http://www.cs.bham.ac.uk/~hxt/2015/mgs-ll-lr/LL-LR-MGS.pdf Nice slides]