LR(0)-разбор — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 27 промежуточных версий 4 участников)
Строка 1: Строка 1:
LR(0)-разборщик это частный случай [[LR(k)-грамматики#LR-разборщик|LR(k)-разборщикa]], заметим, что в данном случае <tex>k=0</tex>, то есть решение о своих действиях принимается только на основании содержимого стека, не учитывая символы входной цепочки.
+
LR(0)-разборщик {{---}} это частный случай [[LR(k)-грамматики#LR-разборщик|LR(k)-разборщикa]]. Заметим, что в данном случае <tex>k=0</tex>, то есть решение о своих действиях принимается только на основании содержимого стека, символы входной цепочки не учитываются.
  
 
== Построение автомата и управляющей таблицы ==  
 
== Построение автомата и управляющей таблицы ==  
Как было сказано в статье про LR(k)-разборщик, управляющая программа одинакова для всех LR-анализаторов, а таблица и автомат изменяются от одного анализатора к другому.
 
 
 
=== Автомат ===
 
=== Автомат ===
 
Каждое состояние автомата будет состоять из 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>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>
  
Таким образом, мы определяем новые состояния, в которое автомат перейдет после переноса того или иного терминала или нетерминала.
+
Таким образом, мы определяем новые состояния, в которые автомат перейдет после переноса того или иного терминала или нетерминала.  
 
 
Заметим, что хранить в каждом состоянии только по одной ситуации не имеет смысла, поэтому пусть в каждое стостояние будет представлять множество ситуаций. Для этого определим базовые операции <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>
 
|}
 
  
 +
Можно заметить, что алгоритм LR-разбора похож на [[Алгоритм Эрли|алгоритм Эрли]].
  
Операция <tex>goto</tex> "переносит" точку после символа <tex>X</tex>. Это означает переход из одного состояния в другое под воздействием символа <tex>X</tex>.
+
==== Базовые операции ====
  
{| border="0"
+
Заметим, что хранить в каждом состоянии только по одной ситуации не имеет смысла, поэтому пусть каждое состояние будет представлять множество ситуаций, а переходы {{---}} терминалы и нетерминалы. Для этого определим базовые операции <tex>closure (I)</tex> и <tex>goto (I, X)</tex>, где <tex>I</tex> {{---}} множество ситуаций, <tex>X</tex> {{---}} символ грамматики (терминал или нетерминал).
|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> – множество переходов.
+
* Операция <tex>closure</tex> добавляет ситуации к множеству ситуаций, у которых точка стоит слева от нетерминала. Добавляются те ситуации, которые получаются из правил, в левой части которых находится этот нетерминал.
  
{| border="0"
+
* Операция <tex>goto</tex> "переносит" точку после символа <tex>X</tex>. Это означает переход из одного состояния в другое под воздействием символа <tex>X</tex>.
|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>.
+
==== Построение автомата ====
 
+
Теперь обсудим алгоритм построения конечного автомата. Обозначим <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{T[state, token]}</tex>, где  
 
*<tex>\mathtt{state}</tex> {{---}} состояние автомата,  
 
*<tex>\mathtt{state}</tex> {{---}} состояние автомата,  
 
*<tex>\mathtt{token}</tex> {{---}} входной символ;  
 
*<tex>\mathtt{token}</tex> {{---}} входной символ;  
В таблице информация имеет следующий вид:
 
'''struct''' Cell
 
    enum:
 
        Shift
 
        Reduce
 
        Accept  <font color="green">// допуск </font>
 
        Error    <font color="green">// ошибка</font>
 
'''struct''' Shift
 
    state: '''int'''  <font color="green">// переход в стостояние state</font>
 
'''struct''' Reduce
 
    rule: '''int'''  <font color="green">// свертка по правилу rule</font>
 
  
== Иллюстрация алгоритма ==
+
В соответствии со [[LR(k)-грамматики#Управляющая программа анализатора |структурой]] управляющей таблицы будем действовать следующим образом:
 +
 
 +
<ol>
 +
<li>Для каждого ребра <tex>I \xrightarrow{\text{X}}  J </tex> (из состояния <tex>I</tex> в состояние <tex>J</tex> по <tex>X</tex>) мы поместим в позицию <tex>T[I,X]</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>[E_0 \to \cdot E]</tex>.  
+
<tex>0</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>
+
[[Файл:eps-dfa.png|600px]]
 
 
<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{\varepsilon} {[} B \to \cdot \gamma] </tex>
+
На картинке в двойной рамке обозначены терминальные состояния {{---}} это такие состояния, из которых можно производить свертку по правилу грамматики, а из остальных возможен только перенос. Этот термин не используется в алгоритме, а нужен только для лучшего визуального восприятия. 
  
Получаем следующий [[Недетерминированные конечные автоматы|НКА]]:
+
Теперь в одно состояние перемещаем все ситуации, в которые идут <tex>\varepsilon</tex>-переходы. Получаем [[Детерминированные конечные автоматы|ДКА]]:
 
 
[[Файл:eps-dfa.png|600px]]
 
 
 
Избавимся от <tex>\varepsilon</tex>-переходов и получим [[Детерминированные конечные автоматы|ДКА]]:
 
  
 
[[Файл:LRk_dfa.png|600px]]
 
[[Файл:LRk_dfa.png|600px]]
  
=== Построение управляющей таблицы ===
+
=== Заполнение управляющей таблицы ===
 
 
Теперь можно построить управляющую таблицу.
 
Поступим следующим образом:
 
 
 
1. для каждого ребра <tex>I \xrightarrow{\text{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>, где <tex>n</tex> {{---}} это номер правила в изначальной грамматике.
 
 
 
3. пустая ячейка означает ошибочную ситуацию.
 
 
   
 
   
Вспомним грамматику и пронумеруем правила для 2 пункта:
+
Пронумеруем правила для выполнения ''свертки'':
  
 
<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>s3</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>s4</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>s5</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>s3</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>s4</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>s3</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>s4</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>s5</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>s8</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)-разбора ==
+
=== LR(0)-разбора конкретной строки===
  
 
Пример будет для строки <tex>(n_1+n_2)+n_3</tex>
 
Пример будет для строки <tex>(n_1+n_2)+n_3</tex>
Строка 255: Строка 203:
 
!style="background-color:#EEE"| Строка
 
!style="background-color:#EEE"| Строка
 
!style="background-color:#EEE"| Стек
 
!style="background-color:#EEE"| Стек
!style="background-color:#EEE"| <tex>s = top()</tex>
+
!style="background-color:#EEE"| <tex>curState</tex>
!style="background-color:#EEE"| <tex>a = w[ip]</tex>
+
!style="background-color:#EEE"| <tex>curToken</tex>
!style="background-color:#EEE"| <tex>action[s,a]</tex>
+
!style="background-color:#EEE"| <tex>T[curState,curToken]</tex>
 
!style="background-color:#EEE"| Комментарий
 
!style="background-color:#EEE"| Комментарий
 
|-
 
|-
Строка 265: Строка 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>
Строка 272: Строка 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>
Строка 279: Строка 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>
Строка 286: Строка 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>
Строка 293: Строка 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>
Строка 300: Строка 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>
Строка 307: Строка 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>
Строка 314: Строка 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>
Строка 321: Строка 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>
Строка 328: Строка 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>
Строка 335: Строка 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>
Строка 342: Строка 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>
Строка 349: Строка 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>
Строка 356: Строка 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>
Строка 363: Строка 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>
Строка 370: Строка 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"| Так как свертка по нулевому правилу {{---}} осуществляем допуск.
 
|}
 
|}
  
Строка 377: Строка 325:
  
 
== Источники информации ==
 
== Источники информации ==
* Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс, 2003. Стр. 301 - 326.
+
* Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс, 2003. Стр. 301-326.
* [http://ict.edu.ru/ft/005128//ch7.pdf Терехов Ан.А., Вояковская Н., Булычев Д., Москаль А. - Разработка компиляторов на платформе .NET - Восходящие анализаторы]
+
* [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. Заметим, что в данном случае [math]k=0[/math], то есть решение о своих действиях принимается только на основании содержимого стека, символы входной цепочки не учитываются.

Построение автомата и управляющей таблицы

Автомат

Каждое состояние автомата будет состоять из 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] [/math] назовем LR(0)-ситуацией (англ. LR(0)-item).

В начале работы стек пуст, и указатель входной цепочки находится перед ее первым символом. Этому состоянию соответствует ситуация [math][E_0 \to \cdot E][/math], где [math]E_0[/math] — нетерминал, добавленный при пополнении грамматики, [math]E[/math] — стартовый нетерминал. Назовем это состояние [math]0[/math]. Входная цепочка может начинаться с любого терминального символа, с которого начинается правая часть любого правила с левой частью [math]E[/math]. Построим соответствующий переход по следующей схеме:

[math]{[} A \to \alpha \cdot B \beta] \xrightarrow{\varepsilon} {[} B \to \cdot \gamma] [/math]

Теперь мы должны выяснить, что произойдет, если анализатор выполнит перенос. Предположим, что мы выполним перенос [math]c[/math] или перенос [math]B[/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]

Таким образом, мы определяем новые состояния, в которые автомат перейдет после переноса того или иного терминала или нетерминала.

Можно заметить, что алгоритм LR-разбора похож на алгоритм Эрли.

Базовые операции

Заметим, что хранить в каждом состоянии только по одной ситуации не имеет смысла, поэтому пусть каждое состояние будет представлять множество ситуаций, а переходы — терминалы и нетерминалы. Для этого определим базовые операции [math]closure (I)[/math] и [math]goto (I, X)[/math], где [math]I[/math] — множество ситуаций, [math]X[/math] — символ грамматики (терминал или нетерминал).

  • Операция [math]closure[/math] добавляет ситуации к множеству ситуаций, у которых точка стоит слева от нетерминала. Добавляются те ситуации, которые получаются из правил, в левой части которых находится этот нетерминал.
  • Операция [math]goto[/math] "переносит" точку после символа [math]X[/math]. Это означает переход из одного состояния в другое под воздействием символа [math]X[/math].

Построение автомата

Теперь обсудим алгоритм построения конечного автомата. Обозначим [math]T[/math] множество состояний, [math]E[/math] — множество переходов.

  1. Изначальное состояние содержит одно правило: [math]E_0 \to E[/math].
  2. Для текущего состояния делаем операцию [math]closure[/math].
  3. По всем возможный символам для каждой ситуации добавляем переходы, используя операцию [math]goto[/math].
  4. Если множество [math]T[/math] или [math]E[/math] во втором или третьем пункте изменилось, возвращаемся ко второму шагу.

Управляющая таблица

После построения автомата можно перейти к построению управляющей таблицы.

Обращение к таблице происходит следующим образом [math]\mathtt{T[state, token]}[/math], где

  • [math]\mathtt{state}[/math] — состояние автомата,
  • [math]\mathtt{token}[/math] — входной символ;

В соответствии со структурой управляющей таблицы будем действовать следующим образом:

  1. Для каждого ребра [math]I \xrightarrow{\text{X}} J [/math] (из состояния [math]I[/math] в состояние [math]J[/math] по [math]X[/math]) мы поместим в позицию [math]T[I,X][/math]
    • [math]s(J)[/math] (сокр. от shift) , если [math]X[/math] — терминал,
    • [math]J[/math], если [math]X[/math] — нетерминал.
  2. Для состояния [math]I[/math], содержащего ситуацию [math][A\to w \cdot][/math] в позицию [math]T[I, Y][/math] для каждого терминала [math]Y[/math]
    • Поместим [math]r(n)[/math] (сокр. от reduce), где [math]n[/math] — это номер правила в изначальной грамматике.
    • Запись [math]r(0)[/math] означает допуск.
  3. Пустая ячейка означает ошибочную ситуацию.

Пример

Для иллюстрации алгоритма 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]0[/math] состоянию будет соответствует ситуация [math][E_0 \to \cdot E][/math]. Добавляем остальные состояния и получаем следующий НКА:

Eps-dfa.png

На картинке в двойной рамке обозначены терминальные состояния — это такие состояния, из которых можно производить свертку по правилу грамматики, а из остальных возможен только перенос. Этот термин не используется в алгоритме, а нужен только для лучшего визуального восприятия.

Теперь в одно состояние перемещаем все ситуации, в которые идут [math]\varepsilon[/math]-переходы. Получаем ДКА:

LRk dfa.png

Заполнение управляющей таблицы

Пронумеруем правила для выполнения свертки:

[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]s(3)[/math] [math]s(4)[/math]
[math]1[/math] [math]s(5)[/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]s(3)[/math] [math]s(4)[/math]
[math]5[/math] [math]7[/math] [math]s(3)[/math] [math]s(4)[/math]
[math]6[/math] [math]s(5)[/math] [math]s(8)[/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]

LR(0)-разбора конкретной строки

Пример будет для строки [math](n_1+n_2)+n_3[/math]

Строка Стек [math]curState[/math] [math]curToken[/math] [math]T[curState,curToken][/math] Комментарий
[math](n_1+n_2)+n_3\$[/math] [math]0[/math] [math]0[/math] [math]([/math] [math]shift\ 4[/math] Перенос [math]"("[/math]. Переход в [math]4[/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]3[/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_{1}3[/math]. Переход в [math]4[/math] состояние. Добавление в стек [math]T2[/math]. Переход в [math]2[/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]T2[/math]. Переход в [math]4[/math] состояние. Добавление в стек [math]E6[/math]. Переход в [math]6[/math] состояние.
[math]+n_2)+n_3\$[/math] [math]0\ (4\ E6[/math] [math]6[/math] [math]+[/math] [math]shift\ 5[/math] Перенос [math]"+"[/math]. Переход в [math]5[/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]3[/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_{2}3[/math]. Переход в [math]5[/math] состояние. Добавление в стек [math]T7[/math]. Переход в [math]7[/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]E6\ +5\ T7[/math]. Переход в [math]4[/math] состояние. Добавление в стек [math]E6[/math]. Переход в [math]6[/math] состояние.
[math])+n_3\$[/math] [math]0\ (4\ E6[/math] [math]6 [/math] [math])[/math] [math]shift\ 8[/math] Перенос [math]")"[/math]. Переход в [math]8[/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](4\ E6\ )8[/math]. Переход в [math]0[/math] состояние. Добавление в стек [math]T2[/math]. Переход в [math]2[/math] состояние.
[math]+n_3\$[/math] [math]0\ T2[/math] [math]2[/math] [math]+[/math] [math]reduce\ 2[/math] Свертка: [math]E \to T[/math]. Удаление из стека [math]T2[/math]. Переход в [math]0[/math] состояние. Добавление в стек [math]E1[/math]. Переход в [math]1[/math] состояние.
[math]+n_3\$[/math] [math]0\ E1[/math] [math]1[/math] [math]+[/math] [math]shift\ 5[/math] Перенос [math]"+"[/math]. Переход в [math]5[/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]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]n_33[/math]. Переход в [math]5[/math] состояние. Добавление в стек [math]T7[/math]. Переход в [math]7[/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]E1\ +5\ T7[/math]. Переход в [math]0[/math] состояние. Добавление в стек [math]E1[/math]. Переход в [math]1[/math] состояние.
[math]\$[/math] [math]0\ E1[/math] [math]1[/math] [math]\$[/math] [math]reduce\ 0[/math] Так как свертка по нулевому правилу — осуществляем допуск.

См. также

Источники информации