Изменения

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

<wikitex>Основным отличием $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$ и парсер должен был выполнить перенос, а не свёртку.

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

== Канонические LR(1)-ситуации ==Основная идея заключается в том, чтобы хранить в ситуациях (англ. ''items'') больше информации, чтобы не производить некорректных свёрток.  Добавим в ситуацию второй компонент: терминальный символ. Таким образом, 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=\epsilonvarepsilon$ и $a=\char36$$.

</wikitex>=== Построение множеств LR(1)-пунктов ситуаций ===<wikitex>Метод построения похож на метод для $LR(0)$ - разбора, с двумя изменёнными функциями: $CLOSUREclosure(I)$ {{--- }} замыкание множества пунктовситуаций, и $GOTOgoto(X,I)$ {{--- }} функция переходов в автомате по символу $X$.

|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 CLOSUREclosure(I)$$Другими словами, при построении замыкания вторая часть добавленных пунктов ситуаций должна принадлежать $FIRST(\beta\alpha)$|proof= Рассмотрим пункт ситуацию вида $[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$ порождает $\epsilonvarepsilon$ слева: $\beta ax\Rightarrow^{*}by$, следовательно $b=a$. Таким образом, $b\in FIRST(\beta ax)$. Поскольку $x$ не может содержать первый терминал из $by$, то $FIRST(\beta ax)=FIRST(\beta a)$

<wikitex>Псевдокод построения множеств $CLOSUREclosure$ и $GOTOgoto$, а также множества пунктов наборов ситуаций $items$ для грамматики $\Gamma' =\langle\Sigma, N, S, P\rangle$:<code> Set'''item'''[] closure('''item'''[] <Itemtex> CLOSURE(SetI<Item/tex> I): '''bool''' changed; Set'''item'''[] <Itemtex> $J$=$I$; </tex>

changed = '''false'''; '''for''' $<tex>[A\rightarrow\alpha\cdot B\beta, a]\in I$</tex> '''for''' $<tex>(B\rightarrow\gamma)\in G\Gamma'$.P</tex> '''for''' $<tex>b\in FIRST(\beta\alpha)$</tex> <tex>J</tex>.add($<tex>[B\rightarrow\cdot\gamma,b]$</tex>); changed = '''true''' '''untilnot''' !changed; '''return''' <tex>J;</codetex><code> Set'''item'''[] goto('''item'''[] <Itemtex> GOTO(SetI<Item/tex> I, '''char''' <tex>X</tex>): Set'''item'''[] <Itemtex> $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''' $CLOSURE<tex>closure(J)$;</codetex><code> Set'''item'''[][] items(<Settex>\Gamma'<Item/tex>> items($G'$): '''bool''' changed; Set'''item'''[][] <Settex>C<Item/tex> <tex> $C$ = $</tex>.add(<tex>closure(\{CLOSURE({[S'\rightarrow\cdot S,\char36$]\})\}$; </tex>)

changed = '''false'''; '''for''' Set'''item'''[] <Itemtex> $I\subset C$</tex> '''for''' $<tex>X \in symbols(G\Gamma')$ <font color="green">//по всем символам грамматики.\Sigma</fonttex> '''if''' $GOTO<tex>goto(I,X)\neq\varnothing$ </tex> '''and $GOTO''' <tex>goto(I,X)\not\subset C$</tex> <tex>C</tex>.add($GOTO<tex>goto(I,X)$</tex>); changed = '''true''' '''untilnot''' !changed; '''return''' <tex>C;</codetex></wikitex>

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

* $SC\rightarrow cC|\mid d$Запустим процедуру $items(G\Gamma')$. Она начинается с вычисления $CLOSUREclosure([S\rightarrow S', \char36$])$. Это правило вида $[A\rightarrow\alpha\cdot B\beta, a]$, где $A=S';\alpha=\epsilonvarepsilon;B=S;\beta=\epsilonvarepsilon;a=\char36$$.  Т.к. в таком случае $FIRST(\beta\alpha) = {\char36$}$, то мы добавим только правило $[S\rightarrow\cdot CC,\char36$]$. Продолжив вычислять замыкание таким образом, мы добавим во множество ситуаций $[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: \{[CS'\rightarrow\cdot CS, c\$]$, $C[S\rightarrow\cdot CCC, d\$]$, $[C\rightarrow\cdot dC, c/d]$, и $[C\rightarrow\cdot d, c/d]\}$. Т.к. ни один из новых пунктов не имеет вид $[A\rightarrow\alpha\cdot B\beta, a]Следующим шагом процедуры $ items(справа от точки во всех пунктах терминалы)$ будет вычисление функции переходов автомата $goto(I_0, то функция X)$ для всех символов $CLOSUREX$ грамматики $\Gamma'$ завершает свою работу и начальное множество пунктов в данном случае равно:

#При $X=S$:#:$$closure({[[ФайлS'\rightarrow S\cdot,\$]}) = \varnothing$$#:lr1_setsМы не добавили ни одной ситуации, т.png|400px|thumb|Риск. 1 Множества пунктов и их переходы]точка является крайней справа. Таким образом, #:*$$I_1: \{[S'\rightarrow S\cdot,\$]\}$$#При $X=C$I_0: #:$$I_2 = closure(\{[S'\rightarrow C\cdot C,\$]\})$$#:*$$I_2 = \{[S\rightarrow C\cdot C, \char36$],[SC\rightarrow\cdot cC,\$],[C\rightarrow\cdot CCd,\char36$]\}$$#При $X=c$:#:$$I_3 = closure(\{[C\rightarrow c\cdot C,c/d]\})$$#:*$$I_3 = \{[C\rightarrowc\cdot C,c/d],[C\rightarrow\cdot cC, c/d],[C\rightarrow\cdot d, c/d]\}$$Следующим шагом процедуры #При $itemsX=d$:#:$ будет вычисление функции переходов автомата $GOTOI_4 = closure(I_0\{[C\rightarrow d\cdot ,Xc/d]\})$ для всех символов $X#:*$ грамматики $G'I_4 = \{[C\rightarrow d\cdot,c/d]\}$$:

$$GOTOgoto(I_1, *)=\varnothing$$*$$I_5 = GOTOgoto(I_2, C) = CLOSUREclosure(\{[S\rightarrow CC\cdot,\char36$]\})=\{[S\rightarrow CC\cdot,\char36$]\}$$:$$I_6 = GOTOgoto(I_2, c) = CLOSUREclosure(\{[C\rightarrow c\cdot C,\char36$]\})$$*$$I_6=\{[C\rightarrow c\cdot C,\char36$],[C\rightarrow \cdot cC,\char36$],[C\rightarrow \cdot d,\char36$]\}$$ '''NB:''' Обратим внимание, что $I_6$ отличается от $I_3$ только правыми частями пунктовситуаций. Такое явление является частым в $LR(1)$-анализе, из-за него результирующая таблица будет неоправданно большой. $LALR$-анализ борется с этим явлением.Продолжим:*$$I_7 = GOTOgoto(I_2, d) = CLOSUREclosure(\{[C\rightarrow d\cdot ,\char36$]\}) = \{[C\rightarrow d\cdot ,\char36$]\}$$На этом рассмотрение $GOTOgoto(I_2)$ завершено, переходим к $GOTOgoto(I_3)$:*$$I_8 = GOTOgoto(I_3, C) = CLOSUREclosure(\{[C\rightarrow cC\cdot ,c/d]\}) = \{[C\rightarrow cC\cdot ,c/d]\}$$В множествах $I_4$ и $I_5$ все пункты ситуации имеют точки в крайнем положении справа, следовательно эти множества не имеют $GOTOgoto$ : $$GOTOgoto(I_6, c) = I_6$$$$GOTOgoto(I_6, d) = I_7$$*$$I_9 = GOTOgoto(I_6, C) = \{[C\rightarrow cC\cdot,\char36$]\}$$Остальные множества пунктов ситуаций не дают нам значений $GOTOgoto$, процедура $items()$ завершает работу. </wikitex>

<font color=green>// вход: <tex>G\Gamma'</tex> {{---}} расширенная грамматика</font> <font color=green>// выход: таблица канонического <tex>LRT</tex>-анализа с функциями канонического <tex>ACTION</tex> и <tex>GOTOLR(1)</tex>-анализа</font> '''function''' <tex>\mathtt{getLR1LexTablegetLR1CanonicalTable}(G\Gamma'):</tex> <tex> C'(G\Gamma') \leftarrow \{I_0,I_1..I_n\}</tex> <font color=green>// множество канонических пунктов ситуаций для <tex>G\Gamma'</tex></font> <tex>\mathtt{sortfillArray}(T,</tex> '''Error'''<tex> ):</tex> '''foreach''' <tex>I_i \in (E(G))\</tex> '''forif''' <tex>vu [A\rightarrow \alpha\cdot a\beta, b] \in EI_i</tex> '''and''' <tex>goto(GI_i,a)= I_j</tex> <font color=green>// здесь <tex>a</tex> {{---}} терминал</font> <tex>T[i,a] = </tex> '''Shift'''(<tex>j</tex>) '''if''' <tex>v[A\rightarrow \alpha\cdot, a] \in I_i</tex> и '''and''' <tex>uA\neq S'</tex> в разных компонентах связности <tex>T[i,a] = </tex> '''Reduce'''(<tex>FA \to a</tex>) '''if''' <tex> [S'\mathtt{F}rightarrow S\ =cdot, \ $] \mathtt{F} \bigcup vuin I_i</tex> <tex>T[i,\$] = </tex>'''Accept''' '''returnif''' <tex> goto(I_i,A) = I_j</tex> <tex>goto[i,A]\mathtt{F} leftarrow j</tex>Если в процессе построения обнаружатся конфликтующие действия {{---}} это значит, что грамматика не принадлежит классу LR(1) Таблица, построенная в результате применения алгоритм называется ''канонической таблицей'' LR(1)-анализа.

<wikitex>Рассмотрим следующую грамматику $G'\Gamma$:* # $S'\rightarrow SCC$* # $SC\rightarrow CCcC$* # $SC\rightarrow cCd$Приведем каноническую таблицу синтаксического анализа <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"|$items\$$|-|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(G3)$|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"|$CLOSUREs([S\rightarrow S', \char36]6)$. Это правило вида |style="background-color:#FFF;padding:2px 20px;text-align:center"|$s(7)$[A\rightarrow\alpha\cdot B\beta, a]|style="background-color:#FFF;padding:2px 20px"||-|style="background-color:#EEE;padding:2px 20px;text-align:center"|$, где 7$A|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=S'"background-color:#FFF;padding:2px 20px;\alphatext-align:center"|$r(3)$|-|style=\epsilon"background-color:#EEE;padding:2px 20px;Btext-align:center"|$8$|style=S"background-color:#FFF;\betapadding:2px 20px"||style=\epsilon"background-color:#FFF;apadding:2px 20px"||style=\char36"background-color:#FFF;padding:2px 20px;text-align:center"|$r(2)$. Т.к. в таком случае |style="background-color:#FFF;padding:2px 20px;text-align:center"|$FIRSTr(\beta\alpha2) $|style="background-color:#FFF;padding:2px 20px"||-|style= {\char36}"background-color:#EEE;padding:2px 20px;text-align:center"|$, то мы добавим только правило 9$[S\rightarrow\cdot CC,\char36]|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">

Продолжив вычислять замыкание таким образом, мы добавим во множество пунктов $== См. также ==* [[C\rightarrow\cdot CLL(k)-грамматики, cмножества FIRST и FOLLOW]$, $C\rightarrow\cdot C, d]$, $C\rightarrow\cdot d, c* [[LR(k)-грамматики]$, и $C\rightarrow\cdot d, d]$. Т.к. ни один из новых пунктов не имеет вид $* [[A\rightarrow\alpha\cdot B\beta, aLR(0)-разбор]]$ * [[SLR(справа от точки во всех пунктах терминалы1), то функция $CLOSURE$ завершает свою работу и начальное множество пунктов в данном случае равно:-разбор]]* [[LALR-разбор]]

== Источники информации ==* Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс, 2003. Стр. 331-338.* [[Файлhttp:lr1_sets//window.edu.ru/resource/974/69974/files/lang_trans.pdf Б.К.png|400px|thumb|РисМартыненко. 1 Множества пунктов Языки и их переходы]трансляции. Стр. 198-223]$$I_0* [http: \{[S'\rightarrow \cdot S, \char36],[S\rightarrow\cdot CC,\char36],[C\rightarrow\cdot C, c/d]/gas-teach.narod.ru/au/tfl/tfl13.pdf Лекции по теории формальных языков,[C\rightarrow\cdot dLR(0)-, c/d]\}$$Следующим шагом процедуры $items$ будет вычисление функции переходов автомата $GOTOSLR(I_01)-,XLR(1)- и LALR(1)$ для всех символов $X$ грамматики $G'$:-анализ ]

При $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$. $$GOTO(I_1, *)=\varnothing$$$$I_5 = GOTO(I_2, C) = CLOSURE(\{[S\rightarrow CC\cdot,\char36]\})=\{[S\rightarrow CC\cdot,\char36Методы трансляции]\}$$$$I_6 = GOTO(I_2, c) = CLOSURE(\{[C\rightarrow c\cdot C,\char36]\})$$$$I_6=\{[C\rightarrow c\cdot C,\char36],[C\rightarrow \cdot cC,\char36],[C\rightarrow \cdot d,\char36]\}$$Обратим внимание, что $I_6$ отличается от $I_3$ только правыми частями пунктов. Такое явление является частым в $LR(1)$-анализе, из-за него результирующая таблица будет неоправданно большой. $LALR$-анализ борется с этим явлением.ПродолжимКатегория:$$I_7 = GOTO(I_2, d) = CLOSURE(\{[C\rightarrow d\cdot ,\char36Восходящий разбор]\}) = \{[C\rightarrow d\cdot ,\char36]\}$$На этом рассмотрение $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,\char36]\}$$Остальные множества пунктов не дают нам значений $GOTO$, процедура $items$ завершает работу. </wikitex>