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

UptoLike

ВУЗ: 

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

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

Рубрика: 

172
лежит множеству
22
FIRST ( FOLLOW ( )).
GG
Aβ Очевидно, что в нашем примере
2
() { , }.
FOLLOW
G
A
aa ba=
Получается так, что следует применять правило A → b, если аванцепочка из
или правило A
→ ε, если аван-
цепочка из множества Соображения о том,
как определять, какое правило из этих двух использовать для замены
нетерминала A, если аванцепочка равна ba, уже были рассмотрены в упомя-
нутом примере. Эту неопределенность можно разрешить, если для определения
правила, по которому следует раскрывать нетерминал, помимо нетерминала и
аванцепочки использовать ещё один параметр: T
A,L
— так называемую LL(k)-
таблицу
3
, ассоциированную с двумя индексами, первый из которых нетер-
минал A, второй — множество L, вычисляемое с учётом следующих рассуж-
дений.
Пусть имеется вывод в некоторой LL(k)-грамматике. Вспоминая
теорему 2.1, нетрудно сообразить, что критерием выбора правила A
→ β для
продолжения этого вывода может служить факт принадлежности текущей
аванцепочки множеству
FIRST ( ) FIRST ( ) FIRST ( ) FIRST ( ) ,
GG GG
kkkkkk
Lβα=β⊕ α=β⊕
где Это множество L и есть тот второй индекс таблицы T
A,L
, о
котором шла речь. По аванцепочке таблица T
A,L
выдаёт правило, которое
следует использовать для замены нетерминала A в текущей левосентенциаль-
ной форме. Ясно, что для любой cfg число таких LL(k)-таблиц конечно и все
таблицы, необходимые для анализа в данной грамматике, могут быть пост-
роены заблаговременно. Они используются k-предсказывающим алгоритмом
анализа в магазинных цепочках взамен нетерминалов (см. алгоритм 2.2 далее).
Теперь дадим точное определение LL(k)-таблиц и опишем способ
построения множества LL(k)-таблиц, необходимых для анализа в данной LL(k)-
грамматике.
Определение 2.12. Пусть G =(V
N
,V
T
,P,S) — контекстно-свободная грам-
матика. Для каждого A
∈V
N
и L ⊆ V
T
*
k
определим T
A,L
— LL(k)-таблицу,
ассоциированную с A и
L как функцию, которая по данной аванцепочке u ∈V
T
*
k
выдаёт либо значение error, либо A-правило
4
и конечный список подмножеств V
T
*
k
.
Именно:
1) T
A,L
(u) = error, если не существует ни одного правила вида A →α∈P,
такого, что u
∈
FIRST
G
k
(α) ⊕
k
L;
3
Не путать с управляющей таблицей k-предсказывающего алгоритма анализа.
4
A-Правило — правило cfg с нетерминалом A в левой части.
l m
*
SwA⇒α
2
2
.
{,}
(
())
FIRST
FOLLOW
G
G
aa ba
A
=
ε
22
2
( ( )) ( { , }),
FIRST
FIRST
FOLLOW
G
G
G
A
baabb
b
=
()
FIRST .
G
k
L
α
=

Страницы