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

                                                                           S → bSa

                                                                       S → ba

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

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

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

       S  aSbS

       S  bSaS

       S  abS

       S  aSb

       S  ab

       S  baS

       S  bSa

       S  ba 

       Пример 3.

       Устранить цепные правила в грамматике G

       Е → Е + Т │ Т

       Т → Т * F │F

       F → (E) │ a

       Разбиваем правила на два множества

       Р1:  Е → Т

                  Т →  F

       Р2:  Е → Е + Т

                  Т →  Т * F

                  F → (E)

              F → a

       N_E = {E, T, F}

       N_T = {T, F}

       N_F = {F}

       Новая грамматика содержит правила:     

       Е → Е + Т

       Е → Т * F

       Е → (E)

       Е → a

       Т → Т * F

       Т → (Е)

       Т → а

       F → (E)

          F → a

       В результате приведения этой грамматики с помощью программы получаем:

       Е   Е+Т

       Е   Т*F

       Е   (E)

       Е   a

       Т   Т*F

       Т   (Е)

       Т   а

       F   (E)

          F   a 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

ЛИТЕРАТУРА

1. Грис Д. Конструирование  компиляторов для цифровых вычислительных  машин. “Мир” 1975г.

2. Мозговой М.В.  Классика программирования: алгоритмы,  языки, автоматы, компиляторы. Практический  подход. – СПб.: Наука и Техника, 2006. -320 c.

3. А. Ахо, Дж. Ульман  Теория синтаксического анализа, перевода и компиляции. Том 1. Синтаксический анализ, М.: “Мир”, 1978 г.

4. Кнут Д. Семантика  контекстно-свободных языков. М.: Мир, 1980. 
 
 
 
 
 
 
 
 
 
 
 
 
 

Приложение

Struct Tablekey

 

{

Public int I;

Public char J;

Public Tablekey (int i,char j) {I=i;J=j;}

} 

static ArrayList Grammar = new Array-List ();

// правила грамматики

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

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

static void ReadGrammar()

{

string s;

Hashtable term = new Hashtable();

// временная  таблица терминалов

Hashtable nonterm = new Hashtable();  // и нетерминалов

while((s = Console.In.ReadLine()) != "")

// считывание  правил 

{

Grammar.Add(s);     // добавить правило в грамматику

for(int i = 0; i < s.Length;i++)

//  анализ  элементов правила 

if(s[i]    !=   '   ')

{

//  если 'текущий  символ -  терминал,

//   еще не добавленный в  term

if(s[i]  == s.ToLower()[i]  &&  !term.ContainsKey(s[i])) term.Add(s[i],   null);

//  аналогично для нетерминалов

if(s[i]   != s.ToLower() [i] && !nonterm.ContainsKey(s[i]))

nonterm.Add(s[i],   null);

}

}

//  переписываем  терминалы и нетерминалы

//   в   строки Terminals и Nonterminals

for(IDictionaryEnumerator с = term.GetEnumerator();  с.MoveNext();)

Terminals   +=   (char)с.Key;

for(IDictionaryEaumerator с = nonterm.GetEnumerator();

с.MoveNext() ; )

Nonterminals += (char)c.Key;

} 
 

static char NewV = 'А' ;      

static ArrayList newrules = new ArrayList();

static char GetNewVar(char OldVar)

{

char NewVar;

if(Nonterminals.IndexOf(OldVar) != -1)

           NewVar = OldVar;     

else 

{

NewVar = NewV++;     

newrules.Add(NewVar + " " + OldVar);

        } 

return NewVar;

}

static void RemoveFruitlessUnSimb()

ArrayList todel = new ArrayList();

      for(IEnumerator rule = Grammar.GetEnumerator();

                   rule.MoveNext();) if(((string)rule.Current).Length > 3)

{

char L = ( (string)rule.Current) [0];

                     string alpha = ((string)rule.Current).Substring(2);

todel.Add(rule.Current);

                   while(alpha.Length >= 2)

char X = GetNewVar(alpha[0]);

char Y = (alpha.Length == 2) ?

GetNewVar(alpha[1]) : NewV;

newrules.Add(L +" " + X + Y); 
alpha = alpha.Substring(1);

                       L = NewV++;

      } 
}

