Стр. 63 - Информационные структуры и их преобразование

Содержание 61
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ ПРЕОБРАЗОВАНИЕ
Итак, восходящий разбор связан с отображением входной цепочки в
последовательность обращенных правых выводов.
Пусть G(N, Σ , P, S) – грамматика, правила которой занумерованы
1, 2 … р.
Пусть α - некоторая цепочка в этой грамматике, где α ∈ (N∪Σ*).
Тогда правый разбор цепочки α - обращенная последовательность
правил, примененных при правом выводе.
1) E:= E+T;
2) E:=T;
3) T:=T*F;
4) T:=F;
5) F:=(E);
6) F:=i.
2 3 5 1 4 6 2
E => T => T*F => T*(E) => T*(E+T) => T*(E+F) => T*(E+i) => T*(T+i)
=>
4 6 4 6
=> T*(F+i) => T*(i+i) => F*(i+i) => i*(i+i).
Правый разбор: 6 4 6 4 2 6 4 1 5 3 2.
Набираем в магазине цепочку терминальных символов и смотрим, есть
ли в правых частях правил соответствующие нетерминальные символы:
МП={Q, Σ , Г, ∆, δ, q0 , Z, F};
δ : Q*Σ *Г -> Q1*Г* *∆* - функция отображения, где * - означает
цепочки.
Будем рассматривать Z как маркер дна магазина,
Σ {i, (, ), *, +},
∆ (1…6) 1,2…6 – номера правил,
Г {N ∪ Σ}.
Рассмотрим несколько примеров функции отображения:
1) δ(q, a, Z) = (q, Za, e),
2) δ(q, e, Zα) = (q, A, i),
3) δ(q, e, ZE) = (r, e, e).
A:= α, q ∈ Q, r ∈ F;
Е – начальный символ грамматики,