Стр. 55 - Информационные структуры и их преобразование
Упрощенная HTML-версия
53
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ
ПРЕОБРАЗОВАНИЕ
Пусть имеем грамматику G(N,
Σ
, P, S), в которой правила
занумерованы от 1 до р.
А также недетерминированный нисходящий распознаватель М1. Тогда
его называют левым анализатором. То есть он моделирует левый вывод в
грамматике G по правилу:
δ
(q, e, A) = (q,
α
, i) A:=
α
. (i – номер правила, записывается в
выходную цепочку).
Анализатор каждый раз развертывает нетерминал, распознанный
наверху магазина, в соответствии с некоторым правилом из Р, а также
одновременно выдает номер этого правила.
Если наверху магазина находится терминальный символ, то М1 по
правилу:
δ
(q, а, а) = (q1, е, е) проверяет, совпадает ли он с соответствующим
символом во входной цепочке.
М
L
{(q
0
,q
2
), (*,+,(,),i), (N
∪
T
∪
$), (1,…,6), (
δ
, q
0
, $, q
1
)};
(*,+,(,),i) – входной алфавит;
(N
∪
T
∪
$) – алфавит магазинных символов;
(1,…,6)
– номера правил на выходе;
q
0
– начальный символ автомата;
$
- начальный символ магазина;
Q*E*Г -> Q*Г
*
*
∆
*
.
1.
(q
0
, e, E) = (q
0
, E+T, 1);
2.
(q
0
, e, E) = (q
0
, T, 2);
3.
(q
0
, e, T) = (q
0
, T*F, 3);
4.
(q
0
, e, T) = (q
0
, F, 4);
5.
(q
0
, e, F) = (q
0
, (E), 5);
6.
(q
0
, e, F) = (q
0
, i, 6);
7.
(q
0
, a, a) = (q
0
, e, e);
8.
(q
0
, e, $) = (q
0
, e,
π
)
π
- левый разбор цепочки.
(q
0
, i*(i+i), E, e) |
(q
0
, i*(i+i), T, 2) |
(q
0
, i*(i+i), T*F, 23) |
(q
0
, i*(i+i), F*F, 234) |
(q
0
, i*(i+i), i*F, 2346) |
(q
0
, *(i+i), *F, 2346) |
(q
0
, (i+i), F, 2346) |
(q
0
, (i+i), (E), 23465) |
(q
0
, i+i), E), 23465) |
(q
0
, i+i), E+T), 234651) |
(q
0
, i+i), T+T), 2346512) |
(q
0
, i+i), F+T), 23465124)|
