code

一个模拟flex的应用程序 主要实现词法分析 语义分析

#include <iostream>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <stack>
using namespace std;
class Edge
{
	public:
		int number;//the value of the vertex the edge points to 
		int position;// the positon of the vertex the edge points to 
		char weight;
		Edge *link;
		Edge();
		Edge(int num, int pos, char ch);
};
Edge::Edge()
{
	number = -1;
	position = -1;
	link = NULL;
}
Edge::Edge(int num,int pos, char ch)
{
	number = num;
	position = pos;
	weight = ch;
    link = NULL;
}
class Vertex
{
	public:
		int number;
		Vertex *next;
		Edge *out;
		Vertex();
		Vertex(int num);
};
Vertex::Vertex()
{
	number = -1;
	next = NULL;
	out = NULL;
}
Vertex::Vertex(int num)
{
	number = num;
	next = NULL;
	out = NULL;
}

class AdjacentTable
{
	private:
		Vertex *start;
		int numOfVertices;
		int numOfEdges;
	public:
		AdjacentTable();
		int GetValueByPos(int pos) const;
		int GetPosByValue(int value) const;
		char GetWeightByPos(int v1, int v2) const;
		char GetWeightByValue(int value1, int value2) const;
		void SetValue(int value, int pos);
		void InsertVertex(int value);
		void InsertEdgeByPos(int v1, int v2, char weight);
		void InsertEdgeByValue(int value1, int value2, char weight);
		void RemoveAllEdges(void);
		void Clear(void);
		int* Closure(int *T);
		int* Move(int *T, char ch);
		void OutputNFA(void);
          ~AdjacentTable();
};
class TransitionTable
{
public:
	TransitionTable(int rowNum, int colNum);
	~TransitionTable();
	void SetValue(int i, int j, int value);
	int GetValue(int i, int j);
	int Transit(int current, char input, char *edge);
	void Clear(void);
private:
	int **matrix;
	int rowNumber;
	int colNumber;
};
TransitionTable::TransitionTable(int rowNum, int colNum)
{
	rowNumber = rowNum;
	colNumber = colNum;
	matrix = (int**)(new int*[rowNumber]);
	for (int i=0; i<rowNumber; i++)
		matrix[i] = new int[colNumber];
}
TransitionTable::~TransitionTable()
{
	Clear();
}
/*Set the value of the element*/
void TransitionTable::SetValue(int i, int j, int value)
{
	matrix[i][j] = value;
}
/*Get the value of the element*/
int TransitionTable::GetValue(int i, int j)
{
	return matrix[i][j];
}
// Transition of the states
int TransitionTable::Transit(int current, char input, char *edge)
{
	for (int i=0; edge[i]!= '\0'; i++)
	{
		if (input == edge[i])
			return matrix[current][i];
	}
	return -1;
}
/*Clear the table*/
void TransitionTable::Clear(void)
{
	for (int i=0; i<rowNumber; i++)
		delete [] matrix[i];

	delete matrix;
}

/*The constructor creates the start vertex */
AdjacentTable::AdjacentTable()
{
	numOfVertices = 1;
	numOfEdges = 0;
	start = new Vertex();
}

