Теория формальных языков, грамматик и автоматов. Ишакова Е.Н. - 54 стр.

UptoLike

ВУЗ: 

ОГУ | Оренбург

Составители: 

Рубрика: 

54
Приложение Б
(обязательное)
Текст программы
Unit2.h
#include <fstream.h>
#include <math.h>
#include <sysutils.hpp>
#include <graphics.hpp>
#include <grids.hpp>
#include <map>
#include <set>
#include <string>
#include <list>
#include <vector>
using std::string;
using std::map;
using std::multimap;
using std::set;
using std::pair;
// компаратор для работы в отображениях
struct rulecmp{
bool operator()(const char c1, const char c2){
return (c1 < c2);
}
};
typedef string rule_r;
typedef char rule_l;
typedef pair<rule_l, rule_r> rule;
typedef multimap<rule_l, rule_r, rulecmp> rulemap;
typedef set<char> charset;
// класс грамматики
class Grammar{
public:
charset N; // мн-во нетерминалов
charset T; // множество терминалов
rulemap P; // множество правил
char S; // начальный символ
int IsRegular(); // проверка грамматики на ре-
гулярность
void InGrammar(char *fname); // ввод грамма-
тики из файла
string AsString(); // вывод грамматики в стро-
ку
void OutGrammar(char *fname); // вывод
грамматики в файл
};
typedef map<char, map<char, charset> > ftable;
// класс конечного автомата
class FAutomat{
public:
Grammar *G; // связанная грамматика
charset Q; // множество состояний
charset T; // множество входных символов
ftable F; // таблица правил
char H; // начальное состояние
charset Z; // множество конечных состояний
int MustPaint; // флаг отрисовки графа
FAutomat(){
MustPaint = 0;
}
void SetGrammar(Grammar *NG); // связывание
с грамматикой
void CreateAutomat(); // создание автомата из
грамматики
void PaintAutomat(TCanvas * Canvas, long w,
long h); // отрисовка графа
void OutToTable(TStringGrid * Grid); // вывод
таблицы правил в StringGrid
void CreateDeterm(); // преобразование в ДКА
};
Unit2.cpp
#include "Unit2.h"
int Grammar::IsRegular(){
if (N.empty() || P.empty())
return 0;
for(rulemap::iterator i = P.begin(); i != P.end();
i++){
if (!N.count(i->first))
return 0;
//по длине правой части
switch(i->second.length()){
case 1:{
if (!T.count(i->second[0]))
return 0;
break;
}
case 2:{
if (!T.count(i->second[0]) || !N.count(i-
>second[1]))
return 0;
break;
}
default:
return 0;
}
}
return 1;
}
void Grammar::InGrammar(char *fname){
long n, i;
rule r;
char c;
Лист
17
                                                   Приложение Б
                                                       (обязательное)
                                                      Текст программы

 Unit2.h                                                        charset Q; // множество состояний
                                                                charset T; // множество входных символов
 #include                                            ftable F; // таблица правил
 #include                                               char H; // начальное состояние
 #include                                         charset Z; // множество конечных состояний
 #include                                         int MustPaint; // флаг отрисовки графа
 #include                                            FAutomat(){
 #include                                                     MustPaint = 0;
 #include                                                  }
 #include                                               void SetGrammar(Grammar *NG); // связывание
 #include                                            с грамматикой
 #include                                               void CreateAutomat(); // создание автомата из
                                                           грамматики
 using std::string;                                             void PaintAutomat(TCanvas * Canvas, long w,
 using std::map;                                           long h); // отрисовка графа
 using std::multimap;                                           void OutToTable(TStringGrid * Grid); // вывод
 using std::set;                                           таблицы правил в StringGrid
 using std::pair;                                               void CreateDeterm(); // преобразование в ДКА
                                                           };
 // компаратор для работы в отображениях
 struct rulecmp{                                           Unit2.cpp
         bool operator()(const char c1, const char c2){
                 return (c1 < c2);                         #include "Unit2.h"
         }
 };                                                        int Grammar::IsRegular(){
                                                              if (N.empty() || P.empty())
 typedef string rule_r;                                          return 0;
 typedef char rule_l;                                         for(rulemap::iterator i = P.begin(); i != P.end();
 typedef pair rule;                        i++){
 typedef multimap rulemap;              if (!N.count(i->first))
 typedef set charset;                                         return 0;
                                                                 //по длине правой части
 // класс грамматики                                             switch(i->second.length()){
 class Grammar{                                                     case 1:{
        public:                                                        if (!T.count(i->second[0]))
                charset N; // мн-во нетерминалов                          return 0;
                charset T; // множество терминалов                     break;
                rulemap P; // множество правил                      }
                char S; // начальный символ                         case 2:{
      int IsRegular(); // проверка грамматики на ре-                   if (!T.count(i->second[0]) || !N.count(i-
 гулярность                                                >second[1]))
      void InGrammar(char *fname); // ввод грамма-                        return 0;
 тики из файла                                                         break;
      string AsString(); // вывод грамматики в стро-                }
 ку                                                                 default:
      void OutGrammar(char *fname); // вывод                           return 0;
 грамматики в файл                                               }
 };                                                           }
                                                                 return 1;
 typedef map > ftable;              }

 // класс конечного автомата                                 void Grammar::InGrammar(char *fname){
 class FAutomat{                                               long n, i;
    public:                                                    rule r;
                                                                                                                   Лист
      Grammar *G; // связанная грамматика                      char c;                                             17

54

Страницы