code

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

	{
		if (((exp[i] != '(' && exp[i] != '.' && exp[i] != '|') 
			|| exp[i] == ')' 
			|| exp[i] == '*')
			&& (exp[i+1] != ')' && exp[i+1] != '.' && exp[i+1] != '|' && exp[i+1] != '*'))
		{
			for (j=len; j>i+1; j--)
			{
				exp[j] = exp[j-1];
			}
			exp[i+1] = '.';
			len++;
			exp[len] = '\0';
			i++;
		}
		i++;
	}
   
}
/*Define the priority of the operator*/
int DFA::getPriority(char symbol)
{
	int priority;
	switch (symbol)
	{
	case '|': priority = 1; break;
	case '.': priority = 2; break;
	case '*': priority = 3; break;
	default:  priority = 0; break;
	}
	return priority;
}
/*Change the regular expression into the postfix form according to the operatpor priority*/
void DFA::RegExpToPost()
{
	int i = 0, j = 0;
	char ch, cl;
	strcpy(post, "\0");
	stack<char> *ls = new stack<char>();
	ls->push('#');
	ch = exp[i];
	while (ch != '\0')
	{
		if (ch == '(')
		{
			ls->push(ch);
			ch = exp[++i];
		}
		else if (ch == ')')
		{
			while (ls->top() != '(')
			{
				post[j++] = ls->top();
				ls->pop();
			}
            ls->pop();
			ch = exp[++i];
		}
		else if ((ch == '|') || (ch == '*') || (ch == '.'))
		{
	    	     cl = ls->top();
		   	while (getPriority(cl) >= getPriority(ch))
			{
		    	post[j++] = cl;
		    	ls->pop();
		    	cl = ls->top();
			}
			ls->push(ch);
			ch = exp[++i];
		}
		else
		{
			post[j++] = ch;
			ch = exp[++i];
		}
	}
	ch = ls->top();
	ls->pop();
	while ((ch == '|') || (ch == '*') || (ch == '.'))
	{
		post[j++] = ch;
		ch = ls->top();
		ls->pop();
	}
	post[j] = '\0';
	ls=new stack<char>();

}
/*Scan the post order string to get the number of the terminals*/
void DFA::GetAllTerminals()
{
	int i = 0, j;
	edgeNumber = 0;
	while (post[i] != '\0')
	{
		if (post[i] == '.' || post[i] == '|' || post[i] == '*')
		{
			i++;
			continue;
		}
		for (j=0; j<edgeNumber; j++)
		{
			if (post[i] == edge[j])
				break;
		}
		if (j == edgeNumber)
		{
			edge[edgeNumber] = post[i];
			edgeNumber++;
		}
		i++;
	}
	edge[edgeNumber] = '\0';
}
/*Construct NFA using Thompson's rule*/
void DFA::ThompsonConstruction()
{
	int i, j;
	char ch;
	int s1, s2;
	stack<int> *states = new stack<int>();
	if (strlen(post) < 1)
	{
		cout << "No Valid Regular Expression Found!" << endl;
		exit(1);
	}
	NFATable->SetValue(0, 0);
	i = 1;
	j = 0;
	ch = post[j];
    while (ch != '\0')
	{
		if (ch == '.')//catenation
		{
		     s2 = states->top();
			states->pop();
			int temp1 = states->top();
			states->pop();
			int temp2 = states->top();
			states->pop();
			s1 = states->top();
			states->pop();
			NFATable->InsertEdgeByValue(temp2, temp1, '~');
			states->push(s1);
			states->push(s2);
		}
		else if (ch == '|')//choice
		{
			s2 = states->top();
			states->pop();
			int temp1 = states->top();
			states->pop();
			int temp2 = states->top();
			states->pop();
			s1 = states->top();
			states->pop();
			NFATable->InsertVertex(i);
			NFATable->InsertVertex(i+1);
			NFATable->InsertEdgeByValue(i, s1, '~');
			NFATable->InsertEdgeByValue(i, temp1, '~');
			NFATable->InsertEdgeByValue(temp2, i+1, '~');
			NFATable->InsertEdgeByValue(s2, i+1, '~');
			s1 = i;
			s2 = i+1;
			states->push(s1);
			states->push(s2);
			i += 2;
		}
		else if (ch == '*')//repetition
		{
			s2 = states->top();
			states->pop();
			s1 = states->top();
			states->pop();
			NFATable->InsertVertex(i);
			NFATable->InsertVertex(i+1);
			NFATable->InsertEdgeByValue(i, i+1, '~');
			NFATable->InsertEdgeByValue(s2, s1, '~');
			NFATable->InsertEdgeByValue(i, s1, '~');
			NFATable->InsertEdgeByValue(s2, i+1, '~');
			s1 = i;
			s2 = i+1;
			states->push(s1);
			states->push(s2);
			i += 2;
		}
		else //terminal
		{
			NFATable->InsertVertex(i);
			NFATable->InsertVertex(i+1);
			NFATable->InsertEdgeByValue(i, i+1, ch);
			s1 = i;
			s2 = i+1;
			states->push(s1);
			states->push(s2);
			i += 2;
		}
		j++;
		ch = post[j];
	}
	s2 = states->top();
	states->pop();
	s1 = states->top();
	states->pop();
	NFATable->InsertEdgeByValue(0, s1, '~');
	if (! states->empty())
	{
		cout << "Some error in your input string!" << endl;
		exit(1);
	}
	NFAStatesNumber = s2 + 1;
}
/*Compare whether two integer array has the same content*/
int DFA::CompArray(int *t1, int *t2)
{
	int i = 0, j = 0, len1, len2;
	while (t1[i] != -1)
		i++;
	len1 = i;
	while (t2[j] != -1)
		j++;
	len2 = j;
	if (len1 != len2)
		return 0;
	for (i=0; i<len1; i++)
	{
		for (j=0; j<len2; j++)
			if (t1[i] == t2[j])
				break;
		if (j == len2)
			return 0;
	}
	return 1;
}
/*Minimize the transition table*/
int DFA::MinimizeDFAStates(int **Dtran, int *AcceptStates, int DtranNumber, int edgeNumber)
{
	int h, i, j, k, l;
	for (i=0; i<DtranNumber-1; i++)
	{
		for (j=i+1; j<DtranNumber; j++)
		{
			if (AcceptStates[i] == AcceptStates[j])
			{
				for (k=0; k<edgeNumber; k++)
				{
					if (Dtran[i][k] != Dtran[j][k])
					{
						break;
					}
				}
				if (k == edgeNumber)
				{
					for (l=j; l<DtranNumber-1; l++)
					{
						for (k=0; k<edgeNumber; k++)
						{
							Dtran[l][k] = Dtran[l+1][k];
						}
						AcceptStates[l] = AcceptStates[l+1];
					}
					for (l=0; l<DtranNumber-1; l++)
					{
						for (k=0; k<edgeNumber; k++)
						{
							if (Dtran[l][k] == j)
							{
								Dtran[l][k] = i;
							}
						}
					}
					for (h=j; h<DtranNumber; h++)
					{
						for (l=0; l<DtranNumber-1; l++)
						{
							for (k=0; k<edgeNumber; k++)
							{
								if (Dtran[l][k] == h+1)
								{
									Dtran[l][k] = h;
								}
							}
						}
					}
					DtranNumber--;
					j--;
				}
			}
		}
	}
	return DtranNumber;
}
/*Construct DFA using subset construction*/
void DFA::SubsetConstruction()
{
	int i, j, k;
	DStatesNumber = 0;
	DtranNumber = 0;   
	// initialize the NFA state table
	DStates = (int**)(new int*[NFAStatesNumber+1]);
	for (i=0; i<NFAStatesNumber+1; i++)
		DStates[i] = new int[NFAStatesNumber+1];
        //initialize the NFA transition table,setting all the element to -1
	Dtran = (int**)(new int*[NFAStatesNumber+1]);
	for (i=0; i<NFAStatesNumber+1; i++)
		Dtran[i] = new int[edgeNumber+1];
	for (i=0; i<NFAStatesNumber+1; i++)
		for (j=0; j<edgeNumber+1; j++)
			Dtran[i][j] = -1;
       //initialize the NFA accepting states array
	AcceptStates = new int[NFAStatesNumber+1];
	for (i=0; i<NFAStatesNumber+1; i++)
		AcceptStates[i] = 0;
	// Construct the NFA state table,NFA transition table and accepting states array using Move and Closure functions
        int *T = new int[NFAStatesNumber+1];
	int *temp = new int[NFAStatesNumber+1];
	T[0] = 0;
	T[1] = -1;
	T = NFATable->Closure(T);
	DStates[DStatesNumber] = T;
	DStatesNumber++;
	k = 0;
	while (k < DStatesNumber)
	{
		for (i=0; edge[i]!='\0'; i++)
		{
			temp = NFATable->Closure(NFATable->Move(T, edge[i]));
			if (temp[0] != -1)
			{
				for (j=0; j<DStatesNumber; j++)
				{
					if (CompArray(temp, DStates[j]) == 1)
					{
						Dtran[k][i] = j;
						break;
					}
				}
				if (j == DStatesNumber)
				{
					DStates[DStatesNumber] = temp;
					Dtran[k][i] = DStatesNumber;
					DStatesNumber++;
				}
			}
		}
		k++;
		T = DStates[k];
	}
	DtranNumber = k;
	for (i=0; i<DStatesNumber; i++)
	{
		for (j=0; DStates[i][j]!= -1; j++)
		{
			if (DStates[i][j] == NFAStatesNumber - 1)
			{
				AcceptStates[i] = 1;
				break;
			}
		}
	}
	
	/*Scan the NFA transition table repeatly to minimize the table until get the minimized DFA*/
	int DtranNumberAfterMinimization = MinimizeDFAStates(Dtran, AcceptStates, DtranNumber, edgeNumber);
	while (DtranNumberAfterMinimization != DtranNumber)
	{
		DtranNumber = DtranNumberAfterMinimization;
		DtranNumberAfterMinimization = MinimizeDFAStates(Dtran, AcceptStates, DtranNumber, edgeNumber);
	}
	/*Copy the transition table to the DFA table*/
	DFATable = new TransitionTable(DtranNumber, edgeNumber);
	for (i=0; i<DtranNumber; i++)
	{
		for (j=0; j<edgeNumber; j++)
		{
			DFATable->SetValue(i, j, Dtran[i][j]);
		}
	}
	// Delete all the tables and arrays created
	for (i=0; i<NFAStatesNumber+1; i++)
	{
		delete [] DStates[i];
		delete [] Dtran[i];
	}
	delete [] DStates;
	delete [] Dtran;
}

