Изменения

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

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

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

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

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

Item'''item'''[] closure(Item'''item'''[] $I$):

Item'''item'''[] $J $ = $I $

changed = '''false'''

'''for''' $(B\rightarrow\gamma)\in G\Gamma'.P$

$J$.add($[B\rightarrow\cdot\gamma,b]$) changed = '''true''' '''untilnot''' not changed '''return''' $J$

Item'''item'''[] goto(Item'''item'''[] $I$, '''char''' $X$): Item'''item'''[] $J $=\varnothing$

$J$.add($[A\rightarrow\alpha X\cdot\beta, a]$)

Item'''item'''[][] items($G\Gamma'$):

Item'''item'''[][] $C = \{$ $C$.add($closure(\{[S'\rightarrow\cdot S,\char36]\})\}$)

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

Рассмотрим следующую грамматику $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=\varepsilon;B=S;\beta=\varepsilon;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\char36]$, $C[S\rightarrow\cdot CCC, d\char36]$, $[C\rightarrow\cdot dC, c/d]$, и $[C\rightarrow\cdot d, c/d]\}$. Т.к. ни одна из новых ситуаций не имеет вид $[A\rightarrow\alpha\cdot B\beta, a]Следующим шагом процедуры $ items(справа от точки во всех ситуациях терминалы)$ будет вычисление функции переходов автомата $goto(I_0, то функция X)$ для всех символов $X$closureграмматики $\Gamma'$ завершает свою работу и начальное множество ситуаций в данном случае равно:

#При $X=S$:#:$$closure({[[ФайлS'\rightarrow S\cdot,\char36]}) = \varnothing$$#:lr1_setsМы не добавили ни одной ситуации, т.png|400px|thumb|Риск. 1 Множества ситуаций и их переходы]точка является крайней справа. Таким образом, #:*$$I_1: \{[S'\rightarrow S\cdot,\char36]\}$$#При $X=C$I_0: #:$$I_2 = closure(\{[S'\rightarrow C\cdot C,\char36]\})$$#:*$$I_2 = \{[S\rightarrow C\cdot C,\char36],[C\rightarrow\cdot cC, \char36],[SC\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#:*$$ грамматики I_4 = \{[C\rightarrow d\cdot,c/d]\}$G'$:

*$$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()$ завершает работу.

В алгоритме будут использоваться структуры, описанные в конспекте про про [[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) грамматики]]

<font color=green>// вход: <tex>G\Gamma'</tex> {{---}} расширенная грамматика</font> <font color=green>// выход: таблицы таблица <tex>ACTION</tex> и <tex>GOTOT</tex> канонического <tex>LR(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>GOTOgoto(I_i,a) = I_j</tex> <font color=green>// здесь <tex>a</tex> {{---}} терминал</font> <tex>ACTIONT[i,a] = </tex> '''Shift'''(<tex>j</tex>)

<tex>ACTIONT[i,a] = </tex> '''Reduce'''(<tex>A \to a</tex>)

<tex>ACTIONT[i,\char36] = </tex> '''Accept''' '''if''' <tex>GOTOgoto(I_i,A) = I_j</tex> <tex>GOTOgoto[i,A]\leftarrow j</tex>

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

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

|style="background-color:#FFFEEE;padding:2px 20px;text-align:center"|$c$|style="background-color:#FFF;padding:2px 20px;text-align:center"|$d$|style="background-color:#FFF;padding:2px 20px;text-align:center"|$\char36$|style="background-color:#FFF;padding:2px 20px;text-align:center"|$S0$|style="background-color:#FFF;padding:2px 20px;text-align:center"|$C1$|-|style="background-color:#FFF;padding:2px 20px;text-align:center"|$02$

|style="background-color:#FFFEEE;padding:2px 20px;text-align:center"|$1$

|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"|$25$

|style="background-color:#FFF;padding:2px 20px;text-align:center"|$5$|-|style="background-color:#FFF;padding:2px 20px;text-align:center"|$38$

|style="background-color:#FFFEEE;padding:2px 20px;text-align:center"|$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)$

[[Категория: Теория формальных языковМетоды трансляции]][[Категория: Контекстно-свободные грамматикиВосходящий разбор]]