Изменения

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

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

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

S \to L=R | \mid R \\L \to *R | \mid id \\

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

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

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

== Канонические LR(1)-пункты ==Основная идея заключается в том, чтобы хранить в пунктах больше информации, чтобы не производить некорректных свёрток. Добавим в пункт ситуацию второй компонент: терминальный символ. Таким образом, $LR(1)$ -пункты ситуации будут выглядеть следующим образом:

$[A\rightarrow\alpha\cdot\beta, a]$, где первая часть {{- --}} продукция, а вторая {{- --}} терминал или маркер конца входной строки $\char36$$. Здесь $a$ называется '''предпросмотром (англ. ''lookahead'') пунктаситуации, а цифра число $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$.{{Лемма|id=lemmaclosure |statement= $$\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)$|proof= Рассмотрим ситуацию вида $[A\rightarrow\alpha\cdot B\beta, a]$ в множестве ситуаций, допустимых для некоторого активного префикса $\gamma$. Тогда существует правое порождение $S\Rightarrow^{* }\delta Aax\Rightarrow\delta\alpha B\beta ax$w, где $\gamma=\epsilondelta\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(\char36beta a)$Значит, $b\in FIRST(\beta a)$.

=== Построение =Псевдокод====Псевдокод построения множеств $closure$ и $goto$, а также множества наборов ситуаций $items$ для грамматики $\Gamma' =\langle\Sigma, N, S, P\rangle$: '''item'''[] closure('''item'''[] <tex>I</tex>): '''bool''' changed '''item'''[] <tex>J = I</tex> '''repeat''' changed = ''false'' '''for''' <tex>[A\rightarrow\alpha\cdot B\beta, a]\in I</tex> '''for''' <tex>(B\rightarrow\gamma)\in \Gamma'.P</tex> '''for''' <tex>b\in FIRST(\beta\alpha)</tex> <tex>J</tex>.add(<tex>[B\rightarrow\cdot\gamma,b]</tex>) changed = ''true'' '''until not''' changed '''return''' <tex>J</tex>  '''item'''[] goto('''item'''[] <tex>I</tex>, '''char''' <tex>X</tex>): '''item'''[] <tex>J=\varnothing</tex> '''for''' <tex>[A\rightarrow\alpha\cdot X\beta, a]\in I</tex> <tex>J</tex>.add(<tex>[A\rightarrow\alpha X\cdot\beta, a]</tex>) '''return''' <tex>closure(J)</tex>  '''item'''[][] items(<tex>\Gamma'</tex>): '''bool''' changed '''item'''[][] <tex>C</tex> <tex>C</tex>.add(<tex>closure(\{[S'\rightarrow\cdot S,\$]\})</tex>) '''repeat''' changed = ''false'' '''for''' '''item'''[] <tex>I\subset C</tex> '''for''' <tex>X \in \Gamma'.\Sigma</tex> '''if''' <tex>goto(I,X)\neq\varnothing</tex> '''and''' <tex>goto(I,X)\not\subset C</tex> <tex>C</tex>.add(<tex>goto(I,X)</tex>) changed = ''true'' '''until not''' changed '''return''' <tex>C</tex> ====Пример====Рассмотрим следующую грамматику $\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()$ завершает свою работу. Начальное множество ситуаций в данном случае равно: [[Файл: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]\}$$ На этом завершается выполнение цикла из процедуры $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)-грамматики]]==== Алгоритм ==== <font color=green>//wikitexвход: <tex>\Gamma'</tex> {{---}} расширенная грамматика</font> <font color=green>// выход: таблица <tex>T</tex> канонического <tex>LR(1)</tex>-анализа</font> '''function''' <tex>\mathtt{getLR1CanonicalTable}(\Gamma'):</tex> <tex> C'(\Gamma') \leftarrow \{I_0,I_1..I_n\}</tex> <font color=green>// множество канонических ситуаций для <tex>\Gamma'</tex></font> <tex>\mathtt{fillArray}(T,</tex> '''Error'''<tex> ):</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> <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> <tex>T[i,a] = </tex> '''Reduce'''(<tex>A \to a</tex>) '''if''' <tex>[S'\rightarrow S\cdot, \$] \in I_i</tex> <tex>T[i,\$] = </tex> '''Accept''' '''if''' <tex>goto(I_i,A) = I_j</tex> <tex>goto[i,A]\leftarrow j</tex>Если в процессе построения обнаружатся конфликтующие действия {{---}} это значит, что грамматика не принадлежит классу LR(1) Таблица, построенная в результате применения алгоритм называется ''канонической таблицей'' LR(1)-анализа. ==== Пример ====Рассмотрим следующую грамматику $\Gamma$:# $S\rightarrow CC$# $C\rightarrow cC$# $C\rightarrow d$Приведем каноническую таблицу синтаксического анализа <tex>T</tex> для этой грамматики:{| style="background-color:#CCC;margin:0.5px"! style="background-color:#EEE;text-align:center"| !style="background-color:#EEE;padding:2px 20px;text-align:center"|$S$!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:#EEE;padding:2px 20px;text-align:center"|$0$|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"|$s(3)$|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"|$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:#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(7)$|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;text-align:center"|$8$|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"||-|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;text-align:center"|$r(1)$|style="background-color:#FFF;padding:2px 20px;text-align:center"|$r(3)$|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"|$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;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:#EEE;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:#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;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:#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"|$r(2)$|}<br clear="left"> == См. также ==* [[LL(k)-грамматики, множества FIRST и FOLLOW]]* [[LR(k)-грамматики]]* [[LR(0)-разбор]]* [[SLR(1)-разбор]]* [[LALR-разбор]] == Источники информации ==* Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс, 2003. Стр. 331-338.* [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)-анализ ] [[Категория: Методы трансляции]][[Категория: Восходящий разбор]]