adjacenttable.cc

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

#include "AdjacentTable.h"
#include<iostream>

/*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;
	}
}