Языки и трансляции. Мартыненко Б.К. - 140 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

Составители: 

Рубрика: 

138
Гомоморфизм h определяет трансляцию τ(h)={(x, h(x)) | x ∈Σ
*
}.
Устройство, которое по заданной цепочке x∈Σ
*
находит соответствующую
цепочку y = h(x), такую, что (x,y)∈τ(h), тривиально: оно должно посимвольно
просмотреть входную цепочку x и заменить каждый её символ a на h(a). Это
устройство является примером простейшего транслятора, реализующего
трансляцию τ(h).
Реалистичным примером транслятора, основанного на гомоморфизме,
является простейший ассемблер.
Транслятором для данной трансляции τ называется такое устройство,
которое по данной входной строке x вычисляет выходную цепочку y, такую, что
(x, y)∈τ. Желательными свойствами транслятора являются
1) эффективность (время, затрачиваемое на перевод входной строки,
должно быть линейно пропорционально её длине);
2) малый размер;
3) правильность (желательно иметь небольшой тест, такой, чтобы если
транслятор прошёл его, то это гарантировало бы правильную работу
транслятора на всех входных цепочках).
§ 1.2. Схемы
синтаксически управляемой трансляции
Трансляторы являются средством реализации трансляций, хотя их можно
рассматривать также и как способ их задания.
Способом спецификации трансляций, более сложных, чем те, которые
описываются при помощи гомоморфизма, является аппарат схем
синтаксически управляемых трансляций (SDTS — Syntax-Directed Translation
Schema).
Определение 1.2. Схемой синтаксически управляемой трансляции назы-
вается формальная система T=(N, Σ, ∆, R, S), где N — алфавит нетерминалов,
Σ — входной алфавит, ∆ — выходной алфавит, причём N ∩ Σ = ∅ и N ∩ ∆ = ∅;
R — конечное множество правил схемы вида A →α,β, где A ∈N, α∈(N ∪Σ)
*
,
β∈(N ∪∆)
*
, причём каждое вхождение нетерминала в цепочку α взаимно-
однозначно связано с некоторым вхождением одноимённого нетерминала в β,
и эта связь является неотъемлемым атрибутом правила; S ∈N — начальный
нетерминал.
Пусть A → α, β — правило схемы. Цепочка α называется синтаксической,
а β — семантической.
Для указания связей между вхождениями нетерминалов можно
использовать индексы. Связанные вхождения нетерминалов помечаются
одинаковыми индексами. Например, A → aB
(1)
bCB
(2)
, B
(2)
B
(1)
dC.

Страницы