Изменения

LR(1)-разбор

461 байт убрано, 01:59, 11 сентября 2016

опечатка в правиле грамматики

====Псевдокод====

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

<code>

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

changed = ''false''

'''for''' $[A\rightarrow\alpha\cdot B\beta, a]\in I$

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

'''for''' $b\in FIRST(\beta\alpha)$

$J$.add($[B\rightarrow\cdot\gamma,b]$)

changed = ''true''

'''untilnot''' ~~not~~ changed

'''return''' $J$

</code>

<code>

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

'''bool''' changed

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

'''repeat'''

changed = ''false''

'''for''' '''item'''[] $I\subset C$

'''for''' $X \in G\Gamma'.\Sigma$ ~~//по всем символам грамматики~~ '''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$

</code>

====Пример====

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

* $S'\rightarrow S$

* $S\rightarrow CC$

* $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]$.

[[Файл: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$:

$$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]\}$$

=== Канонические 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) грамматики]]

==== Алгоритм ====

// вход: <tex>G\Gamma'</tex> {{---}} расширенная грамматика // выход: ~~таблицы~~ таблица <tex>~~ACTION</tex> и <tex>GOTO~~T</tex> канонического <tex>LR(1)</tex>-анализа '''function''' <tex>\mathtt{~~getLR1LexTable~~getLR1CanonicalTable}(G\Gamma'):</tex> <tex> C'(G\Gamma') \leftarrow \{I_0,I_1..I_n\}</tex> // множество канонических ситуаций для <tex>G\Gamma'</tex> <tex>\mathtt{fillArray}(~~ACTION~~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~~goto(I_i,a) = I_j</tex> // здесь <tex>a</tex> {{---}} терминал <tex>~~ACTION~~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>~~ACTION~~T[i,a] = </tex> '''Reduce'''(<tex>A \to a</tex>)

'''if''' <tex>[S'\rightarrow S\cdot, \char36] \in I_i</tex>

<tex>~~ACTION~~T[i,\char36] = </tex> '''Accept''' '''if''' <tex>~~GOTO~~goto(I_i,A) = I_j</tex> <tex>~~GOTO~~goto[i,A]\leftarrow j</tex>

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

==== Пример ====

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

# $S\rightarrow CC$

# $C\rightarrow cC$

# $C\rightarrow d$

Приведем каноническую таблицу синтаксического анализа <tex>T</tex> для этой грамматики:{| ~~cellspacing~~style="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$! ~~rowspan~~style="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" | $~~ACTION~~d$! ~~colspan="2"~~ style="background-color:#EEE;padding:2px 20px;text-align:center" |$~~GOTO~~\char36$

|-

|style="background-color:#~~FFF~~EEE;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"|$S~~0$|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:#FFF;padding:2px 20px;text-align:center"|$s(3)$

|style="background-color:#FFF;padding:2px 20px;text-align:center"|$s(4)$