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

UptoLike

ВУЗ: 

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

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

Рубрика: 

139
Определение 1.3. Введём понятие трансляционной формы следующим
образом.
1) Пара цепочек (S, S) — начальная трансляционная форма, причём эти два
вхождения начального нетерминала связаны друг с другом по определению.
2) Если (αAβ, α′Aβ
′
) — трансляционная форма, в которой два явно
выделенных вхождения нетерминала A связаны, и если A →γ, γ′ — правило из
R, то (αγβ, α′γ′β
′
) — трансляционная форма, причём связь между нетермина-
лами в γ и γ′ — такая же, как в правиле, а нетерминалы в цепочках α и β
связываются с нетерминалами в цепочках α′ и β
′
в новой трансляционной
форме точно так же, как в предыдущей. Связь между нетерминалами является
существенной чертой трансляционной формы.
3) Трансляционными формами являются такие и только такие пары цепо-
чек, которые могут быть получены с помощью данных двух способов.
Это определение фактически вводит отношение непосредственной выводи-
мости одной трансляционной формы из другой.
В таком случае принято писать: (αAβ, α′Aβ
′
) (αγβ,α′γ′β
′
). Для степени,
транзитивного и рефлексивно-транзитивного замыкания этого отношения
используются соответственно следующие обозначения: , и . Когда ясно,
в какой схеме производится вывод, имя схемы может быть опущено.
Определение 1.4. Трансляция, заданная при помощи схемы синтаксически
управляемой трансляции T, есть множество τ(T) = {(x, y) | (S, S) (x, y), x∈Σ
*
,
y∈∆
*
} и называется синтаксически управляемой трансляцией (SDT).
Определение 1.5. Грамматика G
i
=(N, Σ, P
i
, S), где P
i
= {A →α|∃A →α, β∈
R}, называется входной грамматикой схемы. Грамматика G
o
=(N, ∆, P
o
, S), где
P
o
= {A →β |∃ A →α, β∈R}, называется выходной грамматикой схемы.
Очевидно, что G
i
и G
o
— контекстно-свободные грамматики.
Пример 1.2. Пусть SDTS T = ({E, T, F}, {a, +,
*
, (, )}, {a, +,
*
}, R, E), где
R = { (1) E → E + T, ET+ (2) E → T, T (3) T → T
*
F, TF
*
(4) T → F, F (5) F → (E),E (6) F → a, a
}.
Связь между нетерминалами в этих правилах очевидна, так как в
синтаксической и семантической цепочках каждого правила нет двух или более
вхождений одноимённых нетерминалов.
Рассмотрим какой-нибудь вывод в T, например:
(E,
E) ⇒ (E + T, ET+) ⇒ (T
(1)
+ T
(2)
, T
(1)
T
(2)
+)⇒ (F
(1)
+ T
(2)
, F
(1)
T
(2)
+) ⇒
⇒ (a + T, aT+) ⇒ (a + F
(1)
*
F
(2)
, aF
(1)
F
(2)
*
+) ⇒
⇒ (a + a
*
F, a a F
*
+) ⇒ (a + a
*
a, a a a
*
+).
Нетрудно догадаться, что τ(T )={(x, y) | x — инфиксная запись арифметиче-
ского выражения, y — эквивалентная постфиксная запись}.
Определение 1.6. Схема синтаксически управляемой трансляции называет-
ся простой, если в каждом её правиле A →α,β связанные нетерминалы в
цепочках α и β встречаются в одинаковом порядке.
T
⇒
k
T
⇒
T
+
⇒
*
T
⇒
*
T
⇒

Страницы