Преобразование КС-грамматик к приведенному виду

Содержание

Введение…………………………………………………………………..3

1. Основные понятия  и определения теории формальных  языков……4

2. Классификация  грамматик и языков по Хомскому…………………6

3. Приведенные  грамматики…………………………………………….8

4. Преобразования  грамматик…………………………………………...9

      4.1. Алгоритм удаления бесплодных  символов…………………9

     4.2.  Алгоритм удаления недостижимых  символов……………..9

     4.3. Преобразование неукорачивающих  грамматик……………10

     4.4. Исключение цепных правил………………………………...12

5. Разработка  программы……………………………………………….14

Литература

Приложение  

Аннотация

       В курсовой работе рассматривается преобразование КС-грамматик к приведенному виду. Рассмотрены основные понятия и  концепции преобразования.

       Работа  содержит     страниц машинописного  текста,     библиографических источников.

Введение

       Теория  формальных языков и грамматик является разделом математической лингвистики - специфической математической дисциплины,           ориентированной    на изучение структуры естественных и искусственных  языков. По характеру используемого математического аппарата теория формальных грамматик и языков близка к теории алгоритмов и теории автоматов.

           На интуитивном уровне язык  можно определить как некоторое  множество предложений с заданной  структурой, имеющих определенное значение. Правила, определяющие допустимые конструкции языка, составляют синтаксис языка. Значение, или смысл фразы, определяется семантикой языка.

           Если бы все языки состояли  из конечного числа предложений,  то не было бы проблемы синтаксиса. Но, так как язык содержит неограниченное (или довольно большое) число правильно построенных фраз, то возникает проблема описания бесконечных языков с помощью каких-либо конечных средств.

           Различают следующие виды описания  языков:

           1) порождающее, которое предполагает наличие алгоритма,             последовательно порождающего все правильные предложения языка;

           2) распознающее, которое предполагает  наличие алгоритма, определяющего

       принадлежность  любой фразы данному языку. 

  1. Основные понятия и определения теории формальных языков

       Алфавит - это конечное множество символов.

       Например, алфавит A = {a, b, c, +, !} содержит 5 букв, а  алфавит B = {00, 01, 10, 11} содержит 4 буквы, каждая из которых состоит из двух символов.

       Цепочкой  символов в алфавите V называется любая конечная последовательность символов этого алфавита.

       Цепочка, которая не содержит ни одного символа, называется пустой цепочкой. Для ее обозначения будем использовать символ l.

       Более формально цепочка символов в  алфавите V определяется следующим образом:

             1) l - цепочка в алфавите V;

             2) если α - цепочка в алфавите V и a - символ этого алфавита, то αa или аa - цепочка в алфавите V;

             3) β - цепочка в алфавите V тогда и только тогда, когда она является таковой в силу (1) и (2).

       Если  α и β - цепочки, то цепочка αβ называется конкатенацией (или сцеплением) цепочек α и β.

       Например, если α = ab и β = cd, то αβ = abcd.

       Для любой цепочки α всегда αl = lα = α.

       Обращением (или реверсом) цепочки α называется цепочка, символы которой записаны в обратном порядке.

       Обращение цепочки α будем обозначать αR.

       Например, если α = abcdef, то αR = fedcba.

       Для пустой цепочки: l = lR.

       n-ой  степенью цепочки  α(будем обозначать αn) называется конкатенация n цепочек α

       α0 = l; αn = ααn-1 = αn-1α. 

       Длина цепочки - это число составляющих ее символов.

       Например, если α = abcdefg, то длина α равна 7.

       Длину цепочки α будем обозначать |α|. Длина l равна 0.

       Язык  в алфавите V - это подмножество цепочек конечной длины в этом алфавите.

       Обозначим через V* множество, содержащее все цепочки в алфавите V, включая пустую цепочку l.

       Например, если V={0,1}, то V* = {l, 0, 1, 00, 11, 01, 10, 000, 001, 011, ...}.

       Обозначим через V+ множество, содержащее все цепочки в алфавите V, исключая пустую цепочку l.

       Следовательно, V* = V+ U {l}.

       Ясно, что каждый язык в алфавите V является подмножеством множества V*.

       Известно  несколько различных способов описания языков. Один из них использует порождающие  грамматики. Именно этот способ описания языков используется чаще всего.

  2. Классификация грамматик и языков по Хомскому

       Н.Хомский  определил четыре типа грамматик: тип0, тип1, тип2 и тип3.

       Формально грамматика G  - это совокупность четырех объектов.

                     G = (VT, VN, Р, S)

  1. Стартовый символ, задающий вид строк описываемого языка на самом верхнем уровне (S);
  2. Нетерминальные символы (переменные), традиционно обозначаемые заглавными латинскими буквами (VN);
  3. Терминальные символы – базовые, атомарные элементы языка, формирующие его алфавит (VT);
  4. Собственно правила вывода, каждое из которых сопоставляет некоторой переменной или стартовому символу строку, состоящую из конкатенации произвольных терминальных и нетерминальных символов (P).

         Соответствующий тип грамматики  определяется теми ограничениями,  которые налагаются на продукцию  Р. Если таких ограничений нет, грамматика принадлежит к типу 0.

       Единственное  ограничение, налагаемое налагаемое на длину цепочек α и β:

                         │α│ ≤ │β│

       относит грамматику к типу 1. Такие грамматики также называют контекстно-зависимыми, грамматиками непосредственных составляющих (НС-грамматики).

       В том случае, когда цепочка α  состоит из одного символа, то есть α є VN, грамматики относят к типу 2. В это случае их называют бесконтекстными (контекстно-свободными или КС-грамматиками).

       Регулярными грамматиками (типа3) называют такие, для которых α є VN, а       β є VT VN либо β є VT. Иными словами, правые части продукций регулярных грамматик состоят либо из одного терминального и одного нетерминального символов, либо из одного терминального символа.

       В курсовой работе будем рассматривать контекстно-свободные грамматики (КС-грамматики). Правила имеют вид А → с, где А – переменная, а с – строка над алфавитом (VT U VN). Такая грамматика называется контекстно-свободной потому, что правило А → с может применяться независимо от того, в каком контексте встретилась переменная А (то есть независимо от того, какие символы её окружают). Обычно стартовый символ грамматики не выделяют явным образом: по умолчанию считается, что переменная в левой части самого первого правила и есть стартовый символ.

       Грамматику  можно записать короче, пользуясь  вертикальной чертой для объединения  правил с одинаковой левой частью.

       Например

       S → aS | bS | cS

       Здесь три правила, а не одно. 
 
 
 
 
 
 
 
 
 

