Изменения
Нет описания правки
Добавим в пункт второй компонент: терминальный символ. Таким образом, LR(1)-ситуации будут выглядеть следующим образом:
$[A\rightarrow\alpha\cdot\beta, a]$, где первая часть {{- --}} продукция, а вторая {{--- }} терминал или маркер конца входной строки $\char36$. Здесь $a$ называется '''предпросмотром''' (англ. ''lookahead'') ситуации, а число 1 в LR(1) означает его длину.Теперь мы будем выполнять свёртку в соответствии с продукцией $A\rightarrow\alpha$, только в том случае, если находимся в ситуации $[A\rightarrow\alpha\cdot\beta, a]$ и $a$ {{--- }} входной символ.
{{Определение
|id=defValid
=== Построение множеств LR(1)-ситуаций ===
<wikitex>
Метод построения похож на метод для $LR(0)$ - разбора, с двумя изменёнными функциями: $CLOSUREclosure(I)$ {{- --}} замыкание множества пунктов, и $GOTO(X,I)$ {{--- }} функция переходов в автомате по символу $X$.
{{Лемма
|id=lemmaclosure
|statement= $$\forall{b} | b\in FIRST(\beta\alpha): [A\rightarrow\alpha\cdot B\beta, a]\in I\Rightarrow [B\rightarrow\cdot\gamma, b]\in CLOSUREclosure(I)$$
Другими словами, при построении замыкания вторая часть добавленных пунктов должна принадлежать $FIRST(\beta\alpha)$
|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$ порождает $\epsilon$ слева: $\beta ax\Rightarrow^{*}by$, следовательно $b=a$. Таким образом, $b\in FIRST(\beta ax)$. Поскольку $x$ не может содержать первый терминал из $by$, то $FIRST(\beta ax)=FIRST(\beta a)$
====Псевдокод====
<wikitex>
Псевдокод построения множеств $CLOSUREclosure$ и $GOTO$, а также множества пунктов $items$:
<code>
Set<Item> CLOSUREclosure(Set<Item> I):
'''bool''' changed;
Set<Item> $J$=$I$;
'''for''' $[A\rightarrow\alpha\cdot X\beta, a]\in I$
J.add($[A\rightarrow\alpha X\cdot\beta, a]$);
'''return''' $CLOSUREclosure(J)$;
</code>
<code>
Set<Set<Item>> items($G'$):
'''bool''' changed;
Set<Set<Item>> $C$ = $\{CLOSUREclosure({S'\rightarrow\cdot S,\char36})\}$;
'''repeat'''
changed = '''false''';
* $S\rightarrow CC$
* $S\rightarrow cC|d$
Запустим процедуру $items(G')$. Она начинается с вычисления $CLOSUREclosure([S\rightarrow S', \char36])$. Это правило вида $[A\rightarrow\alpha\cdot B\beta, a]$, где $A=S';\alpha=\epsilon;B=S;\beta=\epsilon;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]$ (справа от точки во всех пунктах терминалы), то функция $CLOSUREclosure$ завершает свою работу и начальное множество пунктов в данном случае равно:
[[Файл:lr1_sets.png|400px|thumb|Рис. 1 Множества пунктов и их переходы]]
При $X=S$:
$$CLOSUREclosure({[S'\rightarrow S\cdot,\char36]}) = \varnothing$$
Мы не добавили ни одного пункта, т.к. точка является крайней справа. Таким образом,
$$I_1: \{[S'\rightarrow S\cdot,\char36]\}$$
При $X=C$:
$$I_2 = CLOSUREclosure(\{[S\rightarrow C\cdot C,\char36]\})$$
$$I_2 = \{[S\rightarrow C\cdot C,\char36],[C\rightarrow\cdot cC,\char36],[C\rightarrow\cdot d,\char36]\}$$
При $X=c$:
$$I_3 = CLOSUREclosure(\{[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 = CLOSUREclosure(\{[C\rightarrow d\cdot ,c/d]\})$$
$$I_4 = \{[C\rightarrow d\cdot,c/d]\}$$
На этом завершается выполнение цикла из процедуры $items$ для $I_0$.
$$GOTO(I_1, *)=\varnothing$$
$$I_5 = GOTO(I_2, C) = CLOSUREclosure(\{[S\rightarrow CC\cdot,\char36]\})=\{[S\rightarrow CC\cdot,\char36]\}$$$$I_6 = GOTO(I_2, c) = CLOSUREclosure(\{[C\rightarrow c\cdot C,\char36]\})$$
$$I_6=\{[C\rightarrow c\cdot C,\char36],[C\rightarrow \cdot cC,\char36],[C\rightarrow \cdot d,\char36]\}$$
Обратим внимание, что $I_6$ отличается от $I_3$ только правыми частями пунктов. Такое явление является частым в $LR(1)$ - анализе, из-за него результирующая таблица будет неоправданно большой. $LALR$-анализ борется с этим явлением.
Продолжим:
$$I_7 = GOTO(I_2, d) = CLOSUREclosure(\{[C\rightarrow d\cdot ,\char36]\}) = \{[C\rightarrow d\cdot ,\char36]\}$$
На этом рассмотрение $GOTO(I_2)$ завершено, переходим к $GOTO(I_3)$:
$$I_8 = GOTO(I_3, C) = CLOSUREclosure(\{[C\rightarrow cC\cdot ,c/d]\}) = \{[C\rightarrow cC\cdot ,c/d]\}$$
В множествах $I_4$ и $I_5$ все пункты имеют точки в крайнем положении справа, следовательно эти множества не имеют $GOTO$
$$GOTO(I_6, c) = I_6$$
