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}.