4.1.7. Построение транслирующей
грамматики по СУ - схеме.
Определение. Множество пар цепочек, выводимых с
помощью правил заданной Т - грамматики, образуют перевод, определяемый
этой грамматикой.
Последнее определение позволяет нам сделать вывод, что один и тот же
перевод может быть задан как с помощью СУ - схемы, так и с помощью Т -
грамматики. Эти два способа задания являются равноправными и, более того,
они допускают преобразование друг в друга.
Возможность одного из таких преобразований устанавливается следующим
утверждением.
Утверждение. Для каждой простой СУ-схемы Т можно построить
транслирующую грамматику ГТ такую, что переводы,
порождаемые СУ - схемой и Т - грамматикой, совпадают.
C(T) = C(ГТ)
Чтобы показать справедливость этого утверждения, опишем способ построения
Т - грамматики по заданной СУ - схеме.
Допустим, что задана СУ - схема
Т = {Vтвх, Vтвых,Va,Q,I}
и требуется построить Т - грамматику
Г~ = {V'твх,V'твых,V'a,R,I}.
Для того чтобы получить тот же самый перевод, необходимо, чтобы
Vтвх = Vтвх', Vтвых
=
Vтвх', Va = Va'.
Рассмотрим преобразование правила из множества Q СУ - схемы
A╝a
,b , где цепочки
a = xоAох1А1...xnAn
и b = yоAоу1A1...уnAn,
и поставим в соответствие этому правилу правило грамматики в виде:
А ╝ xоуоAох1у1A1...xnynAn.
Это можно сделать всегда, поскольку СУ - схема - простая и в каждом ее
правиле используются одни и те же нетерминалы в одном и том же порядке.
Рассмотренное построение обеспечивает включение во входную цепочку выходных
символов цепочки, порождаемой СУ-схемой. Следовательно, каждый шаг вывода
в Т - грамматике будет добавлять к выводимой цепочке те же символы, что
и СУ - схема добавляет к выходной цепочке.
Применение описанных положений рассмотрим на примере построения Т -
грамматики по СУ - схеме Т4.4.
Используя фигурные скобки для представления выходных символов и выполняя
пре-образование, получаем грамматику
