LR(0)-разбор — различия между версиями
Margarita (обсуждение | вклад) (→Алгоритм построения конечного автомата) |
м (rollbackEdits.php mass rollback) |
||
(не показано 29 промежуточных версий 4 участников) | |||
Строка 1: | Строка 1: | ||
− | LR(0)-разборщик это частный случай [[LR(k)-грамматики#LR-разборщик|LR(k)-разборщикa]] | + | LR(0)-разборщик {{---}} это частный случай [[LR(k)-грамматики#LR-разборщик|LR(k)-разборщикa]]. Заметим, что в данном случае <tex>k=0</tex>, то есть решение о своих действиях принимается только на основании содержимого стека, символы входной цепочки не учитываются. |
== Построение автомата и управляющей таблицы == | == Построение автомата и управляющей таблицы == | ||
− | |||
− | |||
=== Автомат === | === Автомат === | ||
Каждое состояние автомата будет состоять из LR(0)-ситуации. | Каждое состояние автомата будет состоять из LR(0)-ситуации. | ||
Строка 9: | Строка 7: | ||
|id=def_LR0_item) | |id=def_LR0_item) | ||
|definition= | |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] </tex> назовем '''LR(0)-ситуацией''' (англ. ''LR(0)-item'') | + | Пусть <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''). |
}} | }} | ||
− | В начале работы стек пуст, и указатель входной цепочки находится перед ее первым символом. Этому состоянию соответствует ситуация <tex>[E_0 \to \cdot E]</tex>, где <tex>E_0</tex> {{---}} нетерминал, добавленный при пополнении грамматики, <tex>E</tex> {{---}} стартовый нетерминал. | + | В начале работы стек пуст, и указатель входной цепочки находится перед ее первым символом. Этому состоянию соответствует ситуация <tex>[E_0 \to \cdot E]</tex>, где <tex>E_0</tex> {{---}} нетерминал, добавленный при пополнении грамматики, <tex>E</tex> {{---}} стартовый нетерминал. Назовем это состояние <tex>0</tex>. Входная цепочка может начинаться с любого терминального символа, с которого начинается правая часть любого правила с левой частью <tex>E</tex>. Построим соответствующий переход по следующей схеме: |
<tex>{[} A \to \alpha \cdot B \beta] \xrightarrow{\varepsilon} {[} B \to \cdot \gamma] </tex> | <tex>{[} A \to \alpha \cdot B \beta] \xrightarrow{\varepsilon} {[} B \to \cdot \gamma] </tex> | ||
Строка 21: | Строка 19: | ||
<tex>{[} A \to \alpha \cdot B \beta] \xrightarrow{\text{B}} {[} A \to \alpha B \cdot \beta] </tex> | <tex>{[} A \to \alpha \cdot B \beta] \xrightarrow{\text{B}} {[} A \to \alpha B \cdot \beta] </tex> | ||
− | Таким образом, мы определяем новые состояния, в | + | Таким образом, мы определяем новые состояния, в которые автомат перейдет после переноса того или иного терминала или нетерминала. |
− | + | Можно заметить, что алгоритм LR-разбора похож на [[Алгоритм Эрли|алгоритм Эрли]]. | |
− | + | ==== Базовые операции ==== | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
+ | Заметим, что хранить в каждом состоянии только по одной ситуации не имеет смысла, поэтому пусть каждое состояние будет представлять множество ситуаций, а переходы {{---}} терминалы и нетерминалы. Для этого определим базовые операции <tex>closure (I)</tex> и <tex>goto (I, X)</tex>, где <tex>I</tex> {{---}} множество ситуаций, <tex>X</tex> {{---}} символ грамматики (терминал или нетерминал). | ||
− | Операция <tex> | + | * Операция <tex>closure</tex> добавляет ситуации к множеству ситуаций, у которых точка стоит слева от нетерминала. Добавляются те ситуации, которые получаются из правил, в левой части которых находится этот нетерминал. |
− | + | * Операция <tex>goto</tex> "переносит" точку после символа <tex>X</tex>. Это означает переход из одного состояния в другое под воздействием символа <tex>X</tex>. | |
− | |||
− | < | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | Теперь обсудим алгоритм построения конечного автомата. Обозначим <tex>T</tex> множество состояний, <tex>E</tex> | + | ==== Построение автомата ==== |
+ | Теперь обсудим алгоритм построения конечного автомата. Обозначим <tex>T</tex> множество состояний, <tex>E</tex> {{---}} множество переходов. | ||
+ | # Изначальное состояние содержит одно правило: <tex>E_0 \to E</tex>. | ||
+ | # Для текущего состояния делаем операцию <tex>closure</tex>. | ||
+ | # По всем возможный символам для каждой ситуации добавляем переходы, используя операцию <tex>goto</tex>. | ||
+ | # Если множество <tex>T</tex> или <tex>E</tex> во втором или третьем пункте изменилось, возвращаемся ко второму шагу. | ||
− | + | === Управляющая таблица === | |
− | + | После построения автомата можно перейти к построению управляющей таблицы. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | Обращение к таблице происходит следующим образом <tex>\mathtt{T[state, token]}</tex>, где | |
− | + | *<tex>\mathtt{state}</tex> {{---}} состояние автомата, | |
− | + | *<tex>\mathtt{token}</tex> {{---}} входной символ; | |
− | + | В соответствии со [[LR(k)-грамматики#Управляющая программа анализатора |структурой]] управляющей таблицы будем действовать следующим образом: | |
− | |||
− | + | <ol> | |
− | *<tex> | + | <li>Для каждого ребра <tex>I \xrightarrow{\text{X}} J </tex> (из состояния <tex>I</tex> в состояние <tex>J</tex> по <tex>X</tex>) мы поместим в позицию <tex>T[I,X]</tex> |
− | *<tex> | + | *<tex>s(J)</tex> (сокр. от ''shift'') , если <tex>X</tex> {{---}} терминал, |
− | + | *<tex>J</tex>, если <tex>X</tex> {{---}} нетерминал.</li> | |
− | + | <li>Для состояния <tex>I</tex>, содержащего ситуацию <tex>[A\to w \cdot]</tex> в позицию <tex>T[I, Y]</tex> для каждого терминала <tex>Y</tex> | |
− | + | * Поместим <tex>r(n)</tex> (сокр. от ''reduce''), где <tex>n</tex> {{---}} это номер правила в изначальной грамматике.</li> | |
− | + | * Запись <tex>r(0)</tex> означает допуск. | |
− | + | <li>Пустая ячейка означает ошибочную ситуацию.</li> | |
− | + | </ol> | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | == | + | == Пример == |
Для иллюстрации алгоритма LR(0)-разборщика мы будем использовать грамматику: | Для иллюстрации алгоритма LR(0)-разборщика мы будем использовать грамматику: | ||
Строка 102: | Строка 66: | ||
T \to (E) \\ | T \to (E) \\ | ||
</tex> | </tex> | ||
+ | |||
+ | Обратим внимание, что данная грамматика является [[Устранение левой рекурсии|леворекурсивной]], поэтому нисходящий разборщик не сможет осуществить разбор слова из этой грамматики. | ||
=== Пополнение грамматики=== | === Пополнение грамматики=== | ||
− | Для начала переходим к '' | + | Для начала переходим к ''пополненной грамматике'': |
<tex> | <tex> | ||
Строка 115: | Строка 81: | ||
=== Построение автомата === | === Построение автомата === | ||
− | + | <tex>0</tex> состоянию будет соответствует ситуация <tex>[E_0 \to \cdot E]</tex>. Добавляем остальные состояния и получаем следующий [[Недетерминированные конечные автоматы|НКА]]: | |
− | |||
− | + | [[Файл:eps-dfa.png|600px]] | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | На картинке в двойной рамке обозначены терминальные состояния {{---}} это такие состояния, из которых можно производить свертку по правилу грамматики, а из остальных возможен только перенос. Этот термин не используется в алгоритме, а нужен только для лучшего визуального восприятия. | |
− | + | Теперь в одно состояние перемещаем все ситуации, в которые идут <tex>\varepsilon</tex>-переходы. Получаем [[Детерминированные конечные автоматы|ДКА]]: | |
[[Файл:LRk_dfa.png|600px]] | [[Файл:LRk_dfa.png|600px]] | ||
− | === | + | === Заполнение управляющей таблицы === |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | Пронумеруем правила для выполнения ''свертки'': | |
<tex> | <tex> | ||
Строка 170: | Строка 118: | ||
|style="background-color:#FFF;padding:2px 20px"| <tex>1</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>2</tex> | ||
− | |style="background-color:#FFF;padding:2px 20px"| <tex> | + | |style="background-color:#FFF;padding:2px 20px"| <tex>s(3)</tex> |
|style="background-color:#FFF;padding:2px 20px"| | |style="background-color:#FFF;padding:2px 20px"| | ||
− | |style="background-color:#FFF;padding:2px 20px"| <tex> | + | |style="background-color:#FFF;padding:2px 20px"| <tex>s(4)</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"| | ||
Строка 180: | Строка 128: | ||
|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"| | ||
− | |style="background-color:#FFF;padding:2px 20px"| <tex> | + | |style="background-color:#FFF;padding:2px 20px"| <tex>s(5)</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"| | ||
Строка 206: | Строка 154: | ||
|style="background-color:#FFF;padding:2px 20px"| <tex>6</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>2</tex> | ||
− | |style="background-color:#FFF;padding:2px 20px"| <tex> | + | |style="background-color:#FFF;padding:2px 20px"| <tex>s(3)</tex> |
|style="background-color:#FFF;padding:2px 20px"| | |style="background-color:#FFF;padding:2px 20px"| | ||
− | |style="background-color:#FFF;padding:2px 20px"| <tex> | + | |style="background-color:#FFF;padding:2px 20px"| <tex>s(4)</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"| | ||
Строка 215: | Строка 163: | ||
|style="background-color:#FFF;padding:2px 20px"| | |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>7</tex> | ||
− | |style="background-color:#FFF;padding:2px 20px"| <tex> | + | |style="background-color:#FFF;padding:2px 20px"| <tex>s(3)</tex> |
|style="background-color:#FFF;padding:2px 20px"| | |style="background-color:#FFF;padding:2px 20px"| | ||
− | |style="background-color:#FFF;padding:2px 20px"| <tex> | + | |style="background-color:#FFF;padding:2px 20px"| <tex>s(4)</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"| | ||
Строка 225: | Строка 173: | ||
|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"| | ||
− | |style="background-color:#FFF;padding:2px 20px"| <tex> | + | |style="background-color:#FFF;padding:2px 20px"| <tex>s(5)</tex> |
|style="background-color:#FFF;padding:2px 20px"| | |style="background-color:#FFF;padding:2px 20px"| | ||
− | |style="background-color:#FFF;padding:2px 20px"| <tex> | + | |style="background-color:#FFF;padding:2px 20px"| <tex>s(8)</tex> |
|style="background-color:#FFF;padding:2px 20px"| | |style="background-color:#FFF;padding:2px 20px"| | ||
|- | |- | ||
Строка 249: | Строка 197: | ||
|} | |} | ||
− | == | + | === LR(0)-разбора конкретной строки=== |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
Пример будет для строки <tex>(n_1+n_2)+n_3</tex> | Пример будет для строки <tex>(n_1+n_2)+n_3</tex> | ||
Строка 310: | Строка 203: | ||
!style="background-color:#EEE"| Строка | !style="background-color:#EEE"| Строка | ||
!style="background-color:#EEE"| Стек | !style="background-color:#EEE"| Стек | ||
− | !style="background-color:#EEE"| <tex> | + | !style="background-color:#EEE"| <tex>curState</tex> |
− | !style="background-color:#EEE"| <tex> | + | !style="background-color:#EEE"| <tex>curToken</tex> |
− | !style="background-color:#EEE"| <tex> | + | !style="background-color:#EEE"| <tex>T[curState,curToken]</tex> |
!style="background-color:#EEE"| Комментарий | !style="background-color:#EEE"| Комментарий | ||
|- | |- | ||
Строка 320: | Строка 213: | ||
|style="background-color:#FFF;padding:2px 20px"| <tex>(</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>shift\ 4</tex> | ||
− | |style="background-color:#FFF;padding:2px 20px"| Перенос <tex>"("</tex> | + | |style="background-color:#FFF;padding:2px 20px"| Перенос <tex>"("</tex>. Переход в <tex>4</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;text-align: right;"| <tex>n_1+n_2)+n_3\$</tex> | ||
Строка 327: | Строка 220: | ||
|style="background-color:#FFF;padding:2px 20px"| <tex>n_1</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>shift\ 3</tex> | ||
− | |style="background-color:#FFF;padding:2px 20px"| Перенос <tex>"n_1"</tex> | + | |style="background-color:#FFF;padding:2px 20px"| Перенос <tex>"n_1"</tex>. Переход в <tex>3</tex> состояние. |
|- | |- | ||
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>+n_2)+n_3\$</tex> | |style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>+n_2)+n_3\$</tex> | ||
Строка 334: | Строка 227: | ||
|style="background-color:#FFF;padding:2px 20px"| <tex>+</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>reduce\ 3</tex> | ||
− | |style="background-color:#FFF;padding:2px 20px"| Свертка: <tex>T \to \bf n</tex> | + | |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> состояние. |
|- | |- | ||
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>+n_2)+n_3\$</tex> | |style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>+n_2)+n_3\$</tex> | ||
Строка 341: | Строка 234: | ||
|style="background-color:#FFF;padding:2px 20px"| <tex>+</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>reduce\ 2</tex> | ||
− | |style="background-color:#FFF;padding:2px 20px"| Свертка: <tex>E \to T</tex> | + | |style="background-color:#FFF;padding:2px 20px"| Свертка: <tex>E \to T</tex>. Удаление из стека <tex>T2</tex>. Переход в <tex>4</tex> состояние. Добавление в стек <tex>E6</tex>. Переход в <tex>6</tex> состояние. |
|- | |- | ||
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>+n_2)+n_3\$</tex> | |style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>+n_2)+n_3\$</tex> | ||
Строка 348: | Строка 241: | ||
|style="background-color:#FFF;padding:2px 20px"| <tex>+</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>shift\ 5</tex> | ||
− | |style="background-color:#FFF;padding:2px 20px"| Перенос <tex>"+"</tex> | + | |style="background-color:#FFF;padding:2px 20px"| Перенос <tex>"+"</tex>. Переход в <tex>5</tex> состояние. |
|- | |- | ||
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>n_2)+n_3\$</tex> | |style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>n_2)+n_3\$</tex> | ||
Строка 355: | Строка 248: | ||
|style="background-color:#FFF;padding:2px 20px"| <tex>n_2</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>shift\ 3</tex> | ||
− | |style="background-color:#FFF;padding:2px 20px"| Перенос <tex>"n_2"</tex> | + | |style="background-color:#FFF;padding:2px 20px"| Перенос <tex>"n_2"</tex>. Переход в <tex>3</tex> состояние. |
|- | |- | ||
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>)+n_3\$</tex> | |style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>)+n_3\$</tex> | ||
Строка 362: | Строка 255: | ||
|style="background-color:#FFF;padding:2px 20px"| <tex>)</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>reduce\ 3 </tex> | ||
− | |style="background-color:#FFF;padding:2px 20px"| Свертка: <tex>T \to \bf n</tex> | + | |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> состояние. |
|- | |- | ||
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>)+n_3\$</tex> | |style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>)+n_3\$</tex> | ||
Строка 369: | Строка 262: | ||
|style="background-color:#FFF;padding:2px 20px"| <tex>)</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>reduce\ 1 </tex> | ||
− | |style="background-color:#FFF;padding:2px 20px"| Свертка: <tex>E \to E + T</tex> | + | |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> состояние. |
|- | |- | ||
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>)+n_3\$</tex> | |style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>)+n_3\$</tex> | ||
Строка 376: | Строка 269: | ||
|style="background-color:#FFF;padding:2px 20px"| <tex>)</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>shift\ 8</tex> | ||
− | |style="background-color:#FFF;padding:2px 20px"| Перенос <tex>")"</tex> | + | |style="background-color:#FFF;padding:2px 20px"| Перенос <tex>")"</tex>. Переход в <tex>8</tex> состояние. |
|- | |- | ||
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>+n_3\$</tex> | |style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>+n_3\$</tex> | ||
Строка 383: | Строка 276: | ||
|style="background-color:#FFF;padding:2px 20px"| <tex>+</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>reduce\ 4</tex> | ||
− | |style="background-color:#FFF;padding:2px 20px"| Свертка: <tex>T \to (E)</tex> | + | |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> состояние. |
|- | |- | ||
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>+n_3\$</tex> | |style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>+n_3\$</tex> | ||
Строка 390: | Строка 283: | ||
|style="background-color:#FFF;padding:2px 20px"| <tex>+</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>reduce\ 2</tex> | ||
− | |style="background-color:#FFF;padding:2px 20px"| Свертка: <tex>E \to T</tex> | + | |style="background-color:#FFF;padding:2px 20px"| Свертка: <tex>E \to T</tex>. Удаление из стека <tex>T2</tex>. Переход в <tex>0</tex> состояние. Добавление в стек <tex>E1</tex>. Переход в <tex>1</tex> состояние. |
|- | |- | ||
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>+n_3\$</tex> | |style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>+n_3\$</tex> | ||
Строка 397: | Строка 290: | ||
|style="background-color:#FFF;padding:2px 20px"| <tex>+</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>shift\ 5</tex> | ||
− | |style="background-color:#FFF;padding:2px 20px"| Перенос <tex>"+"</tex> | + | |style="background-color:#FFF;padding:2px 20px"| Перенос <tex>"+"</tex>. Переход в <tex>5</tex> состояние. |
|- | |- | ||
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>n_3\$</tex> | |style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>n_3\$</tex> | ||
Строка 404: | Строка 297: | ||
|style="background-color:#FFF;padding:2px 20px"| <tex>n_3</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>shift\ 3</tex> | ||
− | |style="background-color:#FFF;padding:2px 20px"| Перенос <tex>"n_3"</tex> | + | |style="background-color:#FFF;padding:2px 20px"| Перенос <tex>"n_3"</tex>. Переход в <tex>3</tex> состояние. |
|- | |- | ||
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>\$</tex> | |style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>\$</tex> | ||
Строка 411: | Строка 304: | ||
|style="background-color:#FFF;padding:2px 20px"| <tex>\$</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>reduce\ 3</tex> | ||
− | |style="background-color:#FFF;padding:2px 20px"| Свертка: <tex>T \to \bf n</tex> | + | |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> состояние. |
|- | |- | ||
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>\$</tex> | |style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>\$</tex> | ||
Строка 418: | Строка 311: | ||
|style="background-color:#FFF;padding:2px 20px"| <tex>\$</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>reduce\ 1</tex> | ||
− | |style="background-color:#FFF;padding:2px 20px"| Свертка: <tex>E \to E + T</tex> | + | |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> состояние. |
|- | |- | ||
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>\$</tex> | |style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>\$</tex> | ||
Строка 425: | Строка 318: | ||
|style="background-color:#FFF;padding:2px 20px"| <tex>\$</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"| <tex>reduce\ 0</tex> | ||
− | |style="background-color:#FFF;padding:2px 20px"| | + | |style="background-color:#FFF;padding:2px 20px"| Так как свертка по нулевому правилу {{---}} осуществляем допуск. |
|} | |} | ||
Строка 432: | Строка 325: | ||
== Источники информации == | == Источники информации == | ||
− | * Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс, 2003. Стр. 301 - 326. | + | * Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс, 2003. Стр. 301-326. |
− | * [http://ict.edu.ru/ft/005128//ch7.pdf Терехов Ан.А., Вояковская Н., Булычев Д., Москаль А. | + | * [http://ict.edu.ru/ft/005128//ch7.pdf Терехов Ан.А., Вояковская Н., Булычев Д., Москаль А. Разработка компиляторов на платформе .NET {{---}} Восходящие анализаторы] |
− | * [http://window.edu.ru/resource/974/69974/files/lang_trans.pdf Б.К.Мартыненко. Языки и трансляции. Стр. 198 - 223] | + | * [http://window.edu.ru/resource/974/69974/files/lang_trans.pdf Б.К.Мартыненко. Языки и трансляции. Стр. 198-223] |
* [http://gas-teach.narod.ru/au/tfl/tfl13.pdf Лекции по теории формальных языков, LR(0)-, SLR(1)-, LR(1)- и LALR(1)-анализ ] | * [http://gas-teach.narod.ru/au/tfl/tfl13.pdf Лекции по теории формальных языков, LR(0)-, SLR(1)-, LR(1)- и LALR(1)-анализ ] | ||
[[Категория: Методы трансляции]] | [[Категория: Методы трансляции]] | ||
[[Категория: Восходящий разбор]] | [[Категория: Восходящий разбор]] |
Текущая версия на 19:33, 4 сентября 2022
LR(0)-разборщик — это частный случай LR(k)-разборщикa. Заметим, что в данном случае , то есть решение о своих действиях принимается только на основании содержимого стека, символы входной цепочки не учитываются.
Построение автомата и управляющей таблицы
Автомат
Каждое состояние автомата будет состоять из LR(0)-ситуации.
Определение: |
Пусть | — КС-грамматика и . Композицию назовем LR(0)-ситуацией (англ. LR(0)-item).
В начале работы стек пуст, и указатель входной цепочки находится перед ее первым символом. Этому состоянию соответствует ситуация
, где — нетерминал, добавленный при пополнении грамматики, — стартовый нетерминал. Назовем это состояние . Входная цепочка может начинаться с любого терминального символа, с которого начинается правая часть любого правила с левой частью . Построим соответствующий переход по следующей схеме:
Теперь мы должны выяснить, что произойдет, если анализатор выполнит перенос. Предположим, что мы выполним перенос
или перенос :
Таким образом, мы определяем новые состояния, в которые автомат перейдет после переноса того или иного терминала или нетерминала.
Можно заметить, что алгоритм LR-разбора похож на алгоритм Эрли.
Базовые операции
Заметим, что хранить в каждом состоянии только по одной ситуации не имеет смысла, поэтому пусть каждое состояние будет представлять множество ситуаций, а переходы — терминалы и нетерминалы. Для этого определим базовые операции
и , где — множество ситуаций, — символ грамматики (терминал или нетерминал).- Операция добавляет ситуации к множеству ситуаций, у которых точка стоит слева от нетерминала. Добавляются те ситуации, которые получаются из правил, в левой части которых находится этот нетерминал.
- Операция "переносит" точку после символа . Это означает переход из одного состояния в другое под воздействием символа .
Построение автомата
Теперь обсудим алгоритм построения конечного автомата. Обозначим
множество состояний, — множество переходов.- Изначальное состояние содержит одно правило: .
- Для текущего состояния делаем операцию .
- По всем возможный символам для каждой ситуации добавляем переходы, используя операцию .
- Если множество или во втором или третьем пункте изменилось, возвращаемся ко второму шагу.
Управляющая таблица
После построения автомата можно перейти к построению управляющей таблицы.
Обращение к таблице происходит следующим образом
, где- — состояние автомата,
- — входной символ;
В соответствии со структурой управляющей таблицы будем действовать следующим образом:
- Для каждого ребра
- (сокр. от shift) , если — терминал,
- , если — нетерминал.
(из состояния в состояние по ) мы поместим в позицию
- Для состояния
- Поместим (сокр. от reduce), где — это номер правила в изначальной грамматике.
, содержащего ситуацию в позицию для каждого терминала
- Запись означает допуск.
- Пустая ячейка означает ошибочную ситуацию.
Пример
Для иллюстрации алгоритма LR(0)-разборщика мы будем использовать грамматику:
Обратим внимание, что данная грамматика является леворекурсивной, поэтому нисходящий разборщик не сможет осуществить разбор слова из этой грамматики.
Пополнение грамматики
Для начала переходим к пополненной грамматике:
Построение автомата
НКА:
состоянию будет соответствует ситуация . Добавляем остальные состояния и получаем следующийНа картинке в двойной рамке обозначены терминальные состояния — это такие состояния, из которых можно производить свертку по правилу грамматики, а из остальных возможен только перенос. Этот термин не используется в алгоритме, а нужен только для лучшего визуального восприятия.
Теперь в одно состояние перемещаем все ситуации, в которые идут ДКА:
-переходы. ПолучаемЗаполнение управляющей таблицы
Пронумеруем правила для выполнения свертки:
Управляющая таблица будет выглядеть так:
LR(0)-разбора конкретной строки
Пример будет для строки
Строка | Стек | Комментарий | |||
---|---|---|---|---|---|
Перенос | . Переход в состояние.|||||
Перенос | . Переход в состояние.|||||
Свертка: | . Удаление из стека . Переход в состояние. Добавление в стек . Переход в состояние.|||||
Свертка: | . Удаление из стека . Переход в состояние. Добавление в стек . Переход в состояние.|||||
Перенос | . Переход в состояние.|||||
Перенос | . Переход в состояние.|||||
Свертка: | . Удаление из стека . Переход в состояние. Добавление в стек . Переход в состояние.|||||
Свертка: | . Удаление из стека . Переход в состояние. Добавление в стек . Переход в состояние.|||||
Перенос | . Переход в состояние.|||||
Свертка: | . Удаление из стека . Переход в состояние. Добавление в стек . Переход в состояние.|||||
Свертка: | . Удаление из стека . Переход в состояние. Добавление в стек . Переход в состояние.|||||
Перенос | . Переход в состояние.|||||
Перенос | . Переход в состояние.|||||
Свертка: | . Удаление из стека . Переход в состояние. Добавление в стек . Переход в состояние.|||||
Свертка: | . Удаление из стека . Переход в состояние. Добавление в стек . Переход в состояние.|||||
Так как свертка по нулевому правилу — осуществляем допуск. |
См. также
Источники информации
- Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс, 2003. Стр. 301-326.
- Терехов Ан.А., Вояковская Н., Булычев Д., Москаль А. Разработка компиляторов на платформе .NET — Восходящие анализаторы
- Б.К.Мартыненко. Языки и трансляции. Стр. 198-223
- Лекции по теории формальных языков, LR(0)-, SLR(1)-, LR(1)- и LALR(1)-анализ