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

UptoLike

ВУЗ: 

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

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

Рубрика: 

189
II. Покажем теперь, что ϕ(A, B) ⊆ϕ
j
(A, B). Пусть w ∈ϕ(A, B) благодаря
тому, что существует вывод
Индукцией по длине вывода l покажем, что w ∈ϕ
j
(A, B).
База. Пусть
l = 1. Имеем Тогда существует правило
A →γBα∈P и согласно шагу 1 алгоритма 2.7 w ∈ϕ
0
(A,B) ⊆ϕ
j
(A, B).
База доказана.
Индукционная гипотеза. Предположим, что аналогичное утверждение
выполняется для всех l ≤ n (n ≥ 1).
Индукционный переход. Докажем, что тогда аналогичное утверждение
верно
для l = n +1. Пусть w ∈ϕ(A, B) благодаря тому, что существует вывод
длиной n +1 вида
в котором
11
1
2
11
1
***
... ...
FIRST ( ) FIRST ( ) FIRST ( ) FIRST ( )
FIRST ( ... ) ( ) FIRST ( ... )
() (),
pp p
m
GGG
GG G G
k
kk k k
GG
pppp
kmkm
kk
j
jj
XX X X X X B
w
XB XX XB XX
AB AB
−+
++
+
⇒δ, ⇒η, ⇒β χ,α=χη,γ=δβ,
∈α=χη=χ⊕ η⊆
⊆ϕ( , )⊕ ⊆ϕ , ⊕ ⊆
⊆ϕ , =ϕ ,
поскольку
Последнее вложение следует в соответствии с индукционной гипотезой из
существования вывода длиной не больше n.
Здесь
использовано существование правила
благодаря которому, учитывая шаг 2
алгоритма 2.7, мы заключили, что
1
().
j
wAB
+
∈ϕ , Что и требовалось доказать.
Из рассуждений I и II следует равенство ϕ
j
(A, B)=ϕ(A, B) и утверждение
теоремы.
§ 2.10. k-Предсказывающий
алгоритм трансляции
Ранее в этой части пособия была доказана теорема 1.3 о том, что выходную
цепочку простой семантически однозначной трансляции можно сгенерировать
по левостороннему анализу входной цепочки посредством детерминирован-
ного магазинного преобразователя. Если входная грамматика схемы синтакси-
чески управляемой трансляции принадлежит классу LL(k), то мы имеем
детерминированный механизм, правда, не преобразователь, а k-предсказываю-
щий алгоритм анализа, который выдаёт левосторонний анализ входной
цепочки трансляции, задаваемой такой схемой. Кроме того, в лемме
1.1 этой
части пособия был описан способ построения недетерминированного магазин-
ного преобразователя, реализующего трансляцию, определяемую простой
схемой. Использованный в ней приём можно применить для модификации k-
11
1
2
**
... ...
ppp
p
m
GGG
A
XX X X X X X B B
−+
⇒⇒δη⇒δβχη=γα,
FIRST ( ) ( ) ( ).
G
pp
kj
X
BXBχ⊆ϕ , ⊆ϕ ,
*
p
G
X
B⇒β χ
11
1
2
... ... ,
ppp
m
AXXXXX X P
−+
→∈
и FIRST ( ).
G
k
ABw⇒γ α ∈ α
и FIRST ( ).
l
G
k
ABw⇒γ α ∈ α

Страницы