Изменения

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

== LR(k)-Грамматика грамматика ==

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