����� ������������ ������

� ������� �� ��������� ����������� ������� (��������������� ����� ������������� �������), ��������� �� ������ ������������     ������ ����� ������������ �� ��������. ���� ����� ��������, ������, ������ �� �� ���� �����������. �� ������� ����������� ����������� �������.

���� ������ ������������ ������ ������. ��� ������� ����������� K �� ������ ��������� ReadK, ������� -- � ���������� � ������ �������� ����� x -- ������ ��� ����:

������ ��� ��������� ���� ����� ����� ��������, ����������� � ���, ��� ��������� �������� �������� � ������� ����� � ��� �������� � ����������� ����� ������. �� ������������, ��� ����� �������� ����� ��������� � ��� �� �����, �.�. ������� �������, ���������� << �����������>> ����� �� << �������������>>. ����� �������, ��� ���� ������� (��� ����������)

Next: Symbol
������ ������ ������������� ������. �� ���������� ����� ���� ������������ �������, � ����� ����������� ������ EOI (End Of Input -- ����� �����), ����������, ��� ��� ����� ��� ���������. ����� ���� �������, ����������, �� �������� ������� ����� ����������� � ������������� ������ -- ��� ����� ���� ��������� Move, ������� �������� ������� �� ���� ������. (��� ���������, ���� Next<>EOI.) �����, �������, ������� ��������� ���������� b.

������ �� ����� �������������� ���� ���������� � ��������� ReadK. ��� ������� � ���������:

��� �������� ������ ����� ������������: ��������� �� K ����� ����� �������� K-������, � ����� ������ ������ ���������� �� K ����� -- K-�������. ��� ���������������� ���������� ������ ����� �������� ������� <<ReadK ��������� ��� K>>.

������ � �������. ����� �������

K $\to$ L M
�������� ������������ �������� ����������, ���������� K � ����� �����, ����� L, M -- ����������� � ReadL, ReadM -- ���������� (��� ���) ���������.

���������� ����� ���������:

     procedure ReadK;
     begin
     | ReadL;
     | if b then begin
     | | ReadM;
     | end;
     end;


$\scriptstyle{\blacktriangleright}$ 13.2.1. �������� ������, ����� ��� ��������� ����� ������������ ��� K.

�����. ����� �� L ��������� ����� ����� ���� 00..00, � �� M ��������� ���� ����� 01. ����� �� K ��������� ����� 00001, �� ��������� ReadK ����� �� �������.$\scriptstyle\blacktriangleleft$

������ ����������� ������� ������������ ���������
ReadK. ��� ����� ��� ����������� ��������� �����������. ����� ����������� ��-���������� � ��������� ���������� N ���� ����������. ���������� N -����� A , ������� ����� ����������� ������ B , ����� ���������� N -������ (���� ����� ����). ��� ����� ���� ����� ���� AB ���������� ������������ ������, ������ � A ��������������� �� B . ��������� ���� ����� ���������� ���������   ����(N ). (���� ������� N -����� �� �������� ����������� ������� ������� N -�����, �� ��������� ����(N ) �����.)


$\scriptstyle{\blacktriangleright}$ 13.2.2. ������� (�) ����(E) ��� ������� 1 (�. [*]); (�) ����(E) � ����(T) ��� ������� 2 (�. [*]); (�) ����(33003) � ����(33004) ��� ������� 3 (�. [*]);

