Материал: Лабораторная работа #2

Приложения

1. Пример входного файла для автомата, разбирающего строку for ([abc] = [0-9]; [abc] [<|>] [0-9]; [abc]++)

Здесь [abc] – строка произвольной длины, состоящая из символов a, b, c, A, B, C

[0-9] – строка произвольной длины, состоящая из символов цифр

[<|>] – или символ “<”, или символ “>”

q0, =q0

q0,f=q1

q1,o=q2

q2,r=q3

q3, =q3

q3,(=q4

q4, =q4

q4,i=q5

q5,n=q6

q6,t=q7

q7, =q7

q7,a=q8

q7,b=q8

q7,c=q8

q7,A=q8

q7,B=q8

q7,C=q8

q8,a=q8

q8,b=q8

q8,c=q8

q8,A=q8

q8,B=q8

q8,C=q8

q8,==q10

q8, =q9

q9, =q9

q9,==q10

q10, =q10

q10,0=q11

q10,1=q11

q10,2=q11

q10,3=q11

q10,4=q11

q10,5=q11

q10,6=q11

q10,7=q11

q10,8=q11

q10,9=q11

q11,0=q11

q11,1=q11

q11,2=q11

q11,3=q11

q11,4=q11

q11,5=q11

q11,6=q11

q11,7=q11

q11,8=q11

q11,9=q11

q11,;=q13

q11, =q12

q12, =q12

q12,;=q13

q13, =q13

q13,a=q14

q13,b=q14

q13,c=q14

q13,A=q14

q13,B=q14

q13,C=q14

q14,a=q14

q14,b=q14

q14,c=q14

q14,A=q14

q14,B=q14

q14,C=q14

q14, =q15

q14,<=q16

q14,>=q16

q15, =q15

q15,<=q16

q15,>=q16

q16, =q16

q16,0=q17

q16,1=q17

q16,2=q17

q16,3=q17

q16,4=q17

q16,5=q17

q16,6=q17

q16,7=q17

q16,8=q17

q16,9=q17

q17,0=q17

q17,1=q17

q17,2=q17

q17,3=q17

q17,4=q17

q17,5=q17

q17,6=q17

q17,7=q17

q17,8=q17

q17,9=q17

q17, =q18

q17,;=q19

q18, =q18

q18,;=q19

q19, =q19

q19,a=q20

q19,b=q20

q19,c=q20

q19,A=q20

q19,B=q20

q19,C=q20

q20,a=q20

q20,b=q20

q20,c=q20

q20,A=q20

q20,B=q20

q20,C=q20

q20, =q21

q20,+=q22

q21, =q21

q21,+=q22

q22,+=q23

q23, =q23

q23,)=f0

2. Пример работающей программы (операция детерминирования не производится)

#include <string>

#include <vector>

#include <algorithm>

#include <iostream>

#include <fstream>

typedef unsigned char uchar;

using namespace std;

class format_error: public runtime_error {

public:

format_error(const char* msg): runtime_error(msg){}

};

class StateReader{ //class for reading states from file

public:

struct ElementarySwitch{ // one switch for automat

int initialState; // number of current state

uchar letter; // reading symbol

bool isTerminalState; // is next state terminal?

int nextState; // number of next state

ElementarySwitch():

initialState(-1),

letter(0),

isTerminalState(false),

nextState(-1)

{}

// next 2 operators - for sorting states array

friend bool operator > (const ElementarySwitch& el, const ElementarySwitch& er){

if (el.initialState > er.initialState) return true;

if (el.initialState == er.initialState){

if (el.letter > er.letter) return true;

if (el.letter == er.letter){

if (el.isTerminalState != er.isTerminalState) return er.isTerminalState;

if (el.nextState > er.nextState) return true;

}

}

return false;

}

friend bool operator < (const ElementarySwitch& el, const ElementarySwitch& er){

return !operator>(el, er);

}

};

typedef vector<ElementarySwitch> StatesSwitchArray;

StateReader(const char* filename);

~StateReader() {stateFile.close();}

protected:

StatesSwitchArray statemachineStates; // array of switches for automat

private:

ifstream stateFile; // stream for reading file

};

StateReader::StateReader(const char* filename):stateFile(filename){

if(!stateFile.is_open()) throw runtime_error("Invalid states file"); // can't open file

string tmpStr;

while(getline(stateFile, tmpStr)){

if (tmpStr.size() == 0) continue; // skip empty string

// several check for input file format

if (tmpStr[0] != 'q' && tmpStr[0] != 'Q')

throw format_error("Line must begin with 'q' letter");

string::size_type commaPos = tmpStr.find(',');

if (commaPos == string::npos)

throw format_error("There is no comma");

string stateNumber = tmpStr.substr(1, commaPos - 1);

ElementarySwitch tmpSw; // prepare next elementh in array

tmpSw.initialState = atoi(stateNumber.c_str());

if (tmpSw.initialState == 0 && stateNumber[0] != '0')

throw format_error("State number must contains digits only");

tmpSw.letter = tmpStr[commaPos + 1];

if (tmpStr[commaPos + 2] != '=')

throw format_error("Expected '=' sign");

switch (tmpStr[commaPos + 3]){

case 'f':

case 'F':

tmpSw.isTerminalState = true;

break;

case 'q':

case 'Q':

tmpSw.isTerminalState = false;

break;

default:

throw format_error("Next state must begin with 'q' or 'f' letter");

}

stateNumber = tmpStr.substr(commaPos + 4);

tmpSw.nextState = atoi(stateNumber.c_str());

if (tmpSw.nextState == 0 && stateNumber[0] != '0')

throw format_error("State number must contains digits only");

statemachineStates.push_back(tmpSw); // add one switch to array of switches

}

}

