Стр. 59 - Информационные структуры и их преобразование
Упрощенная HTML-версия
57
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ
ПРЕОБРАЗОВАНИЕ
Алгоритм нисходящего разбора
Леворекурсивные грамматики неприменимы для нисходящего разбора.
Используются 2 стека (магазина), счетчик, в котором хранится текущая
позиция указателя.
Пусть задана не леворекурсивная грамматика G{N,
Σ
, P, Z}. Правила из
Р занумерованы для каждого нетерминала А
∈
N. Упорядочим его
альтернативы:
А =
α
1
|
α
2
|
α
3
.
A
1
=
α
1
.
A
2
=
α
2
.
A
3
=
α
3
.
Конфигурацию алгоритма будем характеризовать четверкой: (S, i, L
1
,
L
2
), где S – состояние алгоритма.
−
−
−
=
дереву
по
возврат
и
дерева)
(свертка
сравнение
неудачное
b
состояние
ьное
заключител
t
)
сравнение
удачное
и
дерева
я
разрастани
(процесс
состояние
рабочее
нормальное
q
S
i – счетчик положения входного указателя.
L
1
– стек, содержащий историю используемых альтернатив и
терминальных символов, которые прошли удачное сравнение.
L
2
– вершина слева хранит левовыводимую цепочку, ту ее часть,
которая получилась к данному моменту в результате развертки нетерминала.
(q, i, $
α
, A
β
) |
(q, i, $
α
,
α
i
β
). Если существует A
i
=
α
i
(А имеет i
альтернатив).
(q, i, $
γ
, a
α
i
β
) |
(q, i+1, $
γ
A
i
a,
α
i
β
). Если A
i
= а
α
i
и произошло
сравнение, то а (терминал входной цепочки) = а (терминал в растущем
дереве).
Примечание: i и индекс у
α
i
– это две разные вещи!
(q, n+1, $
π
, e) |
(t, n+1, $, e);
h(A
i
) = i h(
π
) – номера используемых правил;
h(a) = e.
неудачное сравнение: (q, i, $
γ
A
i
a,
β
) |
(q, i, $
γ
A
i
a,
β
) |
теперь возврат по дереву |
(q, i-1, $
γ
, A
i
a
β
).
