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

UptoLike

ВУЗ: 

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

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

Рубрика: 

173
2) T
A,L
(u)=(A →α, ·Y
1
, Y
2
,…, Y
m
Ò), если A→α — единственное правило из P,
такое, что u
∈
FIRST
G
k
(α) ⊕
k
L; при этом, если α = x
0
B
1
x
1
B
2
…B
m
x
m
, B
i
∈V
N
,
x
j
∈V
T
*
, то
11
( ... ) ,
= FIRST
G
k
ii i m
k
i
x
Bx B L
Y
++
⊕ i =1,2,…,m; j = 0,1,…,m; m ≥ 0;
3)
T
A,L
(u) = undefined, если существует несколько A-правил: A →α
1
|α
2
|…|α
n
,
таких, что
()
FIRST
G
k
i
k
uL
α⊕
∈
для 1 ≤ i ≤ n, n ≥ 2.
Множество терминальных цепочек Y
i
называется множеством локальных
правых контекстов для B
i
. В частности, если m =0, то T
A,L
(u) = (A → α, ∅).
Случай 3 для LL(k)-грамматик не актуален.
Пусть мы имеем левосторонний вывод в LL(k)-грамматике: S
wA
γ
wx.
Как
было сказано в начале этого параграфа, именно таблица T
A,L
, где
(),
FIRST
G
k
L
γ
=
сообщит, что следующую за wAγ сентенциальную форму
следует получать при помощи правила A → α, если для окажется,
что T
A,L
(u) = (A → α, ·Y
1
,Y
2
,…, Y
m
Ò). Если α = x
0
B
1
x
1
B
2
…B
m
x
m
, то следующая за
wA
γ сентенциальная форма будет wαγ = wx
0
B
1
x
1
B
2
…B
m
x
m
γ, и в свое время
раскрытием B
1
будет руководить LL(k)-таблица T
B
1
,Y
1
, а раскрытием B
m
— LL(k)-
таблица T
B
m
,Y
m
.
Пример 2.8. Рассмотрим уже не раз обсуждавшуюся LL(2)-грамматику с
правилами S
→ aAaa | bAba; A → b | ε и построим все LL(2)-таблицы,
необходимые для анализа в этой грамматике.
Начнём с таблицы T
S,{ε}
: именно она диктует выбор первого правила для
раскрытия нетерминала S. Используя правило S
→ aAaa, вычисляем
2
(){}{,}.
FIRST
G
k
aAaa ab aa⊕ε= Используя правило S → bAba, вычисляем
2
(){}{}.
FIRST
G
k
bAba bb⊕ε= Соответственно определяем LL(2)-таблицу T
0
= T
S,{ε}
(табл. 2.3).
Глядя на T
0
, легко определить, что потребуются ещё таблицы T
1
= T
A,{aa}
и
T
2
= T
A,{ba}
. Таблица T
1
получается с учётом того, что для правила A → b получаем
2
() { } { },
FIRST
G
k
baaba⊕= а для правила A →ε —
2
() {}{}.
FIRST
G
k
aa aaε⊕ =
Таблица T
2
получается с учётом того, что для правила A → b имеем
2
() { } { },
FIRST
G
k
bbabb⊕=а для правила A →ε —
2
() {}{}.
FIRST
G
k
ba baε⊕ = В
правых частях правил для нетерминала A нет ни одного нетерминала. Поэтому
в двух последних таблицах множества локальных правых контекстов пусты.
При построении этих LL(2)-таблиц мы придерживались простой
дисциплины: начинали с построения начальной таблицы T
S,{ε}
, а затем в каждой
из уже построенных LL(2)-таблиц использовали значения элементов, чтобы
определить пары индексов других необходимых таблиц — каждое вхождение
нетерминала в правило сочеталось с соответствующим локальным множеством.
Таблица 2.3
LL(2)- u
T(u)
l m
*
⇒
l m
*
⇒
()
FIRST
G
k
x
u ∈

Страницы