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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Пример)
м (Замена \char36 на \$)
(не показаны 32 промежуточные версии 4 участников)
Строка 1: Строка 1:
<wikitex>
 
 
В некоторых случаях [[SLR(1)-разбор|SLR-разбор]] может выдать неправильный результат. В таких случаях используют более сложные методы, такие как  LR(1) и [[LALR-разбор]]. Рассмотрим первый из них.
 
В некоторых случаях [[SLR(1)-разбор|SLR-разбор]] может выдать неправильный результат. В таких случаях используют более сложные методы, такие как  LR(1) и [[LALR-разбор]]. Рассмотрим первый из них.
</wikitex>
 
 
== Отличия от SLR-разбора ==
 
== Отличия от SLR-разбора ==
<wikitex>
 
 
Основным отличием LR(1)-разбора от SLR-разбора является использование '''предпросмотра''' (англ. ''lookahead'') символов.
 
Основным отличием LR(1)-разбора от SLR-разбора является использование '''предпросмотра''' (англ. ''lookahead'') символов.
  
Приведём пример ситуации, в которой SLR-разбор не справится с задачей:
+
Приведём пример, при котором SLR-разбор не справится с задачей:
  
 
Рассмотрим грамматику вида:
 
Рассмотрим грамматику вида:
Строка 61: Строка 58:
 
$S \to L = R \cdot$
 
$S \to L = R \cdot$
 
|}
 
|}
Рассмотрим ситуацию $I_2$. Если SLR-парсер находится в $I_2$ и очередной входной символ равен $=$, то парсер выполняет свёртку в соответствии с продукцией $R \to L$, что неверно, т.к. в этой грамматике не выводится выражение $R=\ldots$ и парсер должен был выполнить перенос, а не свёртку.
+
Рассмотрим состояние $I_2$. Если SLR-парсер находится в $I_2$ и очередной входной символ равен $=$, то парсер выполняет свёртку в соответствии с ситуацией $R \to L$, что неверно, т.к. в этой грамматике не выводится выражение $R=\ldots$ и парсер должен был выполнить перенос, а не свёртку.
  
 
Чтобы решить эту проблему, необходимо хранить в ситуации больший объём информации, который позволит не делать таких ошибочных свёрток.
 
Чтобы решить эту проблему, необходимо хранить в ситуации больший объём информации, который позволит не делать таких ошибочных свёрток.
</wikitex>
+
 
 
== Канонические LR(1)-ситуации ==
 
== Канонические LR(1)-ситуации ==
<wikitex>
+
Основная идея заключается в том, чтобы хранить в ситуациях (англ. ''items'') больше информации, чтобы не производить некорректных свёрток.  
Основная идея заключается в том, чтобы хранить в ситуациях больше информации, чтобы не производить некорректных свёрток.  
+
 
 
Добавим в ситуацию второй компонент: терминальный символ. Таким образом, LR(1)-ситуации будут выглядеть следующим образом:  
 
Добавим в ситуацию второй компонент: терминальный символ. Таким образом, LR(1)-ситуации будут выглядеть следующим образом:  
  
$[A\rightarrow\alpha\cdot\beta, a]$, где первая часть {{---}} продукция, а вторая {{---}} терминал или маркер конца входной строки $\char36$. Здесь $a$ называется '''предпросмотром''' (англ. ''lookahead'') ситуации, а число 1 в LR(1) означает его длину.
+
$[A\rightarrow\alpha\cdot\beta, a]$, где первая часть {{---}} продукция, а вторая {{---}} терминал или маркер конца входной строки $\$$. Здесь $a$ называется '''предпросмотром''' ситуации, а число $1$ в LR(1) означает его длину.
Теперь мы будем выполнять свёртку в соответствии с продукцией $A\rightarrow\alpha$, только в том случае, если находимся в ситуации $[A\rightarrow\alpha\cdot\beta, a]$ и $a$ {{---}} входной символ.
+
Теперь мы будем выполнять свёртку в соответствии с продукцией $A\rightarrow\alpha$, только в том случае, если находимся в ситуации $[A\rightarrow\alpha\cdot\beta, a]$, и $a$ {{---}} входной символ.
 
{{Определение
 
{{Определение
 
|id=defValid  
 
|id=defValid  
 
|definition=
 
|definition=
Назовём LR(1)-ситуацию $[A\rightarrow\alpha\cdot\beta, a]$ '''допустимой''' (англ. ''valid'') для активного префикса $\gamma$, если существует правое порождение $S\Rightarrow^{*}\delta A w\Rightarrow\delta\alpha\beta w$, где верно одно из трёх: либо $\gamma=\delta\alpha$, либо $a$ является первым символом $w$, либо$w=\varepsilon$ и $a=\char36$.
+
Назовём LR(1)-ситуацию $[A\rightarrow\alpha\cdot\beta, a]$ '''допустимой''' (англ. ''valid'') для активного префикса $\gamma$, если существует правое порождение $S\Rightarrow^{*}\delta A w\Rightarrow\delta\alpha\beta w$, где верно одно из трёх: либо $\gamma=\delta\alpha$, либо $a$ является первым символом $w$, либо$w=\varepsilon$ и $a=\$$.
 
}}
 
}}
</wikitex>
 
 
=== Построение множеств LR(1)-ситуаций ===
 