/*Remove first charactor from the string*/
void DFA::RemoveFirstSymbol(char *buf, int &len)
{
	for (int i=0; i<len-1; i++)
	{
		buf[i] = buf[i+1];
	}
	len--;
	buf[len] = '\0';
}
//Read from file and recognize all the match string
void DFA::FindMatchingPatternInFile(char *file)
{
	char filePath[128];
	fstream infile;
	infile.open(file);
	if (! infile)
	{
		cout << "\nOpening file failed！" << endl;
		exit(1);
	}
	// scan 
	int ln = 1, col = 0, bufHead = 0;
	int state = 0;
	int count = 0;
	char buf[256];
	int curr = 0;
	int len = 0;
	char ch;
	char recognized[256];
	while (infile.get(ch))
	{
		if ((ch == '\n') || (ch == ' '))
		{	
			while (curr < len)
			{
				state = 0;
				while ((state != -1) && (curr < len))
				{
					state = DFATable->Transit(state, buf[curr], edge);
			    	        if (AcceptStates[state] == 1)
					{
						cout << "\nLine: " << ln <<": ";
						strncpy(recognized,buf,curr+1);recognized[curr+1]='\0';
			           	printf("Recognized string is %s\n",recognized);
                              invoke();
				    	     count++;
					}
					curr++;
				}
				RemoveFirstSymbol(buf, len);
				bufHead++;
				curr = 0;
			}
			if (ch == '\n')
			{
				ln++;
				col = 0;
			}
			if (ch == ' ')
			{
				col++;
			}
		}
		else
		{
			col++;
			if (len == 0)
			{
				bufHead = col;
			}
			buf[len++] = ch;
			if (len >= 256)
			{
				cout << "The string is overflow！" << endl;
				getchar();
				exit(1);
			}
		}
	}
	while (curr < len)
	{
		state = 0;
	  	curr = 0;
		while ((state != -1) && (curr < len))
		{
			state = DFATable->Transit(state, buf[curr], edge);
		   	if (AcceptStates[state] == 1)
			{
				cout << "\nLine: " << ln <<": ";
				 strncpy(recognized,buf,curr+1);
                    
				 printf("Recognized string is %s\n");
                     invoke();
				count++;
			}
			curr++;
		}
		RemoveFirstSymbol(buf, len);
		bufHead++;
	}
	if (count > 0)
	{
		cout <<"\n"<<count<< " matched string"  << " Found\n" ;
	}
	else
	{
		cout << "\n\nNo string found!";
	}
	infile.close();
}
int main(int argc,char * argv[])
{