Теория формальных языков, грамматик и автоматов. Ишакова Е.Н. - 33 стр.

UptoLike

ВУЗ: 

ОГУ | Оренбург

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

Рубрика: 

33
∀ i≠j, 0<i≤n, 0<j≤n.
Т.е. если для символа А отсутствует правило вида А→ε, то все множества
FIRST(1, α
1
), FIRST(1, α
2
),…, FIRST(1, α
n
) должны попарно не пересекаться, ес-
ли же присутствует правило А→ε, то они не должны также пересекаться с мно-
жеством FOLLOW(1, A).
Для построения распознавателей для LL(1)-грамматик необходимо по-
строить множества FIRST(1, x) и FOLLOW(1, A). Причем, если строка х будет
начинаться с терминального символа а, то FIRST(1, x)=a, и если она будет на-
чинаться с нетерминального символа А, то FIRST(1, x)=FIRST(1, A). Следова-
тельно, достаточно рассмотреть алгоритмы построения множеств FIRST(1, A) и
FOLLOW(1, A) для каждого нетерминального символа А.
Алгоритм 6.1. Построение множества FIRST(1, A)
Для выполнения алгоритма необходимо предварительно преобразовать
исходную грамматику G в грамматику G′, не содержащую ε-правил (см. лабо-
раторную работу № 4). Алгоритм построения множества FIRST(1, A) использу-
ет грамматику G′.
Шаг 1. Первоначально внести во множество первых символов для каждо-
го нетерминального символа А все символы, стоящие в начале правых частей
правил для этого нетерминала, т.е.
∀ А∈V
N
FIRST(1, A) = {X | A→Xα ∈P, X∈(V
T
∪V
N
), α∈(V
T
∪V
N
)
*
}.
Шаг 2. Для всех А∈V
N
положить:
FIRST
i+1
(1, A) = FIRST
i
(1, A) ∪ FIRST
i
(1, B), ∀ В∈(FIRST(1, A)∩V
N
).
Шаг 3. Если существует А∈V
N
, такой что FIRST
i+1
(1, A) ≠ FIRST
i
(1, A), то
присвоить i=i+1 и вернуться к шагу 2, иначе перейти к шагу 4.
Шаг 4. Исключить из построенных множеств все нетерминальные симво-
лы, т.е.
∀ A∈V
N
FIRST(1, A) = FIRST
i
(1, A)
\ N
.
Алгоритм 6.2. Построение множества FOLLOW(1, A)
Алгоритм основан на использовании правил вывода грамматики G.
Шаг 1. Первоначально внести во множество последующих символов для
каждого нетерминального символа А все символы, которые в правых частях
правил вывода встречаются непосредственно за символом А, т.е.
∀ A∈V
N
FOLLOW
0
(1, A) = {X | ∃ B → αAXβ ∈ P, B ∈ V
N
, X ∈ (V
T
∪V
N
),
α
,
β
∈(V
T
∪V
N
)
*
}.
Шаг 2. Внести пустую строку во множество FOLLOW(1, S), т.е.
FOLLOW(1, S) = FOLLOW(1, S)∪{
ε
}. 
     ∀ i≠j, 0

Страницы