LR(1)-����������,
LALR(1)-����������

LR(1)-����������, LALR(1)-����������

��������� ���� SLR(1)-������ ���������� �� ��� ��������� ���������� ��� ��������� ����, �������� �� �������. ������, �� �������� ���������, �������� �� ������� ��� ������ ��������� ����� S � �������� -- �������� �� ������� �� ������� ������� ��� ������ ������� Next. ����� ��� ��� �������� �� �������� ������������: ��� ����� ���� ������������� �����, �� ��� �� ����� ������� ��� ����� S � ��������� ������� Next ����������. � LR(1)-������� ���� ���������� �����������.

LR(1)-������ ������� ��� � ���: ��� ���� ����������� � ����������� �������������� ���, ����� ������, ����� ������ ����� ������ �� ���������������� ����������� (������� �������, ���� ����� Next ��� �������).

����� ${\hbox{\tt K}}\to{\hbox{\tt U}}$ -- ���� �� ������ ����������, � t -- ��������� �������� ��� ���������� EOI (������� �� ����������� � ����� �������� �����). ��������� ���������   ${\hbox{\rm �������}}({\hbox{\tt K}}\to{\hbox{\tt U}},{\hbox{\tt t}})$ ��� ��������� ���� ����, ������� �������� ���������� ����� ��������������� ����� �������� UK � ���� ��������� LR-��������, ��� ������� ${\hbox{\tt Next}} = {\hbox{\tt t}}$ (� ������ �������).

���� ��������� � ���� ���� �� ${\hbox{\rm �������}}({\hbox{\tt K}}\to{\hbox{\tt U}})$�� ����� U, �� ��������� ��������� ���� ����, ������� ����� ��������� � ������ ������� ����� ������������ K, �� ������� ����� ������ t. ��� ��������� (�� ��������� �� ����, ����� �� ������ ${\hbox{\tt K}}\to{\hbox{\tt U}}$ ��� ����������� K �������) ��   ����� ���������� ${\hbox{\rm ���}}({\hbox{\tt K}},{\hbox{\tt t}})$.


$\scriptstyle{\blacktriangleright}$ 14.4.1. �������� ���������� ��� ���������� �������� \begin{displaymath}
{\hbox{\rm ���}}({\hbox{\tt K}},{\hbox{\tt t}}).\end{displaymath}

�������. �� ������������� ����� ������� $\langle{\hbox{\tt ���K}}\:{\hbox{\tt t}}\rangle$ ��� ������� ����������� K � ��� ������� ��������� t (� ����� ��� ${\hbox{\tt t}}={\hbox{\tt EOI}}$). �� ������� ������. ����� P -- ��������� ���������� �������� ����������. ����� � ����� ���������� ����� ������� \begin{displaymath}
\langle {\hbox{\tt ���P}}\:{\hbox{\tt EOI}}\rangle\to \qquad
 \hbox{(������ �����).}\end{displaymath}������ ������� �������� ���������� ��������� ��������� ������ �����. ��������, ��� ������� \begin{displaymath}
{\hbox{\tt K}}\to{\hbox{\tt L}}\,{\hbox{\tt u}}\,{\hbox{\tt M}}\,{\hbox{\tt N}}\end{displaymath}(L, M, N -- �����������, u -- ��������) � ����� ���������� �� ������� ������� \begin{displaymath}
\langle{\hbox{\tt ���L}}\:{\hbox{\tt u}}\rangle \to
 \langle{\hbox{\tt ���K}}\:{\hbox{\tt x}}\rangle\end{displaymath}(��� ���� ���������� x); \begin{displaymath}
\langle{\hbox{\tt ���M}}\:{\hbox{\tt s}}\rangle \to
 \langle...
 ...t ���K}}\:{\hbox{\tt y}}\rangle\,{\hbox{\tt L}}\,{\hbox{\tt u}}\end{displaymath}(��� ���� s, ������� ����� �������� �����, ��������� �� N, � ��� ���� y, � ����� ��� ���� ��� ${\hbox{\tt s}} = {\hbox{\tt y}}$,���� �� N �������� ������ �����); \begin{displaymath}
\langle{\hbox{\tt ���N}}\:{\hbox{\tt s}}\rangle \to
 \langle...
 ...{\tt s}}\rangle\,{\hbox{\tt L}}\,{\hbox{\tt u}}\,{\hbox{\tt M}}\end{displaymath}(��� ���� ���������� s).$\scriptstyle\blacktriangleleft$


$\scriptstyle{\blacktriangleright}$ 14.4.2. ��� �������� ����������� ��������?

�������. ��������� ���������� ���� \begin{displaymath}[
\hbox{\rm �������� � ������ ������},
\hbox{\rm �������� ��� {\hbox{\tt EOI}}}
]\end{displaymath}$\scriptstyle\blacktriangleleft$


