-
Пред.Страница
След.Страница
Раздел
Содержание
3.4.3 Построение
функции СЛЕД(<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.2
. Вначале определим функцию для нетерминала <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}.
-
Пред.Страница
След.Страница
Раздел
Содержание