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

50 Содержание
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ ПРЕОБРАЗОВАНИЕ
Проблему разбора теперь можно трактовать как последовательность
левых или правых выводов.
Пусть G(N, Σ , P, S) – грамматика, правила которой занумерованы 1, 2
… р.
Пусть α - некоторая цепочка в этой грамматике, где α ∈ (N∪Σ*).
Тогда левый разбор цепочки α есть последовательность правил,
примененных при левом выводе. S => +α.
Тогда правый разбор цепочки α - обращенная последовательность
правил, примененных при правом выводе.
2 3 4 6 5 1 2
1) E:= E+T E =>T =>T*F =>F*F =>i*F =>i*(E) =>i*(E+T) =>i*(T+T) =>
2) E:=T 4 6 4 6
3) T:=T*F =>i*(F+T) =>i*(i+T) =>i*(i+F) =>i*(i+i).
4) T:=F;
5) F:=(E);
6) F:=i.
Левый разбор: 2 3 4 6 5 1 2 4 6 4 6.
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.
Пусть имеем G(N, Σ, P, S) - грамматику и занумерованные правила (см.
выше).
Будем писать αi ⇒ βL , если это левый вывод и αi ⇒ βR , если правый.
+
+