$\scriptstyle{\blacktriangleright}$ 14.4.3. ��� ��������� ����������� ���������������?

�������. ���� S �� ���������� � ������������ ����������o � ��������� $[{\hbox{\tt K}}\to{\hbox{\tt U}}\_{\hbox{\tt V}},\,{\hbox{\tt t}}]$ (����� t -- �������� ��� EOI), ���� S ��������� �� U, �� ���� ${\hbox{\tt S}} ={\hbox{\tt TU}}$, �, ����� ����, T ����������� ${\hbox{\rm ���}}({\hbox{\tt K}},{\hbox{\tt t}})$.$\scriptstyle\blacktriangleleft$


$\scriptstyle{\blacktriangleright}$ 14.4.4. ������ ������� ��� ������������ ���������� ��������� ${\hbox{\rm ����}}({\hbox{\tt S}})$ ��������, ������������� � ������ ������ S?

�����:

(1) ���� ����� S ����������� � ��������� $[{\hbox{\tt K}}\to{\hbox{\tt U}}\_{\hbox{\tt V}},\,{\hbox{\tt t}}]$, ������ ����� V ���������� �� ����� J, �� ���� ${\hbox{\tt V}}={\hbox{\tt JW}}$, �� ����� SJ ����������� � ��������� $[{\hbox{\tt K}}\to{\hbox{\tt UJ}}\_{\hbox{\tt W}},\,{\hbox{\tt t}}]$.

��� ������� ��������� ���������� ��� �������� � �������� ����� ��������� (�� ���� �� ������������ � �������������), ������������� � SJ. �������� ����������, ��� ����� ������������ K � ���������� t ����� SJ ����������� ${\hbox{\rm ���}}({\hbox{\tt K}},{\hbox{\tt t}})$. ��� �������� �� ���� ��������:

(2) ���� �������� $[{\hbox{\tt L}}\to{\hbox{\tt U}}\_{\hbox{\tt V}},{\hbox{\tt t}}]$ ����������� � SJ (�������� ������� (1)), � V ���������� �� ���������� , �� SJ ����������� ${\hbox{\rm ���}}({\hbox{\tt K}},{\hbox{\tt s}})$ ��� ���� ���������� s, ������� ����� �������� �����, ��������� �� ����� ${\hbox{\tt V}}\setminus{\hbox{\tt K}}$ (����� V ��� ������ ����� K), � ����� ��� ${\hbox{\tt s}}={\hbox{\tt t}}$, ���� �� ${\hbox{\tt V}}\setminus{\hbox{\tt K}}$ ��������� ������ �����.

(3) ���� SJ ������ � ${\hbox{\rm ���}}({\hbox{\tt L}},{\hbox{\tt t}})$ ��� ��������� Lt, ������ ${\hbox{\tt L}}\to{\hbox{\tt V}}$ -- ������� ���������� � V ���������� �� ���������� K, �� SJ ����������� ${\hbox{\rm ���}}({\hbox{\tt K}},{\hbox{\tt s}})$��� ���� ���������� s, ������� ����� �������� �����, ��������� �� ${\hbox{\tt V}}\setminus{\hbox{\tt K}}$, � ����� ��� ${\hbox{\tt s}}={\hbox{\tt t}}$, ���� �� ${\hbox{\tt V}}\setminus{\hbox{\tt K}}$ ��������� ������ �����.$\scriptstyle\blacktriangleleft$


$\scriptstyle{\blacktriangleright}$ 14.4.5. ���� ����������� ���������� �����/������� � �������/������� �� �������� � ������� ����.

�������. ����� ���� ��������� ����������. ����� S -- ������������ ����� �� ���������� � ������������. ���� ��������� ${\hbox{\rm ����}}({\hbox{\tt S}})$ �������� ��������, � ������� ������ �� ������������� ����� �������� t, �� �������, ��� ��� ���� $\langle {\hbox{\tt S}},{\hbox{\tt t}}\rangle$ �������� �����. (��� ����������� �� ���������� �� ��������� � SLR(1)-������� -- ������ ���������� ��� �� ${\hbox{\rm ����}}({\hbox{\tt S}})$ �� �����������.)

���� � ${\hbox{\rm ����}}({\hbox{\tt S}})$ ���� ��������, � ������� ������ �� ������������� ������ ���, � ������ ������ ���� �������� �������� t, �� �������, ��� ��� ���� $\langle {\hbox{\tt S}},{\hbox{\tt t}}\rangle$LR(1)-�������� ������� (�� ���������������� �������). �������, ��� ��� ���� $\langle {\hbox{\tt S}},{\hbox{\tt t}}\rangle$��������� LR(1)-�������� ���� �����/�������, ���� �������� � �����, � �������. �������,     ��� ��� ���� $\langle {\hbox{\tt S}},{\hbox{\tt t}}\rangle$��������� LR(1)-�������� ���� �������/�������, ���� ���� ��������� ������, �� ������� �������� �������.$\scriptstyle\blacktriangleleft$

