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

UptoLike

ВУЗ: 

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

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

Рубрика: 

150
I. Докажем сначала, что если (x, y)∈τ
e
(P), то (x, y)∈τ(P’).
Пусть (x, y)∈τ
e
(P), т.е. (q
0
, x, Z
0
, ε)
(q, ε, ε, y). Посмотрим, как будет
действовать pdt P
’ с такой же входной цепочкой.
Согласно п.1 (q
0
’ , x, Z
0
’, ε)
(q
0
, x, Z
0
Z
0
’, ε). Далее согласно п.2 pdt P’
повторяет все движения pdt P, т.е. (q
0
,x, Z
0
Z
0
’,ε)
(q,ε, Z
0
’, y), а затем согласно
п.3 pdt P’ переходит в состояние q
f
:
(q, ε, Z
0
’
, y)
(q
f
, ε, α, y). Следовательно, (x, y)∈τ(P’).
II. Докажем теперь обратное, т.е. если (x,y)∈τ(P’), то (x, y)∈τ
e
(P). Пусть
(x, y)∈τ(P’), т.е. (q
0
’ , x, Z
0
’, ε)
(q
f
, ε, α, y) при некотором α∈Γ
*
. Рассмотрим
подробнее его движения. Первое движение согласно п.1 имеет вид
(q
0
’, x, Z
0
’ , ε) (q
0
, x, Z
0
Z
0
’, ε).
Далее pdt P’ оказывается в своем конечном состоянии q
f
. Это возможно
только в результате движения, построенного в соответствии с п.3, который
применим лишь тогда, когда на вершине магазина pdt P’ покажется символ Z
0
’,
т.е. дальнейшие движения имеют вид
(q
0
, x, Z
0
Z
0
’, ε) (q, ε, Z
0
’, y) (q
f
, ε, α, y).
На участке (q
0
, x, Z
0
Z
0
’, ε) (q, ε, Z
0
’, y) магазинный преобразователь P’
просто повторяет движения pdt P: (q
0
, x, Z
0
, ε) (q, ε, ε, y). А это значит, что
(x, y) ∈ τ
e
(P).
Из рассуждений I и II следует утверждение леммы.
Из лемм 1.3 и 1.4 следует
Теорема 1.2. Классы трансляций, реализуемых недетерминированными
магазинными преобразователями при конечном состоянии и пустом магазине,
совпадают.
Замечание 1.1. Принимая во внимание теорему 1.2, формулировку теоремы 1.1
можно усилить, не подчеркивая того факта, что простая трансляция реализуется
недетерминированным магазинным преобразователем при пустом магазине.
К сожалению, не всякая, даже простая, синтаксически управляемая транс-
ляция может быть реализована детерминированным МП-преобразователем.
§ 1.4. Детерминированная генерация
выходной цепочки трансляции
по левостороннему анализу входной цепочки
Определение 1.11. Схема синтаксически управляемой трансляции
называется семантически однозначной, если в ней не существует двух правил
вида A
→α,β и A →α,γ, в которых β≠γ.
Другими словами, семантическая цепочка однозначно определяется
правилом входной грамматики.
Определение 1.12. Пусть G = (V
N
, V
T
, P, S) — контекстно-свободная
грамматика, правила которой занумерованы как 1,2,…, p и S x — левосто-
ронний вывод x ∈ V
T
*
в грамматике G. Последовательность номеров правил π,
примененных в этом выводе, называется левосторонним анализом цепочки x.
*
P
−
−
*
P
′
−
−
*
P
′
−
−
*
P
′
−
−
P
−
−
'
P
−
−
'
*
P
′
−−
P
−
−
'
*
P
′
−
−
*
P
−
−
lm
π
⇒

Страницы