Аналізуючі автомати

Програмна реалізація синтаксичного аналізу з допомогою аналізуючих автоматів.

Опис програми:

Програма аналізує введений рядок і вказує на належнічність, чи не належність його до заданої граматики. Програма реалізована на мові програмування С++, у середовищі Microsoft Visual Studio 6.0.Граматика вводиться у файл. Ввід рядка проводиться з клавіатури. Програма працює на будь-якому комп'ютері з операційною системою Windows. Для коректної роботи програми необхідно привести граматику до такого вигляду:

де,

А, В - нетермінали;

?,? - довільна стрічка терміналів.

Опис класів використаних у програмі:

SyntaxAnalyze:

cache - змінна необхідна для оптимізації і прискорення роботи функції.

rules - контейнер який містить правила граматики і по суті є множиною керуючих таблиць.

in - файлова змінна з допомогою якої реалізується зв'язок з граматикою яка збережена в файлі.

void Construct() - функція яка будує множину керуючих таблиць.

SyntaxAnalize(char * name_in) - конструктор який приймає ім'я файла.

Tree* Analyze(int start, int finish, char neterminal, string rez) - основна функція яка проводить аналіз введеной стрічки.

Tree:

Об'єкти класу являть собою вузли дерева виводу введеного рядка.

Neterminal - зберігає інформацію про нетермінал.

m_left_terminals - зберігає термінальні символи які знаходяться зліва від нетерміналів.

m_right_terminals - зберігає термінальні символи які знаходяться зправа від нетерміналів.

Tree *m_left_branch, *m_right_branch - зберігають вказівники на відповідно ліву і праву дочірні вітки.

int m_begin_lex, m_end_lex - зберігає початок і кінець підстрічки відповідно.

rule_numver - зберігає номер правила за яким розбиралась підстрічка.

Tree() - конструктор без параметрів.

Tree& operator = (const Tree &rop) - перегружений оператор присвоєння.

Tree(Tree &rop) -конструктор копій.

Контрольний приклад

Для заданої граматики:

S-AB

A-aC

B-bA

C-c

Вводимо стрічку:

acbac

Отримуємо результат:

Код програми:

Файл Analyz.h

#include<vector>

#include<map>

#include<fstream>

#include"tree_of_life.h"

#ifndef _GRAm_

#define _GRAm_

class SyntaxAnalize

{

private:

map<pair<pair<int, int>, char>, Tree*> cache;

map<char,vector<string> > rules;

ifstream in;

void Construct();

public:

SyntaxAnalize(char * name_in)

{

in.open(name_in, ios::in);

Construct();

}

Tree* Analyze(int start, int finish, char neterminal, string rez);

};

#endif

Файл tree_of_life.h

#include <vector>

using namespace std;

#ifndef TREE_OF_LIFE_H

#define TREE_OF_LIFE_H

class Tree

{

public:

char Neterminal;

string m_left_terminals;

string m_right_terminals;

Tree *m_left_branch, *m_right_branch;

//Tree *m_father_branch;

int m_begin_lex, m_end_lex;

int rule_numver;

Tree()

{

m_left_branch = NULL;

m_right_branch = NULL;

}

Tree& operator = (const Tree &rop)

{

m_begin_lex = rop.m_begin_lex;

m_end_lex = rop.m_end_lex;

m_left_branch = rop.m_left_branch;

m_right_branch = rop.m_right_branch;

m_left_terminals = rop.m_left_terminals;

m_right_terminals = rop.m_right_terminals;

Neterminal =rop.Neterminal;

return *this;

}

Tree(Tree &rop)

{

m_begin_lex = rop.m_begin_lex;

m_end_lex = rop.m_end_lex;

m_left_branch = rop.m_left_branch;

m_right_branch = rop.m_right_branch;

m_left_terminals = rop.m_left_terminals;

m_right_terminals = rop.m_right_terminals;

Neterminal =rop.Neterminal;

}

};

#endif

Файл funkcii.cpp

#include <iostream>

#include <string>

#include "Analiz.h"

using namespace std;

void SyntaxAnalize::Construct()