���������� ���������� LR(1)-�����������, ���� � ��� ���     LR(1)-���������� ���� �����/������� � �������/������� �� ��� ����� ���� $\langle {\hbox{\tt S}},{\hbox{\tt t}}\rangle$


$\scriptstyle{\blacktriangleright}$ 14.4.6. ��������� �������� �������� ����������� ����� � LR(1)-����������.

�������. ��� � ������, �� ������ ���� LR-�������� ����� ���������� ����������, ����� ��� ������ � ����� ���� ���������.$\scriptstyle\blacktriangleleft$


������� (� ���������, ��� LALR(1)-�������, ������ ����) ������, ��� ������� ������� LR(0) � LR(1)-���������������.


$\scriptstyle{\blacktriangleright}$ 14.4.7. �������������� � �������� ��������������� �����������.

�����. ����� ����������� ��������� ����������. ����� S �� ���������� � ������������ �������� LR(0)-������������� � ��������� ${\hbox{\tt K}}\to{\hbox{\tt U}}\_{\hbox{\tt V}}$ ����� � ������ �����, ����� ��� LR(1)-����������� � ����� $[{\hbox{\tt K}}\to{\hbox{\tt U}}\_{\hbox{\tt V}},{\hbox{\tt t}}]$��� ���������� ��������� t (��� ��� ${\hbox{\tt t}}={\hbox{\tt EOI}}$). �� �� ����� ������� �������: ${\hbox{\rm ���}}({\hbox{\tt K}})$ ���� ����������� ${\hbox{\rm ���}}({\hbox{\tt K}},{\hbox{\tt t}})$ �� ���� t. � ��������� ����� ��� ������ ����.$\scriptstyle\blacktriangleleft$

���������. ����� �������, ������� ${\hbox{\rm ����}}({\hbox{\tt S}})$ � LR(1)-������ �������� ����������� ������� ${\hbox{\rm ����}}({\hbox{\tt S}})$ � LR(0)-������: \begin{displaymath}
{\hbox{\rm ����}}_{\rm LR(0)}({\hbox{\tt S}})\qquad\hbox{���������� ��}\qquad{\hbox{\rm ����}}_{\rm LR(1)}({\hbox{\tt S}}),\end{displaymath}���� �� ���� ����� ��������� ������ �����.

������ �� ����� ���� ����������� LALR(1)-����������. ����� ����������� ��������� ����������, S -- ����� �� ������������ � ����������, t -- ��������� �������� (��� EOI). ����� ��������, ��� ��� ���� $\langle {\hbox{\tt S}},{\hbox{\tt t}}\rangle$ LALR(1)-�������� ������� �� ���������� �������, ���� ���������� ������ ����� ${\hbox{\tt S}}_1$${\hbox{\rm ����}}_{\rm LR(0)}({\hbox{\tt S}}_0) = {\hbox{\rm ����}}_{\rm
LR(0)}({\hbox{\tt S}}_1)$, ������ ��� ���� $\langle{\hbox{\tt S}}_1,{\hbox{\tt t}}\rangle$LR(1)-�������� ������� �� ���������������� �������. ����� ������������ ��������� (������������ �������), � ����������     ���������� LALR(1)-�����������, ���� ���������� ���.


$\scriptstyle{\blacktriangleright}$ 14.4.8. ��������, ��� ������ SLR(1)-���������� ��������
LALR(1)-�����������, � ������ LALR(1)-���������� �������� LR(1)-�����������.

[��������. ��� -- ������� ��������� �����������.]$\blacktriangleleft$


$\scriptstyle{\blacktriangleright}$ 14.4.9. ��������� �������� �������� ����������� � LALR(1)-����������, ������� ������ � ����� ������ ����������, ��� ��������������� LR(1)-��������.

[��������. ���������� ������� � ����� ��������� \begin{displaymath}
{\hbox{\rm ����}}_{\rm LR(0)}({\hbox{\tt S}}),\end{displaymath}��������� �������� ����������� LALR(1)-����������� ������� ��� ������������. (��� ��� ��� �������� ����� �� ���������� �� SLR(1)-������, ����� ������� ��������� �������.)]$\blacktriangleleft$


$\scriptstyle{\blacktriangleright}$ 14.4.10. �������� ������ LALR(1)-����������, �� ���������� SLR(1)-�����������.$\scriptstyle\blacktriangleleft$


$\scriptstyle{\blacktriangleright}$ 14.4.11. �������� ������ LR(1)-����������, �� ���������� LALR(1)-�����������.$\scriptstyle\blacktriangleleft$

����� ��������� � ������ ������� �������     width0pt


pvv
1/8/1999