58
Содержание
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ
ПРЕОБРАЗОВАНИЕ
Пример:
E
1
:= T+E.
E
2
:= T.
T
1
:= F*T.
T
2
:= F.
F
1
:= (E).
F
2
:= a.
(q, 1, $, E
1
) |
(q, 1, $E
1
, T+E) |
(q, 1, $E
1
T
1
,F*T+E) |
(q, 1,
$E
1
T
1
F
2
,a*T+E) |
(q, 2, $E
1
T
1
F
2
a,*T+E) |
(b, 2, $E
1
T
1
F
2
a,*T+E) |
(b, 1, $E
1
T
1
,F*T+E) |
(q, 1, $E
1
T
2
,F+E)|
(q, 1, $E
1
T
2
F
2
,a+E)|
(q, 3, $E
1
T
2
a+, E) |
(q, 3,
$E
1
T
2
a+E
1
, T+E) |
(q, 3, $E
1
T
2
a+E
1
T
1
,F*T+E).
а+а#
E:=E+T|T


=
=
=
=
=
+ +
)E( F
a F ; F:T
T*F:T ; T E
E T E
2
1
2
1
2
1
3
2
1
e )a(h
)F(h )F(h
)T(h )T(h
)E(h )E(h
=
=
=
=
=
=
=
3
3
2
2
1
1
2
1
2
1
2
1
$)E,e,1,q(
|→
$)E T,E,1,q(
1
+
|→
$)E T*F,TE,1,q(
11
+
|→
|→
$)E T*a,FTE,1,q(
111
+
|→
$)E T,*aFTE,2,q(
111
+
- a здесь нужна для
возможности вернуться, в случае неудачи мы загружаем в стек
терминальный символ |→
$)E T,*aFTE,2,b(
111
+
- неудачное сравнение,
возврат по дереву
|→
$)E T*a,FTE,1,b(
111
+
|→
$)E T*F,TE,1,b(
11
+
|→
$)E T,E,1,b(
1
+
|→
|→
$)E F,TE,1,q(
21
+
|→
$)E a,FTE,1,q(
121
+
|→
$)E,aFTE,2,q(
121
+
-
удачное
сравнение, перемещаем указатель:
#a a
↑
+
;
|→
$)E,aFTE,3,q(
121
+
|→
$)E T,E aFTE,3,q(
1
121
+
+
|→ далее мы повторим то же
самое, но указатель уже передвинется, сравнение будет удачно, но
дерево останется,
↑
+
#a a
, и мы вернёмся назад и возьмём вторую
альтернативу |→
$)T,E aFTE,3,q(
2
121
+
|→ |→
$)F,ТE aFTE,3,q(
22
121
+
-
пояснения по поводу последней Т
2
в последних скобках: машина
1...,50,51,52,53,54,55,56,57,58,59 61,62,63,64,65,66,67,68,69,70,...88