=== Построение множеств LR(1)-ситуаций ===
<wikitex>
 
 
Метод построения похож на метод для $LR(0)$-разбора, с двумя изменёнными функциями: $closure(I)$ {{---}} замыкание множества ситуаций, и $goto(X,I)$ {{---}} функция переходов в автомате по символу $X$.
 
Метод построения похож на метод для $LR(0)$-разбора, с двумя изменёнными функциями: $closure(I)$ {{---}} замыкание множества ситуаций, и $goto(X,I)$ {{---}} функция переходов в автомате по символу $X$.
 
{{Лемма
 
{{Лемма
Строка 88: Строка 83:
 
Значит, $b\in FIRST(\beta a)$.
 
Значит, $b\in FIRST(\beta a)$.
 
}}
 
}}
</wikitex>
 
 
====Псевдокод====
 
====Псевдокод====
<wikitex>
+
Псевдокод построения множеств $closure$ и $goto$, а также множества наборов ситуаций $items$ для грамматики
Псевдокод построения множеств $closure$ и $goto$, а также множества ситуаций $items$:
+
$\Gamma' =\langle\Sigma, N, S, P\rangle$:
<code>
+
   '''item'''[] closure('''item'''[] <tex>I</tex>):
   Item[] closure(Item[] I):
 
 
       '''bool''' changed
 
       '''bool''' changed
       Item[] J = I  
+
       '''item'''[] <tex>J = I</tex>
 
       '''repeat'''
 
       '''repeat'''
           changed = '''false'''
+
           changed = ''false''
           '''for''' $[A\rightarrow\alpha\cdot B\beta, a]\in I$
+
           '''for''' <tex>[A\rightarrow\alpha\cdot B\beta, a]\in I</tex>
               '''for''' $(B\rightarrow\gamma)\in G'$
+
               '''for''' <tex>(B\rightarrow\gamma)\in \Gamma'.P</tex>
                   '''for''' $b\in FIRST(\beta\alpha)$
+
                   '''for''' <tex>b\in FIRST(\beta\alpha)</tex>
                       J.add($[B\rightarrow\cdot\gamma,b]$)
+
                       <tex>J</tex>.add(<tex>[B\rightarrow\cdot\gamma,b]</tex>)
                       changed = '''true'''
+
                       changed = ''true''
       '''until''' not changed
+
       '''until not''' changed
       '''return''' J
+
       '''return''' <tex>J</tex>
</code>
+
 
<code>
+
   '''item'''[] goto('''item'''[] <tex>I</tex>, '''char''' <tex>X</tex>):
   Item[] goto(Item[] I, X):
+
       '''item'''[] <tex>J=\varnothing</tex>
       Item[] J $=\varnothing$
+
       '''for''' <tex>[A\rightarrow\alpha\cdot X\beta, a]\in I</tex>
       '''for''' $[A\rightarrow\alpha\cdot X\beta, a]\in I$
+
           <tex>J</tex>.add(<tex>[A\rightarrow\alpha X\cdot\beta, a]</tex>)
           J.add($[A\rightarrow\alpha X\cdot\beta, a]$)
+
       '''return''' <tex>closure(J)</tex>
       '''return''' $closure(J)$
+
 