/*Get the vertex value by the position of the vertex*/
int AdjacentTable::GetValueByPos(int pos) const
{
	if ((pos >= 0) && (pos < numOfVertices))
	{
    	Vertex *vertex = start;
    	for (int i=0; i<pos; i++)
		{
	    vertex = vertex->next;
		}
		return vertex->number;
	}
	return -1;
}
/*Get the position of the vertex by value*/
int AdjacentTable::GetPosByValue(int value) const
{
	Vertex *p = start;
    for (int i=0; i<numOfVertices; i++)
	{
		if (p->number == value)
		{
			return i;
		}
	    p = p->next;
	}
	return -1;
}
/*Get the weight of the edge which starts from v1 to v2*/
char AdjacentTable::GetWeightByPos(int v1, int v2) const
{
	if ((v1 >= 0) && (v2 >= 0) && (v1 < numOfVertices) && (v2 < numOfVertices))
	{
		Vertex *p = start;
		for (int i=0; i<v1; i++)
	      	p = p->next;
		Edge *q = p->out;
		while (q)
		{
			if (q->position == v2)
				return (q->weight);
			else
				q = q->link;
		}
	}
	return '#';
}
/*Get the weight of the edge by the value of the vertexes*/
char AdjacentTable::GetWeightByValue(int value1, int value2) const
{
	return GetWeightByPos(GetPosByValue(value1), GetPosByValue(value2));
}
/*Set the value of the vertex*/
void AdjacentTable::SetValue(int value, int pos)
{
	if ((pos < 0) || (pos >= numOfVertices))
	{
		cout << "Illegal setting: The vertex doesn't exist!" << endl;
		exit(1);
	}
	Vertex *p = start;
	for (int i=0; i<pos; i++)
	{
		p = p->next;
	}
	p->number = value;
}
/*Insert  a Vertex*/
void AdjacentTable::InsertVertex(int value)
{
	int pos = GetPosByValue(value);
	if ((pos >= 0) && (pos < numOfVertices))
	{
		cout << "Illegal insertion: The same vertex has existed!" << endl;
		exit(1);
	}
	Vertex *p = start;
	while (p->next)
		p = p->next;
	Vertex *newVertex = new Vertex(value);
	p->next = newVertex;
	numOfVertices++;
}
/*Insert the edge which starts from v1 to v2*/
void AdjacentTable::InsertEdgeByPos(int v1, int v2, char weight)
{
	if ((v1 < 0) || (v1 >= numOfVertices) || (v2 < 0) || (v2 >= numOfVertices))
	{
		cout << "Illegal insertion: The vertex doesn't exist!" <<endl;
		exit(1);
	}
	Vertex *p = start;
	for (int i=0; i<v1; i++)//find v1
		p = p->next;
	Edge *q = p->out;
	Edge *newEdge = new Edge(GetValueByPos(v2), v2, weight);
	if (! q)
	{
		p->out = newEdge;
		numOfEdges++;
		return;
	}
	while ((q->position != v2) && (q->link))
		q = q->link;
	if (q->position == v2)
	{
		cout << "Illegal insertion: The Edge has existed!" <<endl;
		exit(1);
	}
	if (! q->link)
	{
		q->link = newEdge;
		numOfEdges++;
	}
}
/*Insert the edge which starts from v1 of value1 to v2 of value2*/
void AdjacentTable::InsertEdgeByValue(int value1, int value2, char weight)
{
	int v1 = GetPosByValue(value1), v2 = GetPosByValue(value2);
	InsertEdgeByPos(v1, v2, weight);
}
/*Delete all the edges*/
void AdjacentTable::RemoveAllEdges(void)
{
	Vertex *p = start;
	for (int i=0; i<numOfVertices; i++)
	{
		Edge *q = p->out;
		while (q)
		{
			p->out = q->link;
			delete q;
			q = p->out;
		}
		p = p->next;
	}
	numOfEdges = 0;
}
/*Clear the Adjacent Table*/
void AdjacentTable::Clear(void)
{
	RemoveAllEdges();
	Vertex *p = start->next;
	while (p)
	{
		start->next = p->next;
		delete p;
		p = start->next;
	}
	numOfVertices = 1;
}
/* The e-closure*/
int* AdjacentTable::Closure(int *T)
{
	int i = 0, j, k = 0, l, len = 0;
	int *temp = new int[128];
	Vertex *p;
	Edge *q;
	while (T[len] != -1)
		len++;
	while (T[i] != -1)
	{
    	for (l=0; l<k; l++)
			if (T[i] == temp[l])
		    	     break;
	    if (l == k)
		{
			temp[k] = T[i];
			k++;
		}
		int pos = GetPosByValue(T[i]);
		p = start;
		for (j=0; j<pos; j++)
			p = p->next;
		q = p->out;
		while (q)
		{
			if (q->weight == '~')
			{
				for (l=0; l<k; l++)
			    		if (q->number == temp[l])
			    			break;
		    	if (l == k)
				{
			    		temp[k] = q->number;
		    			k++;
					T[len++] = q->number;
					T[len] = -1;
				}
			}
			q = q->link;
		}
		i++;
	}
	temp[k] = -1;
	return temp;
}

