myyacc.cpp

一个不算完整的编译器实现

#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<fstream>
#include<algorithm>
#include<queue>
#include<stdlib.h>
using namespace std;

struct item_struct
{
	int pronum;//产生式号
	int pp;//pointposition，点的位置，例：E->a.Bc，pp=1
	vector<int> searchnum;//搜索符数组，存进来的时候要保证是升序排列
};
struct DFAnode_struct
{
	vector<item_struct> heart;//代表核心项
	string id;//代表状态核心项确定的唯一标识
	vector<pair<int,int> > nontermin,termin;
	//这两个是转移边，前面的是通过非终极符号转到的状态，在GOTO表中用；后面的是通过终极符号转到的状态，在ACTION表中用
	//pair中前面的int是输入符，后面的int是状态
};
//------------------------------------------------------------------------
string cal_state_id(vector<item_struct> &heart)
{//用来计算核心项的标识字符串
	vector<string> heart_string;
	char c[10];
	sprintf(c,"%d;",heart.size());
	string result=c;
	for(int i=0;i<heart.size();i++)
	{//分别把每一个项目转成字符串，然后对字符串排序
		char pn[20];
		sprintf(pn,"%d;%d;",heart[i].pronum,heart[i].pp);
		string item=pn;
		for(int j=0;j<heart[i].searchnum.size();j++)
		{
			sprintf(pn,"%d,",heart[i].searchnum[j]);
			item += pn;
		}
		heart_string.push_back(item);
	}
	sort(heart_string.begin(),heart_string.end());
	for(int i=0;i<heart_string.size();i++)
	{
		//cout << heart_string[i] << endl;
		result += heart_string[i] + ";";
	}
//	cout << result << endl;
	return result;
}
//------------------------------------------------------------------------
void show_item(item_struct &item,vector<pair<int,bool> > *pro,vector<string> &tToString,vector<string> &ntToString)
{//用来输出一个产生式项目
	int pp=item.pp;
	int pn=item.pronum;
	cout << ntToString[pro[pn][0].first] << " --> ";
	for(int i=1;i<pro[pn].size();i++)
	{
		if(pp==i-1) cout << " . ";
		if(pro[pn][i].second==true)
		{
			cout << ntToString[pro[pn][i].first] << " ";
		}
		else cout << tToString[pro[pn][i].first] << " ";
	}
	cout << "\t|||\t";
	for(int i=0;i<item.searchnum.size();i++)
	{
		cout << tToString[item.searchnum[i]] << "  ";
	}
	cout << endl;
}
void showDFA(vector<DFAnode_struct> &DFAnode,vector<pair<int,bool> > *pro,vector<string> &tToString,vector<string> &ntToString,bool *state_used)
{//用来把整个DFA所有结点输出
	for(int i=0;i<DFAnode.size();i++)
	{
		if(!state_used[i]) continue;
		cout << "STATE" << i << endl;
		for(int j=0;j<DFAnode[i].heart.size();j++)
		{
			show_item(DFAnode[i].heart[j],pro,tToString,ntToString);
		}
		for(int j=0;j<DFAnode[i].nontermin.size();j++)
		{
			cout << "通过" << ntToString[DFAnode[i].nontermin[j].first] << "到状态" << DFAnode[i].nontermin[j].second << endl;
		}
		for(int j=0;j<DFAnode[i].termin.size();j++)
		{
			cout << "通过" << tToString[DFAnode[i].termin[j].first] << "到状态" << DFAnode[i].termin[j].second << endl;
		}
	}
}
void showACTION(const vector<int*> &action_table,const vector<string> &tToString,const int pc)
{//打印出ACTION表
	printf("\t");
	for(int i=0;i<tToString.size();i++)
		printf("%s\t",tToString[i].c_str());
	cout << endl;
	for(int i=0;i<action_table.size();i++)
	{
		printf("%d\t",i);
		for(int j=0;j<tToString.size();j++)
		{
			if(action_table[i][j]>0) printf("S%d\t",action_table[i][j]);
			else if(action_table[i][j]<0) 
			{
				if(action_table[i][j]<-pc-5) printf("ACC\t");
				else printf("R%d\t",-action_table[i][j]);
			}
			else printf("%d\t",0);
		}
		cout << endl;
	}
}
void showGOTO(const vector<int*> &goto_table,const vector<string> &ntToString)
{
	printf("\t");
	for(int i=0;i<ntToString.size();i++)
		printf("%s\t",ntToString[i].c_str());
	cout << endl;
	for(int i=0;i<goto_table.size();i++)
	{
		printf("%d\t",i);
		for(int j=0;j<ntToString.size();j++)
		{
			if(goto_table[i][j]>0) printf("S%d\t",goto_table[i][j]);
			else printf("%d\t",0);
		}
		cout << endl;
	}
}
//------------------------------------------------------------------------
string get_num(const string &id,int &count)
{//就是提取分号前的字符的函数
	string result="";
	for(;count<id.size();count++)
	{
		if(id[count]!=';') result.push_back(id[count]);
		else
		{
			count++;
			return result;
		}
	}
}
bool is_same_heart(DFAnode_struct &s1,DFAnode_struct &s2)
{//用来判断两个状态的核心项是否相同
 //id组成：第一个是核心项的个数n；然后有n项，每一项第一个为项目产生式号，第二个是点的位置，后面都是搜索符号
 //看id是否相等，先看核心项个数是否相等，相等再看每一项的项目产生式号和点的位置，不看搜索符
	bool result=true;
	string id1=s1.id,id2=s2.id;
	string left="",right="";
	int count1=0,count2=0;
	//先判断核心项数是否相同
	left=get_num(id1,count1);
	right=get_num(id2,count2);
	if(left!=right) return false;
	while(1)
	{//这时两个id的核心项个数肯定相同
		//得到每一项的第一部分
		left=get_num(id1,count1);
		right=get_num(id2,count2);
		if(left!=right) return false;
		//得到每一项的第二部分
		left=get_num(id1,count1);
		right=get_num(id2,count2);
		if(left!=right) return false;
		//忽略搜索符
		left=get_num(id1,count1);
		right=get_num(id2,count2);
		//看是否到了id的末尾
		if(count1>=id1.size() && count2>=id2.size()) return true;
	}
	return result;
}
void combine_searchsymbol(DFAnode_struct &from,DFAnode_struct &to,const int tCount)
{//把from的各项目的搜索符给to的对应项目
	for(int i=0;i<from.heart.size();i++)
	{//对于每一个核心项
		item_struct &fromheart=from.heart[i];
		item_struct &toheart=to.heart[i];
		bool *ss=new bool[tCount];//用来记录哪些是搜索符
		for(int j=0;j<tCount;j++)
			ss[j]=false;
		//把from和to的对应项目的搜索符都记下来
		for(int j=0;j<fromheart.searchnum.size();j++)
			ss[fromheart.searchnum[j]]=true;
		for(int j=0;j<toheart.searchnum.size();j++)
			ss[toheart.searchnum[j]]=true;
		vector<int> newss;//这个就是新的记录搜索符的结构，用来替换原来的
		for(int j=0;j<tCount;j++)
			if(ss[j]) newss.push_back(j);
		to.heart[i].searchnum=newss;//赋新值
	}
	//搜索符更新完以后更改id标识
	to.id=cal_state_id(to.heart);
	return;
}
//-------------------------------------------------------------------------
int main()
{
	//语法分析器生成器
	//从文件读入上下文无关方法，取出来终极字符和非终极字符
	//要求输入的文法是已经拓广了的，也就是只有一个是开始符号
	ifstream infile;
	infile.open("system\\grammar.txt");
	if(!infile)
	{//打开文件失败就退出
		printf("Unable to open the LexText file.\n");
		return -1;
	}
	vector<string> grammar1;//原始文法
	string input="";
	while(getline(infile,input))
	{
		//输入串末尾加个空格，分词的时候容易些
		input.push_back(' ');
		grammar1.push_back(input);
	}
	//建立产生式的存储结构，我用vector<string>[]数组来存
	vector<string> *production=new vector<string>[grammar1.size()];
	for(int i=0;i<grammar1.size();i++)
	{
		input="";
		//把原始文法分词后写入到产生式数组中
		for(int j=0;j<grammar1[i].size();j++)
		{
			if(grammar1[i][j]!=' ') input.push_back(grammar1[i][j]);
			else
			{
				production[i].push_back(input);
				input="";
			}
		}
	}
	int productionCount=grammar1.size();
	/*
	for(int i=0;i<grammar1.size();i++)
	{//检测输入是否正确
		for(int j=0;j<production[i].size();j++)
			cout << production[i][j] << "\t";
		cout << endl;
	}
	*/
	
	//用来识别非终极符和终极符
	map<string,int> nonterminal;
	vector<string> ntToString;
	int ntCount=0;
	map<string,int> terminal;
	vector<string> tToString;
	int tCount=0;
	int eposition=-1;//用来记录ε的位置
	for(int i=0;i<productionCount;i++)
	{//先识别非终极符
		input=production[i][0];
		if(nonterminal.find(input)==nonterminal.end())
		{
			nonterminal[input]=ntCount++;
			ntToString.push_back(input);
		}
	}
	for(int i=0;i<productionCount;i++)
	{//识别终极符
		for(int j=1;j<production[i].size();j++)
		{
			input=production[i][j];
			if(nonterminal.find(input)==nonterminal.end())
			{
				if(terminal.find(input)==terminal.end())
				{
					terminal[input]=tCount++;
					tToString.push_back(input);
				}
			}
		}
	}
	if(terminal.find("#")!=terminal.end()) eposition=terminal.find("#")->second;//找#（ε）
	vector<pair<int,bool> > *pro=new vector<pair<int,bool> >[productionCount];
	//把原始的文法变成可以很容易看出是否为非终极符和终极符的结构，pair的second为1时为非终极符，为0时为终极符
	//pair的first为对应输入串的下标编号
	for(int i=0;i<productionCount;i++)
	{
		for(int j=0;j<production[i].size();j++)
		{
			bool isNT=true;
			int num=-1;
			input=production[i][j];
			if(nonterminal.find(input)!=nonterminal.end())
			{
				num=nonterminal.find(input)->second;
				isNT=true;
			}
			else
			{
				num=terminal.find(input)->second;
				isNT=false;
			}
			pro[i].push_back(make_pair(num,isNT));
		}
	}
	/*//用来测试转换后的产生式是否正确
	for(int i=0;i<productionCount;i++)
	{
		for(int j=0;j<pro[i].size();j++)
		{
			if(pro[i][j].second) cout << ntToString[pro[i][j].first] << " " << pro[i][j].second << "\t";
			else cout << tToString[pro[i][j].first] << " " << pro[i][j].second << "\t";
		}
		cout << endl;
	}
	*/