class StateMachine: public StateReader{

public:

StateMachine(const char* filename);

bool isDeterministic() const {return deterministic;}

bool hasHangs() const {return hangs;} // means that graph contains isolated node(s)

const StateReader::StatesSwitchArray& GetSwitches() const {return statemachineStates;} // just for printing

bool isExpressionCorrect(const string& expression, int& errorPos);

protected:

void SortStates();

bool _isDeterministic();

bool _hasHangs();

int _findNextIndex(int curState, uchar sym);

private:

bool deterministic;

bool hangs;

};

StateMachine::StateMachine(const char* filename):

StateReader(filename),

deterministic(true),

hangs(false)

{

SortStates();

//some little check of machine

if (statemachineStates.size() == 0)

throw runtime_error("Automat is empty");

if (statemachineStates[0].initialState != 0)

throw runtime_error("There is no initial state");

size_t ln = statemachineStates.size();

bool hasFinalState = false;

for (size_t i = 0; i < ln; i++)

if (hasFinalState = statemachineStates[i].isTerminalState)

break;

if (!hasFinalState)

throw runtime_error("There is no final state");

deterministic = _isDeterministic(); // check if automat is deterministic

hangs = _hasHangs(); // check if may be hangs

}

bool StateMachine::_isDeterministic(){

size_t ln = statemachineStates.size(); // count of elements in array

bool isDet = true;

for (size_t i = 1; i < ln; i++)

if (statemachineStates[i-1].initialState == statemachineStates[i].initialState &&

statemachineStates[i-1].letter == statemachineStates[i].letter &&

(statemachineStates[i-1].isTerminalState != statemachineStates[i].isTerminalState ||

statemachineStates[i-1].nextState != statemachineStates[i].nextState))

{

isDet = false;

break;

};

return isDet;

}

bool StateMachine::_hasHangs(){

size_t ln = statemachineStates.size();

bool isHangs = false;

for (size_t i = 0; i < ln; i++){

if (!statemachineStates[i].isTerminalState){

bool found = false;

// very bad algorithm to search in _SORTED_ array. I was laziness to do better :->

for (size_t j = 0; j < ln; j++){

if (statemachineStates[i].nextState == statemachineStates[j].initialState){

found = true;

break;

}

}

if (!found){

isHangs = true;

break;

}

}

}

return isHangs;

}

void StateMachine::SortStates(){

sort(statemachineStates.begin(), statemachineStates.end()); // common sorting algorithm from <algorithm>

}

int StateMachine::_findNextIndex(int curState, uchar sym){

int found = -1;

size_t ln = statemachineStates.size();

// very bad algorithm to search in _SORTED_ array

for (size_t j = 0; j < ln; j++){

if (statemachineStates[j].initialState == curState &&

statemachineStates[j].letter == sym){

found = j;

break;

}

}

return found;

}

bool StateMachine::isExpressionCorrect(const string& expression, int& errorPos){

if ( !deterministic || hangs)

throw runtime_error("This automat cannot check expression");

// emulate automat's task

int currentState = 0;

size_t strLen = expression.size();

for (int i = 0; i < strLen; i++){

int idx = _findNextIndex(currentState, expression[i]);

if (idx < 0){

errorPos = i;

return false;

}

if (statemachineStates[idx].isTerminalState){

if (i == strLen - 1) return true;

errorPos = i + 1;

return false;

}

currentState = statemachineStates[idx].nextState;

}

errorPos = strLen;

return false;

}

int _tmain(int argc, _TCHAR* argv[]) {

try{ // try to create object of StateMachine

StateMachine sr("states.txt");

StateReader::StatesSwitchArray::const_iterator it; // another way to access to array's elements

for (it = sr.GetSwitches().begin(); it != sr.GetSwitches().end(); it++)

cout << "q" << it->initialState << "," << it->letter << "=" << (it->isTerminalState ? "f" : "q") << it->nextState << endl;

cout << "There are" << (sr.hasHangs() ? "" : "n't") << " hangs" << endl;

cout << "Automat is" << (sr.isDeterministic() ? "" : "n't") << " deterministic" << endl;

string testExpr;

cout << "Please, enter expression to check ";

cin >> testExpr;

// for test with related "states.txt" file

// testExpr = " for( int abAccc= 943 ; a<478; bbc++ )";

// cout << testExpr << endl;

int err;

bool res = sr.isExpressionCorrect(testExpr, err);

if (res) cout << "Expression is correct!" << endl;

else cout << "Incorrect expression. Error position: " << err << endl;

}

catch(const exception& err){

cerr << err.what() << endl;

}

return 0;

}

// Mark for such realization will be 4

Copyright © 2005 – 2010 Voldem@r