part342

Пред.Страница След.Страница Раздел Содержание

3.4.2 Построение функции ПЕРВ(µ)
Значение функции ПЕРВ(m) можно определить пользуясь следующими правилами:
1) Если цепочка µ начинается терминальным символом и имеет вид bµ', то функция
ПЕРВ(µ) = {b},
2) Если цепочка µ является пустой цепочкой, µ = $, то функция

ПЕРВ(µ) = $,

3) Если цепочка µ начинается нетерминальным символом  и имеет вид µ', а в схеме грамматики имеется n правил, в любой части которых находится символ :
 ® a₁ | a₂ | ... | a_n , и, если не существует вывода  ==>* $, то функция ПЕРВ(µ') представляет собой объединение множеств:
ПЕРВ(µ') = ПЕРВ(a₁) И ПЕРВ (a₂) И...ИПЕРВ(a_n), 4) Если цепочка µ начинается нетерминальным символом и имеет вид µ', в схему грамматики входят n правил вида
 ® a₁ | a₂ | ... | a_n, и  является аннулирующим нетерминалом, т.е. существует  ==> *$, то функция ПЕРВ(µ')=ПЕРВ(µ') И ПЕРВ(a ₁)И ПЕРВ(a ₂) И...И ПЕРВ(a _n). В качестве примера выполним вычисление функции ПЕРВ для правил следующей грамматики:
Г_3.
2 : R = { (1) <A> ® <C>c, (2) <A> ® g<D>,
(3) ® $,
(4) ® b<C><D><E>,
(5) <C> ® <D>a,
(6) <C> ® ca,
(7) <D> ® $,
(8) <D> ® d<D>,
(9) <E> ® g<A>f,
(10) <E> ® c }. Вначале найдем значения функции для правых частей правил (2), (4), (6), (8), (9) , (10) , начинающихся терминальными символами: ПЕРВ(g,<D>,) = {g}
ПЕРВ(b<C><D><E>) = {b}
ПЕРВ(ca) = {c}
ПЕРВ(d<D>) = {d}
ПЕРВ(g<A>f) {g}
ПЕРВ(c) = {c} Затем вычислим функцию для правил (5) и (6) : ПЕРВ (<C>) = ПЕРВ (<D>a) И ПЕРВ (ca). Учитывая, что <D> является аннулирующим нетерминалом, получаем: ПЕРВ(<C>) = ПЕРВ(a) ИПЕРВ(<D>) И{c} = {a}И{d}И{c}={a,d,c}. При вычислении функции для правил (1) и (2) также необходимо иметь в виду то, что является аннулирующим терминалом, поэтому имеем: ПЕРВ(<A>) = ПЕРВ(<C>c) И ПЕРВ(g<D>) =
ПЕРВ(<C>c) И ПЕРВ() И ПЕРВ(g<D>) = {a,d,c} И {b} И{g} = {a,b,c,d,g}.

Пред.Страница След.Страница Раздел Содержание