LR(1)-разбор — различия между версиями
DK3!8 (обсуждение | вклад) м (Нормальное отображение latex) |
м (rollbackEdits.php mass rollback) |
||
(не показаны 3 промежуточные версии 2 участников) | |||
Строка 1: | Строка 1: | ||
− | |||
В некоторых случаях [[SLR(1)-разбор|SLR-разбор]] может выдать неправильный результат. В таких случаях используют более сложные методы, такие как LR(1) и [[LALR-разбор]]. Рассмотрим первый из них. | В некоторых случаях [[SLR(1)-разбор|SLR-разбор]] может выдать неправильный результат. В таких случаях используют более сложные методы, такие как LR(1) и [[LALR-разбор]]. Рассмотрим первый из них. | ||
− | |||
== Отличия от SLR-разбора == | == Отличия от SLR-разбора == | ||
− | |||
Основным отличием LR(1)-разбора от SLR-разбора является использование '''предпросмотра''' (англ. ''lookahead'') символов. | Основным отличием LR(1)-разбора от SLR-разбора является использование '''предпросмотра''' (англ. ''lookahead'') символов. | ||
Строка 64: | Строка 61: | ||
Чтобы решить эту проблему, необходимо хранить в ситуации больший объём информации, который позволит не делать таких ошибочных свёрток. | Чтобы решить эту проблему, необходимо хранить в ситуации больший объём информации, который позволит не делать таких ошибочных свёрток. | ||
− | |||
== Канонические LR(1)-ситуации == | == Канонические LR(1)-ситуации == | ||
− | |||
Основная идея заключается в том, чтобы хранить в ситуациях (англ. ''items'') больше информации, чтобы не производить некорректных свёрток. | Основная идея заключается в том, чтобы хранить в ситуациях (англ. ''items'') больше информации, чтобы не производить некорректных свёрток. | ||
Добавим в ситуацию второй компонент: терминальный символ. Таким образом, LR(1)-ситуации будут выглядеть следующим образом: | Добавим в ситуацию второй компонент: терминальный символ. Таким образом, LR(1)-ситуации будут выглядеть следующим образом: | ||
− | $[A\rightarrow\alpha\cdot\beta, a]$, где первая часть {{---}} продукция, а вторая {{---}} терминал или маркер конца входной строки $\ | + | $[A\rightarrow\alpha\cdot\beta, a]$, где первая часть {{---}} продукция, а вторая {{---}} терминал или маркер конца входной строки $\$$. Здесь $a$ называется '''предпросмотром''' ситуации, а число $1$ в LR(1) означает его длину. |
Теперь мы будем выполнять свёртку в соответствии с продукцией $A\rightarrow\alpha$, только в том случае, если находимся в ситуации $[A\rightarrow\alpha\cdot\beta, a]$, и $a$ {{---}} входной символ. | Теперь мы будем выполнять свёртку в соответствии с продукцией $A\rightarrow\alpha$, только в том случае, если находимся в ситуации $[A\rightarrow\alpha\cdot\beta, a]$, и $a$ {{---}} входной символ. | ||
{{Определение | {{Определение | ||
|id=defValid | |id=defValid | ||
|definition= | |definition= | ||
− | Назовём 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=\varepsilon$ и $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=\varepsilon$ и $a=\$$. |
}} | }} | ||
− | |||
=== Построение множеств LR(1)-ситуаций === | === Построение множеств LR(1)-ситуаций === | ||
− | |||
Метод построения похож на метод для $LR(0)$-разбора, с двумя изменёнными функциями: $closure(I)$ {{---}} замыкание множества ситуаций, и $goto(X,I)$ {{---}} функция переходов в автомате по символу $X$. | Метод построения похож на метод для $LR(0)$-разбора, с двумя изменёнными функциями: $closure(I)$ {{---}} замыкание множества ситуаций, и $goto(X,I)$ {{---}} функция переходов в автомате по символу $X$. | ||
{{Лемма | {{Лемма | ||
Строка 90: | Строка 83: | ||
Значит, $b\in FIRST(\beta a)$. | Значит, $b\in FIRST(\beta a)$. | ||
}} | }} | ||
− | |||
====Псевдокод==== | ====Псевдокод==== | ||
Псевдокод построения множеств $closure$ и $goto$, а также множества наборов ситуаций $items$ для грамматики | Псевдокод построения множеств $closure$ и $goto$, а также множества наборов ситуаций $items$ для грамматики | ||
Строка 128: | Строка 120: | ||
====Пример==== | ====Пример==== | ||
− | |||
Рассмотрим следующую грамматику $\Gamma'$: | Рассмотрим следующую грамматику $\Gamma'$: | ||
* $S'\rightarrow S$ | * $S'\rightarrow S$ | ||
* $S\rightarrow CC$ | * $S\rightarrow CC$ | ||
* $C\rightarrow cC\mid d$ | * $C\rightarrow cC\mid d$ | ||
− | Запустим процедуру $items(\Gamma')$. Она начинается с вычисления $closure([S\rightarrow S', \ | + | Запустим процедуру $items(\Gamma')$. Она начинается с вычисления $closure([S\rightarrow S', \$])$. Это правило вида $[A\rightarrow\alpha\cdot B\beta, a]$, где $A=S';\alpha=\varepsilon;B=S;\beta=\varepsilon;a=\$$. |
− | Т.к. в таком случае $FIRST(\beta\alpha) = {\ | + | Т.к. в таком случае $FIRST(\beta\alpha) = {\$}$, то мы добавим только правило $[S\rightarrow\cdot CC,\$]$. |
Продолжив вычислять замыкание таким образом, мы добавим во множество ситуаций $[C\rightarrow\cdot C, c]$, $[C\rightarrow\cdot C, d]$, $C\rightarrow\cdot d, c]$ и $[C\rightarrow\cdot d, d]$. | Продолжив вычислять замыкание таким образом, мы добавим во множество ситуаций $[C\rightarrow\cdot C, c]$, $[C\rightarrow\cdot C, d]$, $C\rightarrow\cdot d, c]$ и $[C\rightarrow\cdot d, d]$. | ||
Строка 143: | Строка 134: | ||
[[Файл:lr1_sets.png|400px|thumb|Рис. 1 Множества ситуаций и переходы между ними]] | [[Файл:lr1_sets.png|400px|thumb|Рис. 1 Множества ситуаций и переходы между ними]] | ||
− | *$$I_0: \{[S'\rightarrow \cdot S, \ | + | *$$I_0: \{[S'\rightarrow \cdot S, \$],[S\rightarrow\cdot CC,\$],[C\rightarrow\cdot C, c/d],[C\rightarrow\cdot d, c/d]\}$$ |
Следующим шагом процедуры $items()$ будет вычисление функции переходов автомата $goto(I_0,X)$ для всех символов $X$ грамматики $\Gamma'$: | Следующим шагом процедуры $items()$ будет вычисление функции переходов автомата $goto(I_0,X)$ для всех символов $X$ грамматики $\Gamma'$: | ||
#При $X=S$: | #При $X=S$: | ||
− | #:$$closure({[S'\rightarrow S\cdot,\ | + | #:$$closure({[S'\rightarrow S\cdot,\$]}) = \varnothing$$ |
#:Мы не добавили ни одной ситуации, т.к. точка является крайней справа. Таким образом, | #:Мы не добавили ни одной ситуации, т.к. точка является крайней справа. Таким образом, | ||
− | #:*$$I_1: \{[S'\rightarrow S\cdot,\ | + | #:*$$I_1: \{[S'\rightarrow S\cdot,\$]\}$$ |
#При $X=C$: | #При $X=C$: | ||
− | #:$$I_2 = closure(\{[S\rightarrow C\cdot C,\ | + | #:$$I_2 = closure(\{[S\rightarrow C\cdot C,\$]\})$$ |
− | #:*$$I_2 = \{[S\rightarrow C\cdot C,\ | + | #:*$$I_2 = \{[S\rightarrow C\cdot C,\$],[C\rightarrow\cdot cC,\$],[C\rightarrow\cdot d,\$]\}$$ |
#При $X=c$: | #При $X=c$: | ||
#:$$I_3 = closure(\{[C\rightarrow c\cdot C,c/d]\})$$ | #:$$I_3 = closure(\{[C\rightarrow c\cdot C,c/d]\})$$ | ||
Строка 162: | Строка 153: | ||
На этом завершается выполнение цикла из процедуры $items$ для $I_0$. | На этом завершается выполнение цикла из процедуры $items$ для $I_0$. | ||
$$goto(I_1, *)=\varnothing$$ | $$goto(I_1, *)=\varnothing$$ | ||
− | *$$I_5=goto(I_2, C) = closure(\{[S\rightarrow CC\cdot,\ | + | *$$I_5=goto(I_2, C) = closure(\{[S\rightarrow CC\cdot,\$]\})=\{[S\rightarrow CC\cdot,\$]\}$$ |
− | :$$I_6=goto(I_2, c) = closure(\{[C\rightarrow c\cdot C,\ | + | :$$I_6=goto(I_2, c) = closure(\{[C\rightarrow c\cdot C,\$]\})$$ |
− | *$$I_6=\{[C\rightarrow c\cdot C,\ | + | *$$I_6=\{[C\rightarrow c\cdot C,\$],[C\rightarrow \cdot cC,\$],[C\rightarrow \cdot d,\$]\}$$ |
'''NB:''' Обратим внимание, что $I_6$ отличается от $I_3$ только правыми частями ситуаций. Такое явление является частым в LR(1)-анализе, из-за него результирующая таблица будет неоправданно большой. LALR-анализ борется с этим явлением. | '''NB:''' Обратим внимание, что $I_6$ отличается от $I_3$ только правыми частями ситуаций. Такое явление является частым в LR(1)-анализе, из-за него результирующая таблица будет неоправданно большой. LALR-анализ борется с этим явлением. | ||
− | *$$I_7 = goto(I_2, d) = closure(\{[C\rightarrow d\cdot ,\ | + | *$$I_7 = goto(I_2, d) = closure(\{[C\rightarrow d\cdot ,\$]\}) = \{[C\rightarrow d\cdot ,\$]\}$$ |
На этом рассмотрение $goto(I_2)$ завершено, переходим к $goto(I_3)$: | На этом рассмотрение $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_8 = goto(I_3, C) = closure(\{[C\rightarrow cC\cdot ,c/d]\}) = \{[C\rightarrow cC\cdot ,c/d]\}$$ | ||
Строка 174: | Строка 165: | ||
$$goto(I_6, c) = I_6$$ | $$goto(I_6, c) = I_6$$ | ||
$$goto(I_6, d) = I_7$$ | $$goto(I_6, d) = I_7$$ | ||
− | *$$I_9 = goto(I_6, C) = \{[C\rightarrow cC\cdot,\ | + | *$$I_9 = goto(I_6, C) = \{[C\rightarrow cC\cdot,\$]\}$$ |
Остальные множества ситуаций не дают нам значений $goto$, процедура $items()$ завершает работу. | Остальные множества ситуаций не дают нам значений $goto$, процедура $items()$ завершает работу. | ||
− | |||
=== Канонические LR(1)-таблицы === | === Канонические LR(1)-таблицы === | ||
Строка 191: | Строка 181: | ||
'''if''' <tex>[A\rightarrow \alpha\cdot, a] \in I_i</tex> '''and''' <tex>A\neq S'</tex> | '''if''' <tex>[A\rightarrow \alpha\cdot, a] \in I_i</tex> '''and''' <tex>A\neq S'</tex> | ||
<tex>T[i,a] = </tex> '''Reduce'''(<tex>A \to a</tex>) | <tex>T[i,a] = </tex> '''Reduce'''(<tex>A \to a</tex>) | ||
− | '''if''' <tex>[S'\rightarrow S\cdot, \ | + | '''if''' <tex>[S'\rightarrow S\cdot, \$] \in I_i</tex> |
− | <tex>T[i,\ | + | <tex>T[i,\$] = </tex> '''Accept''' |
'''if''' <tex>goto(I_i,A) = I_j</tex> | '''if''' <tex>goto(I_i,A) = I_j</tex> | ||
<tex>goto[i,A]\leftarrow j</tex> | <tex>goto[i,A]\leftarrow j</tex> | ||
Строка 200: | Строка 190: | ||
==== Пример ==== | ==== Пример ==== | ||
− | |||
Рассмотрим следующую грамматику $\Gamma$: | Рассмотрим следующую грамматику $\Gamma$: | ||
# $S\rightarrow CC$ | # $S\rightarrow CC$ | ||
Строка 212: | Строка 201: | ||
!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"|$d$ | ||
− | !style="background-color:#EEE;padding:2px 20px;text-align:center"|$\ | + | !style="background-color:#EEE;padding:2px 20px;text-align:center"|$\$$ |
|- | |- | ||
|style="background-color:#EEE;padding:2px 20px;text-align:center"|$0$ | |style="background-color:#EEE;padding:2px 20px;text-align:center"|$0$ | ||
Строка 285: | Строка 274: | ||
|} | |} | ||
<br clear="left"> | <br clear="left"> | ||
− | |||
== См. также == | == См. также == |
Текущая версия на 19:19, 4 сентября 2022
В некоторых случаях SLR-разбор может выдать неправильный результат. В таких случаях используют более сложные методы, такие как LR(1) и LALR-разбор. Рассмотрим первый из них.
Содержание
Отличия от SLR-разбора
Основным отличием LR(1)-разбора от SLR-разбора является использование предпросмотра (англ. lookahead) символов.
Приведём пример, при котором SLR-разбор не справится с задачей:
Рассмотрим грамматику вида: $ S \to L=R \mid R \\ L \to *R \mid id \\ R \to L $
Покажем её канонический LR(0)-набор:
$I_0$ | $I_1$ | $I_2$ | $I_3$ | $I_4$ | $I_5$ | $I_6$ | $I_7$ | $I_8$ | $I_9$ |
---|---|---|---|---|---|---|---|---|---|
$S' \to \cdot S \\ S \to \cdot L = R \\ S \to \cdot R \\ L \to \cdot * R \\ L \to \cdot id \\ R \to \cdot L$ |
$S' \to S \cdot$ |
$S \to L \cdot = R \\ R \to L \cdot$ |
$S \to R \cdot$ |
$L \to * \cdot R \\ R \to \cdot L \\ L \to \cdot * R \\ L \to \cdot id$ |
$L \to id \cdot$ |
$S \to L = \cdot R \\ R \to \cdot L \\ L \to \cdot * R \\ L \to \cdot id$ |
$L \to * R \cdot$ |
$R \to L \cdot$ |
$S \to L = R \cdot$ |
Рассмотрим состояние $I_2$. Если SLR-парсер находится в $I_2$ и очередной входной символ равен $=$, то парсер выполняет свёртку в соответствии с ситуацией $R \to L$, что неверно, т.к. в этой грамматике не выводится выражение $R=\ldots$ и парсер должен был выполнить перенос, а не свёртку.
Чтобы решить эту проблему, необходимо хранить в ситуации больший объём информации, который позволит не делать таких ошибочных свёрток.
Канонические LR(1)-ситуации
Основная идея заключается в том, чтобы хранить в ситуациях (англ. items) больше информации, чтобы не производить некорректных свёрток.
Добавим в ситуацию второй компонент: терминальный символ. Таким образом, LR(1)-ситуации будут выглядеть следующим образом:
$[A\rightarrow\alpha\cdot\beta, a]$, где первая часть — продукция, а вторая — терминал или маркер конца входной строки $\$$. Здесь $a$ называется предпросмотром ситуации, а число $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=\varepsilon$ и $a=\$$. |
Построение множеств LR(1)-ситуаций
Метод построения похож на метод для $LR(0)$-разбора, с двумя изменёнными функциями: $closure(I)$ — замыкание множества ситуаций, и $goto(X,I)$ — функция переходов в автомате по символу $X$.
Лемма: |
$$\forall{b} \mid b\in FIRST(\beta\alpha): [A\rightarrow\alpha\cdot B\beta, a]\in I\Rightarrow [B\rightarrow\cdot\gamma, b]\in closure(I)$$
Другими словами, при построении замыкания вторая часть добавленных ситуаций должна принадлежать $FIRST(\beta\alpha)$ |
Доказательство: |
Рассмотрим ситуацию вида $[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$ порождает $\varepsilon$ слева: $\beta ax\Rightarrow^{*}by$, следовательно $b=a$. Таким образом, $b\in FIRST(\beta ax)$. Поскольку $x$ не может содержать первый терминал из $by$, то $FIRST(\beta ax)=FIRST(\beta a)$ Значит, $b\in FIRST(\beta a)$. |
Псевдокод
Псевдокод построения множеств $closure$ и $goto$, а также множества наборов ситуаций $items$ для грамматики $\Gamma' =\langle\Sigma, N, S, P\rangle$:
item[] closure(item[]): bool changed item[] repeat changed = false for for for .add( ) changed = true until not changed return
item[] goto(item[], char ): item[] for .add( ) return
item[][] items(): bool changed item[][] .add( ) repeat changed = false for item[] for if and .add( ) changed = true until not changed return
Пример
Рассмотрим следующую грамматику $\Gamma'$:
- $S'\rightarrow S$
- $S\rightarrow CC$
- $C\rightarrow cC\mid d$
Запустим процедуру $items(\Gamma')$. Она начинается с вычисления $closure([S\rightarrow S', \$])$. Это правило вида $[A\rightarrow\alpha\cdot B\beta, a]$, где $A=S';\alpha=\varepsilon;B=S;\beta=\varepsilon;a=\$$.
Т.к. в таком случае $FIRST(\beta\alpha) = {\$}$, то мы добавим только правило $[S\rightarrow\cdot CC,\$]$.
Продолжив вычислять замыкание таким образом, мы добавим во множество ситуаций $[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()$ завершает свою работу.
Начальное множество ситуаций в данном случае равно:
- $$I_0: \{[S'\rightarrow \cdot S, \$],[S\rightarrow\cdot CC,\$],[C\rightarrow\cdot C, c/d],[C\rightarrow\cdot d, c/d]\}$$
Следующим шагом процедуры $items()$ будет вычисление функции переходов автомата $goto(I_0,X)$ для всех символов $X$ грамматики $\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,\$]\}$$
- $$I_2 = closure(\{[S\rightarrow C\cdot C,\$]\})$$
- При $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]\}$$
- $$I_3 = closure(\{[C\rightarrow c\cdot C,c/d]\})$$
- При $X=d$:
- $$I_4 = closure(\{[C\rightarrow d\cdot ,c/d]\})$$
- $$I_4 = \{[C\rightarrow d\cdot,c/d]\}$$
- $$I_4 = closure(\{[C\rightarrow d\cdot ,c/d]\})$$
На этом завершается выполнение цикла из процедуры $items$ для $I_0$. $$goto(I_1, *)=\varnothing$$
- $$I_5=goto(I_2, C) = closure(\{[S\rightarrow CC\cdot,\$]\})=\{[S\rightarrow CC\cdot,\$]\}$$
- $$I_6=goto(I_2, c) = closure(\{[C\rightarrow c\cdot C,\$]\})$$
- $$I_6=\{[C\rightarrow c\cdot C,\$],[C\rightarrow \cdot cC,\$],[C\rightarrow \cdot d,\$]\}$$
NB: Обратим внимание, что $I_6$ отличается от $I_3$ только правыми частями ситуаций. Такое явление является частым в LR(1)-анализе, из-за него результирующая таблица будет неоправданно большой. LALR-анализ борется с этим явлением.
- $$I_7 = goto(I_2, d) = closure(\{[C\rightarrow d\cdot ,\$]\}) = \{[C\rightarrow d\cdot ,\$]\}$$
На этом рассмотрение $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,\$]\}$$
Остальные множества ситуаций не дают нам значений $goto$, процедура $items()$ завершает работу.
Канонические LR(1)-таблицы
В алгоритме будут использоваться структуры, описанные в конспекте про про LR(k)-грамматики
Алгоритм
// вход:— расширенная грамматика // выход: таблица канонического -анализа function // множество канонических ситуаций для Error foreach if and // здесь — терминал Shift( ) if and Reduce( ) if Accept if
Если в процессе построения обнаружатся конфликтующие действия — это значит, что грамматика не принадлежит классу LR(1)
Таблица, построенная в результате применения алгоритм называется канонической таблицей LR(1)-анализа.
Пример
Рассмотрим следующую грамматику $\Gamma$:
- $S\rightarrow CC$
- $C\rightarrow cC$
- $C\rightarrow d$
Приведем каноническую таблицу синтаксического анализа
для этой грамматики:$S$ | $C$ | $c$ | $d$ | $\$$ | |
---|---|---|---|---|---|
$0$ | $1$ | $2$ | $s(3)$ | $s(4)$ | |
$1$ | Accept | ||||
$2$ | $5$ | $s(6)$ | $s(7)$ | ||
$3$ | $8$ | $s(3)$ | $s(4)$ | ||
$4$ | $r(1)$ | $r(3)$ | |||
$5$ | $r(1)$ | ||||
$6$ | $9$ | $s(6)$ | $s(7)$ | ||
$7$ | $r(3)$ | ||||
$8$ | $r(2)$ | $r(2)$ | |||
$9$ | $r(2)$ |
См. также
Источники информации
- Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс, 2003. Стр. 331-338.
- Б.К.Мартыненко. Языки и трансляции. Стр. 198-223
- Лекции по теории формальных языков, LR(0)-, SLR(1)-, LR(1)- и LALR(1)-анализ