int* AdjacentTable::Move(int *T, char ch)
{
	int i = 0, j, k = 0, l;
	int *temp = new int[128];
	Vertex *p;
	Edge *q;
	while (T[i] != -1)
	{
		int pos = GetPosByValue(T[i]);
		p = start;
		for (j=0; j<pos; j++)
		{
			p = p->next;
		}
		q = p->out;
		while (q)
		{
			if (q->weight == ch)
			{
				for (l=0; l<k; l++)
			    	if (q->number == temp[l])
			    		break;
		    	if (l == k)
				{
			    	temp[k] = q->number;
		    		k++;
				}
			}
			q = q->link;
		}
		i++;
	}
	temp[k] = -1;
	return temp;
}
//Display the NFA
void AdjacentTable::OutputNFA(void)
{
	Vertex *p = start;
	Edge *q = new Edge();
	cout << "From   To(Transition Symbol)" << endl;
	for (int i=0; i<numOfVertices; i++)
	{
		cout << p->number;
		if (p->number < 10)	 cout << "      ";
		else if (p->number < 100)  cout << "     ";
		else if (p->number < 1000)	cout << "    ";
		else  cout << "   ";
		q = p->out;
		if (q)
			while (q)
			{
				cout << q->number << "(" << q->weight << ") ";
				q = q->link;
			}
		else 
			cout << "END";
		cout << endl;
		p = p->next;
	}
}

AdjacentTable::~AdjacentTable()
{
	Vertex *vertex;
	Edge *edge;
	vertex= start;
	for (int i=0; i<numOfVertices; i++)
	{
		edge = vertex->out;
		while (edge)
		{
			vertex->out = edge->link;
			delete edge;
			edge = vertex->out;
		}
		vertex= vertex->next;
	}
}

class DFA
{

public:
	DFA();
	~DFA();
	void prepare(char* re,char*file);
	void FindMatchingPatternInFile(char*file);

private:
	char *exp;         //stores the regular expression 
	char *post;       //stores the postfix expression
	char *edge;      //stores the terminal of the expression
	int edgeNumber; // the number of the terminal
	int **DStates;
	int **Dtran;
	int *AcceptStates;
	int DStatesNumber;
	int DtranNumber;
	int NFAStatesNumber;
	int DFAStatesNumber;
	AdjacentTable *NFATable;
	TransitionTable *DFATable;
	void GetRegExp();                          //get the regular expression from the console
	void InsertCatNode();                   // Insert dot to represent catenation
	void RegExpToPost();                   //Change the regular expression into the postfix form according to the operatpor priority
	void GetAllTerminals();               //Scan the post order string to get the number of the terminals
	void ThompsonConstruction();   //Construct NFA using Thompson's rule
	void SubsetConstruction();
	int getPriority(char symbol);//Define the priority of the operator
	int CompArray(int *t1, int *t2);
	int MinimizeDFAStates(int **Dtran, int *AcceptStates, int DtranNumber, int edgeNumber);
	void RemoveFirstSymbol(char *buf, int &len);
};
DFA::DFA()
{
	exp = new char[128];
	post = new char[128];
	edge = new char[128];
        edgeNumber = 0;
	NFAStatesNumber = 0;
	DFAStatesNumber = 0;
	DStatesNumber = 0;
	DtranNumber = 0;
	NFATable = new AdjacentTable();
}
DFA::~DFA()
{
	delete [] exp;
	delete [] post;
	delete [] edge;
	delete [] AcceptStates;
	NFATable->Clear();
	DFATable->Clear();
}
void DFA::prepare(char* re,char* file)
{
    exp=re;
	for (int i=0; exp[i]!='\0'; i++)
	{
		if (exp[i] == '~')
		{
			cout << "\nERROR:Character '~' has been used to represents e transition in the program！" << endl;
			getchar();
			exit(1);
		}
	}
	
   InsertCatNode(); 
   RegExpToPost(); 
   GetAllTerminals();   
   ThompsonConstruction();
   SubsetConstruction();
   FindMatchingPatternInFile(file);
}

void DFA::GetRegExp()
{
	cout << "\nStep1:Enter the regular expression:" << endl;
	
    cout<<endl;
}
/*Insert dot to represent catenation*/
void DFA::InsertCatNode()
{
	int i = 0, j, len = strlen(exp);
	while (exp[i+1] != '\0')