262
правки
Изменения
→Канонические LR(1)-пункты
=== Построение множеств LR(1)-пунктов ===
<wikitex>
Метод построения похож на метод для $LR(0)$ - разбора, с двумя изменёнными функциями: $CLOSURE(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 CLOSURE(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)$
Значит, $b\in FIRST(\beta a)$.
}}
Псевдокод построения множеств $CLOSURE$ и $GOTO$, а также множества пунктов $items$:
<code>
'''function''' constructFOLLOW():
'''for''' <tex>( A \in N )</tex>
<tex>\mathrm{FOLLOW}[A] = \varnothing </tex>
<tex>\mathrm{FOLLOW}[S] = \{\$\} </tex> <font color=green> // в стартовый терминал помещается символ конца строки </font>
changed = ''true''
'''while''' changed
changed = ''false''
'''for''' <tex>( A \to \alpha \in P )</tex>
'''for''' <tex>( B : \alpha = \beta B \gamma)</tex>
<tex> \mathrm{FOLLOW}[B]\ \cup =\ \mathrm{FIRST}(\gamma) \setminus \{\varepsilon\} </tex>
'''if''' <tex> \varepsilon \in \mathrm{FIRST}(\gamma) </tex>
<tex> \mathrm{FOLLOW}[B]\ \cup =\ \mathrm{FOLLOW}[A]</tex>
changed = ''true'' '''if''' <tex> \mathrm{FOLLOW}[B] </tex> изменился
</code>
</wikitex>
