Изменения

LR(1)-разбор

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

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

changed = ''false''

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

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

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

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

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

'''bool''' changed

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

'''repeat'''

changed = ''false''

* $S'\rightarrow S$

* $S\rightarrow CC$

* $SC\rightarrow cC\mid d$

Запустим процедуру $items(\Gamma')$. Она начинается с вычисления $closure([S\rightarrow S', \char36])$. Это правило вида $[A\rightarrow\alpha\cdot B\beta, a]$, где $A=S';\alpha=\varepsilon;B=S;\beta=\varepsilon;a=\char36$.

=== Канонические LR(1)-таблицы ===

В алгоритме будут использоваться структуры, описанные в конспекте про про [[LLLR(k)-грамматики~~, множества FIRST и FOLLOW~~]]

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

// вход: <tex>\Gamma'</tex> {{---}} расширенная грамматика

// выход: ~~таблицы~~ таблица <tex>~~ACTION</tex> и <tex>GOTO~~T</tex> канонического <tex>LR(1)</tex>-анализа '''function''' <tex>\mathtt{~~getLR1LexTable~~getLR1CanonicalTable}(\Gamma'):</tex>

<tex> C'(\Gamma') \leftarrow \{I_0,I_1..I_n\}</tex> // множество канонических ситуаций для <tex>\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)$