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

Содержание 71
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ ПРЕОБРАЗОВАНИЕ
5.2. Синтаксически управляемый перевод
Транслятором, реализующим перевод Т, назовем устройство, которое
по данной входной цепочке х вычисляет выходную цепочку у, такую, что
( ) T y,x ∈ .
Определим основные требования к такому транслятору:
- определение перевода должно устанавливать однозначное
соответствие между парами цепочек;
- определение перевода должно быть легко алгоритмизировано;
- время обработки входной цепочки должно линейно зависеть
от n =ω;
- программа транслятора должна проверяться тестом конечной
длины, гарантирующим правильность его работы.
Схема синтаксически управляемого перевода (СУ-перевода)
представляет собой грамматику, в которой каждому правилу присоединяется
элемент перевода.
Всякий раз, когда правило участвует в выводе входной цепочки, с
помощью элемента перевода вычисляется часть выходной цепочки,
порождаемой этим правилом.
Рассмотрим следующий пример :
{ }
{ } цепочка обращенная x 1,0|x L
1. и 0 из состоящююх, цепочку содержитязык 1,0|x L
R R
2 − =
=
Пусть имеется цепочка – 0011, необходимо получить - 1100.
Порождающие
правила
Преобразующие
правила
S:=0S S:=S0
S:=1S S:=S1
S:=e S:=e
Преобразование по правилам:
S=>0S, S0=>00S, S00=>001S, S100=>0011S, S1100=> 0011, 1100.
Схема трансляции определяет перевод Т. По этой схеме можно
построить транслятор, реализующий перевод ( )Т τ , работающий следующим