http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&user=46.56.241.219&feedformat=atom
Викиконспекты - Вклад участника [ru]
2024-03-29T15:44:15Z
Вклад участника
MediaWiki 1.30.0
http://neerc.ifmo.ru/wiki/index.php?title=LR(0)-%D1%80%D0%B0%D0%B7%D0%B1%D0%BE%D1%80&diff=80788
LR(0)-разбор
2021-04-14T11:49:39Z
<p>46.56.241.219: Исправление очепятки</p>
<hr />
<div>LR(0)-разборщик {{---}} это частный случай [[LR(k)-грамматики#LR-разборщик|LR(k)-разборщикa]]. Заметим, что в данном случае <tex>k=0</tex>, то есть решение о своих действиях принимается только на основании содержимого стека, символы входной цепочки не учитываются.<br />
<br />
== Построение автомата и управляющей таблицы == <br />
=== Автомат ===<br />
Каждое состояние автомата будет состоять из LR(0)-ситуации.<br />
{{Определение<br />
|id=def_LR0_item) <br />
|definition=<br />
Пусть <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] </tex> назовем '''LR(0)-ситуацией''' (англ. ''LR(0)-item'').<br />
}}<br />
В начале работы стек пуст, и указатель входной цепочки находится перед ее первым символом. Этому состоянию соответствует ситуация <tex>[E_0 \to \cdot E]</tex>, где <tex>E_0</tex> {{---}} нетерминал, добавленный при пополнении грамматики, <tex>E</tex> {{---}} стартовый нетерминал. Назовем это состояние <tex>0</tex>. Входная цепочка может начинаться с любого терминального символа, с которого начинается правая часть любого правила с левой частью <tex>E</tex>. Построим соответствующий переход по следующей схеме:<br />
<br />
<tex>{[} A \to \alpha \cdot B \beta] \xrightarrow{\varepsilon} {[} B \to \cdot \gamma] </tex><br />
<br />
Теперь мы должны выяснить, что произойдет, если анализатор выполнит перенос. Предположим, что мы выполним перенос <tex>c</tex> или перенос <tex>B</tex>:<br />
<br />
<tex>{[} A \to \alpha \cdot c \beta] \xrightarrow{\text{c}} {[} A \to \alpha c \cdot \beta] </tex><br />
<br />
<tex>{[} A \to \alpha \cdot B \beta] \xrightarrow{\text{B}} {[} A \to \alpha B \cdot \beta] </tex><br />
<br />
Таким образом, мы определяем новые состояния, в которые автомат перейдет после переноса того или иного терминала или нетерминала. <br />
<br />
Можно заметить, что алгоритм LR-разбора похож на [[Алгоритм Эрли|алгоритм Эрли]].<br />
<br />
==== Базовые операции ====<br />
<br />
Заметим, что хранить в каждом состоянии только по одной ситуации не имеет смысла, поэтому пусть каждое состояние будет представлять множество ситуаций, а переходы {{---}} терминалы и нетерминалы. Для этого определим базовые операции <tex>closure (I)</tex> и <tex>goto (I, X)</tex>, где <tex>I</tex> {{---}} множество ситуаций, <tex>X</tex> {{---}} символ грамматики (терминал или нетерминал). <br />
<br />
* Операция <tex>closure</tex> добавляет ситуации к множеству ситуаций, у которых точка стоит слева от нетерминала. Добавляются те ситуации, которые получаются из правил, в левой части которых находится этот нетерминал.<br />
<br />
* Операция <tex>goto</tex> "переносит" точку после символа <tex>X</tex>. Это означает переход из одного состояния в другое под воздействием символа <tex>X</tex>.<br />
<br />
==== Построение автомата ==== <br />
Теперь обсудим алгоритм построения конечного автомата. Обозначим <tex>T</tex> множество состояний, <tex>E</tex> {{---}} множество переходов.<br />
# Изначальное состояние содержит одно правило: <tex>E_0 \to E</tex>.<br />
# Для текущего состояния делаем операцию <tex>closure</tex>.<br />
# По всем возможный символам для каждой ситуации добавляем переходы, используя операцию <tex>goto</tex>.<br />
# Если множество <tex>T</tex> или <tex>E</tex> во втором или третьем пункте изменилось, возвращаемся ко второму шагу.<br />
<br />
=== Управляющая таблица ===<br />
После построения автомата можно перейти к построению управляющей таблицы. <br />
<br />
Обращение к таблице происходит следующим образом <tex>\mathtt{T[state, token]}</tex>, где <br />
*<tex>\mathtt{state}</tex> {{---}} состояние автомата, <br />
*<tex>\mathtt{token}</tex> {{---}} входной символ; <br />
<br />
В соответствии со [[LR(k)-грамматики#Управляющая программа анализатора |структурой]] управляющей таблицы будем действовать следующим образом:<br />
<br />
<ol><br />
<li>Для каждого ребра <tex>I \xrightarrow{\text{X}} J </tex> (из состояния <tex>I</tex> в состояние <tex>J</tex> по <tex>X</tex>) мы поместим в позицию <tex>T[I,X]</tex><br />
*<tex>s(J)</tex> (сокр. от ''shift'') , если <tex>X</tex> {{---}} терминал,<br />
*<tex>J</tex>, если <tex>X</tex> {{---}} нетерминал.</li><br />
<li>Для состояния <tex>I</tex>, содержащего ситуацию <tex>[A\to w \cdot]</tex> в позицию <tex>T[I, Y]</tex> для каждого терминала <tex>Y</tex><br />
* Поместим <tex>r(n)</tex> (сокр. от ''reduce''), где <tex>n</tex> {{---}} это номер правила в изначальной грамматике.</li><br />
* Запись <tex>r(0)</tex> означает допуск.<br />
<li>Пустая ячейка означает ошибочную ситуацию.</li><br />
</ol><br />
<br />
== Пример ==<br />
Для иллюстрации алгоритма LR(0)-разборщика мы будем использовать грамматику:<br />
<br />
<tex><br />
E \to E + T \\<br />
E \to T \\<br />
T \to {\bf n} \\<br />
T \to (E) \\<br />
</tex><br />
<br />
Обратим внимание, что данная грамматика является [[Устранение левой рекурсии|леворекурсивной]], поэтому нисходящий разборщик не сможет осуществить разбор слова из этой грамматики.<br />
=== Пополнение грамматики===<br />
<br />
Для начала переходим к ''пополненной грамматике'':<br />
<br />
<tex><br />
E_0 \to E \\<br />
E \to E + T \\<br />
E \to T \\<br />
T \to {\bf n} \\<br />
T \to (E) \\<br />
</tex><br />
<br />
=== Построение автомата ===<br />
<tex>0</tex> состоянию будет соответствует ситуация <tex>[E_0 \to \cdot E]</tex>. Добавляем остальные состояния и получаем следующий [[Недетерминированные конечные автоматы|НКА]]:<br />
<br />
[[Файл:eps-dfa.png|600px]]<br />
<br />
На картинке в двойной рамке обозначены терминальные состояния {{---}} это такие состояния, из которых можно производить свертку по правилу грамматики, а из остальных возможен только перенос. Этот термин не используется в алгоритме, а нужен только для лучшего визуального восприятия. <br />
<br />
Теперь в одно состояние перемещаем все ситуации, в которые идут <tex>\varepsilon</tex>-переходы. Получаем [[Детерминированные конечные автоматы|ДКА]]:<br />
<br />
[[Файл:LRk_dfa.png|600px]]<br />
<br />
=== Заполнение управляющей таблицы ===<br />
<br />
Пронумеруем правила для выполнения ''свертки'':<br />
<br />
<tex><br />
(0)\ E_0 \to E\\<br />
(1)\ E \to E + T\\<br />
(2)\ E \to T\\<br />
(3)\ T \to {\bf n} \\<br />
(4)\ T \to (E) \\<br />
</tex><br />
<br />
Управляющая таблица будет выглядеть так:<br />
<br />
{| style="background-color:#CCC;margin:0.5px"<br />
!style="background-color:#EEE"| <br />
!style="background-color:#EEE"| <tex>E</tex><br />
!style="background-color:#EEE"| <tex>T</tex><br />
!style="background-color:#EEE"| <tex>n</tex><br />
!style="background-color:#EEE"| <tex>+</tex><br />
!style="background-color:#EEE"| <tex>(</tex><br />
!style="background-color:#EEE"| <tex>)</tex><br />
!style="background-color:#EEE"| <tex>\$</tex><br />
|-<br />
|style="background-color:#EEE;padding:2px 30px"| <tex>0</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>1</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>2</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>s(3)</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <br />
|style="background-color:#FFF;padding:2px 20px"| <tex>s(4)</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <br />
|style="background-color:#FFF;padding:2px 20px"| <br />
|-<br />
|style="background-color:#EEE;padding:2px 30px"| <tex>1</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <br />
|style="background-color:#FFF;padding:2px 20px"| <br />
|style="background-color:#FFF;padding:2px 20px"| <br />
|style="background-color:#FFF;padding:2px 20px"| <tex>s(5)</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <br />
|style="background-color:#FFF;padding:2px 20px"| <br />
|style="background-color:#FFF;padding:2px 20px"| <tex>r(0)</tex><br />
|-<br />
|style="background-color:#EEE;padding:2px 30px"| <tex>2</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <br />
|style="background-color:#FFF;padding:2px 20px"| <br />
|style="background-color:#FFF;padding:2px 20px"| <br />
|style="background-color:#FFF;padding:2px 20px"| <tex>r(2)</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <br />
|style="background-color:#FFF;padding:2px 20px"| <tex>r(2)</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>r(2)</tex><br />
|-<br />
|style="background-color:#EEE;padding:2px 30px"| <tex>3</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <br />
|style="background-color:#FFF;padding:2px 20px"| <br />
|style="background-color:#FFF;padding:2px 20px"| <br />
|style="background-color:#FFF;padding:2px 20px"| <tex>r(3)</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <br />
|style="background-color:#FFF;padding:2px 20px"| <tex>r(3)</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>r(3)</tex><br />
|-<br />
|style="background-color:#EEE;padding:2px 30px"| <tex>4</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>6</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>2</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>s(3)</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <br />
|style="background-color:#FFF;padding:2px 20px"| <tex>s(4)</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <br />
|style="background-color:#FFF;padding:2px 20px"| <br />
|-<br />
|style="background-color:#EEE;padding:2px 30px"| <tex>5</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <br />
|style="background-color:#FFF;padding:2px 20px"| <tex>7</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>s(3)</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <br />
|style="background-color:#FFF;padding:2px 20px"| <tex>s(4)</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <br />
|style="background-color:#FFF;padding:2px 20px"| <br />
|-<br />
|style="background-color:#EEE;padding:2px 30px"| <tex>6</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <br />
|style="background-color:#FFF;padding:2px 20px"| <br />
|style="background-color:#FFF;padding:2px 20px"| <br />
|style="background-color:#FFF;padding:2px 20px"| <tex>s(5)</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <br />
|style="background-color:#FFF;padding:2px 20px"| <tex>s(8)</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <br />
|-<br />
|style="background-color:#EEE;padding:2px 30px"| <tex>7</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <br />
|style="background-color:#FFF;padding:2px 20px"| <br />
|style="background-color:#FFF;padding:2px 20px"| <br />
|style="background-color:#FFF;padding:2px 20px"| <tex>r(1)</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <br />
|style="background-color:#FFF;padding:2px 20px"| <tex>r(1)</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>r(1)</tex><br />
|-<br />
|style="background-color:#EEE;padding:2px 30px"| <tex>8</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <br />
|style="background-color:#FFF;padding:2px 20px"| <br />
|style="background-color:#FFF;padding:2px 20px"| <br />
|style="background-color:#FFF;padding:2px 20px"| <tex>r(4)</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <br />
|style="background-color:#FFF;padding:2px 20px"| <tex>r(4)</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>r(4)</tex><br />
|}<br />
<br />
=== LR(0)-разбора конкретной строки===<br />
<br />
Пример будет для строки <tex>(n_1+n_2)+n_3</tex><br />
{| style="background-color:#CCC;margin:0.5px"<br />
!style="background-color:#EEE"| Строка<br />
!style="background-color:#EEE"| Стек<br />
!style="background-color:#EEE"| <tex>curState</tex><br />
!style="background-color:#EEE"| <tex>curToken</tex><br />
!style="background-color:#EEE"| <tex>T[curState,curToken]</tex><br />
!style="background-color:#EEE"| Комментарий<br />
|-<br />
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>(n_1+n_2)+n_3\$</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>(</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>shift\ 4</tex><br />
|style="background-color:#FFF;padding:2px 20px"| Перенос <tex>"("</tex>. Переход в <tex>4</tex> состояние.<br />
|-<br />
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>n_1+n_2)+n_3\$</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ (4</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>4</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>n_1</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>shift\ 3</tex><br />
|style="background-color:#FFF;padding:2px 20px"| Перенос <tex>"n_1"</tex>. Переход в <tex>3</tex> состояние. <br />
|-<br />
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>+n_2)+n_3\$</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ (4\ n_{1}3</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>3</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>reduce\ 3</tex><br />
|style="background-color:#FFF;padding:2px 20px"| Свертка: <tex>T \to \bf n</tex>. Удаление из стека <tex>n_{1}3</tex>. Переход в <tex>4</tex> состояние. Добавление в стек <tex>T2</tex>. Переход в <tex>2</tex> состояние. <br />
|-<br />
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>+n_2)+n_3\$</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ (4\ T2</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>2</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>reduce\ 2</tex><br />
|style="background-color:#FFF;padding:2px 20px"| Свертка: <tex>E \to T</tex>. Удаление из стека <tex>T2</tex>. Переход в <tex>4</tex> состояние. Добавление в стек <tex>E6</tex>. Переход в <tex>6</tex> состояние. <br />
|-<br />
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>+n_2)+n_3\$</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ (4\ E6</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>6</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>shift\ 5</tex><br />
|style="background-color:#FFF;padding:2px 20px"| Перенос <tex>"+"</tex>. Переход в <tex>5</tex> состояние. <br />
|-<br />
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>n_2)+n_3\$</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ (4\ E6\ +5</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>5</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>n_2</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>shift\ 3</tex><br />
|style="background-color:#FFF;padding:2px 20px"| Перенос <tex>"n_2"</tex>. Переход в <tex>3</tex> состояние. <br />
|-<br />
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>)+n_3\$</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ (4\ E6\ +5\ n_23</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>3</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>)</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>reduce\ 3 </tex><br />
|style="background-color:#FFF;padding:2px 20px"| Свертка: <tex>T \to \bf n</tex>. Удаление из стека <tex>n_{2}3</tex>. Переход в <tex>5</tex> состояние. Добавление в стек <tex>T7</tex>. Переход в <tex>7</tex> состояние. <br />
|-<br />
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>)+n_3\$</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ (4\ E6\ +5\ T7</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>7</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>)</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>reduce\ 1 </tex><br />
|style="background-color:#FFF;padding:2px 20px"| Свертка: <tex>E \to E + T</tex>. Удаление из стека <tex>E6\ +5\ T7</tex>. Переход в <tex>4</tex> состояние. Добавление в стек <tex>E6</tex>. Переход в <tex>6</tex> состояние.<br />
|-<br />
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>)+n_3\$</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ (4\ E6</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>6 </tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>)</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>shift\ 8</tex><br />
|style="background-color:#FFF;padding:2px 20px"| Перенос <tex>")"</tex>. Переход в <tex>8</tex> состояние. <br />
|-<br />
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>+n_3\$</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ (4\ E6\ )8</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>8 </tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>reduce\ 4</tex><br />
|style="background-color:#FFF;padding:2px 20px"| Свертка: <tex>T \to (E)</tex>. Удаление из стека <tex>(4\ E6\ )8</tex>. Переход в <tex>0</tex> состояние. Добавление в стек <tex>T2</tex>. Переход в <tex>2</tex> состояние.<br />
|-<br />
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>+n_3\$</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ T2</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>2</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>reduce\ 2</tex><br />
|style="background-color:#FFF;padding:2px 20px"| Свертка: <tex>E \to T</tex>. Удаление из стека <tex>T2</tex>. Переход в <tex>0</tex> состояние. Добавление в стек <tex>E1</tex>. Переход в <tex>1</tex> состояние.<br />
|-<br />
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>+n_3\$</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ E1</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>1</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>shift\ 5</tex><br />
|style="background-color:#FFF;padding:2px 20px"| Перенос <tex>"+"</tex>. Переход в <tex>5</tex> состояние.<br />
|-<br />
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>n_3\$</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ E1\ +5</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>5</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>n_3</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>shift\ 3</tex><br />
|style="background-color:#FFF;padding:2px 20px"| Перенос <tex>"n_3"</tex>. Переход в <tex>3</tex> состояние.<br />
|-<br />
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>\$</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ E1\ +5\ n_33</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>3</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>\$</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>reduce\ 3</tex><br />
|style="background-color:#FFF;padding:2px 20px"| Свертка: <tex>T \to \bf n</tex>. Удаление из стека <tex>n_33</tex>. Переход в <tex>5</tex> состояние. Добавление в стек <tex>T7</tex>. Переход в <tex>7</tex> состояние.<br />
|-<br />
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>\$</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ E1\ +5\ T7</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>7</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>\$</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>reduce\ 1</tex><br />
|style="background-color:#FFF;padding:2px 20px"| Свертка: <tex>E \to E + T</tex>. Удаление из стека <tex>E1\ +5\ T7</tex>. Переход в <tex>0</tex> состояние. Добавление в стек <tex>E1</tex>. Переход в <tex>1</tex> состояние.<br />
|-<br />
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>\$</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>0\ E1</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>1</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>\$</tex><br />
|style="background-color:#FFF;padding:2px 20px"| <tex>reduce\ 0</tex><br />
|style="background-color:#FFF;padding:2px 20px"| Так как свертка по нулевому правилу {{---}} осуществляем допуск.<br />
|}<br />
<br />
== См. также ==<br />
* [[Предиктивный синтаксический анализ]]<br />
<br />
== Источники информации ==<br />
* Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс, 2003. Стр. 301-326.<br />
* [http://ict.edu.ru/ft/005128//ch7.pdf Терехов Ан.А., Вояковская Н., Булычев Д., Москаль А. Разработка компиляторов на платформе .NET {{---}} Восходящие анализаторы]<br />
* [http://window.edu.ru/resource/974/69974/files/lang_trans.pdf Б.К.Мартыненко. Языки и трансляции. Стр. 198-223]<br />
* [http://gas-teach.narod.ru/au/tfl/tfl13.pdf Лекции по теории формальных языков, LR(0)-, SLR(1)-, LR(1)- и LALR(1)-анализ ]<br />
<br />
[[Категория: Методы трансляции]]<br />
[[Категория: Восходящий разбор]]</div>
46.56.241.219