</code>
+
   '''item'''[][] items(<tex>\Gamma'</tex>):
<code>
 
   Item[][] items($G'$):
 
 
       '''bool''' changed
 
       '''bool''' changed
       Item[][] $C = \{closure({S'\rightarrow\cdot S,\char36})\}$
+
       '''item'''[][] <tex>C</tex>
 +
      <tex>C</tex>.add(<tex>closure(\{[S'\rightarrow\cdot S,\$]\})</tex>)
 
       '''repeat'''
 
       '''repeat'''
           changed = '''false'''
+
           changed = ''false''
           '''for''' Item[] $I\subset C$
+
           '''for''' '''item'''[] <tex>I\subset C</tex>
               '''for''' $X \in symbols(G')$ <font color="green">//по всем символам грамматики</font>
+
               '''for''' <tex>X \in \Gamma'.\Sigma</tex>
                   '''if''' $goto(I,X)\neq\varnothing$ and $goto(I,X)\not\subset C$
+
                   '''if''' <tex>goto(I,X)\neq\varnothing</tex> '''and''' <tex>goto(I,X)\not\subset C</tex>
                       C.add($goto(I,X)$)
+
                       <tex>C</tex>.add(<tex>goto(I,X)</tex>)
                       changed = '''true'''
+
                       changed = ''true''
       '''until''' not changed
+
       '''until not''' changed
       '''return''' C
+
       '''return''' <tex>C</tex>
</code>
+
 
</wikitex>
 
 
====Пример====
 
====Пример====
<wikitex>
+
Рассмотрим следующую грамматику $\Gamma'$:
Рассмотрим следующую грамматику $G'$:
 
 
* $S'\rightarrow S$
 
* $S'\rightarrow S$
 
* $S\rightarrow CC$
 
* $S\rightarrow CC$
* $S\rightarrow cC|d$
+
* $C\rightarrow cC\mid d$
Запустим процедуру $items(G')$. Она начинается с вычисления $closure([S\rightarrow S', \char36])$. Это правило вида $[A\rightarrow\alpha\cdot B\beta, a]$, где $A=S';\alpha=\varepsilon;B=S;\beta=\varepsilon;a=\char36$. Т.к. в таком случае $FIRST(\beta\alpha) = {\char36}$, то мы добавим только правило $[S\rightarrow\cdot CC,\char36]$.
+
Запустим процедуру $items(\Gamma')$. Она начинается с вычисления $closure([S\rightarrow S', \$])$. Это правило вида $[A\rightarrow\alpha\cdot B\beta, a]$, где $A=S';\alpha=\varepsilon;B=S;\beta=\varepsilon;a=\$$.
  
Продолжив вычислять замыкание таким образом, мы добавим во множество ситуаций $[C\rightarrow\cdot C, c]$, $C\rightarrow\cdot C, d]$, $C\rightarrow\cdot d, c]$, и $C\rightarrow\cdot d, d]$. Т.к. ни одна из новых ситуаций не имеет вид $[A\rightarrow\alpha\cdot B\beta, a]$ (справа от точки во всех ситуациях терминалы), то функция $closure$ завершает свою работу и начальное множество ситуаций в данном случае равно:
+
Т.к. в таком случае $FIRST(\beta\alpha) = {\$}$, то мы добавим только правило $[S\rightarrow\cdot CC,\$]$.
  
[[Файл:lr1_sets.png|400px|thumb|Рис. 1 Множества ситуаций и их переходы]]
+
Продолжив вычислять замыкание таким образом, мы добавим во множество ситуаций $[C\rightarrow\cdot C, c]$, $[C\rightarrow\cdot C, d]$, $C\rightarrow\cdot d, c]$ и $[C\rightarrow\cdot d, d]$.
$$I_0: \{[S'\rightarrow \cdot S, \char36],[S\rightarrow\cdot CC,\char36],[C\rightarrow\cdot C, c/d],[C\rightarrow\cdot d, c/d]\}$$
+
Поскольку ни одна из новых ситуаций не имеет вид $[A\rightarrow\alpha\cdot B\beta, a]$ (справа от точки во всех ситуациях терминалы), то функция $closure()$ завершает свою работу.
Следующим шагом процедуры $items$ будет вычисление функции переходов автомата $goto(I_0,X)$ для всех символов $X$ грамматики $G'$:
+
 
 +
Начальное множество ситуаций в данном случае равно:
 +
 
 +
[[Файл:lr1_sets.png|400px|thumb|Рис. 1 Множества ситуаций и переходы между ними]]
 +
*$$I_0: \{[S'\rightarrow \cdot S, \$],[S\rightarrow\cdot CC,\$],[C\rightarrow\cdot C, c/d],[C\rightarrow\cdot d, c/d]\}$$
 +
Следующим шагом процедуры $items()$ будет вычисление функции переходов автомата $goto(I_0,X)$ для всех символов $X$ грамматики $\Gamma'$:
 +
 
 +
#При $X=S$:
 +
#:$$closure({[S'\rightarrow S\cdot,\$]}) = \varnothing$$
 +
#:Мы не добавили ни одной ситуации, т.к. точка является крайней справа. Таким образом, 
 +
#:*$$I_1: \{[S'\rightarrow S\cdot,\$]\}$$
 +
#При $X=C$:
 +
#:$$I_2 = closure(\{[S\rightarrow C\cdot C,\$]\})$$
 +
#:*$$I_2 = \{[S\rightarrow C\cdot C,\$],[C\rightarrow\cdot cC,\$],[C\rightarrow\cdot d,\$]\}$$
 +
#При $X=c$:
 +
#:$$I_3 = closure(\{[C\rightarrow c\cdot C,c/d]\})$$
 +
#:*$$I_3 = \{[C\rightarrow c\cdot C,c/d],[C\rightarrow\cdot cC,c/d],[C\rightarrow\cdot d,c/d]\}$$
 +
#При $X=d$:
 +
#:$$I_4 = closure(\{[C\rightarrow d\cdot ,c/d]\})$$
 +
#:*$$I_4 = \{[C\rightarrow d\cdot,c/d]\}$$
  
При $X=S$:
 
$$closure({[S'\rightarrow S\cdot,\char36]}) = \varnothing$$
 
Мы не добавили ни одной ситуации, т.к. точка является крайней справа. Таким образом,
 
$$I_1: \{[S'\rightarrow S\cdot,\char36]\}$$
 
При $X=C$:
 
$$I_2 = closure(\{[S\rightarrow C\cdot C,\char36]\})$$
 
$$I_2 = \{[S\rightarrow C\cdot C,\char36],[C\rightarrow\cdot cC,\char36],[C\rightarrow\cdot d,\char36]\}$$
 
При $X=c$:
 
$$I_3 = closure(\{[C\rightarrow c\cdot C,c/d]\})$$
 
$$I_3 = \{[C\rightarrow c\cdot C,c/d],[C\rightarrow\cdot cC,c/d],[C\rightarrow\cdot d,c/d]\}$$
 
При $X=d$:
 
$$I_4 = closure(\{[C\rightarrow d\cdot ,c/d]\})$$
 
$$I_4 = \{[C\rightarrow d\cdot,c/d]\}$$
 
 
На этом завершается выполнение цикла из процедуры $items$ для $I_0$.  
 
На этом завершается выполнение цикла из процедуры $items$ для $I_0$.  
 
$$goto(I_1, *)=\varnothing$$
 
$$goto(I_1, *)=\varnothing$$
$$I_5 = goto(I_2, C) = closure(\{[S\rightarrow CC\cdot,\char36]\})=\{[S\rightarrow CC\cdot,\char36]\}$$
+
*$$I_5=goto(I_2, C) = closure(\{[S\rightarrow CC\cdot,\$]\})=\{[S\rightarrow CC\cdot,\$]\}$$
$$I_6 = goto(I_2, c) = closure(\{[C\rightarrow c\cdot C,\char36]\})$$
+
:$$I_6=goto(I_2, c) = closure(\{[C\rightarrow c\cdot C,\$]\})$$
$$I_6=\{[C\rightarrow c\cdot C,\char36],[C\rightarrow \cdot cC,\char36],[C\rightarrow \cdot d,\char36]\}$$
+
*$$I_6=\{[C\rightarrow c\cdot C,\$],[C\rightarrow \cdot cC,\$],[C\rightarrow \cdot d,\$]\}$$
Обратим внимание, что $I_6$ отличается от $I_3$ только правыми частями ситуаций. Такое явление является частым в LR(1)-анализе, из-за него результирующая таблица будет неоправданно большой. LALR-анализ борется с этим явлением.
+
 
Продолжим:
+
'''NB:''' Обратим внимание, что $I_6$ отличается от $I_3$ только правыми частями ситуаций. Такое явление является частым в LR(1)-анализе, из-за него результирующая таблица будет неоправданно большой. LALR-анализ борется с этим явлением.
$$I_7 = goto(I_2, d) = closure(\{[C\rightarrow d\cdot ,\char36]\}) = \{[C\rightarrow d\cdot ,\char36]\}$$
+
 
 +
*$$I_7 = goto(I_2, d) = closure(\{[C\rightarrow d\cdot ,\$]\}) = \{[C\rightarrow d\cdot ,\$]\}$$
 
На этом рассмотрение $goto(I_2)$ завершено, переходим к $goto(I_3)$:
 
На этом рассмотрение $goto(I_2)$ завершено, переходим к $goto(I_3)$:
$$I_8 = goto(I_3, C) = closure(\{[C\rightarrow cC\cdot ,c/d]\}) = \{[C\rightarrow cC\cdot ,c/d]\}$$
+
*$$I_8 = goto(I_3, C) = closure(\{[C\rightarrow cC\cdot ,c/d]\}) = \{[C\rightarrow cC\cdot ,c/d]\}$$
В множествах $I_4$ и $I_5$ все ситуации имеют точки в крайнем положении справа, следовательно эти множества не имеют $goto$  
+
В множествах $I_4$ и $I_5$ все ситуации имеют точки в крайнем положении справа, следовательно эти множества не имеют $goto$:
 
$$goto(I_6, c) = I_6$$
 
$$goto(I_6, c) = I_6$$
 
$$goto(I_6, d) = I_7$$
 
$$goto(I_6, d) = I_7$$
$$I_9 = goto(I_6, C) = \{[C\rightarrow cC\cdot,\char36]\}$$
+
*$$I_9 = goto(I_6, C) = \{[C\rightarrow cC\cdot,\$]\}$$
Остальные множества ситуаций не дают нам значений $goto$, процедура $items$ завершает работу.  
+
Остальные множества ситуаций не дают нам значений $goto$, процедура $items()$ завершает работу.  
</wikitex>
+
 
 
=== Канонические LR(1)-таблицы ===
 
=== Канонические LR(1)-таблицы ===
В алгоритме будут использоваться структуры, описанные в [http://neerc.ifmo.ru/wiki/index.php?title=LR(k)-%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B8#.D0.A3.D0.BF.D1.80.D0.B0.D0.B2.D0.BB.D1.8F.D1.8E.D1.89.D0.B0.D1.8F_.D0.BF.D1.80.D0.BE.D0.B3.D1.80.D0.B0.D0.BC.D0.BC.D0.B0_.D0.B0.D0.BD.D0.B0.D0.BB.D0.B8.D0.B7.D0.B0.D1.82.D0.BE.D1.80.D0.B0 конспекте про LL(k) грамматики]
+
В алгоритме будут использоваться структуры, описанные в конспекте про про [[LR(k)-грамматики]]
 
==== Алгоритм ====
 
==== Алгоритм ====
  <font color=green>// вход: <tex>G'</tex> {{---}} расширенная грамматика</font>
+
  <font color=green>// вход: <tex>\Gamma'</tex> {{---}} расширенная грамматика</font>
  <font color=green>// выход: таблицы <tex>ACTION</tex> и <tex>GOTO</tex> канонического <tex>LR</tex>-анализа</font>
+
  <font color=green>// выход: таблица <tex>T</tex> канонического <tex>LR(1)</tex>-анализа</font>
  '''function''' <tex>\mathtt{getLR1LexTable}(G'):</tex>
+
  '''function''' <tex>\mathtt{getLR1CanonicalTable}(\Gamma'):</tex>
     <tex> C'(G') \leftarrow \{I_0,I_1..I_n\}</tex> <font color=green>// множество канонических ситуаций для <tex>G'</tex></font>
+
     <tex> C'(\Gamma') \leftarrow \{I_0,I_1..I_n\}</tex> <font color=green>// множество канонических ситуаций для <tex>\Gamma'</tex></font>
     <tex>\mathtt{fillArray}(ACTION,</tex> '''Error'''<tex> ):</tex>
+
     <tex>\mathtt{fillArray}(T,</tex> '''Error'''<tex> ):</tex>
 
     '''foreach''' <tex>I_i \in (E(G))\</tex>
 
     '''foreach''' <tex>I_i \in (E(G))\</tex>
         '''if''' <tex>[A\rightarrow \alpha\cdot a\beta, b] \in I_i</tex> '''and''' <tex>GOTO(I_i,a) = I_j</tex> <font color=green>// здесь <tex>a</tex> {{---}} терминал</font>
+
         '''if''' <tex>[A\rightarrow \alpha\cdot a\beta, b] \in I_i</tex> '''and''' <tex>goto(I_i,a) = I_j</tex> <font color=green>// здесь <tex>a</tex> {{---}} терминал</font>
             <tex>ACTION[i,a] = </tex> '''Shift'''(<tex>j</tex>)
+
             <tex>T[i,a] = </tex> '''Shift'''(<tex>j</tex>)
 
         '''if''' <tex>[A\rightarrow \alpha\cdot, a] \in I_i</tex> '''and''' <tex>A\neq S'</tex>  
 
         '''if''' <tex>[A\rightarrow \alpha\cdot, a] \in I_i</tex> '''and''' <tex>A\neq S'</tex>  
             <tex>ACTION[i,a] = </tex> '''Reduce'''(<tex>A  \to a</tex>)
+
             <tex>T[i,a] = </tex> '''Reduce'''(<tex>A  \to a</tex>)
         '''if''' <tex>[S'\rightarrow S\cdot, \char36] \in I_i</tex>
+
         '''if''' <tex>[S'\rightarrow S\cdot, \$] \in I_i</tex>
             <tex>ACTION[i,\char36] = </tex> '''Accept'''
+
             <tex>T[i,\$] = </tex> '''Accept'''
         '''if''' <tex>GOTO(I_i,A) = I_j</tex>
+
         '''if''' <tex>goto(I_i,A) = I_j</tex>
             <tex>GOTO[i,A]\leftarrow j</tex>
+
             <tex>goto[i,A]\leftarrow j</tex>
 
Если в процессе построения обнаружатся конфликтующие действия {{---}} это значит, что грамматика не принадлежит классу LR(1)
 
Если в процессе построения обнаружатся конфликтующие действия {{---}} это значит, что грамматика не принадлежит классу LR(1)
  
Строка 193: Строка 190:
  
 
==== Пример ====
 
==== Пример ====
<wikitex>
+
Рассмотрим следующую грамматику $\Gamma$:
Рассмотрим следующую грамматику $G$:
 
 
# $S\rightarrow CC$
 
# $S\rightarrow CC$
 
# $C\rightarrow cC$
 
# $C\rightarrow cC$
 
# $C\rightarrow d$
 
# $C\rightarrow d$
Приведем каноническую таблицу синтаксического анализа для этой грамматики:
+
Приведем каноническую таблицу синтаксического анализа <tex>T</tex> для этой грамматики:
{| cellspacing="0" cellpadding="10" align="left" border="1"
+
{| style="background-color:#CCC;margin:0.5px"
! rowspan="2" style="background-color:#EEE;text-align:center"| Состояние
+
! style="background-color:#EEE;text-align:center"|
! colspan="3" style="background-color:#EEE;text-align:center" | $ACTION$
+
!style="background-color:#EEE;padding:2px 20px;text-align:center"|$S$
! colspan="2" style="background-color:#EEE;text-align:center" |$GOTO$
+
!style="background-color:#EEE;padding:2px 20px;text-align:center"|$C$
 +
!style="background-color:#EEE;padding:2px 20px;text-align:center"|$c$
 +
!style="background-color:#EEE;padding:2px 20px;text-align:center"|$d$
 +
!style="background-color:#EEE;padding:2px 20px;text-align:center"|$\$$
 
|-
 
|-
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$c$
+
|style="background-color:#EEE;padding:2px 20px;text-align:center"|$0$
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$d$
+
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$1$
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$\char36$
+
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$2$
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$S$
 
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$C$
 
|-
 
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$0$
 
 
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$s(3)$
 
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$s(3)$
 
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$s(4)$
 
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$s(4)$
 
|style="background-color:#FFF;padding:2px 20px"|
 
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$1$
 
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$2$
 
 
|-
 
|-
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$1$
+
|style="background-color:#EEE;padding:2px 20px;text-align:center"|$1$
 
|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 10px;text-align:center"| '''Accept'''
 
 
|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 10px;text-align:center"| '''Accept'''
 
|-
 
|-
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$2$
+
|style="background-color:#EEE;padding:2px 20px;text-align:center"|$2$
 +
|style="background-color:#FFF;padding:2px 20px"|
 +
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$5$
 
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$s(6)$
 
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$s(6)$
 
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$s(7)$
 
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$s(7)$
 
|style="background-color:#FFF;padding:2px 20px"|
 
|style="background-color:#FFF;padding:2px 20px"|
 +
|-
 +
|style="background-color:#EEE;padding:2px 20px;text-align:center"|$3$
 
|style="background-color:#FFF;padding:2px 20px"|
 
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$5$
+
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$8$
|-
 
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$3$
 
 
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$s(3)$
 
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$s(3)$
 
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$s(4)$
 
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$s(4)$
 +
|style="background-color:#FFF;padding:2px 20px"|
 +
|-
 +
|style="background-color:#EEE;padding:2px 20px;text-align:center"|$4$
 
|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;text-align:center"|$8$
 
|-
 
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$4$
 
 
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$r(1)$
 
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$r(1)$
 
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$r(3)$
 
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$r(3)$
 
|style="background-color:#FFF;padding:2px 20px"|
 
|style="background-color:#FFF;padding:2px 20px"|
 +
|-
 +
|style="background-color:#EEE;padding:2px 20px;text-align:center"|$5$
 
|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;text-align:center"|$5$
 
 
|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;text-align:center"|$r(1)$
 
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$r(1)$
 +
|-
 +
|style="background-color:#EEE;padding:2px 20px;text-align:center"|$6$
 
|style="background-color:#FFF;padding:2px 20px"|
 
|style="background-color:#FFF;padding:2px 20px"|
 +
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$9$
 +
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$s(6)$
 +
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$s(7)$
 
|style="background-color:#FFF;padding:2px 20px"|
 
|style="background-color:#FFF;padding:2px 20px"|
 
|-
 
|-
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$6$
+
|style="background-color:#EEE;padding:2px 20px;text-align:center"|$7$
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$s(6)$
 
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$s(7)$
 
 
|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;text-align:center"|$9$
 
|-
 
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$7$
 
 
|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;text-align:center"|$r(3)$
 
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$r(3)$
 +
|-
 +
|style="background-color:#EEE;padding:2px 20px;text-align:center"|$8$
 
|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;text-align:center"|$8$
 
 
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$r(2)$
 
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$r(2)$
 
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$r(2)$
 
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$r(2)$
 
|style="background-color:#FFF;padding:2px 20px"|
 
|style="background-color:#FFF;padding:2px 20px"|
 +
|-
 +
|style="background-color:#EEE;padding:2px 20px;text-align:center"|$9$
 
|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;text-align:center"|$9$
 
 
|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;text-align:center"|$r(2)$
 
|style="background-color:#FFF;padding:2px 20px;text-align:center"|$r(2)$
|style="background-color:#FFF;padding:2px 20px"|
 
|style="background-color:#FFF;padding:2px 20px"|
 
 
|}
 
|}
</wikitex>
+
<br clear="left">
  
 
== См. также ==
 
== См. также ==
Строка 294: Строка 287:
 
* [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)-анализ ]
  
[[Категория: Теория формальных языков]]
+
[[Категория: Методы трансляции]]
[[Категория: Контекстно-свободные грамматики]]
+
[[Категория: Восходящий разбор]]

Версия 22:12, 4 декабря 2021

В некоторых случаях SLR-разбор может выдать неправильный результат. В таких случаях используют более сложные методы, такие как LR(1) и LALR-разбор. Рассмотрим первый из них.

Отличия от SLR-разбора

Основным отличием LR(1)-разбора от SLR-разбора является использование предпросмотра (англ. lookahead) символов.

Приведём пример, при котором SLR-разбор не справится с задачей:

Рассмотрим грамматику вида: $ S \to L=R \mid R \\ L \to *R \mid id \\ R \to L $

Покажем её канонический LR(0)-набор:

$I_0$ $I_1$ $I_2$ $I_3$ $I_4$ $I_5$ $I_6$ $I_7$ $I_8$ $I_9$

$S' \to \cdot S \\ S \to \cdot L = R \\ S \to \cdot R \\ L \to \cdot * R \\ L \to \cdot id \\ R \to \cdot L$

$S' \to S \cdot$

$S \to L \cdot = R \\ R \to L \cdot$

$S \to R \cdot$

$L \to * \cdot R \\ R \to \cdot L \\ L \to \cdot * R \\ L \to \cdot id$

$L \to id \cdot$

$S \to L = \cdot R \\ R \to \cdot L \\ L \to \cdot * R \\ L \to \cdot id$

$L \to * R \cdot$

$R \to L \cdot$

$S \to L = R \cdot$

Рассмотрим состояние $I_2$. Если SLR-парсер находится в $I_2$ и очередной входной символ равен $=$, то парсер выполняет свёртку в соответствии с ситуацией $R \to L$, что неверно, т.к. в этой грамматике не выводится выражение $R=\ldots$ и парсер должен был выполнить перенос, а не свёртку.

Чтобы решить эту проблему, необходимо хранить в ситуации больший объём информации, который позволит не делать таких ошибочных свёрток.

Канонические LR(1)-ситуации

Основная идея заключается в том, чтобы хранить в ситуациях (англ. items) больше информации, чтобы не производить некорректных свёрток.

Добавим в ситуацию второй компонент: терминальный символ. Таким образом, LR(1)-ситуации будут выглядеть следующим образом:

$[A\rightarrow\alpha\cdot\beta, a]$, где первая часть — продукция, а вторая — терминал или маркер конца входной строки $\$$. Здесь $a$ называется предпросмотром ситуации, а число $1$ в LR(1) означает его длину. Теперь мы будем выполнять свёртку в соответствии с продукцией $A\rightarrow\alpha$, только в том случае, если находимся в ситуации $[A\rightarrow\alpha\cdot\beta, a]$, и $a$ — входной символ.

Определение:
Назовём LR(1)-ситуацию $[A\rightarrow\alpha\cdot\beta, a]$ допустимой (англ. valid) для активного префикса $\gamma$, если существует правое порождение $S\Rightarrow^{*}\delta A w\Rightarrow\delta\alpha\beta w$, где верно одно из трёх: либо $\gamma=\delta\alpha$, либо $a$ является первым символом $w$, либо$w=\varepsilon$ и $a=\$$.

Построение множеств LR(1)-ситуаций

Метод построения похож на метод для $LR(0)$-разбора, с двумя изменёнными функциями: $closure(I)$ — замыкание множества ситуаций, и $goto(X,I)$ — функция переходов в автомате по символу $X$.

Лемма:
$$\forall{b} \mid b\in FIRST(\beta\alpha): [A\rightarrow\alpha\cdot B\beta, a]\in I\Rightarrow [B\rightarrow\cdot\gamma, b]\in closure(I)$$ Другими словами, при построении замыкания вторая часть добавленных ситуаций должна принадлежать $FIRST(\beta\alpha)$
Доказательство:
[math]\triangleright[/math]

Рассмотрим ситуацию вида $[A\rightarrow\alpha\cdot B\beta, a]$ в множестве ситуаций, допустимых для некоторого активного префикса $\gamma$. Тогда существует правое порождение $S\Rightarrow^{*}\delta Aax\Rightarrow\delta\alpha B\beta ax$, где $\gamma=\delta\alpha$. Предположим, что $\beta ax$ порождает строку терминалов $by$. Тогда для каждой продукции вида $\forall{B\rightarrow\eta}\exists{\eta}$ мы имеем порождение $ S\Rightarrow^{*}\delta Bby\Rightarrow\delta\eta by$. Таким образом, $[B\rightarrow\cdot\eta,b]$ является допустимым для $\gamma$. Заметим, что $b$ может быть первым терминалом, порожденным из $\beta$, либо, возможно что $\beta$ порождает $\varepsilon$ слева: $\beta ax\Rightarrow^{*}by$, следовательно $b=a$. Таким образом, $b\in FIRST(\beta ax)$. Поскольку $x$ не может содержать первый терминал из $by$, то $FIRST(\beta ax)=FIRST(\beta a)$

Значит, $b\in FIRST(\beta a)$.
[math]\triangleleft[/math]

Псевдокод

Псевдокод построения множеств $closure$ и $goto$, а также множества наборов ситуаций $items$ для грамматики $\Gamma' =\langle\Sigma, N, S, P\rangle$:

 item[] closure(item[] [math]I[/math]):
     bool changed
     item[] [math]J = I[/math]
     repeat
         changed = false
         for [math][A\rightarrow\alpha\cdot B\beta, a]\in I[/math]
             for [math](B\rightarrow\gamma)\in \Gamma'.P[/math]
                 for [math]b\in FIRST(\beta\alpha)[/math]
                     [math]J[/math].add([math][B\rightarrow\cdot\gamma,b][/math])
                     changed = true
     until not changed
     return [math]J[/math]
 item[] goto(item[] [math]I[/math], char [math]X[/math]):
     item[] [math]J=\varnothing[/math]
     for [math][A\rightarrow\alpha\cdot X\beta, a]\in I[/math]
         [math]J[/math].add([math][A\rightarrow\alpha X\cdot\beta, a][/math])
     return [math]closure(J)[/math]
 item[][] items([math]\Gamma'[/math]):
     bool changed
     item[][] [math]C[/math]
     [math]C[/math].add([math]closure(\{[S'\rightarrow\cdot S,\$]\})[/math])
     repeat
         changed = false
         for item[] [math]I\subset C[/math]
             for [math]X \in \Gamma'.\Sigma[/math]
                 if [math]goto(I,X)\neq\varnothing[/math] and [math]goto(I,X)\not\subset C[/math]
                     [math]C[/math].add([math]goto(I,X)[/math])
                     changed = true
     until not changed
     return [math]C[/math]

Пример

Рассмотрим следующую грамматику $\Gamma'$:

  • $S'\rightarrow S$
  • $S\rightarrow CC$
  • $C\rightarrow cC\mid d$

Запустим процедуру $items(\Gamma')$. Она начинается с вычисления $closure([S\rightarrow S', \$])$. Это правило вида $[A\rightarrow\alpha\cdot B\beta, a]$, где $A=S';\alpha=\varepsilon;B=S;\beta=\varepsilon;a=\$$.

Т.к. в таком случае $FIRST(\beta\alpha) = {\$}$, то мы добавим только правило $[S\rightarrow\cdot CC,\$]$.

Продолжив вычислять замыкание таким образом, мы добавим во множество ситуаций $[C\rightarrow\cdot C, c]$, $[C\rightarrow\cdot C, d]$, $C\rightarrow\cdot d, c]$ и $[C\rightarrow\cdot d, d]$. Поскольку ни одна из новых ситуаций не имеет вид $[A\rightarrow\alpha\cdot B\beta, a]$ (справа от точки во всех ситуациях терминалы), то функция $closure()$ завершает свою работу.

Начальное множество ситуаций в данном случае равно:

Рис. 1 Множества ситуаций и переходы между ними
  • $$I_0: \{[S'\rightarrow \cdot S, \$],[S\rightarrow\cdot CC,\$],[C\rightarrow\cdot C, c/d],[C\rightarrow\cdot d, c/d]\}$$

Следующим шагом процедуры $items()$ будет вычисление функции переходов автомата $goto(I_0,X)$ для всех символов $X$ грамматики $\Gamma'$:

  1. При $X=S$:
    $$closure({[S'\rightarrow S\cdot,\$]}) = \varnothing$$
    Мы не добавили ни одной ситуации, т.к. точка является крайней справа. Таким образом,
    • $$I_1: \{[S'\rightarrow S\cdot,\$]\}$$
  2. При $X=C$:
    $$I_2 = closure(\{[S\rightarrow C\cdot C,\$]\})$$
    • $$I_2 = \{[S\rightarrow C\cdot C,\$],[C\rightarrow\cdot cC,\$],[C\rightarrow\cdot d,\$]\}$$
  3. При $X=c$:
    $$I_3 = closure(\{[C\rightarrow c\cdot C,c/d]\})$$
    • $$I_3 = \{[C\rightarrow c\cdot C,c/d],[C\rightarrow\cdot cC,c/d],[C\rightarrow\cdot d,c/d]\}$$
  4. При $X=d$:
    $$I_4 = closure(\{[C\rightarrow d\cdot ,c/d]\})$$
    • $$I_4 = \{[C\rightarrow d\cdot,c/d]\}$$

На этом завершается выполнение цикла из процедуры $items$ для $I_0$. $$goto(I_1, *)=\varnothing$$

  • $$I_5=goto(I_2, C) = closure(\{[S\rightarrow CC\cdot,\$]\})=\{[S\rightarrow CC\cdot,\$]\}$$
$$I_6=goto(I_2, c) = closure(\{[C\rightarrow c\cdot C,\$]\})$$
  • $$I_6=\{[C\rightarrow c\cdot C,\$],[C\rightarrow \cdot cC,\$],[C\rightarrow \cdot d,\$]\}$$

NB: Обратим внимание, что $I_6$ отличается от $I_3$ только правыми частями ситуаций. Такое явление является частым в LR(1)-анализе, из-за него результирующая таблица будет неоправданно большой. LALR-анализ борется с этим явлением.

  • $$I_7 = goto(I_2, d) = closure(\{[C\rightarrow d\cdot ,\$]\}) = \{[C\rightarrow d\cdot ,\$]\}$$

На этом рассмотрение $goto(I_2)$ завершено, переходим к $goto(I_3)$:

  • $$I_8 = goto(I_3, C) = closure(\{[C\rightarrow cC\cdot ,c/d]\}) = \{[C\rightarrow cC\cdot ,c/d]\}$$

В множествах $I_4$ и $I_5$ все ситуации имеют точки в крайнем положении справа, следовательно эти множества не имеют $goto$: $$goto(I_6, c) = I_6$$ $$goto(I_6, d) = I_7$$

  • $$I_9 = goto(I_6, C) = \{[C\rightarrow cC\cdot,\$]\}$$

Остальные множества ситуаций не дают нам значений $goto$, процедура $items()$ завершает работу.

Канонические LR(1)-таблицы

В алгоритме будут использоваться структуры, описанные в конспекте про про LR(k)-грамматики

Алгоритм

// вход: [math]\Gamma'[/math] — расширенная грамматика
// выход: таблица [math]T[/math] канонического [math]LR(1)[/math]-анализа
function [math]\mathtt{getLR1CanonicalTable}(\Gamma'):[/math]
   [math] C'(\Gamma') \leftarrow \{I_0,I_1..I_n\}[/math] // множество канонических ситуаций для [math]\Gamma'[/math]
   [math]\mathtt{fillArray}(T,[/math] Error[math] ):[/math]
   foreach [math]I_i \in (E(G))\[/math]
       if [math][A\rightarrow \alpha\cdot a\beta, b] \in I_i[/math] and [math]goto(I_i,a) = I_j[/math] // здесь [math]a[/math] — терминал
           [math]T[i,a] = [/math] Shift([math]j[/math])
       if [math][A\rightarrow \alpha\cdot, a] \in I_i[/math] and [math]A\neq S'[/math] 
           [math]T[i,a] = [/math] Reduce([math]A  \to a[/math])
       if [math][S'\rightarrow S\cdot, \$] \in I_i[/math]
           [math]T[i,\$] = [/math] Accept
       if [math]goto(I_i,A) = I_j[/math]
           [math]goto[i,A]\leftarrow j[/math]

Если в процессе построения обнаружатся конфликтующие действия — это значит, что грамматика не принадлежит классу LR(1)

Таблица, построенная в результате применения алгоритм называется канонической таблицей LR(1)-анализа.

Пример

Рассмотрим следующую грамматику $\Gamma$:

  1. $S\rightarrow CC$
  2. $C\rightarrow cC$
  3. $C\rightarrow d$

Приведем каноническую таблицу синтаксического анализа [math]T[/math] для этой грамматики:

$S$ $C$ $c$ $d$ $\$$
$0$ $1$ $2$ $s(3)$ $s(4)$
$1$ Accept
$2$ $5$ $s(6)$ $s(7)$
$3$ $8$ $s(3)$ $s(4)$
$4$ $r(1)$ $r(3)$
$5$ $r(1)$
$6$ $9$ $s(6)$ $s(7)$
$7$ $r(3)$
$8$ $r(2)$ $r(2)$
$9$ $r(2)$


См. также

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