Стр. 79 - Информационные структуры и их преобразование
Упрощенная HTML-версия
77
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ
ПРЕОБРАЗОВАНИЕ
(q, x,
α
, e)|
(q
1
, e, e, y).
Расширенный МП – преобразователь
определяется аналогично
расширенному МП – автомату.
Пример:
Переведем польскую запись в некоторую цепочку. Используем все
ту же грамматику.
Запишем автомат:
{(q
0
,q
1
), (*,+,(,),i), (N
∪
T
∪
$), (*,+,(,),i), (
δ
, q
0
, $, q
1
)}
(*,+,(,),i) – терминальные символы. (N – нетерминальные,
T – терминальные).
Q*E*Г -> Q*Г
*
*
∆
*
.
1.
(q
0
, e, E) = (q
0
, e+T, ET+);
2.
(q
0
, e, E) = (q
0
, T, T);
3.
(q
0
, e, T) = (q
0
, T*F, TF*);
4.
(q
0
, e, T) = (q
0
, F, F);
5.
(q
0
, e, F) = (q
0
, (E), E);
6.
(q
0
, e, F) = (q
0
, i, i);
7.
(q
0
, a, a) = (q
0
, e, e);
8.
(q
0
, e, e) = (q
0
, e, y).
i*(i+i) в этом случае мы должны получить iii+*.
(q
0
, i*(i+i), E, e) |
(q
0
, i*(i+i), T, T) |
(q
0
, i*(i+i), T*F, TF*) |
(q
0
, i*(i+i), T*(E), TE*) |
(q
0
, i*(i+i), T*(E+T), TET+*) |
(q
0
, i*(i+i), T*(E+F), TEF+*) |
(q
0
, i*(i+i), T*(E+i), TEi+*) |
(q
0
, i*(i+i), T*(T+i), TTi+*) |
(q
0
, i*(i+i), T*(i+i), Tii+*) |
(q
0
, i*(i+i), F*(i+i), Fii+*) |
(q
0
, i*(i+i), i*(i+i), iii+*) |
(q
0
, e, e$, iii+*) |
(q
0
, e, e, iii+*)
7 – сравнение выходной цепочки со входной.
2
7
