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


3.5. Функции  ПЕРВ, СЛЕД  и  ВЫБОР. 

 

Множество ВЫБОР строится для каждого правила и включает те терминальные символы, при появлении которых под читающей головкой распознаватель должен применять это правило.

Для определения множества ВЫБОР используются функции ПЕРВ и СЛЕД . Аргументом функции ПЕРВ может быть любая цепочка полного словаря µ, а значением функции ПЕРВ(µ) является множество терминальных символов, которые могут стоять на
первом месте в цепочках, выводимых из цепочки µ.

Построение функции ПЕРВ(µ)  

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

ПЕРВ(µ) = {b},

 
2)  Если цепочка µ является пустой цепочкой, µ = $, то функция
 

ПЕРВ(µ) = $,
 

3)   Если цепочка µ начинается нетерминальным символом <B> и имеет вид <B>µ', а в схеме грамматики имеется n  правил, в любой части которых находится символ <B>:
 

<B>  ® a1 | a2 | ... | an ,

и, если не существует вывода <B> ==>* $, то функция ПЕРВ(<B>µ') представляет собой объединение множеств:
 

ПЕРВ(<B>µ') = ПЕРВ(a1) È ПЕРВ (a2) È...ÈПЕРВ(an),

4)   Если цепочка µ начинается нетерминальным символом и имеет вид <B>µ', в схему грамматики входят n правил вида
 

<B>  ® a1 | a2 | ... | an ,

и <B> является аннулирующим нетерминалом, т.е. существует  <B> ==> *$, то функция

 

ПЕРВ(<B>µ')=ПЕРВ(µ') È ПЕРВ(a 1)È ПЕРВ(a 2) È...È ПЕРВ(a n).

В качестве примера выполним вычисление функции ПЕРВ для правил следующей грамматики:

 
 

 Г3.6 :     R = {      (1) <A>  ® <B><C>c,

(2) <A>  ® g<D><B>,
(3) <B>  ® $,
(4) <B>  ® b<C><D><E>,
(5) <C>  ® <D>a<B>,
(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>,<B>) = {g}
ПЕРВ(b<C><D><E>) = {b}
ПЕРВ(ca) = {c}
ПЕРВ(d<D>) = {d}
ПЕРВ(g<A>f) {g}
ПЕРВ(c) = {c}

Затем вычислим функцию для правил (5) и (6) :

ПЕРВ (<C>) = ПЕРВ (<D>a<B>) È ПЕРВ (ca).

Учитывая, что <D> является аннулирующим нетерминалом, получаем:

ПЕРВ(<C>) = ПЕРВ(a<B>) ÈПЕРВ(<D>) È{c} = {a}È{d}È{c}={a,d,c}.

При вычислении функции для правил (1) и (2) также необходимо иметь в виду то, что <B> является аннулирующим терминалом, поэтому имеем:

ПЕРВ(<A>) = ПЕРВ(<B><C>c) È ПЕРВ(g<D><B>) =
ПЕРВ(<C>c) È ПЕРВ(<B>) È ПЕРВ(g<D><B>) =

{a,d,c} È {b} È{g} = {a,b,c,d,g}.
 

Построение функции СЛЕД(<B>)  

 

Аргументом функции СЛЕД является нетерминальный символ, например <B>, а значение функции СЛЕД(<B>) представляет собой множество терминалов, которые могут следовать непосредственно за нетерминалом  <B>  в цепочках, выводимых из начального символа грамматики.
Вычисление значения функции СЛЕД(<B>) должно выполняться  по следующим правилам:
1)    Если в схеме грамматики имеются правила вида

<X1 ® µ1<B>a1,  <X2 ® µ2<B>a2, ... , <Xn ® µn<B>an,
 

и все цепочки a i =/= $ , то

СЛЕД(<B>) = ПЕРВ(a 1) È ПЕРВ(a 2) È ... È ПЕРВ(a n).
 

2)   Если же среди приведенных выше правил имеется хотя бы одна цепочка ai = $, например пусть a1 = $, то функция вычисляется так:

СЛЕД(<B>) = СЛЕД(<X1>) È ПЕРВ(a 2) È ... È ПЕРВ(a n).

Выполним вычисление функции СЛЕД для нетерминалов грамматики Г3.6 . Вначале определим функцию для нетерминала <A>, который встречается в правой части правила (9).
          СЛЕД(<A>) = ПЕРВ(f) = {f}.
Нетерминал <C> входит в правые части правил (1) и (4), учитывая также, что нетерминал <D> являетя анулирующим, получаем:

СЛЕД(<C>) = ПЕРВ(<D>) È ПЕРВ(<E>) ÈПЕРВ(c) = {c,d,g}.

Нетерминал <B> входит в правые части правил (1), (2), (5), поэтому имеем:

СЛЕД(<B>) =ПЕРВ(<C>c) È СЛЕД(<A>)  È СЛЕД(<C>),

подставляя в полученное выражение значения функций, входящих в правую часть, получаем:

СЛЕД(<B>) = { a, c, d, }È { f } È U { c, d, g, } = { a, c, d, g, f }.

Для нетерминала <D> , который входит в правила (2), (4) , (5) и  (8), с учетом того, что нетерминал <B> является аннулирующим, получаем:

СЛЕД(<D>) =ПЕРВ(<B>) È СЛЕД(<A>)  È ПЕРВ(<E>) È ПЕРВ(a<B>),

учитывая, что , для нетерминала <E>, входящего в правило (4)
          СЛЕД(<E>) = СЛЕД(<B>) = {a,d,c,g,f},
окончательно имеем:
          СЛЕД(<D>) = ПЕРВ(<B>)È СЛЕД(<A>) ÈПЕРВ(<E>) È {a} =

= {b}È {f} È {c,g} È {a} = {a,b,c,g,f}.

 

Построение функции ВЫБОР 

Функция ВЫБОР, которая потребуется нам для построения переходов магазинных автоматов,можно определить  с помощью функций ПЕРВ и СЛЕД следующим образом:

1)   Если правило грамматики имеет вид <B> - > a и a не является аннулирующей цепочкой, другими словами не существует вывод a ==>*$, то
 

ВЫБОР(<B>  ® a ) = ПЕРВ( a ).

 
2)    Для аннулирующих правил грамматики вида <B>  ®$, мно-
жество выбора определяется так
 

ВЫБОР(<B>  ® $) = СЛЕД(<B>).

 
3)    Если правило грамматики имеет вид <B>  ® µ и µ яв-
ляется аннулирующей цепочкой, то

ВЫБОР(<B>  ® µ) = ПЕРВ(µ) È СЛЕД(<B>).

 

Для рассматриваемой грамматики Г3.6 множества ВЫБОР для каждого из правил, построенные описанным выше способом, имеют вид:

ВЫБОР(<A>  ® <B><C>c) = ПЕРВ(<B><C>c) = {a,b,c,d},
ВЫБОР(<A>  ® g<D><B>) = ПЕРВ(g<D><B>) = {g},
ВЫБОР(<B>  ® $) = ПЕРВ($) È СЛЕД(<B>) = {a,c,d,g,f},
ВЫБОР(<B>  ® b<C><D><E>) = ПЕРВ(b<C><D><E>) = {b},
ВЫБОР(<C>  ® <D>a<B>) = ПЕРВ(<D>a<B>) = {a,d},
ВЫБОР(<C>  ® ca) = ПЕРВ(ca) = {a},
ВЫБОР(<D>  ® $) = ПЕРВ($) È СЛЕД(<D>) = {a,b,c,g,f},
ВЫБОР(<D>  ® d<D>) = ПЕРВ(d<D>) = {d},
ВЫБОР(<E>  ® g<A>f) = ПЕРВ(g<A>f) = {g},
ВЫБОР(<E>  ® c) = ПЕРВ(c) = {c}.


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