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

       В качестве примера рассмотрим контекстно-свободную  грамматику 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 построить N_A={B│A =>*B} следующим образом:

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

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

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

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

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

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

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

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

       Построим  новое множество правил P’ путем объединения правил P₂ и всех построенных множеств S(A_i). Получим грамматику 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).

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

       P₁ = {E → T, T → F} ,

       P₂ = {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

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

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

       Применим алгоритм получения грамматики без недостижимых символов. V₀ = {S}, V₁ = {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