�����. (�) ����(E) = $\{ \hbox{\tt [}, \hbox{\tt (}\}$.(�) ����(E) = $\{ \hbox{\tt [}, \hbox{\tt (}\}$;����(T) ����� (������� T-����� �� �������� ������� �������).
(�) ����(33005) = $\{\hbox{\tt *}\}$; ����(33006) �����.$\scriptstyle\blacktriangleleft$

����� ����, ��� ������� ����������� N ��������� ����� ���(N )  ��������� ���� ����������, ���������� ������� ������� �������� N -����. ��� ����������� -- ������ � ���������� -- �������� ���� ����������� ������� ������������ ��������� ReadK � ��������� ���� ��������.


$\scriptstyle{\blacktriangleright}$ 13.2.3. ��������, ��� ���� ����(L) �� ������������ � ���(M) � ��������� ���� M-���� �������, �� ReadK ���������.

�������. ���������� ��� ������.

(1) ����� ����� ReadL �������� ���������� b �����. � ���� ������ ReadL ������ �� ����� ������������ L-������ A , �� ���������� L-������. ��� �������� K-������� (����� �����, ��� ��������� M-���� �������.). ����� �� ��� ������������ K-������� ����� ����� �����? ���� ���, �� A �������� ������� ����� BC , ��� B ���� L-�����, C ���� M-������ � BC -- ����� ������� ������ �����, ��� A . ���� B ������� A , �� A -- �� ������������ ������ �����, ���������� L-�������, ��� ������������ ������������ ReadL. ���� B = A , �� A ���� �� L-������, � ��� �� ���. ������, B ������ A , C ������� � ������ ������ ����� C ������� � A �� ��������� �������� ����� B , �.�. ����(L) ������������ � ���(M). ������������. ����, A �����������. �� ���������� ������� �����, ��� A �� �������� K-������. ������������ ��������� ReadK � ���� ������ ���������.

(2) ����� ����� ReadL �������� ���������� b �������. ����� ����������� ���������� ReadK ������ ����� ����� ��� AB , ��� A ���� L-�����, � B ���� M-������. ��� ����� AB ���� K-������. �������� ��� ��������������. ����� C ���� ������� K-������. ����� ���� C ���� L-������ (��� ����������, ��� ��� A ���� ������������ L-�������), ���� C = A'B' , ��� A' -- L-�����, B' -- M-������. ���� A' ������ A , �� B' ������� � ���������� � �������, �������������� � ���(M), � ����(L), ��� ����������. ���� A' ������� A , �� A -- �� ������������ L-������. ������������. ����, A' = A . �� � ���� ������ B' ���� ����������� B , ��� ������������ ������������ ReadM. ����, AB -- ������������ K-������. �������� ��������� ������������ ����������� ���������� ReadK �������� ���������� b. ���� ��� �������, �� ��� ��������. ���� ��� �����, �� B �� ���� M-�����, � ���� ���������, ��� AB -- �� K-�����. � ����� ����, ���� �� ����������� AB = A'B' , ��� A' -- L-�����, B' -- M-�����, �� A' �� ����� ���� ������� A (ReadL ������ ������������ �����), A' �� ����� ���� ����� A (����� B' ����� B � �� �������� M-������) � A' �� ����� ���� ������ A (����� ������ ������ B' ����������� � ���(M), � ����(L)). ������ ������.$\scriptstyle\blacktriangleleft$

�������� ������ � ������� �������� ������. ����� � ��-���������� ���� ������� \begin{eqnarray*}
\hbox{\tt K}&\to&\hbox{\tt L}\\  \hbox{\tt K}&\to&\hbox{\tt M}\\  \hbox{\tt K}&\to&\hbox{\tt N}\end{eqnarray*}� ������ ������ � ����� ������ K ���.


$\scriptstyle{\blacktriangleright}$ 13.2.4. ������, ��� ReadL, ReadMReadN ��������� (��� L, MN) � ��� ��������� ���(L), ���(M) � ���(N) �� ������������, �������� ���������, ���������� ��� K.

�������. ����� ��������� ������:
     procedure ReadK;
     begin
     | if (Next ����������� ���(L)) then begin
     | | ReadL;
     | end else if (Next ����������� ���(M)) then begin
     | | ReadM;
     | end else if (Next ����������� ���(N)) then begin
     | | ReadN;
     | end else begin
     | | b := true ��� false  � ����������� �� ����,
     | |      �������� �� ������ ����� �� K ��� ���
     | end;
     end;
�������, ��� ReadK ��������� ��������� K. ���� Next �� ����������� �� ������ �� �������� ���(L), ���(M), ���(N),�� ������ ����� �������� ���������� ������� �����, ���������� K-�������. ���� Next ����������� ������ (�, �������������, ������ ������) �� ���� ��������, �� ������������ ������ �����, ���������� K-�������, ������� � �������� ��������������� ����������.$\scriptstyle\blacktriangleleft$


$\scriptstyle{\blacktriangleright}$ 13.2.5. ��������� ���������, ��������� ��������� ������������� ��������� ��� ���������� (������ 3, �. [*]): \begin{eqnarray*}
\vyrazh &\to&\slag \ \ostvyr \\  \ostvyr &\to& \hbox{\tt +}\ \...
 ... \hbox{\tt x}\\  \mnozh &\to& \hbox{\tt(}\ \vyrazh \ \hbox{\tt )}\end{eqnarray*}

�������. ��� ���������� �� ��������� ��������� ��� ������������� ������� ������: � ������ ������ ���� ���������� ���������� � ������������
+ 32998
� ������ �� ���� ��������
( 32999 )
� ���������� ���� ����� ��������� ������ � ����� ����� ������ � � ������� ������� ������� ����, �������� \begin{eqnarray*}
\ostvyr &\to& \hbox{\tt +}\ \vyrazh \\  \ostvyr &\to&\end{eqnarray*}��� ����������� �� �������� ���������������. ���, ������� ���� $\hbox{\tt K}\to \hbox{\tt L M N}$����� ���� �� �������� �� ��� ������� $\hbox{\tt K} \to \hbox{\tt L Q}$$\hbox{\tt Q} \to \hbox{\tt M N}$, ������������ ������� � ������ ����� -- �� ����������� (� ������������ �������� ������ �� ��������������� ���������). ��������� ������ � ����� ����� ������ � ������������ ������� ����� ����� ������ � ��� ������������ ������: ��������, \begin{eqnarray*}
\hbox{\tt K}&\to&\hbox{\tt L M N}\\ \hbox{\tt K}&\to&\hbox{\tt P Q}\\ \hbox{\tt K}&\to&\end{eqnarray*}����� �������� �� ������� \begin{eqnarray*}
\hbox{\tt K}&\to&\hbox{\tt K}_1\\ \hbox{\tt K}&\to&\hbox{\tt K...
 ... M N}\\ \hbox{\tt K}_2 &\to&\hbox{\tt P Q}\\ \hbox{\tt K}_3 &\to&\end{eqnarray*}�� �� �� ����� ����� ������ -- � ����� �� ������� ��, ��� ���������, ���� ���������� �������� �������� ��� ����� ������������ �������� � ����� �� �������������. ��������, ��� ������� \begin{displaymath}
\hbox{\tt K} \to \hbox{\tt L M N}\end{displaymath}��� ���� ���������
        procedure ReadK;
        begin
        | ReadL;
        | if b then begin ReadM; end;
        | if b then begin ReadN; end;
        end;
��� �� ������������ ����, ����� ����(L) �� ������������ � ���(MN) (������� ����� ���(M), ���� �� M �� ��������� ������ �����, � ����� ����������� ���(M) � ���(N), ���� ���������), � ����� ����� ����(M) �� ������������ � ���(N).

����������� ������� ������� \begin{eqnarray*}
\hbox{\tt K}&\to&\hbox{\tt L M N}\\ \hbox{\tt K}&\to&\hbox{\tt P Q}\\ \hbox{\tt K}&\to&\end{eqnarray*}�������� � ���������

        procedure ReadK;
        begin
        | if (Next ����������� ���(LMN)) then begin
        | | ReadL;
        | | if b then begin ReadM; end;
        | | if b then begin ReadN; end;
        | end else if (Next ����������� ���(PQ)) then begin
        | | ReadP;
        | | if b then begin ReadQ; end;
        | end else begin
        | | b := true;
        | end;
        end;
������������ ������� �������, ����� ���(LMN) �� ������������ � ���(PQ).

����� ����������� ����� ���������, ������� ����� � ���� ������������ ����� �������� � ����������� �������: \begin{displaymath}
\begin{tabular}
{ll}
 ��������� & {\hbox{\cmrfont EXPRession...
 ...ive term}}\\  ��������� & {\hbox{\cmrfont FACTor}}\end{tabular}\end{displaymath}

     procedure ReadSymb (c: Symbol);
     | b := (Next = c);
     | if b then begin Move; end;
     end;

     procedure ReadExpr;
     | ReadAdd;
     | if b then begin ReadRestExpr; end;
     end;

     procedure ReadRestExpr;
     | if Next = '+' then begin
     | | ReadSymb ('+');
     | | if b then begin ReadExpr; end;
     | end else begin
     | | b := true;
     | end;
     end;

     procedure ReadAdd;
     | ReadFact;
     | if b then begin ReadRestAdd; end;
     end;

     procedure ReadRestAdd;
     | if Next = '*' then begin
     | | ReadSymb ('*');
     | | if b then begin ReadAdd; end;
     | end else begin
     | | b := true;
     | end;
     end;

     procedure ReadFact;
     | if Next = 'x' then begin
     | | ReadSymb ('x');
     | end else if Next = '(' then begin
     | | ReadSymb ('(');
     | | if b then begin ReadExpr; end;
     | | if b then begin ReadSymb (')'); end;
     | end else begin
     | | b := false;
     | end;
     end;
�������� �������� ��������, ��������� � �������� �������������� ���� �������� (���� ���������� ������ � ��������). � ������� ��� �����������, ������ ��������� ���� ��������������� �������� �������� (<< forward>>). ��� ������ ��� ����������� ��������, ������ �������������� ����, ��� ������ ��������� �������� ��������� � �������������, ��� ������������ � ��� ������ �������� �������� ���������, ���� �������� ��������, ��� ������ �����������. (��� �� ��������: ���� � ���������� ���� ������� $\hbox{\tt K}\to\hbox{\tt KK}$, �� �� K ������ �� ���������, ����(K) � ���(K) �����, �� ���������� �� ����� ������� ���������
     procedure ReadK;
     begin
     | ReadK;
     | if b then begin
     | | ReadK;
     | end;
     end;
�� ����������� ������.)

� ������� ������ ��������� ReadRestExpr, ReadRestAdd, ReadFact ���� �����������, ���� ��������� ����� ������������� ����� �����. ��������� ����� ���� ������� �������� ���� �� ���, �� ������������ ����������. ������ ������.$\scriptstyle\blacktriangleleft$


$\scriptstyle{\blacktriangleright}$ 13.2.6. ����� � ���������� ������� ��� ������� � ������������ K � ����� �����, ������� ��� \begin{eqnarray*}
\hbox{\tt K}&\to&\hbox{\tt L K}\\  \hbox{\tt K}&\to&\end{eqnarray*}�� ������� K-����� ������������ ����� �������� ������������������ L-����, ������ ��������� ����(L) � ���(K) (� ������ ������ ������ ���(L)) �� ������������. ��������� ���������� ��� L ��������� ReadL, �������� ���������� ��� K ��������� ReadK, �� ��������� ��������. ��������������, ��� ������ ����� �� �������� �� L.

�������. �� ����� �������� ��������� �� ��������
     procedure ReadK;
     begin
     | if (Next ����������� ���(L)) then begin
     | | ReadL;
     | | if b then begin ReadK; end;
     | end else begin
     | | b := true;
     | end;
     end;
���������� ������ ������������� ���, ��� ������ ����� �� �������� �� L (�, �������������, ����� ����������� ������� ����� ������������� ����� �����������).

��� ����������� ��������� ������������ �������������:

     procedure ReadK;
     begin
     | b := true;
     | while b and (Next ����������� ���(L)) do begin
     | | ReadL;
     | end;
     end;
��������� ����� ��������� ��� ��������������� ���. ������������� � ����� ������� ����. ���������� ��������� �������, ��� ���� ����������� ��������� ������������ ������������� � �������������, ��� �� ����������� ����� ������������ ������ ������������� ���������. ���������:
     if (Next ����������� ���(L)) then begin
     | ReadL;
     | if b then begin
     | | b := true;
     | | while b and (Next ����������� ���(L)) do begin
     | | | ReadL;
     | | end;
     | end;
     end else begin
     | b := true;
     end;
������ ������� b:=true ����� �������� (� ���� ����� � ��� b �������). ������ ������� ����� ��������� � ������:
     b := true;
     if (Next ����������� ���(L) then begin
     | ReadL;
     | if b then begin
     | | while b and (Next ����������� ���(L)) do begin
     | | | ReadL;
     | | end;
     | end;
     end;
������ ���������� if ����� �������� (���� b �����, ���� while ��� ����� �� �����������) � �������� � ������� �������� if ������� b (������� ��� ����� �������).
     b := true;
     if b and (Next ����������� ���(L)) then begin
     | ReadL;
     | while b and (Next ����������� ���(L)) do begin
     | | ReadL;
     | end;
     end;
��� ������������ ����������� ���� ������������� ��������� (�� ������� �������� ������ �������� �����).$\scriptstyle\blacktriangleleft$


$\scriptstyle{\blacktriangleright}$ 13.2.7. �������� ������������ ����������� ���� ������������� ��������� ���������������, ��� ������ �� �����������.

�������. ���������� ���������� ������ �����, ���������� K-�������. ��� �������������� � ���� ������������ (����������������� ������������) ���������� �������� L-���� �, ��������, ������ ��������� L-������, �� ����������� L-������. ��������� �����: ��������� ��������� �� ���; b $\Leftrightarrow$ (��������� ����������� �������� L-������).

���������� ����������: ���� �������� ��������� �����, ��� ��������; ���� �������� ���������, �� �� ������ L-������ (�� ����� ����������) ���� ������ �� ���(L), � ������ ��� ����� -- ������������ ������ �����, ���������� L-�������.$\scriptstyle\blacktriangleleft$

�� �������� ��� ������ ���������� ���������� ����������. ���� ������� ��� ������-�� ����������� K ����� ��� \begin{eqnarray*}
\hbox{\tt K}&\to&\hbox{\tt L K}\\  \hbox{\tt K}&\to&\end{eqnarray*}(�.�. K-����� -- ��� ������������������ L-����), �� ���� ������ �� �����, � ������ K ����� L � �������� �������. ��������� ������ � ����� ����� ������ � ������� ������� ���������� ��� ���� �������, �������� �������������� ������ ����� ������������ ������.

��������, ������������� ���� ���������� ��� 33008 ����� ���� �������� ���: \begin{eqnarray*}
\vyrazh &\to& \slag \hbox{ \tt \{ + \slag \ \}}\\  \slag &\to&...
 ...\mnozh \ \}}\\  \mnozh &\to& \hbox{ \tt x}\ \vert\ (\ \vyrazh \ )\end{eqnarray*}


$\scriptstyle{\blacktriangleright}$ 13.2.8. �������� ���������, ���������� ��� 33009, ������ ���� ���������� � ��������� ���� ������ ��������, ��� �����.

�������:

     procedure ReadSymb (c: Symbol);
     | b := (Next = c);
     | if b then begin Move; end;
     end;

     procedure ReadExpr;
     begin
     | ReadAdd;
     | while b and (Next = '+') do begin
     | | Move; ReadAdd;
     | end;
     end;

     procedure ReadAdd;
     begin
     | ReadFact;
     | while b and (Next = '*') do begin
     | | Move; ReadFact;
     | end;
     end;

     procedure ReadFact;
     begin
     | if Next = 'x' do begin
     | | Move; b := true;
     | end else if Next = '(' then begin
     | | Move; ReadExpr;
     | | if b then begin ReadSymb (')'); end;
     | end else begin
     | | b := false;
     | end;
     end;`


$\scriptstyle{\blacktriangleright}$ 13.2.9.  � ��������� ��������� ������� b:=true ����� ��������. ������?

�������. ����� ������������, ��� ��� ��������� ���������� ��� b=true.$\scriptstyle\blacktriangleleft$

�������� ������� ��� LL(1)-���������


pvv
1/8/1999