{

int y = 1;

int x = y+++y;

char neterminal;

string temp = "";

string temp_rule = "";

vector<string> bufer;

while(!in.eof())

{

in >> temp;

neterminal = temp[0];

temp = temp + '|';

for (int i = 2; i < temp.length(); ++i)

{

if (temp[i] == '|')

{

bufer.push_back(temp_rule);

temp_rule = "";

continue;

}

temp_rule = temp_rule + temp[i];

}

rules.insert(pair<char,vector <string> >(neterminal, bufer));

bufer.clear();

}

rules.begin();

for(int i = 'A'; i < 'Z'+1; ++i)

{

neterminal = i;

for(int j = 0; j < rules[i].size(); ++j)

{

cout << neterminal << '-';

cout << rules[i][j]<< '\n';

}

}

}

Tree* SyntaxAnalize::Analyze(int start, int finish, char neterminal, string rez)

{

pair<pair<int, int>, char> p = make_pair(make_pair(start, finish), neterminal);

Tree branch;

branch.m_begin_lex = start;

branch.m_end_lex = finish;

branch.Neterminal = neterminal;

if (cache.find(p) != cache.end())

{

//branch.m_left_branch = cache[p];

return cache[p];

}

for (int i = 0; i < rules[neterminal].size(); ++i)

{

int begin = start;

int end = finish;

bool fl_left = false;

bool fl_right = false;

int left = 0;

int right = rules[neterminal][i].size() - 1;

string temp_part_of_rule;

while(begin <= finish)

{

if (rules[neterminal][i][left] == rez[begin])

{

++left;

++begin;

}

else

fl_left = true;

if (rules[neterminal][i][right] == rez[end])

{

--end;

--right;

}

else

fl_right = true;

if (fl_left && fl_right)

break;

}

if(begin > end && left > right)

{

for(int j = start; j <= finish;++j)

temp_part_of_rule = temp_part_of_rule + rez[j];

branch.m_left_terminals = temp_part_of_rule;

branch.rule_numver = i;

cache[p] = new Tree (branch);

return cache[p];

}

for (int j = start; j < begin; ++j)

temp_part_of_rule = temp_part_of_rule + rez[j];

branch.m_left_terminals = temp_part_of_rule ;

temp_part_of_rule = "";

for (int k = end+1; k <= finish; ++k)

temp_part_of_rule = temp_part_of_rule + rez[k];

branch.m_right_terminals = temp_part_of_rule ;

if (left == right && isupper(rules[neterminal][i][left]))

{

branch.m_left_branch = Analyze(begin, end,rules[neterminal][i][left], rez);

if(branch.m_left_branch != NULL)

{

cache[p] = new Tree(branch);

return cache[p];

}

}

if(left + 1 == right && isupper(rules[neterminal][i][left]) && isupper(rules[neterminal][i][right]))

{

for(int j = begin; j < end; ++j)

{

fl_left = false;

fl_right = false;

branch.m_left_branch = Analyze(begin, j,rules[neterminal][i][left], rez);

if (branch.m_left_branch != NULL)

fl_left = true;

branch.m_right_branch = Analyze(j+1, end,rules[neterminal][i][right], rez);

if (branch.m_right_branch != NULL)

fl_right = true;

if (fl_left && fl_right)

{

cache[p] = new Tree (branch);

return cache[p];

}

else

continue;

}

}

}

cache[p] = NULL;

return NULL;

}

Файл main.cpp

#include "Analiz.h"

#include <iostream>

using namespace std;

void main()

{

Tree *noda;

string input;

char temp[100];

SyntaxAnalize grama("gramatyka.txt");

bool fl_continue = true;

char c;

while(fl_continue)

{

fl_continue = false;

cout << "Enter string!\n";

cin >> temp;

for(int i =0; temp[i];++i)

input += temp[i];

noda = grama.Analyze(0,input.length(),'S',input);

if (noda)

cout << "Ok\n";

else

cout << "Error!\n";

cout << "continue?(y/n)\n";

cin >> c;

if (c == 'y')

fl_continue = true;

}

}

Размещено на Allbest.ru