LR(0)-разборщик это частный случай LR(k)-разборщикa, для которого сейчас будет рассмотрено построение автомата и управляющей таблицы.
Формальное описаное 2
Заметим, что LR(0)-разборщик принимает решение о своих действиях только на основании содержимого стека, не учитывая символы входной цепочки.
Ситауции
| Определение: |
| Пусть [math]\Gamma =\langle \Sigma, N, S, P \rangle[/math] — КС-грамматика и [math]A \to w_1 w_2 \in P[/math]. Композицию [math][A \to w_1 \cdot w_2, u] [/math], где [math]u \in \Sigma^{k}[/math], назовем LR(k)-ситуацией (англ. LR(k)-item) |
LR(0)-ситуации не должны содержать терминальной цепочки, так как [math]k=0[/math], то есть мы можем записывать их следующим образом: [math][A \to w_1 \cdot w_2][/math]
Автомат для множества ситуаций
В начале работы стек пуст, и указатель входной цепочки находится перед ее первым символом. Этому состоянию соответствует ситуация [math][E_0 \to \cdot E][/math], где [math]E_0[/math] — нетерминал, добавленный при пополнении грамматики, [math]E[/math] — стартовый нетерминал.
Для терминалов или нетерминалов, мы строим переходы к другим ситуациям по следующей схеме:
[math]{[} A \to \alpha \cdot c \beta] \xrightarrow{\text{c}} {[} A \to \alpha c \cdot \beta] [/math]
[math]{[} A \to \alpha \cdot B \beta] \xrightarrow{\text{B}} {[} A \to \alpha B \cdot \beta] [/math]
[math]{[} A \to \alpha \cdot B \beta] \xrightarrow{\varepsilon} {[} B \to \cdot \gamma] [/math]
Получаем НКА.
Далее избавимся от [math]\varepsilon[/math]-переходов и получаем ДКА.
Построение управляющей таблицы
Иллюстрация алгоритма
Для иллюстрации алгоритма LR(0)-разборщика мы будем использовать грамматику:
[math]
E \to E + T \\
E \to T \\
T \to {\bf n} \\
T \to (E) \\
[/math]
Пополнение грамматики
Для начала переходим к Пополненной грамматике:
[math]
E_0 \to E \\
E \to E + T \\
E \to T \\
T \to {\bf n} \\
T \to (E) \\
[/math]
Построение автомата
В начале работы стек пуст, и указатель входной цепочки находится перед ее первым символом. Этому состоянию соответствует ситуация [math][E_0 \to \cdot E][/math].
Для терминалов или нетерминалой, мы строим переходы к другим ситуациям по следующей схеме:
[math]{[} A \to \alpha \cdot c \beta] \xrightarrow{\text{c}} {[} A \to \alpha c \cdot \beta] [/math]
[math]{[} A \to \alpha \cdot B \beta] \xrightarrow{\text{B}} {[} A \to \alpha B \cdot \beta] [/math]
[math]{[} A \to \alpha \cdot B \beta] \xrightarrow{\varepsilon} {[} B \to \cdot \gamma] [/math]
Получаем следующий НКА:
Избавимся от [math]\varepsilon[/math]-переходов и получим ДКА:
Управляющая таблица
Теперь можно построить управляющую таблицу.
Поступим следующим образом:
1. для каждого ребра [math]I \xrightarrow{\text{X}} J [/math] мы поместим в позицию [math][I,X][/math] таблицы
- [math]s\ J[/math] (сокр. от shift) , если [math]X[/math] — терминал,
- [math]J[/math], если [math]X[/math] — нетерминал.
2. для состояния, содержащего ситуацию [math][A\to w \cdot][/math], поместим [math]r(n)[/math] (сокр. от reduce) в позицию [math][I, Y][/math] для каждого терминала [math]Y[/math], где [math]n[/math] — это номер правила в изначальной грамматике.
3. пустая ячейка означает ошибочную ситуацию.
Вспомним грамматику и пронумеруем правила для 2 пункта:
[math]
(0)\ E_0 \to E\\
(1)\ E \to E + T\\
(2)\ E \to T\\
(3)\ T \to {\bf n} \\
(4)\ T \to (E) \\
[/math]
Управляющая таблица будет выглядеть так:
|
|
[math]E[/math]
|
[math]T[/math]
|
[math]n[/math]
|
[math]+[/math]
|
[math]([/math]
|
[math])[/math]
|
[math]\$[/math]
|
| [math]0[/math]
|
[math]1[/math]
|
[math]2[/math]
|
[math]s3[/math]
|
|
[math]s4[/math]
|
|
|
| [math]1[/math]
|
|
|
|
[math]s5[/math]
|
|
|
[math]r(0)[/math]
|
| [math]2[/math]
|
|
|
|
[math]r(2)[/math]
|
|
[math]r(2)[/math]
|
[math]r(2)[/math]
|
| [math]3[/math]
|
|
|
|
[math]r(3)[/math]
|
|
[math]r(3)[/math]
|
[math]r(3)[/math]
|
| [math]4[/math]
|
[math]6[/math]
|
[math]2[/math]
|
[math]s3[/math]
|
|
[math]s4[/math]
|
|
|
| [math]5[/math]
|
|
[math]7[/math]
|
[math]s3[/math]
|
|
[math]s4[/math]
|
|
|
| [math]6[/math]
|
|
|
|
[math]s5[/math]
|
|
[math]s8[/math]
|
|
| [math]7[/math]
|
|
|
|
[math]r(1)[/math]
|
|
[math]r(1)[/math]
|
[math]r(1)[/math]
|
| [math]8[/math]
|
|
|
|
[math]r(4)[/math]
|
|
[math]r(4)[/math]
|
[math]r(4)[/math]
|
Формальное описание
Базовые операции
Теперь опишем алгоритм формально.
Для построения множества состояний определим базовые операции [math]closure (I)[/math] и [math]goto (I, X)[/math], где [math]I[/math] – множество ситуаций, [math]X[/math] – символ грамматики (терминал или нетерминал). Операция [math]closure[/math] добавляет ситуации к множеству ситуаций, у которых точка стоит слева от нетерминала. Добавляются те ситуации, которые получаются из правил, в левой части которого находится этот нетерминал.
|
[] closure (I)
do
for каждой ситуации [A [math]\to[/math] w.Xv] из I
for каждого правила грамматики X [math]\to[/math] u
I += [X [math]\to[/math] .u] // Операция += добавляет элемент к множеству
while I изменилось
return I
|
Операция [math]goto[/math] "переносит" точку после символа [math]X[/math]. Это означает переход из одного состояния в другое под воздействием символа [math]X[/math].
|
[] goto (I, X)
J={} // {} обозначает пустое множество
for каждой ситуации [A [math]\to[/math] w.Xv] из I
J += [A [math] \to [/math]wX.v]
return closure (J)
|
Алгоритм построения конечного автомата
Теперь обсудим алгоритм построения анализатора. Обозначим [math]T[/math] множество состояний, [math]E[/math] – множество переходов.
|
E, T build()
E = {}
T = {closure ([S' [math]\to[/math] .S])}
do
for каждого состояния I из T
for каждой ситуации [A [math]\to[/math] w.Xv] из I
J = goto(I, X)
T += {J} // ко множеству состояний добавляется новое состояние
E += (I [math]\to[/math] J) // ко множеству ребер добавляется ребро, идущее из состояния I в состояние J. Этот переход осуществляется по символу X
while E или T изменились
return E, T
|
Поскольку для символа [math]\$[/math] операция [math]goto(I , \$)[/math] не определена , мы выполняем действие [math]accept[/math].
Пример LR(0)-разбора
Пример будет для строки [math](n_1+n_2)+n_3[/math]
| Строка
|
Стек
|
[math]s = top()[/math]
|
[math]a = w[ip][/math]
|
[math]action[s,a][/math]
|
Комментарий
|
| [math](n_1+n_2)+n_3\$[/math]
|
[math]0[/math]
|
[math]0[/math]
|
[math]([/math]
|
[math]shift\ 4[/math]
|
Перенос [math]"("[/math]
|
| [math]n_1+n_2)+n_3\$[/math]
|
[math]0\ (4[/math]
|
[math]4[/math]
|
[math]n_1[/math]
|
[math]shift\ 3[/math]
|
Перенос [math]"n_1"[/math]
|
| [math]+n_2)+n_3\$[/math]
|
[math]0\ (4\ n_{1}3[/math]
|
[math]3[/math]
|
[math]+[/math]
|
[math]reduce\ 3[/math]
|
Свертка: [math]T \to \bf n[/math]
|
| [math]+n_2)+n_3\$[/math]
|
[math]0\ (4\ T2[/math]
|
[math]2[/math]
|
[math]+[/math]
|
[math]reduce\ 2[/math]
|
Свертка: [math]E \to T[/math]
|
| [math]+n_2)+n_3\$[/math]
|
[math]0\ (4\ E6[/math]
|
[math]6[/math]
|
[math]+[/math]
|
[math]shift\ 5[/math]
|
Перенос [math]"+"[/math]
|
| [math]n_2)+n_3\$[/math]
|
[math]0\ (4\ E6\ +5[/math]
|
[math]5[/math]
|
[math]n_2[/math]
|
[math]shift\ 3[/math]
|
Перенос [math]"n_2"[/math]
|
| [math])+n_3\$[/math]
|
[math]0\ (4\ E6\ +5\ n_23[/math]
|
[math]3[/math]
|
[math])[/math]
|
[math]reduce\ 3 [/math]
|
Свертка: [math]T \to \bf n[/math]
|
| [math])+n_3\$[/math]
|
[math]0\ (4\ E6\ +5\ T7[/math]
|
[math]7[/math]
|
[math])[/math]
|
[math]reduce\ 1 [/math]
|
Свертка: [math]E \to E + T[/math]
|
| [math])+n_3\$[/math]
|
[math]0\ (4\ E6[/math]
|
[math]6 [/math]
|
[math])[/math]
|
[math]shift\ 8[/math]
|
Перенос [math]")"[/math]
|
| [math]+n_3\$[/math]
|
[math]0\ (4\ E6\ )8[/math]
|
[math]8 [/math]
|
[math]+[/math]
|
[math]reduce\ 4[/math]
|
Свертка: [math]T \to (E)[/math]
|
| [math]+n_3\$[/math]
|
[math]0\ T2[/math]
|
[math]2[/math]
|
[math]+[/math]
|
[math]reduce\ 2[/math]
|
Свертка: [math]E \to T[/math]
|
| [math]+n_3\$[/math]
|
[math]0\ E1[/math]
|
[math]1[/math]
|
[math]+[/math]
|
[math]shift\ 5[/math]
|
Перенос [math]"+"[/math]
|
| [math]n_3\$[/math]
|
[math]0\ E1\ +5[/math]
|
[math]5[/math]
|
[math]n_3[/math]
|
[math]shift\ 3[/math]
|
Перенос [math]"n_3"[/math]
|
| [math]\$[/math]
|
[math]0\ E1\ +5\ n_33[/math]
|
[math]3[/math]
|
[math]\$[/math]
|
[math]reduce\ 3[/math]
|
Свертка: [math]T \to \bf n[/math]
|
| [math]\$[/math]
|
[math]0\ E1\ +5\ T7[/math]
|
[math]7[/math]
|
[math]\$[/math]
|
[math]reduce\ 1[/math]
|
Свертка: [math]E \to E + T[/math]
|
| [math]\$[/math]
|
[math]0\ E1[/math]
|
[math]1[/math]
|
[math]\$[/math]
|
[math]reduce\ 0[/math]
|
Допуск
|
См. также
Источники информации
- Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс, 2003. Стр. 301 - 326.
- Терехов Ан.А., Вояковская Н., Булычев Д., Москаль А. - Разработка компиляторов на платформе .NET - Восходящие анализаторы
- Б.К.Мартыненко. Языки и трансляции. Стр. 198 - 223
- Лекции по теории формальных языков, LR(0)-, SLR(1)-, LR(1)- и LALR(1)-анализ
