� ������� �� ��������� ����������� ������� (��������������� ����� ������������� �������), ��������� �� ������ ������������ ������ ����� ������������ �� ��������. ���� ����� ��������, ������, ������ �� �� ���� �����������. �� ������� ����������� ����������� �������.
���� ������ ������������ ������ ������. ��� ������� ����������� K �� ������ ��������� ReadK, ������� -- � ���������� � ������ �������� ����� x -- ������ ��� ����:
������ ��� ��������� ���� ����� ����� ��������, ����������� � ���, ��� ��������� �������� �������� � ������� ����� � ��� �������� � ����������� ����� ������. �� ������������, ��� ����� �������� ����� ��������� � ��� �� �����, �.�. ������� �������, ���������� << �����������>> ����� �� << �������������>>. ����� �������, ��� ���� ������� (��� ����������)
������ �� ����� �������������� ���� ���������� � ��������� ReadK. ��� ������� � ���������:
��� �������� ������ ����� ������������: ��������� �� K ����� ����� �������� K-������, � ����� ������ ������ ���������� �� K ����� -- K-�������. ��� ���������������� ���������� ������ ����� �������� ������� <<ReadK ��������� ��� K>>.
������ � �������. ����� �������
���������� ����� ���������:
procedure ReadK; begin | ReadL; | if b then begin | | ReadM; | end; end;
13.2.1. �������� ������, ����� ��� ��������� �����
������������ ��� K.
������ ����������� ������� ������������ ���������
ReadK.
��� ����� ��� ����������� ��������� �����������. �����
����������� ��-���������� � ��������� ���������� N ����
����������. ���������� N -����� A , ������� ����� �����������
������ B , ����� ���������� N -������ (���� ����� ����). ��� �����
���� ����� ���� A � B ���������� ������������ ������, ������ � A
��������������� �� B . ��������� ���� ����� ���������� ���������
����(N ). (���� ������� N -����� �� �������� ����������� �������
������� N -�����, �� ��������� ����(N ) �����.)
13.2.2. ������� (�) ����(E) ��� ������� 1 (�.
);
(�) ����(E) �
����(T) ��� ������� 2 (�.
);
(�) ����(33003) � ����(33004) ���
������� 3 (�.
);
����� ����, ��� ������� ����������� N ��������� ����� ���(N ) ��������� ���� ����������, ���������� ������� ������� �������� N -����. ��� ����������� -- ������ � ���������� -- �������� ���� ����������� ������� ������������ ��������� ReadK � ��������� ���� ��������.
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)). ������
������.
�������� ������ � ������� �������� ������. ����� �
��-���������� ���� �������
� ������ ������ � ����� ������ K ���.
13.2.4. ������, ��� ReadL, ReadM �
ReadN ��������� (��� L, M � N) � ���
��������� ���(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-�������, ������� � �������� ��������������� ����������.
13.2.5. ��������� ���������, ��������� ���������
������������� ��������� ��� ����������
(������ 3, �.
):
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).
����������� ������� �������
�������� � ���������
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).
����� ����������� ����� ���������,
������� ����� � ���� ������������
����� �������� � ����������� �������:
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>>). ��� ������ ��� ����������� ��������, ������ �������������� ����, ��� ������ ��������� �������� ��������� � �������������, ��� ������������ � ��� ������ �������� �������� ���������, ���� �������� ��������, ��� ������ �����������. (��� �� ��������: ���� � ���������� ���� �������
procedure ReadK; begin | ReadK; | if b then begin | | ReadK; | end; end;�� ����������� ������.)
� ������� ������ ��������� ReadRestExpr,
ReadRestAdd, ReadFact ���� �����������, ����
��������� ����� ������������� ����� �����. ��������� ����� ����
������� �������� ���� �� ���, �� ������������ ����������. ������
������.
13.2.6. ����� � ���������� ������� ��� ������� �
������������ K � ����� �����, ������� ���
�� ������� 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;��� ������������ ����������� ���� ������������� ��������� (�� ������� �������� ������ �������� �����).
13.2.7. �������� ������������ ����������� ���� �������������
��������� ���������������, ��� ������ �� �����������.
���������� ����������: ���� �������� ��������� �����, ���
��������; ���� �������� ���������, �� �� ������ L-������
(�� ����� ����������) ���� ������ �� ���(L), � ������ ���
����� -- ������������ ������ �����, ���������� L-�������.
�� �������� ��� ������ ���������� ���������� ����������.
���� ������� ��� ������-�� ����������� K ����� ���
(�.�. K-����� -- ��� ������������������ L-����),
�� ���� ������ �� �����, � ������ K ����� L � �������� �������.
��������� ������ � ����� ����� ������ � ������� �������
���������� ��� ���� �������, �������� �������������� ������
����� ������������ ������.
��������, ������������� ���� ���������� ��� 33008 �����
���� �������� ���:
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;`
13.2.9.
� ��������� ��������� ������� b:=true ����� ��������.
������?
�������� ������� ��� LL(1)-���������