Стр. 49 - Информационные структуры и их преобразование
Упрощенная HTML-версия
47
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ
ПРЕОБРАЗОВАНИЕ
Пример:
E:=E+T
E:=T
T:=T*F
T:=F
F:=(E)
F:=i
(
)
(
) (
)
{
}
(
)
(
) (
)
{
}
(
)
(
) (
)
{
}
(
)
(
)
(
)
(
)
(
)
e,q E,e,q
N b
e,q bZ,b,q
i,q,)E(,q F,e,q
F,q,F*T,q T,e,q
T,q,T E,q E,e,q
2
0
1
0
0
0
0
0
0
0
0
0
0
=
δ
Σ∪ ∈
=
δ
=
δ
=
δ
+
=
δ
q
0
– начальное состояние; z
0
:=E – начальный символ магазина;
q
2
– заключительное состояние.
Рассмотрим i*i+i:
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
e,q E,e,q i i*i,i i*i,q F F*F,i i*i,q
T F*T,i i*i,q T T,i i*i,q T E,i i*i,q E,i i*i,q
2
1
0
0
0
0
0
0
+
+
+
+
+
+
+ +
+ +
+
МП, работающий снизу вверх
Рассмотрим i+i*i в грамматике G(E). Рассмотрим правый вывод этой
цепочки:
E=>E+T=>E+T*F=>+i+i*i.
Цепочка i+i*i сворачивается к цепочке F+i*i по правилу F:=i. Это левая
свертка.
Формальное определение для левой свертки
Пусть
{
}
S,F,,NG
Σ
- грамматика.
αβω =ωα+ =>
A
S
- правый вывод в ней, и
имеется правило
β=
:A
. Говорят, что право выводимую цепочку
αβω
можно
свернуть слева к цепочке
ωα
A
с помощью правила
β=
:A
.
{
}
{
}
),i(, ,*, ,F,T,E
),i(, ,*,
q
q
q
Q
2
1
0
+
Σ=Γ
+Σ
=
{
}
{
}
), (, ,*,
, , ,
), (, ,*,
2
1
0
i
FTE
i
q
q
q
Q
+
Σ=Γ
+Σ
=
