3.5. Функции перв, след и выбор.

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

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

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

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

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

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

ПЕРВ(µ) = $,  

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

<B>  ® a₁ | a₂ | ... | a_n ,

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

ПЕРВ(<B>µ') = ПЕРВ(a₁) È ПЕРВ (a₂) È...ÈПЕРВ(a_n),

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

<B>  ® a₁ | a₂ | ... | a_n ,

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

ПЕРВ(<B>µ')=ПЕРВ(µ') È ПЕРВ(a ₁)È ПЕРВ(a ₂) È...È ПЕРВ(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)    Если в схеме грамматики имеются правила вида

<X₁>  ® µ₁<B>a₁,  <X₂>  ® µ₂<B>a₂, ... , <X_n>  ® µ_n<B>a_n,  

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

СЛЕД(<B>) = ПЕРВ(a ₁) È ПЕРВ(a ₂) È ... È ПЕРВ(a _n).  

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

СЛЕД(<B>) = СЛЕД(<X₁>) È ПЕРВ(a ₂) È ... È ПЕРВ(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}.