Изменения

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

Пусть <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>

Использование в определении LR(k)-грамматики пополненной грамматики существенно для однозначного определения конца анализа. Действительноследует, если грамматика использует что <tex>S\beta \alpha = \gamma \xi</tex> в правых частях правил, то свертка основы в  тогда <tex>S\beta = \gamma</tex> не может служить сигналом приема входной цепочки. Свертка же в и <tex>S'A = B</tex> .}}Говоря неформально, мы делаем правостороннюю свёртку нашей строки в пополненной грамматике служит таким сигналом, поскольку стартовый нетерминал. Если по не более чем <tex>S'k</tex> нигдесимволам неразобранной части строки мы можем однозначно определить, кроме начальной сентенциальной формыво что сворачивается хвост выведенного правила, не встречаетсято грамматика будет LR(k).

LR(k) означает, что: * входная цепочка обрабатывается слева направо (англ. ''left-to-right parse''),* выполняется правый вывод (англ. ''rightmost derivation''),* для принятия решения используется не более <tex>k<// TODO сделать пример, когда нам точно нужно пополнять грамматикуtex> символов цепочки (англ. ''k-token lookahead'').

{{Определение|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 E</tex>в правых частях правил,* то свертка основы в <tex>S' \Rightarrow^* \gamma B x \Rightarrow \alpha \beta y E</tex>,не может служить сигналом приема входной цепочки. Свертка же в которых <tex> \mathrm{FIRST}_k(w) = \mathrm{FIRST}_k(y)E_0</tex>в пополненной грамматике служит таким сигналом, должно быть поскольку <tex>\alpha A y = \gamma B xE_0</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>определении LR(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>грамматик продемонстрируем на следующем конкретном примере.Пусть пополненная грамматика имеет следующие правила:

<tex>(0)\ E_0 \to E \\(1)\ E \to Ea \\(2)\ E \to a \\<// TODO endtex>

LR(k) означаетЕсли игнорировать <tex>0</tex>-е правило, то, не заглядывая в правый контекст основы <tex>Ea</tex>, можно сказать, что * входная цепочка обрабатывается слева направо (англона должна сворачиваться в <tex>E</tex>. ''left-to-right parse'');* выполняется правый вывод (англАналогично основа <tex>a</tex> безусловно должна сворачиваться в <tex>E</tex>. ''rightmost derivation'');* не более Создается впечатление, что данная грамматика без <tex>k0</tex> символов цепочки -го правила есть LR(англ0)-грамматика. ''kЧто на самом деле неверно, в чём можно убедиться, рассмотрев процесс [[LR(0)-token lookahead''разбор|LR(0) используются для принятия решения-разбора]].

При LR(k)-анализе применяется метод '''перенос-свертка''' (англ. ''shift-reduce''). Суть метода сводится к следующему. :* # Программа анализатора читает последовательно символы входной строки до тех пор, пока не накопится цепочка, совпадающая с правой частью какого-нибудь из правил. Рассмотренные символы переносим в стек (операция '''перенос'''). * # Далее все символы совпадающей цепочки извлекаются из стека и на их место помещается нетерминал, находящийся в левой части этого правила (операция '''свертка''').

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

Для запоминания строки запись в [[Стек|стек ]] имеет вид: <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> {{---}} стартовае стартовое состояние автомата. Ображение к таблице происходит по паре <tex>[s_m, a_i]</tex>, где *<tex>s_m</tex> {{Комбинация символа состояния на вершине стека и текущего входного символа используется для индексирования управляющей таблицы и определения операции переноса---}} текущее состояние автомата, *<tex>a_i</tex> {{---}} текущий входной символ; В таблице информация отображается слудующим образом:*переход свертки. При реализации грамматические символы не обязательно располагаются в стостояние <tex>(shift)</tex>*свертка по правилу <tex>(reduce)</tex>стеке,*допуск <tex>(accept)</tex>однако,*ошибка <tex>(error)</tex>мы будем использовать их при обсуждении для лучшего понимания поведения LR-анализатора.

# Обращается к утравляющей управляющей таблице.

# Возвращается к первому пункту, пока входная цепочка не закончится.

{| 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) pushShift(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]