3. Приведенные грамматики

       Приведенные грамматики — это КС-грамматики, которые не содержат недостижимых и бесплодных символов, циклов и l-правил («пустых» правил). Приведенные грамматики называют также КС-грамматиками в каноническом виде.

       Для того, чтобы преобразовать произвольную КС-грамматику к приведенному виду, необходимо выполнить следующие действия:

  • удалить все бесплодные символы;
  • удалить все недостижимые символы;
  • удалить l-правила;
  • удалить цепные правила.

       Следует подчеркнуть, что шаги преобразования должны выполняться именно в указанном  порядке, и никак иначе.

  4. Преобразования грамматик

       В некоторых случаях КС-грамматика может содержать недостижимые и  бесплодные символы, которые не участвуют  в порождении цепочек языка и  поэтому могут быть удалены из грамматики.

       Определение: символ A є VN называется бесплодным в грамматике G = (VT, VN, P, S), если множество { a | a є VT*, A => a} пусто.

       Определение: символ x є (VT U VN) называется недостижимым в грамматике G = (VT, VN, P, S), если он не появляется ни в одной сентенциальной форме этой грамматики. 

4.1. Алгоритм удаления бесплодных символов

       Вход: КС-грамматика G = (VT, VN, P, S).

       Выход: КС-грамматика G’ = (VT, VN’, P’, S), не содержащая бесплодных символов, для которой L(G) = L(G’).

       Метод:

       Рекурсивно  строим множества N0, N1, ...

    1. N0 = Æ, i = 1.
    2. Ni = {A | (A → a) є P и a є (Ni-1 U VT)*} U Ni-1.
  1. Если Ni ≠ Ni-1, то i = i+1 и переходим к шагу 2, иначе VN’ = Ni; P’ состоит из правил множества P, содержащих только символы из     VN’ È VT; G’ = (VT, VN’, P’, S). 

  

  • 4.2.Алгоритм удаления недостижимых символов

    •        Вход: КС-грамматика G = (VT, VN, P, S)

           Выход: КС-грамматика G’ = (VT’, VN’, P’, S), не содержащая недостижимых символов, для которой L(G) = L(G’).

           Метод:

      1. V0 = {S}; i = 1.
      2. Vi = {x | x є (VT U VN), (A → axb) Î P и A є Vi-1} U Vi-1.
      3. Если Vi ≠ Vi-1, то i = i+1 и переходим к шагу 2, иначе VN’ =  
        Vi         Ç VN;  VT’ = Vi Ç VT; P’ состоит из правил множества P, содержащих только символы из Vi; G’ = (VT’, VN’, P’, S).

           Удаление  символов сопровождается удалением  правил вывода, содержащих эти символы.

           Если  в этом алгоритме переставить  шаги (1) и (2), то не всегда результатом будет правильным.

           В качестве примера рассмотрим контекстно-свободную  грамматику G с правилами S → U, S → VZ, T → aa, T → bb, U → aUa, U → bUb, V → aTb, V → bTa, W → YZY , W → aab, X → Xa, X → Xb, X → ε, Y → YY , Y → aU, Y → ε,         Z → W, Z → b. Удалив четыре правила, содержащие бесплодный символ U, получим грамматику G1: S → VZ, T → aa, T → bb, V → aTb, V → bTa,             W → YZY ,  W → aab,   X → Xa,  X → Xb,  X → ε,  Y → YY ,  Y → ε,  Z → W,  Z → b.

           В ней символ X является недостижимым. Удалив три правила, содержащие X, получим грамматику G2 с правилами: S → VZ, T → aa, T → bb, V → aT b,    V → bT a, W → YZY , W → aab, Y → YY , Y → ε, Z → W, Z → b. Очевидно, L(G) = L(G2) и грамматика G2 не содержит бесплодных и недостижимых  символов. 

        4.3. Преобразование неукорачивающих  грамматик

           Последний вид рассматриваемых преобразований связан с удалением из грамматики правил с пустой правой частью.

           Определение. Правило вида A → l называется «пустым» (аннулирующим) правилом.

           Определение. Грамматика называется неукорачивающей или грамматикой без «пустых» правил, если либо

           1)схема  грамматики не содержит аннулирующих  правил,

           2)либо  схема грамматики содержит только  одно правило вида S → l, где S - начальный символ грамматики, и символ S не встречается в правых частях остальных правил грамматики.

           Для грамматик, содержащих аннулирующие правила, справедливо следующее утверждение.

           Утверждение. Для каждой КС-грамматики G', содержащей аннулирующие правила, можно построить эквивалентную ей неукорачивающую грамматику G, такую что L(G')=L(G).

           Построение  неукорачивающей грамматики приведет к увеличению числа правил заданной грамматики из-за построения дополнительных правил, получаемых в результате исключения нетерминалов аннулирующих правил. Чтобы построить дополнительные правила необходимо выполнить все возможные подстановки пустой цепочки вместо аннулирующего нетерминала во все правила грамматики.

           Если  же в грамматике есть правило вида S → l, где S – начальный символ грамматики, и символ S входит в правые части других правил грамматики, то следует ввести новый начальный символ S’ и заменить правило S → l двумя новыми правилами: S' → l и S'→ S.

           В качестве иллюстрации способа построения неукорачивающих грамматик, исключим аннулирующие правила из следующей грамматики:

           G ({a,b}, {S}, P = { S → aSbS, S → bSaS, S → l }, S).

           Выполняя  все возможные замены символа  S в первом правиле грамматики, получаем четыре правила вида:

               S → aSbS, S → abS, S → aSb, S → ab .

           Поступая  аналогично со вторым правилом, имеем:

               S → bSaS, S →baS, S → bSa, S → ba.

           Учитывая, что начальный символ, образующий аннулирующее правило, входит в правые части других правил грамматики, заменим  правило S → l правилами вида S' → l и S' → S.

           Построенная совокупность правил образует множество правил искомой неукорачивающей грамматики.

           S' → S | l

           S → aSbS | abS | aSb | ab | bSaS | baS | bSa | ba

           Все приведенные выше преобразования грамматик  могут быть использованы при построении как конечных, так и магазинных автоматов.  
     
     

    4.4. Исключение цепных правил

           Определение. Правило грамматики вида A → B, где A, B є VN, называется цепным.

           Для КС-грамматики G, содержащей цепные правила, можно построить эквивалентную ей грамматику G', не содержащую цепных правил.

           Идея  доказательства заключается в следующем.

           Если  грамматика G имеет правила A → B, B → C, C → aX, то такие правила могут быть заменены одним правилом А → aX, поскольку вывод А => B => C => aX цепочки aX в грамматике G может быть получен в грамматике G' с помощью правила A → aX.

           1. Для каждого А є N построить NA={B│A =>*B} следующим образом:

                 а) Положить N0 = {A} и i=1.

             б) Положить Ni ={C│B→C  принадлежит Р и В є Ni-1 }  U Ni-1.

             в) Если Ni  ≠ Ni-1, положить i = i+1 и повторить шаг (б).

                 В противном случае положить NA = Ni.

           2. Построить Р’ так: если В → α принадлежит Р и не является цепным правилом, включить в Р’ правило А → α для всех таких А, что В є NА.

           3. Положить G’ = (VT, VN, P’, S).

           Разобьем  множество правил P грамматики G на два подмножества P1 и P2, включая в P1 все правила вида A → B.

           Для каждого правила из P1 найдем множество правил S(Ai), которые строятся так: если Ai => * Aj и в P2 есть правило Aj → α , где α - цепочка словаря (VN U NT)*, то в S(Ai) включим правило Ai → α .

           Построим  новое множество правил P’ путем объединения правил P2 и всех построенных множеств S(Ai). Получим грамматику G' = {VN ,VT , P’, S}, которая эквивалентна заданной и не содержит правил вида A → B.

           В качестве примера выполним исключение цепных правил из грамматики G :

           G = ({+,*,(,),a}, {E,T,F}, P={E → E+T | T, Т → T*F | F, F → (E) | a}, E).

           Вначале разобьем правила грамматики на два  подмножества:

               P1 = {E → T, T → F} ,

               P2 = {E → E+T, T → T*F, F → (E) | a }

           Для каждого правила из P1 построим соответствующее  подмножество.

               S(E) = { E →T*F, E → (E) | a },

               S(T) = { T → (E) | a}

           В результате получаем искомое множество  правил грамматики без цепных правил в виде:

             P2 U S(E) U S(T) = { E → T+T | T*F | (E) | a, T → T*F | (E) | a, F → (E) | a } 
       
       
       
       
       
       
       
       
       
       
       

    5. Разработка программы

           Входными  данными будет считанная грамматика. Выходными данными будет грамматика приведенная.

           Грамматика  будет задана в обычном виде, только вместо символа → будет использоваться пробел

           S  Ac

           A  aA

           Чтобы упростить работу с грамматикой, синтаксис вариантов, разделенных  вертикальной чертой, не поддерживается. Например, вместо     A → a | b | Ac следует писать

           A a

           A b

           A Ac

           В качестве терминалов допускается использовать символы арифметических операций. Вместо символа λ будем использовать букву «э».

           Правила грамматики, терминальные и нетерминальные символы будут храниться в соответствующих переменных:

           static ArrayList Grammar = new ArrayList(); // правила грамматики

           static string Terminals; // список терминалов

           static string Nonterminals; // список нетерминалов

           На  каждой итерации в грамматику добавляется очередное считанное правило. В последнюю очередь формируются строки терминалов  и нетерминалов.

           Процедура RemoveFruitlessUnSimb() удаляет из грамматики бесплодные и недостижимые символы и правила, содержащие их.

           Далее, из входной грамматики следует удалить λ-правила. Они удаляются следующим образом:

             ПОКА существуют λ-правила

                       найти  правило  вида А → λ;

                       для любого правила, содержащего А в правой части (Х → αАβ)

                             добавить аналогичное  правило, но без А: Х → αβ;

                       удалить правило А → λ;

           КОНЕЦ ЦИКЛА

           здесь α и β – любые строки в  том числе пустые. Например, грамматику

           S → Ac

           A → aA

           А → λ

           можно преобразовать с помощью приведенного алгоритма к виду

           S → Ac

           S → c

           A → aA

           А → а

           Исключение  одних λ-правил может привести к  образованию других. Если выполнение алгоритма приводит к таким результатам, придется повторить его еще раз.

           Если  нетерминал, участвующий в правиле А → λ, встречается в правой части некоторого вывода несколько раз, придется добавить по одному новому правилу для каждой возможной комбинации, где те или иные символы А вычеркнуты.

           Служебная функция GenerateRulesWithout(A) создает список правил, в которых вычеркнут один или более символов А в правой части.

           Далее создаем главную процедуру удаления λ-правил RemoveEpsilonRules.

           Переменная AcceptEmptyString содержит флаг принадлежности пустой строки описываемому языку.

           Цепные  правила будем удалять по следующему алгоритму

           ПОКА  существуют правила вида А → В

                     найти  правило вида А → В;

                 для любого правила вида В  → α (где α – любя строка,

                                   кроме одиночного нетерминала)

                       добавить правило  А → α;

                удалить правило А → В

           КОНЕЦ  ЦИКЛА

           Добавим функцию RemoveAtoBRules(), удаляющую правила вида А → В

           Для удаления дублирующих правил напишем  функцию KillDuplicates()

           Программа приведения КС-грамматики приведена  в Приложении 1 

           Приведем  примеры грамматик и покажем  на них применение правил приведения. А также протестируем на них работу программы.

           Пример 1.

           Из  заданной грамматики удалить бесплодные и недостижимые символы:

           G=({S,A,B},{a,b},P,S)

           P состоит из правил

                             S → a│A

               A → AB

               B → b

           Применим  алгоритм получения грамматики без  бесплодных символов. На первом шаге получим N1 = {S, B}, на последующих шагах новых элементов в множество N не добавляется. Значит, в грамматике будут присутствовать только нетерминалы S и B и правила, их содержащие.

               G1=({S, B},{a,b},{ S → a , B → b},S)

           Применим алгоритм получения грамматики без недостижимых символов. V0 = {S}, V1 = {S, a}, на последующих шагах новых элементов в множество V не добавляется. Значит, в грамматике будут присутствовать только нетерминал S и терминал a и правила, их содержащие.

               G2=({S},{a},{ S → a },S)

           В результате выполнения программы получаем результат

           S a 

           Пример 2.

           Преобразовать грамматику в грамматику без λ-правил:

           S → aSbS│bSaS│ λ

           Выполняя  все возможные замены символа  S в первом правиле грамматики, получаем три правила вида: S → abS

                                            S → aSb

                                            S → ab

           Выполняя  все возможные замены символа  S во втором правиле грамматики, получаем три правила вида: S → baS

    Преобразование КС-грамматик к приведенному виду