Изменения

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

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

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

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

$[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(0)$-разбора, с двумя изменёнными функциями: $closure(I)$ {{---}} замыкание множества пунктовситуаций, и $goto(X,I)$ {{---}} функция переходов в автомате по символу $X$.

|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>Псевдокод построения множеств $closure$ и $goto$, а также множества наборов ситуаций $items$ для грамматики $\Gamma' =\langle\Sigma, N, S, P\rangle$:<code> Set<Item> '''item'''[] closure(Set'''item'''[] <Itemtex> I</tex>): '''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''' not changed; '''return''' <tex>J;</codetex><code> Set<Item> '''item'''[] goto(Set'''item'''[] <Itemtex> I</tex>, '''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''' $<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(\{[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''' $<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''' '''untilnot''' not changed; '''return''' <tex>C;</codetex></wikitex>

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

* $SC\rightarrow cC|\mid d$Запустим процедуру $items(G\Gamma')$. Она начинается с вычисления $closure([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()$ завершает свою работу.

Продолжив вычислять замыкание таким образом, мы добавим во множество ситуаций $[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, \char36$],[S\rightarrow\cdot CC,\char36$],[C\rightarrow\cdot C, c/d],[C\rightarrow\cdot d, c/d]\}$$Следующим шагом процедуры $items()$ будет вычисление функции переходов автомата $goto(I_0,X)$ для всех символов $X$ грамматики $G\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]\}$$

*$$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$]\}$$ '''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_8 = goto(I_3, C) = closure(\{[C\rightarrow cC\cdot ,c/d]\}) = \{[C\rightarrow cC\cdot ,c/d]\}$$В множествах $I_4$ и $I_5$ все ситуации имеют точки в крайнем положении справа, следовательно эти множества не имеют $goto$ :

*$$I_9 = goto(I_6, C) = \{[C\rightarrow cC\cdot,\char36$]\}$$Остальные множества ситуаций не дают нам значений $goto$, процедура $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{fillArray}(ACTIONT,</tex>"ошибка"'''Error'''<tex> ):</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>ACTIONT[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>ACTIONT[i,a] = </tex> "свертка '''Reduce'''(<tex>A \rightarrow to a</tex>") '''if''' <tex>[S'\rightarrow S\cdot, \char36$] \in I_i</tex> <tex>ACTIONT[i,\char36$] = </tex> "принятие"'''Accept'''

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

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

Приведем каноническую таблицу синтаксического анализа <tex>T</tex> для этой грамматики:{| cellspacingstyle="background-color:#CCC;margin:0.5px" cellpadding! style="10background-color:#EEE;text-align:center" align| !style="background-color:#EEE;padding:2px 20px;text-align:center" border|$S$!style="1background-color:#EEE;padding:2px 20px;text-align:center"|$C$! rowspanstyle="2background-color:#EEE;padding:2px 20px;text-align:center" | Состояние$c$! colspanstyle="3background-color:#EEE;padding:2px 20px;text-align:center" | $ACTIONd$! colspanstyle="2background-color:#EEE;padding:2px 20px;text-align:center" |$goto\$$

|style="background-color:#EEE;padding:2px 20px;text-align:center"|$c0$|style="background-color:#FFF;padding:2px 20px;text-align:center"|$d1$|style="background-color:#FFF;padding:2px 20px;text-align:center"|$\char362$|style="background-color:#FFF;padding:2px 20px;text-align:center"|$Ss(3)$|style="background-color:#FFF;padding:2px 20px;text-align:center"|$Cs(4)$|style="background-color:#FFF;padding:2px 20px"|

|style="background-color:#EEE;padding:2px 20px;text-align:center"|$01$|$s3$style="background-color:#FFF;padding:2px 20px"||$s4$style="background-color:#FFF;padding:2px 20px"||style="background-color:#FFF;padding:2px 20px"||$1$style="background-color:#FFF;padding:2px 20px"||$2$style="background-color:#FFF;padding:2px 10px;text-align:center"| '''Accept'''

|style="background-color:#EEE;padding:2px 20px;text-align:center"|$12$|style="background-color:#FFF;padding:2px 20px"||style="background-color:#FFF;padding:2px 20px;text-align:center"|$5$| style="fontbackground-color:#FFF;padding:2px 20px;text-align:center"|$s(6)$|style="background-color:italic#FFF;colorpadding:green2px 20px;text-align:center" | ok$s(7)$|style="background-color:#FFF;padding:2px 20px"|

|style="background-color:#EEE;padding:2px 20px;text-align:center"|$23$|style="background-color:#FFF;padding:2px 20px"||style="background-color:#FFF;padding:2px 20px;text-align:center"|$s68$|style="background-color:#FFF;padding:2px 20px;text-align:center"|$s7s(3)$|style="background-color:#FFF;padding:2px 20px;text-align:center"|$s(4)$|style="background-color:#FFF;padding:2px 20px"|$5$

|style="background-color:#EEE;padding:2px 20px;text-align:center"|$34$|style="background-color:#FFF;padding:2px 20px"||style="background-color:#FFF;padding:2px 20px"||style="background-color:#FFF;padding:2px 20px;text-align:center"|$s3r(1)$|style="background-color:#FFF;padding:2px 20px;text-align:center"|$s4r(3)$||style="background-color:#FFF;padding:2px 20px"|$8$

|style="background-color:#EEE;padding:2px 20px;text-align:center"|$45$|$r1$style="background-color:#FFF;padding:2px 20px"||$r3$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"|$56$|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"|$r1s(7)$|style="background-color:#FFF;padding:2px 20px"|

|style="background-color:#EEE;padding:2px 20px;text-align:center"|$67$|$s6$style="background-color:#FFF;padding:2px 20px"||$s7$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"|$9r(3)$

|style="background-color:#EEE;padding:2px 20px;text-align:center"|$78$|style="background-color:#FFF;padding:2px 20px"||style="background-color:#FFF;padding:2px 20px"||style="background-color:#FFF;padding:2px 20px;text-align:center"|$r3r(2)$|style="background-color:#FFF;padding:2px 20px;text-align:center"|$r(2)$|style="background-color:#FFF;padding:2px 20px"|

|$8$style="background-color:#EEE;padding:2px 20px;text-align:center"|$r29$|$r2$style="background-color:#FFF;padding:2px 20px"||style="background-color:#FFF;padding:2px 20px"||style="background-color:#FFF;padding:2px 20px"||$9$style="background-color:#FFF;padding:2px 20px"||style="background-color:#FFF;padding:2px 20px;text-align:center"|$r2r(2)$||

</wikitexbr clear="left"> == См. также ==* [[LL(k)-грамматики, множества FIRST и FOLLOW]]* [[LR(k)-грамматики]]* [[LR(0)-разбор]]* [[SLR(1)-разбор]]* [[LALR-разбор]]