Стр. 50 - Информационные структуры и их преобразование
Упрощенная HTML-версия
48
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ
ПРЕОБРАЗОВАНИЕ
Восходящий распознаватель
По КС-грамматике можно построить эквивалентный расширенный
МП-автомат, работа которого заключается в отсечении основ. Для этого
случая удобно представить магазин в виде цепочки, верхним символом
которой является самый правый. Конфигурация автомата остается прежней, а
отношения перехода несколько меняются.
Пусть есть автомат:
{
}
F,Z,q,,,,Q P
0
δΓΣ =
;
(
)
(
)
γ
= αβω δ
,q
,a,q
1
0
.
Отношения перехода будут иметь вид:
(
)
(
)
αγ ω
αβω
,,q
,a,q
0
, т.е. верхний
символ становится справа.
E:=E+T;
E:=T;
T:=T*F;
F:=(E);
F:=i.
Введем символ «маркер дна» - $, который не принадлежит грамматике,
добавим его в магазин.
(
)
(
)
(
)
(
)
. :A:
правило
имеется
грамматики
правилах
в когда т.т., и т. место имеет это
правый;
на символ левый
заменяя
такт, -е
выполняем
- A,$q
,$e,q
магазин.
в его
загружаем
то
символ,
ьный
нетерминал
входе на
существует
если - a,$q ,$a,q
0
0
0
0
α=
=α
δ
=
δ
+
=
i
)
(
*
a
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
,$q E,$e,q .7
F,$q i,$e,q .6
F,$q )E,$(e,q .5
T,$q F,$e,q .4
T,$q F*T,$e,q .3
E,$q T,$e,q .2
E,$q T E,$e,q .1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
=
δ
=
δ
=
δ
=
δ
=
δ
=
δ
= +
δ
{
}
{
}
{
}
1
0
1
0
q ,$, q,,,,Q P
символов
магазинных
множество
- ),i(, ,*, ,F,T,E
),i(, ,*,
символ кон. - q
символ нач. - q Q
δΓΣ =
+
Σ=Γ
+=Σ
=
)
(
)
(
) (
) (
)
)
(
) (
) (
)
(
)
) (
)
(
)
(
)
(
)
E*E,$e,q T*E,$e,q F*E,$e,q i*E,$e,q *E,$i,
E,$i,*q T E,$i,*q F E,$i,*q i E,$i,*q
E,$i*i,
E,$i*i,q T,$i*i,q F,$i*i,q i,$i*i,q
,$i*i i
0
0
0
0
0
0
0
)4(
0
)6(
0
0
0
)2(
0
)4(
0
0
+
+
+
+
+
+
+
+
+
