Изменения

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

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

верноследует, что <tex>\beta \alpha = \gamma \xi</tex>,

следует, что тогда <tex>\beta = \gamma</tex> и <tex>A = B</tex>.

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

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

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

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

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

(0)\ S' E_0 \to S E \\(1)\ S E \to Sa Ea \\(2)\ S E \to a \\

Если игнорировать <tex>0</tex>-е правило, то, не заглядывая в правый контекст основы <tex>SaEa</tex>, можно сказать, что она должна сворачиваться в <tex>SE</tex>. Аналогично основа <tex>a</tex> безусловно должна сворачиваться в <tex>SE</tex>. Создается впечатление, что данная грамматика без <tex>0</tex>-го правила есть LR(0)-грамматика. С учетом же <tex>0</tex>-го правилаЧто на самом деле неверно, после свертки в <tex>S</tex>чём можно убедиться, просматривая <tex>k=рассмотрев процесс [[LR(0</tex> символов, нельзя определить, делать ли свертку в <tex>S'</tex>, следовательно это не )-разбор|LR(0)-грамматика. Получили противоречиеразбора]].--------- TODO тут надо либо дать более формальное объяснение, либо объяснить почему k не должно меняться от пополнения грамматики. ----------------

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

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

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

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

<font color=green>// curToken {{---}} указатель на перый первый символ в строке w</font> '''while''' haveTokenhasTokens()

'''ifwhen''' (<tex>\mathtt{T}</tex>[curState, curToken] == ) Shift (s ) '''->''' push(curToken) push(s) nextToken() '''else if''' <tex>\mathtt{T} Reduce(</tex>[curState, curToken] == Reduce A <tex> \to \beta</tex> ) '''->''' '''for''' j = 1 '''to''' <tex>|\beta |</tex> pop() pop() s = top() push(<tex>A</tex>) push(goto [(s, <tex>A]</tex>)) Вывод правила (A : <tex> A \to \beta</tex>) Accept '''else->''' '''ifreturn''' <tex>\mathtt{T}</tex>[curState, curToken] == Accept Error '''return'->'' Accept '''else''' '''return''' Error </font>|}

* Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс, 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]