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

2015-09-03T15:37:11Z

217.66.159.66:

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

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

{{Определение
|id=def_augmented_grammar)
|definition=
Пусть <tex>\Gamma =\langle \Sigma, N, E, P \rangle</tex> {{---}} [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|контекстно-свободная]] грамматика. '''Пополненной грамматикой''' (англ. ''augmented grammar''), полученной из <tex>\Gamma</tex>, назовем грамматику <tex>\Gamma' =\langle \Sigma', N', E_0, P' \rangle</tex>, где <tex>\Sigma' = \Sigma; N' = N \cup \{E_0\}; E_0 \notin N; P' = P \cup \{E_0 \to E\}</tex>
}}
{{Определение
|id=def_LR_K
|definition=
Пусть <tex>\Gamma' =\langle \Sigma', N', E_0, P' \rangle</tex> {{---}} пополненная грамматика для КС-грамматики <tex>\Gamma</tex>. Грамматика <tex>\Gamma</tex> является '''LR(k)-грамматикой''', если из того, что для любых двух [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора#Лево-_и_правосторонний_вывод_слова|правосторонних выводов]] верно, что:
* <tex>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>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>E</tex> в правых частях правил, то свертка основы в <tex>E</tex> не может служить сигналом приема входной цепочки. Свертка же в <tex>E_0</tex> в пополненной грамматике служит таким сигналом, поскольку <tex>E_0</tex> нигде, кроме начальной сентенциальной формы, не встречается.

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

<tex>
(0)\ E_0 \to E \\
(1)\ E \to Ea \\
(2)\ E \to a \\
</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)-разбора]].

== LR-разборщик ==

=== Принцип переноса-свёртки ===
При 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''' Cell
enum:
Shift
Reduce
Error // ошибка
Accept // допуск 
'''struct''' Shift
state: '''int''' // переход в стостояние state
'''struct''' Reduce
rule: '''int''' // свертка по правилу rule

Рузультатом работы управляющей программы будет:
'''struct''' Result
enum:
Accept // допуск 
Error // ошибка

=== Алгоритм ===
# Программа читает символ из входной цепочки.
# Обращается к управляющей таблице.
# Совершает соответствующее действие.
# Возвращается к первому пункту, пока входная цепочка не закончится.

{| border="0"
|align="left" colspan="4"|

'''Result''' algorithmLR(w: '''string''')
curToken {{---}} указатель на первый символ в строке w
'''while''' haveToken()
curState = top()
'''if''' <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>)
'''else''' '''if''' <tex>\mathtt{T}</tex>[curState, curToken] == Accept
'''return''' Accept
'''else'''
'''return''' Error

|}

Функция <tex>goto</tex> получает состояние и символ грамматики и выдает состояние. Функция <tex>goto</tex>, строящаяся по грамматике <tex>\Gamma</tex>, есть функция переходов детерминированного магазинного автомата, который распознает язык,
порождаемый грамматикой <tex>\Gamma</tex>.

== См. также ==
* [[Предиктивный синтаксический анализ]]
* [[LL(k)-грамматики, множества FIRST и FOLLOW]]

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

[[Категория: Методы трансляции]]
[[Категория: Восходящий разбор]]

Викиконспекты - Вклад участника [ru]

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