LR(0)-����������

��������, ��� ���� �������� ���� -- ��� ����� ������ ��������� �����, ���, ������� �������, ����� ��������� LR-�������� ��� ���. �� ���� ��������������� ���� ����������� �������� LR-������� (��� ������ ������) ���������. ������ ���� ������������ �������� ������� �� ����� ����������: � ������ ������ �� �������, ����� ��� �������� ���������. ��� ����� �� ���������� ���� �������� �������������� ����������, � ������ �� ���������� ���������� ������ ��� ���������� LR(0)-���������. �� ��� �����:

(1) � �������� LR-�������� �������� ������� �� ������� ${\hbox{\tt K}}\to{\hbox{\tt U}}$ ��� ���������� ����� S ����� � ������ �����, ����� S ����������� ${\hbox{\rm �������}}({\hbox{\tt K}}\to{\hbox{\tt U}})$ ���, ������� �������, ����� ����� S ����������� � ��������� ${\hbox{\tt K}}\to{\hbox{\tt U}}\_$.
����������� ����������� ��� ����� ������:
(2) � �������� LR-�������� ��� ���������� ����� S �������� ����� � ��������� �������� a ����� � ������ �����, ����� S ����������� � ��������� ��������� ${\hbox{\tt K}}\to{\hbox{\tt U}}\_{\hbox{\tt aV}}$.


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

[��������. ����� ��������� ����� � � ����� S ���������� ����� a. ����������� ������ �������, ������������� ��� �����.]$\blacktriangleleft$

���������� ��������� ���������� � ������������ ����� S �� ���������� � ������������. ���� ��������� ${\hbox{\rm ����}}({\hbox{\tt S}})$ �������� ��������, � ������� ������ �� ������������� ����� ��������, �� �������, ��� ��� ����� S �������� �����. ���� � ${\hbox{\rm ����}}({\hbox{\tt S}})$ ���� ��������, � ������� ������ �� ������������� ������ ���, �� �������, ��� ��� ����� S �������� ������� (�� ���������������� �������). �������, ��� ��� ����� S ��������� ��������     ���� �����/�������, ���� �������� � �����, � �������. �������, ��� ��� ����� S ��������� �������� ���� �������/�������, ���� ���� ��������� ������, �� ������� �������� �������.

���������� ���������� LR(0)-�����������, ���� � ���     ��� ���������� ���� �����/������� � �������/������� �� ��� ������ ����� S.


$\scriptstyle{\blacktriangleright}$ 14.2.2. �������� �� ����������� ���� ���������� LR(0)-�����������?

�������. ���, �� ��������. ��� ���� TE+T ������� ��������� ���� �����/�������.$\scriptstyle\blacktriangleleft$


$\scriptstyle{\blacktriangleright}$ 14.2.3. �������� �� LR(0)-������������ �����:

\begin{displaymath}
\begin{tabular}
{ll}
 \begin{tabular}
{rrcl}
 (�)&{\hbox{\tt...
 ...box{\tt T}}&$\to$&{\hbox{\tt 3TTT}}
 \end{tabular}\end{tabular}\end{displaymath}

�������. ��������, ��. ��������������� ������� (���������� ���).$\scriptstyle\blacktriangleleft$


\begin{figure}
\begin{displaymath}
\begin{tabular}
{\vert l\vert l\vert}
\hline
...
 ...\ \hline\end{tabular}\end{displaymath}\begin{center}
(�)\end{center}\end{figure}


\begin{figure}
\begin{displaymath}
\begin{tabular}
{\vert l\vert l\vert}
\hline
...
 ...\end{tabular}\end{displaymath}\begin{center}
(�), ������\end{center}\end{figure}


\begin{figure}
\begin{displaymath}
\begin{tabular}
{\vert l\vert l\vert}
\hline
...
 ...d{tabular}\end{displaymath}\begin{center}
(�), ���������\end{center}\end{figure}

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


$\scriptstyle{\blacktriangleright}$ 14.2.4. ����� ���� LR(0)-����������. ��������, ��� � ������ ����� ���������� �� ����� ������ ������� ������. ��������� �������� �������� ����������� � LR(0)-����������.

�������. ����� ���� ������������ �����. ����� ������� LR-������� ��� ��� �� �����. ����� ������� ��������� ����� LR-�������� ����� S. ��� ���� ������, ������ ����� ��� ������� (� ���� �������, �� �� ������ �������). �������� ����������� LR(0)-����������, � ����� ��������� S �������� ���� ������ �����, ���� ������ ������� (������ ���� �� ������ �������). ����� �������, ����� ��������� ����������� LR-�������� ���������� ���������������� (�� ������ ���� ����� ����������, ����� �������� ������ � ��������).$\scriptstyle\blacktriangleleft$


$\scriptstyle{\blacktriangleright}$ 14.2.5. ��� ����������, ���� ������������� ����� �� ����� ������ � ������ ����������?

�����. ���� �� ��������� ���� �� ����� �������� �� �����, �� �������, ���� ��� ��������� ������ ����� ����� ������������ ��������� ������.$\scriptstyle\blacktriangleleft$

���������. 1. ��� ���������� ����� ��������� ��� ������������� ������ ��� ������ ��������� ��������� ${\hbox{\rm ����}}({\hbox{\tt S}})$ ��� �������� �������� S. ��� ��������� ����� ����� ������� � ����� (� ������ ������ �������� ��������� ${\hbox{\rm ����}}({\hbox{\tt T}})$ ��� ���� ����� T �������� ����� S).

2. �� ����� ���� ���� ����� S ����� �� ������� -- ���������� ������� ��������� �������� ${\hbox{\rm ����}}({\hbox{\tt T}})$ ��� ���� ��� ����� T (������� ���� S).


� ��������� �������� ����������� � LR(0)-���������� �� ���������� �� ��� ����������, ������� ����� ��. � ���� ��������� ��� ������� ��������� �������� �������, ��� � ��� �������� ������ ����� ��� ������ ������� (������ � ��������� ������ ��������, �� ������ �������). ����� ���������� �������� ��� �� ��������� ������� � ������ ����� ������� � ��������, ��������� �� ��������� ������ (Next). ����� �� ���������, ����� �������, ��� ����� ��������� Next �������� ����� (��� �� ���������, ������� � ��������� ����� ��������� ����� ��������������� �� ��������������). ������� ��������������� ����������� � ������� Next ��� ������� ������� � ���, �������� �� �������. ��� ����� ���� ���������� ����� (����������, � ������� �� ��������, �������� SLR(1)-������������ [���������� �� Simple LR(1)]) � ������ ����� (����� �������, �� ������������ ��� ��������� ����������; ����������, � ������� �� ��������, �������� LR(1)-������������). ���� � ������������� ����� ���������, ���������� LALR(1).



pvv
1/8/1999