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

UptoLike

ВУЗ: 

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

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

Рубрика: 

192
Таблица 2.8
Аванцепочки
Маг.
сим-ы
a +
∗
( )
ε
E
TE’
TE’
E’
+T+’E’
ε ε
T
FT’
FT’
T’
ε
*
F
*
’T’
ε ε
F
aa’
(E)
a pop
+ pop
* pop
( pop
) pop
a’
+’
*
’
p a s s
$ accept
Посмотрим, как будет действовать построенный нами 1-предсказывающий
алгоритм трансляции на входной цепочке (a+a)
5
.
(),$, (),$, (), $,
( ),()$, ),)$, ),)$,
), ) $, ), ) $,
), ) $, ),
() ( ) ( )
( ) ( ) ( )
() ( )
() (
aaE aaTE aaFTE
a a E TE a a E TE a a TE TE
a a FTETE a a aaTETE
aaTETE aTE
−− −− −−
−− −− −− −−
−− −− −−
−− −−
′
′′
+ε + ε + ε
′′ ′′ ′ ′′
+ε+ε+ ε
′′ ′′ ′′′ ′′
+ε+ ε
′′′ ′′ ′′
+ε+
)$, ),)$,
), ) $, ), ) $,
), ) $, ), ) $,
), ) $, ), ) $,
), ) $,
) ( )
() ()
() ( )
() ()
() (
TE a a E TE a
a T ETE a aT ETE a
aFTETEa aaaTETEa
aT E TE a T E TE aa
ETE aa
−− −−
−− −− −−
−− −− −−
−− −− −−
−− −−
′′ ′ ′′
+
′′′′ ′′′′
+++ +
′′′ ′′ ′′′′ ′′
++
′′′ ′ ′′ ′′ ′ ′′
++
′′ ′′
+
), ) $, ),) $, , $,
,$, ,$,
) ( ) ( )
() ().
ETEaa TEaa TEaa
Eaa aa
−
−−−−−
−− −−
′′′ ′′ ′′
++ε+
′
ε+ε+
Итак, ℑ((a + a)) = aa+. Нетрудно проверить, что
*
(,) ( ), ().
T
EE a a aa⇒+ +
Теорема
2.10. Пусть T = (N, Σ, ∆, R, S) — простая семантически
однозначная
схема синтаксически управляемой трансляции с входной
грамматикой G
i
класса LL(k) и ℑ = (Σ, Γ∪{$}, ∆, M, T
0
, $) — k-
предсказывающий алгоритм трансляции, построенный посредством
алгоритма 2.8, примененного к данной схеме трансляции T. Тогда τ(T)=τ(ℑ).
Доказательство. Справедливость данного утверждения следует из того
факта, что LL(k)-анализатор, построенный по входной грамматике данной
5
Не следует путать скобки, ограничивающие компоненты конфигурации, со скобками —
входными символами.

Страницы