Изменения

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

тогда <tex>\beta = \gamma</tex> и <tex>A = B</tex>.

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

* для принятия решения используется не более <tex>k</tex> символов цепочки (англ. ''k-token lookahead'') используются для принятия решения.

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

Если игнорировать <tex>0</tex>-е правило, то, не заглядывая в правый контекст основы <tex>Ea</tex>, можно сказать, что она должна сворачиваться в <tex>E</tex>. Аналогично основа <tex>a</tex> безусловно должна сворачиваться в <tex>E</tex>. Создается впечатление, что данная грамматика без <tex>0</tex>-го правила есть LR(0)-грамматика. Но Что на самом деле это не такневерно, в этом чём можно убедиться , рассмотрев процесс [[LR(0)-разбор|LR(0)-разбора]].

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

Полученное значение в таблице должно информировать о текущем действии, то есть о переносе или свертке. В этих двух случаях, необходима дополнительная информация: к какому состоянию происходит переход (при переносе) и по какому правилу происходит свертка. В случае некорректного входного символа Если входной символ некорректен, то происходит ошибка, а свертка в стартовое состояние идентифицируется как допуск: '''struct''' Cell enum: Shift Reduce Error <font color="green">// ошибка</font> Accept <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}</tex>[curState, curToken] == Reduce (<tex> A \to \beta</tex> ) '''->''' '''for''' j = 1 '''to''' <tex>|\beta |</tex> pop() pop() s = top() push(<tex>A</tex>) push(goto [(s, <tex>A]</tex>)) Вывод правила (: <tex> A \to \beta</tex>) Accept '''else->''' '''ifreturn''' <tex>\mathtt{T}</tex>[curState, curToken] == Accept Error '''return''' Accept '''else->''' '''return''' Error </font>|}