Формальные языки

программы софт скачать бесплатно

Построение функции СЛЕД(<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}.

     

  • Пред.Страница 

    След.Страница   Раздел   Содержание




- Начало -  - Назад -  - Вперед -