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

72 Содержание
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ ПРЕОБРАЗОВАНИЕ
образом: по данной входной цепочке х с помощью правил схемы трансляции
должен быть построен некоторый вывод цепочки у.
Правила порождающей
грамматики Pi
Правила выходной
грамматики P0
E+T
T
T*F
F
(E)
ET+
T
TF*
F
E
Польская
запись
Пусть имеется цепочка: i+i*i.
Преобразование по правилам:
E=>E+T, ET+=>T+T, TT+=>F+T, FT+=>i+T, iT+=>i+T*F,
iTF*+=>i+F*F, iFF*+=>i+i*F, iiF*+=>i+i*i, iii*+.
Этот метод проще, так как здесь нет необходимости в подпрограмме,
но преобразование по нему происходит дольше.
Схемой СУ-перевода называют цепочку символов:


















∆∪ ∈β Σ∪ ∈αβα=
∆
Σ
=
∗ ∗ ∗ ∗
символ начальный- S
N ; N ;, :A : вида правил система- R
алфавит выходной-
алфавит входной-
символыьные нетерминал- N
G
Пусть А:=α,β. Каждому вхождению некоторого нетерминала в цепочку
α, соответствует вхождение того же нетерминала в цепочку β. Если
нетерминал (В) входит в цепочку 1 раз, то соответствие очевидно, если
больше одного раза, то требуется индексировать.
Пусть A:=BcB, BBc. Если β γ= | B, то не ясно, где какое В брать.
При индексации же этой проблемы не возникает: A:=B1cB2, B1B2c.
Если { }
S,R,,,NG T ∆Σ =- СУ-схема, то ( )Т τ называется СУ-
транслятором.
Грамматики:
{ }
S,P,,NG
i i Σ называется входной;