3.4 Множество выбора.

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

 

3.4.1 Функции перв, след и множество выбор.

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

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

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

<X₁>   µ₁<B>₁,<X₂>   µ₂<B>₂, ... , <X_n>   µ_n<B>_n,

и все цепочки _i/$ , то

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

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

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

 

3.4.4 Построение множества выбор.

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

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

ВЫБОР(<B>    ) = ПЕРВ(  ).

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