for(IEnumerator rule -  todel.GetEnumerator(); rule.MoveNext();) Grammar . Remove ( (string) rule '. Current) ;

   Grammar.AddRange(newrules);

}

// список найденных комбинаций

static ArrayList combinations = new ArrayList();

static void GenerateCombinations(int depth, string s)

{

if(depth == 0)

combinations.Add(s);

else

{

GenerateCombinations(depth - 1, "0" + s);

GenerateCombinations(depth - 1, "1" + s);

}

} 

static  ArrayList  GenerateRulesWithout(char  A)

{

ArrayList  result  = new ArrayList();         //  итоговый список

// цикл по правилам

for(IEnumerator rule = Grammar.GetEnumerator(); rule.MoveNext();)

{

string current = (string)rule.Current;

// текущее правило,

string rhs = current.Substring(2);

// его правая часть,

string[] rhs_split = rhs.Split(A);

// отдельные  сегменты rhs

int counter;

if(rhs.IndexOf(A) != -1)

// если правая  часть содержит А 

{

counter =0;       // подсчитываем количество

// вхождений А

for(int i = 0; i < rhs.Length; i++)

if(rhs[i] == A) counter++;

combinations.Clear();

GenerateCombinat ions(counter, "");

// генерация комбинаций

for(IEnumerator element = combinations.GetEnumerator();

element.MoveNext();)

if(((string)element.Current).IndexOf('1') != -1)

{

// если текущая  комбинация содержит хоть один 

// вычеркиваемый  символ (т.е. единицу)

string combination = (string)element.Current;

string this_rhs = rhs_split[0];

// если текущий  символ комбинации - единица 

// (вычеркиваем  А), просто соединяем сегменты

// правой части  правила, иначе вставляем 

// дополнительный  символ А

for(int i = 0; i < combination.Length; i++)

this_rhs += (combination[i] == '0' ? A.ToString() : "") + rhs_split[i + 1];

result.Add(current[0] + " " + this_rhs);

}

}

}

Return result;

} 
 

static bool AcceptEmptyString;// допускать ли пустую строку

static void RemoveEpsilonRules()

{

AcceptEmptyString = false;

bool EpsilonRulesExist

do

{

EpsilonRulesExist = false;

for(IEnumerator rule = Grammar.GetEnumerator();

rule.MoveNext();)

if(((string)rule.Current)[2] == 'э')

// нашли эпсилон-правило 

{

// принимаем  пустую строку, если левая часть 

// правила содержит  стартовый символ 

char А = ((string)rule.Current)[0];

if(A == 'S')

         AcceptEmptyString = true;

// добавляем  все новые правила для нетерминала А Grammar.AddRange(GenerateRulesWithout(A));

Grammar.Remove(rule.Current);

// удаляем эпсилон-правило 

EpsilonRulesExist = true;

break;

}

}

while(EpsilonRulesExist);

//  пока  существуют  эпсилон-правила 

} 

static void RemoveAtoBRules () // удаление правил А ->В

                                      // аналогично

                                      // удалению эпсило-правил

bool  AtoBRulesExist;

do                                             // пока правила А ->В

                                                // существуют

{

      AtoBRulesExist = false;

      for (IEnumerator rule = Grammar.GetEnumerator();

                              rule.MoveNext();)

if(((string)rule.Current).Length == 3 &&

                              // нашли А ->В правило

                  Nonterminals.IndexOf(((string)rule.

                                    Current) [2]) != -1)

  {

      char lhs = ((string)rule.Current) [0];

     // левая часть (А)

     char rhs = ((string)rule.Current) [2];

                        // правая часть (В)

      ArrayList newrules = new ArayList();

                        // добавляемые правила

// для любого  правила вида ( В -> alpha)

for (IEnumerator ruleBA = Grammar.GetEnuverator();

                              ruleBA.MoveNext();)

     {

      char new_lhs = ((string)ruleBA.Current) [0];

                        // левая часть  (b)

     // правая часть (alpha)

     string new_rhs =  ((string)ruleBA.Current).

                       Substring(2);

     // если alpha - не терминал