297
правок
Изменения
Новая страница: «== LR(0)-Разбор == === Иллюстрация алгоритма === Заметим, что LR(0)-анализатор принимает решение о...»
== LR(0)-Разбор ==
=== Иллюстрация алгоритма ===
Заметим, что LR(0)-анализатор принимает решение о своих действиях только на основании содержимого магазина, не учитывая символы входной цепочки. Для иллюстрации построения таблиц LR(0)-анализатора мы будем использовать грамматику:
<tex>
E \to E + T \\
E \to T \\
T \to {\bf n} \\
T \to (E) \\
</tex>
Для начала переходим к ''Пополненной грамматике'':
<tex>
E_0 \to E \\
E \to E + T \\
E \to T \\
T \to {\bf n} \\
T \to (E) \\
</tex>
{{Определение
|id=def_LRk_item)
|definition=
Пусть <tex>\Gamma =\langle \Sigma, N, S, P \rangle</tex> {{---}} КС-грамматика и <tex>A \to w_1 w_2 \in P</tex>. Композицию <tex>[A \to w_1 \cdot w_2, u] </tex>, где <tex>u \in \Sigma^{*k}</tex>, назовем '''LR(k)-ситуацией''' (англ. ''LR(k)-item'')
}}
LR(0)-ситуации не должны содержать терминальной цепочки, так как <tex>k=0</tex>, то есть мы можем записывать их следующим образом: <tex>[A \to w_1 \cdot w_2]</tex>
==== Построение автомата ====
В начале работы магазин пуст, и указатель входной цепочки находится перед ее первым символом. Этому состоянию соответствует ситуация <tex>[E_0 \to \cdot E]</tex>.
Для терминалов или нетерминалой, мы строим переходы к другим ситуациям по следующей схеме:
<tex>{[} A \to \alpha \cdot c \beta] \xrightarrow{\text{c}} {[} A \to \alpha c \cdot \beta] </tex>
<tex>{[} A \to \alpha \cdot B \beta] \xrightarrow{\text{B}} {[} A \to \alpha B \cdot \beta] </tex>
Также стоим <tex>\epsilon</tex>-переходы:
<tex>{[} A \to \alpha \cdot B \beta] \xrightarrow{\epsilon} {[} B \to \cdot \gamma] </tex>
Получаем следующий недетерминированный конечный автомат:
[[Файл:eps-dfa.png|600px]]
Избавимся от <tex>\epsilon</tex>-переходов и получим детерминированный автомат:
[[Файл:LRk_dfa.png|600px]]
==== Управляющая таблица ====
Теперь можно построить управляющую таблицу.
Поступим следующим образом:
1. для каждого ребра <tex>I \to^X J </tex> мы поместим в позицию <tex>[I,X]</tex> таблицы
* <tex>s\ J</tex> (англ. ''shift'') , если <tex>X</tex> {{---}} терминал,
*<tex>J</tex>, если <tex>X</tex> {{---}} нетерминал.
2. для состояния, содержащего ситуацию <tex>[A\to w \cdot]</tex>, поместим <tex>r(n)</tex> (англ. ''reduce'') в позицию <tex>[I, Y]</tex> для каждого терминала <tex>Y</tex>, где n {{---}} это номер правила в изначальной грамматике.
3. пустая ячейка означает ошибочную ситуацию.
Вспомним грамматику и пронумеруем правила для 2 пункта:
<tex>
(0)\ E_0 \to E\\
(1)\ E \to E + T\\
(2)\ E \to T\\
(3)\ T \to {\bf n} \\
(4)\ T \to (E) \\
</tex>
Управляющая таблица будет выглядеть так:
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"|
!style="background-color:#EEE"| <tex>E</tex>
!style="background-color:#EEE"| <tex>T</tex>
!style="background-color:#EEE"| <tex>n</tex>
!style="background-color:#EEE"| <tex>+</tex>
!style="background-color:#EEE"| <tex>(</tex>
!style="background-color:#EEE"| <tex>)</tex>
!style="background-color:#EEE"| <tex>\$</tex>
|-
|style="background-color:#EEE;padding:2px 30px"| <tex>0</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>1</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>2</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>s3</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"| <tex>s4</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"|
|-
|style="background-color:#EEE;padding:2px 30px"| <tex>1</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"| <tex>s5</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"| <tex>r(0)</tex>
|-
|style="background-color:#EEE;padding:2px 30px"| <tex>2</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"| <tex>r(2)</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"| <tex>r(2)</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>r(2)</tex>
|-
|style="background-color:#EEE;padding:2px 30px"| <tex>3</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"| <tex>r(3)</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"| <tex>r(3)</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>r(3)</tex>
|-
|style="background-color:#EEE;padding:2px 30px"| <tex>4</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>6</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>2</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>s3</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"| <tex>s4</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"|
|-
|style="background-color:#EEE;padding:2px 30px"| <tex>5</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"| <tex>7</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>s3</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"| <tex>s4</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"|
|-
|style="background-color:#EEE;padding:2px 30px"| <tex>6</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"| <tex>s5</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"| <tex>s8</tex>
|style="background-color:#FFF;padding:2px 20px"|
|-
|style="background-color:#EEE;padding:2px 30px"| <tex>7</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"| <tex>r(1)</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"| <tex>r(1)</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>r(1)</tex>
|-
|style="background-color:#EEE;padding:2px 30px"| <tex>8</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"| <tex>r(4)</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"| <tex>r(4)</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>r(4)</tex>
|}
=== Формальное описание ===
==== Базовые операции ====
Теперь опишем алгоритм формально.
Для построения множества состояний определим базовые операции <tex>closure (I)</tex> и <tex>goto (I, X)</tex>, где <tex>I</tex> – множество ситуаций, <tex>X</tex> – символ грамматики (терминал или нетерминал). Операция <tex>closure</tex> добавляет ситуации к множеству ситуаций, у которых точка стоит слева от нетерминала. Добавляются те ситуации, которые получаются из правил, в левой части которого находится этот нетерминал.
{| border="0"
|align="left" colspan="4"|
<font size=2>
[] '''closure''' (I)
'''do'''
'''for''' каждой ситуации [A <tex>\to</tex> w.Xv] из I
'''for''' каждого правила грамматики X <tex>\to</tex> u
I += [X <tex>\to</tex> .u] <font color=green> // Операция += добавляет элемент к множеству </font>
'''while''' I изменилось
'''return''' I
</font>
|}
Операция <tex>goto</tex> "переносит" точку после символа <tex>X</tex>. Это означает переход из одного состояния в другое под воздействием символа <tex>X</tex>.
{| border="0"
|align="left" colspan="4"|
<font size=2>
[] '''goto''' (I, X)
J={} <font color=green> // {} обозначает пустое множество </font>
'''for''' каждой ситуации [A <tex>\to</tex> w.Xv] из I
J += [A <tex> \to </tex>wX.v]
'''return''' closure (J)
</font>
|}
==== Алгоритм построения конечного автомата ====
Теперь обсудим алгоритм построения анализатора. Обозначим <tex>T</tex> множество состояний, <tex>E</tex> – множество переходов.
{| border="0"
|align="left" colspan="4"|
<font size=2>
E, T '''build'''()
E = {}
T = {closure ([S' <tex>\to</tex> .S])}
'''do'''
'''for''' каждого состояния I из T
'''for''' каждой ситуации [A <tex>\to</tex> w.Xv] из I
J = goto(I, X)
T += {J} <font color=green> // ко множеству состояний добавляется новое состояние </font>
E += (I <tex>\to</tex> J) <font color=green> // ко множеству ребер добавляется ребро, идущее из состояния I в состояние J. Этот переход осуществляется по символу X </font>
'''while''' E или T изменились
'''return''' E, T
</font>
|}
Поскольку для символа <tex>\$</tex> операция <tex>goto(I , \$)</tex> не определена , мы выполняем действие <tex>accept</tex>.
=== Пример LR(0)-разбора ===
Пример будет для строки <tex>(n_1+n_2)+n_3</tex>
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| Строка
!style="background-color:#EEE"| Стек
!style="background-color:#EEE"| <tex>s = top()</tex>
!style="background-color:#EEE"| <tex>a = w[ip]</tex>
!style="background-color:#EEE"| <tex>action[s,a]</tex>
!style="background-color:#EEE"| Комментарий
|-
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>(n_1+n_2)+n_3\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>(</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>shift\ 4</tex>
|style="background-color:#FFF;padding:2px 20px"| Перенос <tex>"("</tex>
|-
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>n_1+n_2)+n_3\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ (4</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>4</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>n_1</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>shift\ 3</tex>
|style="background-color:#FFF;padding:2px 20px"| Перенос <tex>"n_1"</tex>
|-
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>+n_2)+n_3\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ (4\ n_{1}3</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>3</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>reduce\ 3</tex>
|style="background-color:#FFF;padding:2px 20px"| Свертка: <tex>T \to \bf n</tex>
|-
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>+n_2)+n_3\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ (4\ T2</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>2</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>reduce\ 2</tex>
|style="background-color:#FFF;padding:2px 20px"| Свертка: <tex>E \to T</tex>
|-
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>+n_2)+n_3\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ (4\ E6</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>6</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>shift\ 5</tex>
|style="background-color:#FFF;padding:2px 20px"| Перенос <tex>"+"</tex>
|-
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>n_2)+n_3\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ (4\ E6\ +5</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>5</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>n_2</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>shift\ 3</tex>
|style="background-color:#FFF;padding:2px 20px"| Перенос <tex>"n_2"</tex>
|-
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>)+n_3\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ (4\ E6\ +5\ n_23</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>3</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>)</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>reduce\ 3 </tex>
|style="background-color:#FFF;padding:2px 20px"| Свертка: <tex>T \to \bf n</tex>
|-
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>)+n_3\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ (4\ E6\ +5\ T7</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>7</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>)</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>reduce\ 1 </tex>
|style="background-color:#FFF;padding:2px 20px"| Свертка: <tex>E \to E + T</tex>
|-
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>)+n_3\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ (4\ E6</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>6 </tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>)</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>shift\ 8</tex>
|style="background-color:#FFF;padding:2px 20px"| Перенос <tex>")"</tex>
|-
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>+n_3\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ (4\ E6\ )8</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>8 </tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>reduce\ 4</tex>
|style="background-color:#FFF;padding:2px 20px"| Свертка: <tex>T \to (E)</tex>
|-
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>+n_3\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ T2</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>2</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>reduce\ 2</tex>
|style="background-color:#FFF;padding:2px 20px"| Свертка: <tex>E \to T</tex>
|-
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>+n_3\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ E1</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>1</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>shift\ 5</tex>
|style="background-color:#FFF;padding:2px 20px"| Перенос <tex>"+"</tex>
|-
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>n_3\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ E1\ +5</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>5</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>n_3</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>shift\ 3</tex>
|style="background-color:#FFF;padding:2px 20px"| Перенос <tex>"n_3"</tex>
|-
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ E1\ +5\ n_33</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>3</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>reduce\ 3</tex>
|style="background-color:#FFF;padding:2px 20px"| Свертка: <tex>T \to \bf n</tex>
|-
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ E1\ +5\ T7</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>7</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>reduce\ 1</tex>
|style="background-color:#FFF;padding:2px 20px"| Свертка: <tex>E \to E + T</tex>
|-
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ E1</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>1</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>reduce\ 0</tex>
|style="background-color:#FFF;padding:2px 20px"| Допуск
|}
== См. также ==
* [[Предиктивный синтаксический анализ]]
== Источники информации ==
* Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс, 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]
[[Категория: Методы трансляции]]
[[Категория: Восходящий разбор]]
=== Иллюстрация алгоритма ===
Заметим, что LR(0)-анализатор принимает решение о своих действиях только на основании содержимого магазина, не учитывая символы входной цепочки. Для иллюстрации построения таблиц LR(0)-анализатора мы будем использовать грамматику:
<tex>
E \to E + T \\
E \to T \\
T \to {\bf n} \\
T \to (E) \\
</tex>
Для начала переходим к ''Пополненной грамматике'':
<tex>
E_0 \to E \\
E \to E + T \\
E \to T \\
T \to {\bf n} \\
T \to (E) \\
</tex>
{{Определение
|id=def_LRk_item)
|definition=
Пусть <tex>\Gamma =\langle \Sigma, N, S, P \rangle</tex> {{---}} КС-грамматика и <tex>A \to w_1 w_2 \in P</tex>. Композицию <tex>[A \to w_1 \cdot w_2, u] </tex>, где <tex>u \in \Sigma^{*k}</tex>, назовем '''LR(k)-ситуацией''' (англ. ''LR(k)-item'')
}}
LR(0)-ситуации не должны содержать терминальной цепочки, так как <tex>k=0</tex>, то есть мы можем записывать их следующим образом: <tex>[A \to w_1 \cdot w_2]</tex>
==== Построение автомата ====
В начале работы магазин пуст, и указатель входной цепочки находится перед ее первым символом. Этому состоянию соответствует ситуация <tex>[E_0 \to \cdot E]</tex>.
Для терминалов или нетерминалой, мы строим переходы к другим ситуациям по следующей схеме:
<tex>{[} A \to \alpha \cdot c \beta] \xrightarrow{\text{c}} {[} A \to \alpha c \cdot \beta] </tex>
<tex>{[} A \to \alpha \cdot B \beta] \xrightarrow{\text{B}} {[} A \to \alpha B \cdot \beta] </tex>
Также стоим <tex>\epsilon</tex>-переходы:
<tex>{[} A \to \alpha \cdot B \beta] \xrightarrow{\epsilon} {[} B \to \cdot \gamma] </tex>
Получаем следующий недетерминированный конечный автомат:
[[Файл:eps-dfa.png|600px]]
Избавимся от <tex>\epsilon</tex>-переходов и получим детерминированный автомат:
[[Файл:LRk_dfa.png|600px]]
==== Управляющая таблица ====
Теперь можно построить управляющую таблицу.
Поступим следующим образом:
1. для каждого ребра <tex>I \to^X J </tex> мы поместим в позицию <tex>[I,X]</tex> таблицы
* <tex>s\ J</tex> (англ. ''shift'') , если <tex>X</tex> {{---}} терминал,
*<tex>J</tex>, если <tex>X</tex> {{---}} нетерминал.
2. для состояния, содержащего ситуацию <tex>[A\to w \cdot]</tex>, поместим <tex>r(n)</tex> (англ. ''reduce'') в позицию <tex>[I, Y]</tex> для каждого терминала <tex>Y</tex>, где n {{---}} это номер правила в изначальной грамматике.
3. пустая ячейка означает ошибочную ситуацию.
Вспомним грамматику и пронумеруем правила для 2 пункта:
<tex>
(0)\ E_0 \to E\\
(1)\ E \to E + T\\
(2)\ E \to T\\
(3)\ T \to {\bf n} \\
(4)\ T \to (E) \\
</tex>
Управляющая таблица будет выглядеть так:
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"|
!style="background-color:#EEE"| <tex>E</tex>
!style="background-color:#EEE"| <tex>T</tex>
!style="background-color:#EEE"| <tex>n</tex>
!style="background-color:#EEE"| <tex>+</tex>
!style="background-color:#EEE"| <tex>(</tex>
!style="background-color:#EEE"| <tex>)</tex>
!style="background-color:#EEE"| <tex>\$</tex>
|-
|style="background-color:#EEE;padding:2px 30px"| <tex>0</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>1</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>2</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>s3</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"| <tex>s4</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"|
|-
|style="background-color:#EEE;padding:2px 30px"| <tex>1</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"| <tex>s5</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"| <tex>r(0)</tex>
|-
|style="background-color:#EEE;padding:2px 30px"| <tex>2</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"| <tex>r(2)</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"| <tex>r(2)</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>r(2)</tex>
|-
|style="background-color:#EEE;padding:2px 30px"| <tex>3</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"| <tex>r(3)</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"| <tex>r(3)</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>r(3)</tex>
|-
|style="background-color:#EEE;padding:2px 30px"| <tex>4</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>6</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>2</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>s3</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"| <tex>s4</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"|
|-
|style="background-color:#EEE;padding:2px 30px"| <tex>5</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"| <tex>7</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>s3</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"| <tex>s4</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"|
|-
|style="background-color:#EEE;padding:2px 30px"| <tex>6</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"| <tex>s5</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"| <tex>s8</tex>
|style="background-color:#FFF;padding:2px 20px"|
|-
|style="background-color:#EEE;padding:2px 30px"| <tex>7</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"| <tex>r(1)</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"| <tex>r(1)</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>r(1)</tex>
|-
|style="background-color:#EEE;padding:2px 30px"| <tex>8</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"| <tex>r(4)</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"| <tex>r(4)</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>r(4)</tex>
|}
=== Формальное описание ===
==== Базовые операции ====
Теперь опишем алгоритм формально.
Для построения множества состояний определим базовые операции <tex>closure (I)</tex> и <tex>goto (I, X)</tex>, где <tex>I</tex> – множество ситуаций, <tex>X</tex> – символ грамматики (терминал или нетерминал). Операция <tex>closure</tex> добавляет ситуации к множеству ситуаций, у которых точка стоит слева от нетерминала. Добавляются те ситуации, которые получаются из правил, в левой части которого находится этот нетерминал.
{| border="0"
|align="left" colspan="4"|
<font size=2>
[] '''closure''' (I)
'''do'''
'''for''' каждой ситуации [A <tex>\to</tex> w.Xv] из I
'''for''' каждого правила грамматики X <tex>\to</tex> u
I += [X <tex>\to</tex> .u] <font color=green> // Операция += добавляет элемент к множеству </font>
'''while''' I изменилось
'''return''' I
</font>
|}
Операция <tex>goto</tex> "переносит" точку после символа <tex>X</tex>. Это означает переход из одного состояния в другое под воздействием символа <tex>X</tex>.
{| border="0"
|align="left" colspan="4"|
<font size=2>
[] '''goto''' (I, X)
J={} <font color=green> // {} обозначает пустое множество </font>
'''for''' каждой ситуации [A <tex>\to</tex> w.Xv] из I
J += [A <tex> \to </tex>wX.v]
'''return''' closure (J)
</font>
|}
==== Алгоритм построения конечного автомата ====
Теперь обсудим алгоритм построения анализатора. Обозначим <tex>T</tex> множество состояний, <tex>E</tex> – множество переходов.
{| border="0"
|align="left" colspan="4"|
<font size=2>
E, T '''build'''()
E = {}
T = {closure ([S' <tex>\to</tex> .S])}
'''do'''
'''for''' каждого состояния I из T
'''for''' каждой ситуации [A <tex>\to</tex> w.Xv] из I
J = goto(I, X)
T += {J} <font color=green> // ко множеству состояний добавляется новое состояние </font>
E += (I <tex>\to</tex> J) <font color=green> // ко множеству ребер добавляется ребро, идущее из состояния I в состояние J. Этот переход осуществляется по символу X </font>
'''while''' E или T изменились
'''return''' E, T
</font>
|}
Поскольку для символа <tex>\$</tex> операция <tex>goto(I , \$)</tex> не определена , мы выполняем действие <tex>accept</tex>.
=== Пример LR(0)-разбора ===
Пример будет для строки <tex>(n_1+n_2)+n_3</tex>
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| Строка
!style="background-color:#EEE"| Стек
!style="background-color:#EEE"| <tex>s = top()</tex>
!style="background-color:#EEE"| <tex>a = w[ip]</tex>
!style="background-color:#EEE"| <tex>action[s,a]</tex>
!style="background-color:#EEE"| Комментарий
|-
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>(n_1+n_2)+n_3\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>(</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>shift\ 4</tex>
|style="background-color:#FFF;padding:2px 20px"| Перенос <tex>"("</tex>
|-
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>n_1+n_2)+n_3\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ (4</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>4</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>n_1</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>shift\ 3</tex>
|style="background-color:#FFF;padding:2px 20px"| Перенос <tex>"n_1"</tex>
|-
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>+n_2)+n_3\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ (4\ n_{1}3</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>3</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>reduce\ 3</tex>
|style="background-color:#FFF;padding:2px 20px"| Свертка: <tex>T \to \bf n</tex>
|-
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>+n_2)+n_3\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ (4\ T2</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>2</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>reduce\ 2</tex>
|style="background-color:#FFF;padding:2px 20px"| Свертка: <tex>E \to T</tex>
|-
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>+n_2)+n_3\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ (4\ E6</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>6</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>shift\ 5</tex>
|style="background-color:#FFF;padding:2px 20px"| Перенос <tex>"+"</tex>
|-
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>n_2)+n_3\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ (4\ E6\ +5</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>5</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>n_2</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>shift\ 3</tex>
|style="background-color:#FFF;padding:2px 20px"| Перенос <tex>"n_2"</tex>
|-
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>)+n_3\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ (4\ E6\ +5\ n_23</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>3</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>)</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>reduce\ 3 </tex>
|style="background-color:#FFF;padding:2px 20px"| Свертка: <tex>T \to \bf n</tex>
|-
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>)+n_3\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ (4\ E6\ +5\ T7</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>7</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>)</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>reduce\ 1 </tex>
|style="background-color:#FFF;padding:2px 20px"| Свертка: <tex>E \to E + T</tex>
|-
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>)+n_3\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ (4\ E6</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>6 </tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>)</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>shift\ 8</tex>
|style="background-color:#FFF;padding:2px 20px"| Перенос <tex>")"</tex>
|-
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>+n_3\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ (4\ E6\ )8</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>8 </tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>reduce\ 4</tex>
|style="background-color:#FFF;padding:2px 20px"| Свертка: <tex>T \to (E)</tex>
|-
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>+n_3\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ T2</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>2</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>reduce\ 2</tex>
|style="background-color:#FFF;padding:2px 20px"| Свертка: <tex>E \to T</tex>
|-
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>+n_3\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ E1</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>1</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>shift\ 5</tex>
|style="background-color:#FFF;padding:2px 20px"| Перенос <tex>"+"</tex>
|-
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>n_3\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ E1\ +5</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>5</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>n_3</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>shift\ 3</tex>
|style="background-color:#FFF;padding:2px 20px"| Перенос <tex>"n_3"</tex>
|-
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ E1\ +5\ n_33</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>3</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>reduce\ 3</tex>
|style="background-color:#FFF;padding:2px 20px"| Свертка: <tex>T \to \bf n</tex>
|-
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ E1\ +5\ T7</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>7</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>reduce\ 1</tex>
|style="background-color:#FFF;padding:2px 20px"| Свертка: <tex>E \to E + T</tex>
|-
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ E1</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>1</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>reduce\ 0</tex>
|style="background-color:#FFF;padding:2px 20px"| Допуск
|}
== См. также ==
* [[Предиктивный синтаксический анализ]]
== Источники информации ==
* Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс, 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]
[[Категория: Методы трансляции]]
[[Категория: Восходящий разбор]]
