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

UptoLike

ВУЗ: 

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

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

Рубрика: 

179
каждым из них. Следовательно, общее число движений — не более чем
n + c
× n. Что и требовалось доказать.
§ 2.6. Тестирование LL(k)-грамматик
Пусть имеется контекстно-свободная грамматика G. Алгоритмы
построения управляющих таблиц LL(k)-анализаторов 2.1 и 2.3 достигают
успеха только если G — LL(k)-грамматика. Поэтому естественно поинтересо-
ваться, является ли данная грамматика G LL(k)-грамматикой для данного
значения k. Для
ответа на этот вопрос можно воспользоваться теоремой 2.1, а
для k = 1 и сильных LL(k)-грамматик также и теоремой 2.2 при данном
значении k. Напомним, что в общем случае cfg G = (V
N
,V
T
,P,S) не является
LL(k)-грамматикой тогда и только тогда,
когда существуют левосторонний
вывод вида и пара различных A-правил
A →β и A →γ∈P (β≠γ), для
которых () ) () ) ,
(FIRST (FIRST
GG
kk
kk
LLβ⊕ ∩ γ⊕ ≠∅где
().
FIRST
G
k
L
α
=
Для описания алгоритма, разрешающего этот вопрос, введём вспомогатель-
ную функцию.
Определение 2.13. Пусть G = (V
N
,V
T
,P,S) — cfg и A ∈V
N
. Определим
**
TT
lm
*
FIRST
k
G
k
ALV SwAwVLσ( ) ={ ⊆ ∃ ⇒ α,∈,= (α)}.
Алгоритм 2.4: тестирование LL(k)-грамматик.
Вход: G = (V
N
,V
T
,P,S) — контекстно-свободная грамматика
Выход: “да”, если G — LL(k)-грамматика; “нет” — в противном случае.
Метод.
1. Для каждого нетерминала A, для которого существуют две или более
альтернативы, вычисляется
σ(A).
2. Пусть A →β и A →γ∈P (β≠γ) — два различных A-правила. Для каждого
L
∈σ(A) вычисляется
() ) () ) .
( ) (FIRST (FIRST
GG
kk
kk
LL
fL
β
⊕∩
γ
⊕≠∅
=
Если
f(L) ≠ ∅, то алгоритм завершается с результатом “нет”.
Если f(L)
= ∅ для всех L∈σ(A), то шаг 2 повторяется для всех пар A-правил.
3. Повторять шаги 1 и 2 для всех нетерминалов из множества V
N
.
4. Завершить алгоритм с результатом “да”. Этот шаг выполняется, если
были рассмотрены все нетерминалы и алгоритм не завершился на шаге 2.
Разумеется, это описание можно считать алгоритмом, если мы располагаем
алгоритмами для вычисления функций для
β∈V
*
и σ(A) для A ∈V
N
.
§ 2.7. Вычисление функции
()
FIRST
G
k
β
Алгоритм 2.5: вычисление FIRST ( )
G
k
β
для β∈V
*
.
Вход: G =(V
N
,V
T
,P,S) — контекстно-свободная грамматика и β = X
1
X
2
…X
n
,
X
i
∈V (i =1, 2,…, n; n ≥ 0).
Выход: FIRST ( )
G
k
β .
lm
*
SwA⇒α
FIRST ( )
G
k
β

Страницы