Построение множества ВЫБОР
Множество ВЫБОР, которое потребуется нам для построения переходов магазинных автоматов,можно определить с помощью функций ПЕРВ и СЛЕД следующим образом: 1) Если правило грамматики имеет вид <B>
- > a и
a не является аннулирующей цепочкой, другими словами не существует вывод a
==>*$, то
ВЫБОР(<B> ®
a ) = ПЕРВ( a ).
2) Для аннулирующих правил грамматики вида <B> ®$, мно-
жество выбора определяется так
ВЫБОР(<B>
® $) = СЛЕД(<B>).
3) Если правило грамматики имеет вид <B> ® µ и µ
яв-
ляется аннулирующей цепочкой, то
ВЫБОР(<B>
® µ) = ПЕРВ(µ) И
СЛЕД(<B>).
Для рассматриваемой грамматики Г3.2 множества ВЫБОР для каждого из правил, построенные описанным выше способом, имеют вид:
ВЫБОР(<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}.
Пред.Страница
След.Страница Раздел Содержание
