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

UptoLike

ВУЗ: 

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

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

Рубрика: 

168
Итак,
A((a+a))=14714862486363. Нетрудно проверить, что E
(a + a), где
π = 14714862486363.
Теорема 2.4. Алгоритм 2.1 производит правильный 1-предсказывающий
алгоритм анализа для любой LL(1)-грамматики.
Доказательство. Пусть G =(V
N
,V
T
,P,S) — LL(1)-грамматика, и A —
1-предсказывающий
алгоритм анализа для грамматики G, построенный
согласно алгоритму 2.1. Требуется доказать, что S
x тогда и только тогда, когда
(x, S$, ε) (ε, $, π).
По индукции докажем вспомогательное утверждение, общий смысл
которого состоит в том, что анализатор в своём магазине воспроизводит
последовательность открытых частей сентенциальных форм левостороннего
вывода входной цепочки, если она выводима в данной грамматике G, причём
если π — последовательность номеров правил, участвующих в её выводе, то π
образуется на выходе анализатора.
I.
Докажем сначала, что если S
xα, где x ∈Σ
*
— закрытая часть, а α∈
(V
N
∪ V
T
)
*
— открытая часть данной сентенциальной формы, то для любой
цепочки y∈Σ
*
, такой, что
11
() (),
FIRST FIRST
GG
y
∈
α анализатор совершает переход
(xy, S$, ε) (y, α$, π).
Индукция по l = |π|.
База. Пусть l =1, т. е. π = i, где i — номер некоторого правила грамматики.
Пусть и y ∈Σ
*
— такая цепочка, что На един-
ственном шаге этого вывода применялось правило вида S → xα, имеющее
номер
i. Для всех согласно алгоритму 2.1 M(S, a) =
(xα, i).
Посмотрим, как будет действовать анализатор, начиная с конфигурации
(xy, S$, ε).
Очевидно, что аванцепочка
и,
следовательно, M(S, u)=(xα, i).
Поэтому причём последний переход
реализуется посредством pop-движений. База доказана.
Индукционная
гипотеза. Предположим, что утверждение выполняется
для всех l ≤ n (n ≥ 1).
Индукционный переход. Докажем утверждение для l= n +1. Пусть
имеется левосторонний вывод длиной n +1:
Здесь , iA z
′
′
π=π α = γ, βγ= α, где
**
N
T
, , , , .zV x xzAV V
′
∈= ∈βγ∈ На пос-
леднем шаге вывода применялось правило A →β
— i-е правило из множества
правил
P.
Согласно алгоритму 2.1
M(A, a) = (β, i) для всех
11
FIRST ( FOLLOW ( )). (2.1)
GG
aA∈β
l m
π
⇒
l m
π
⇒
l m
π
⇒
*
−−
*
−−
()
l m
i
Sx⇒α
()
l m
l m
i
Sx xAx x
π
′′ ′ ′
⇒α= γ⇒ γ=α.
β
'
11
() ().
FIRST FIRST
GG
y
⊆
α
1
1
( FOLLOW ( ))
FIRST
G
G
ax S∈α
*
( , $, ) ( , $, ) ( , $, ),
x
yS xyx i y i−− −−εα α
111
11
() ( ) ( ) ( ())
FIRST FIRST FOLLOW
FIRST FIRST
GGG
GG
x
yx x x S
u
⊆
∈α=αε α
=

Страницы