wordanalyse.cpp

很好用的词法分析器

// WordAnalyse.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include "auto_machine.h"
#include "State.h"
#include <string>
#include <list>
#include <set>
#include <fstream>
#include <algorithm>
#include <stdio.h>
using namespace std;
int FormNFA( auto_machine &NFA, ifstream &grammar )
{//文法形式为:
	//id
	//[Start]->a[Y]
	//[Y]->b
	//[Y]->$
	State* StartState = new State;					//将所有文法的开始符,用一个统一的开始符指向他们.
	StartState->GrammarName = "";
	StartState->StateName = "";

	NFA.insert_state(StartState);
	NFA.insert_beginstate( StartState );
	string generation;
	getline( grammar, generation );
	while( !grammar.eof( ) )
	{//一遍循环读入一个文法.
		string grammarname = generation;
		getline( grammar, generation );
		int tag = 0;			//标记文法的开始符,若为0即为开始符.
		char z[2] = "0";
		while(generation[0] == '[')
		{//一遍循环读入一个产生式.
			State* HeadState = new State;
			State* NextState = new State;
			const char seps[] = "[]→ ";
			int i = 1;		//标记产生式的第i个部分.
			char *token = strtok(const_cast< char* >( generation.c_str( ) ), seps);
			char InputChar;
			while(token)
			{
				if(i == 1)
				{//读到产生式左边的非中止符.
					HeadState->GrammarName = grammarname;
					HeadState->StateName = token;
					if( !NFA.inserted( HeadState ) )
						NFA.insert_state(HeadState);
					if(!tag)
					{//遇到文法的开始符,将其和NFA的开始符联系起来.
						NFA.insert_map(StartState, '$', HeadState);
						tag = 1;
					}
					++i;
				}
				else if(i == 2)
				{
					InputChar = *token;
					++i;
					NFA.insert_char( InputChar );
				}
				else
				{
					NextState->GrammarName = grammarname;
					NextState->StateName = token;
					if( !NFA.inserted( NextState ) )
						NFA.insert_state( NextState );
					NFA.insert_map(HeadState, InputChar, NextState);
					++i;
				}
				token = strtok(NULL, seps);
			}
			if(i == 3)
			{
				NextState->GrammarName = grammarname;
				NextState->StateName = string("Z") + string(z);
				++z[0];
				if(!NFA.inserted(NextState))
				{
					NFA.insert_state( NextState );
					NFA.insert_endstate(NextState);
				}
				NFA.insert_map(HeadState, InputChar, NextState);
			}
			generation = "";
			getline( grammar, generation );
		}
	}
	return 0;
}

void CheckProgram(auto_machine DFA, ifstream &program, ofstream &result)
{
	while( !program.eof() )
	{
		string s;
		getline( program, s );
		const char seps[] = "	 ";
		char* token = strtok( const_cast< char* >( s.c_str() ), seps );
		while( token )
		{
			State* Now = DFA.BeginState;
			for( size_t i = 0; i < strlen( token ); ++i )
			{
				list<State*>::iterator it = find( DFA.StateCollect.begin( ), DFA.StateCollect.end( ), Now );
				list<ArcNode>::iterator inerit;
				for( inerit = (*it)->MapTo.begin( ); inerit != (*it)->MapTo.end( ); ++inerit )
				{
					if( inerit->InputChar == token[i] )
					{
						Now = inerit->NextState;
						break;
					}
				}
				if( inerit == (*it)->MapTo.end( ) )
					break;
			}
			if( i == strlen( token )  )
			{
				list<State*>::iterator it = find( DFA.EndState.begin( ), DFA.EndState.end( ), Now );
				if( it == DFA.EndState.end( ) )
					result<<"ErrorWord ";
				else
					result << (*it)->GrammarName<<"("<<token<<") ";
			}
			else 
				result << "ErrorWord ";
			token = strtok( NULL, seps );
		}
		result<<endl;
	}
	return ;
}
int main(int argc, char* argv[])
{
	auto_machine DFA;
	ifstream grammar("grammar.txt");
	auto_machine NFA;
	NFA.insert_char( '$' );
	FormNFA(NFA, grammar);
	NFA.NFA_TO_DFA( DFA );
	NFA.Destroy( );
	DFA.Minimize( );
	ifstream program( "program.txt" );
	ofstream Word( "result.txt" );
	CheckProgram(DFA, program, Word);
	DFA.Destroy( );
	return 0;
}