yacc.cpp

语法分析器lex和词法分析器yacc的C++语言实现 1.Lex （1）Lex输入文件的解析 （2）正规表达式的解析 （3）一个正规表达式到NFA的转换算法实现 （4）多个NFA的合并

			if(!itemsetTable.count(ph->second))
			{
				pair<set<Item>,int> tp;
				tp.first=ph->second;			
				curState++;//只在此处增加项目集，故只在此处修改其值
				tp.second=curState;

				itemsetTable.insert(tp);
				//如果当前的项目集未出现过的话，需要将其放入队列中等待处理。
				Q.push(ph->second);
			}	

			//下面开始生成对应的action表
			//首先求得边所对应的表中的序号
			column=(nonterminSet.count(ph->first)?nonterminSet[ph->first]:terminSet[ph->first]);

			//此处加一些条件，判断是否有归约、移进冲突
			if(actionTable[row][column]<=0)
			{	
				if(producerPreTable[actionTable[row][column]*(-1)]<precedenceTable[ph->first])
				{
					actionTable[row][column]=itemsetTable[ph->second];
					continue;
				}
				if(rightTable.count(ph->first))
				{
					actionTable[row][column]=itemsetTable[ph->second];
					continue;
				}
				if(leftTable.count(ph->first))//如果此操作符不在两个结合表中
				{
					continue;
				}
	
				//如果上述条件都不满足，则报错。
				cout<<"Reduction & Shift Confliction"<<endl;
				cout<<"row="<<row<<" column="<<column<<" old="<<actionTable[row][column]
					<<" new="<<itemsetTable[ph->second]
					<<" signal="<<ph->first<<endl;
				return false;
			}
			else
				actionTable[row][column]=itemsetTable[ph->second];
			//cout<<"actionTable row="<<row<<" column="<<column<<endl;
			//getch();
		}
	}
	return true;
	//到此完成了项目集到分析表的构造
}
void generateTableCode()
{
	fout<<"int actionTable["<<actionTable.size()<<"]["<<actionTable.front().size()<<"]=\n\t\t{";
	for(int i=0;i<actionTable.size();i++)
	{
		fout<<"\t\t{";
		for(int j=0;j<actionTable.front().size();j++)
		{
			if(actionTable[i][j]!=40000)
				fout<<actionTable[i][j];
			else
				fout<<"E";
			if(j==actionTable.front().size()-1) continue;
			fout<<",";
		}
		fout<<"}";
		if(i==actionTable.size()-1) continue;
		fout<<",\n";
	}
	fout<<"};\n";
	fout<<"int searchTable(int cstate,char symbol)\n";
	fout<<"{\n";
	fout<<"\treturn actionTable[cstate][symbol];\n";
	fout<<"}\n";
	fout<<"\n";
	//此部分完成查表程序的输出
	//下面完成读Token程序的输出
	fout<<"int readToken()\n";
	fout<<"{\n";
	fout<<"\tif(fin.eof())\n";
	fout<<"\t\treturn SOURCE_END;\n";
	fout<<"\tchar buf[256];//不支持超过256个字符的符号\n";
	fout<<"\tint pos=0;\n";
	fout<<"\tbool isEnd=false;\n";
	fout<<"\tbool isToken=false;//与isOperator互斥\n";
	fout<<"\tbool isOperator=false;\n";
	fout<<"\tstring ops(\"!@#$%^&*()+-=|\[]{};':\\\",.<>/?\");\n";
	fout<<"\tstring wss(\"\\t\\n\\r \");\n";
	fout<<"\tstring letter(\"_0123456789aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ\");\n";

	fout<<"\tchar c=fin.get();\n";
	fout<<"\twhile(c==' '||c=='\\t'||c=='\\n'||c=='\\r') c=fin.get();//滤掉空白符\n";
	fout<<"\twhile(!isEnd)\n";
	fout<<"\t{\n";
	fout<<"\t\tif(c==-1)\n";
	fout<<"\t\t{\n";
	fout<<"\t\t\tbuf[pos]='\\0';\n";
	fout<<"\t\t\tisEnd=true;\n";
	fout<<"\t\t\tcontinue;\n";
	fout<<"\t\t}";
	fout<<"\t\tif(ops.find(c)>=0&&ops.find(c)<ops.size())//表示当c不是正常字符时。\n";
	fout<<"\t\t{\n";
	fout<<"\t\t\t//进入非正常字符的处理过程\n";
	fout<<"\t\t\tif(isToken)\n";
	fout<<"\t\t\t{\n";
	fout<<"\t\t\t\tfin.unget();\n";
	fout<<"\t\t\t\tbuf[pos]='\\0';\n";
	fout<<"\t\t\t\tisEnd=true;\n";
	fout<<"\t\t\t}\n";
	fout<<"\t\t\telse\n";
	fout<<"\t\t\t{\n";
	fout<<"\t\t\t\tisOperator=true;\n";
	fout<<"\t\t\t\tbuf[pos]=c;\n";
	fout<<"\t\t\t\tpos++;\n";
	fout<<"\t\t\t\tc=fin.get();\n";
	fout<<"\t\t\t}\n";
	fout<<"\t\t\tcontinue;\n";
	fout<<"\t\t}\n";
	fout<<"\t\tif(letter.find(c)>=0&&letter.find(c)<letter.size())\n";
	fout<<"\t\t{\n";
	fout<<"\t\t\tif(isOperator)\n";
	fout<<"\t\t\t{\n";
	fout<<"\t\t\t\tfin.unget();\n";
	fout<<"\t\t\t\tbuf[pos]='\\0';\n";
	fout<<"\t\t\t\tisEnd=true;\n";
	fout<<"\t\t\t}\n";
	fout<<"\t\t\telse\n";
	fout<<"\t\t\t{\n";
	fout<<"\t\t\t\tisToken=true;\n";
	fout<<"\t\t\t\tbuf[pos]=c;\n";
	fout<<"\t\t\t\tpos++;\n";
	fout<<"\t\t\t\tc=fin.get();\n";
	fout<<"\t\t\t}\n";
	fout<<"\t\t\tcontinue;\n";
	fout<<"\t\t}\n";
	fout<<"\t\tif(wss.find(c)>=0&&wss.find(c)<wss.size())\n";
	fout<<"\t\t{\n";
	fout<<"\t\t\tbuf[pos]='\\0';\n";
	fout<<"\t\t\tisEnd=true;\n";
	fout<<"\t\t}\n";
	fout<<"\t\t\n";
	fout<<"\t\t\n";

	fout<<"\t\telse return -1;\n";
	fout<<"\t}\n";
	fout<<"\treturn analysis(buf,strlen(buf));\n";
	fout<<"}\n";
}

void generateSemanticActionCode()
{
	fout<<"void runaction(int num)\n";
	fout<<"{\n";
	fout<<"\tswitch(num)\n";
	fout<<"\t{\n";
	for(int i=0;i<produceActionTable.size();i++)
	{
		if(produceActionTable[i].size()!=0)
		{
			fout<<"\tcase "<<i+1<<":\n";
			fout<<"\t\t{\n";
			fout<<"\t\t\t"<<produceActionTable[i]<<"\n";
			fout<<"\t\t\tbreak;\n";
			fout<<"\t\t}\n";
		}
	}
	fout<<"\t}\n";
	fout<<"}\n";
}

void generateParseCode()
{
	fout<<"int parse()\n";
	fout<<"{\n";
	fout<<"\tint inputsymbol=0;\n";
	fout<<"\tint cstate=0;\n";
	fout<<"\tstack<Sym> symStack;//符号栈\n";
	fout<<"\tstack<SV> valStack;//语义值栈\n";
	fout<<"\tSym st;//用作分析时的临时栈顶元素存储变量\n";
	fout<<"\tst.symbol=0;\n";
	fout<<"\tst.state=0;\n";
	fout<<"\tSV val;\n";
	fout<<"\tsymStack.push(st);//语义值栈必须要和符号栈同步\n";
	fout<<"\tvalStack.push(val);\n";
	fout<<"\tinputsymbol=readToken();\n";
	fout<<"\twhile(1)\n";
	fout<<"\t{\n";
	fout<<"\t\tst=symStack.top();\n";
	fout<<"\t\tint col=signalTable[inputsymbol];\n";
	fout<<"\t\tint result=searchTable(st.state,col);\n";
	fout<<"\t\tif(result==E)//出错\n";
	fout<<"\t\t{\n";
	fout<<"\t\t\tcout<<\"Compile Error!\"<<endl;\n";
	fout<<"\t\t\treturn 0;\n";
	fout<<"\t\t}\n";
	fout<<"\t\tif(result==ACCEPT)\n";
	fout<<"\t\t{\n";
	fout<<"\t\t\tcout<<\"Compile sucessfully!\"<<endl;\n";
	fout<<"\t\t\treturn 1;\n";
	fout<<"\t\t}\n";
	fout<<"\t\tif(result<0)//负数表示为归约项目\n";
	fout<<"\t\t{\n";
	fout<<"\t\t\tresult*=-1;\n";
	fout<<"\t\t\tint n=producerN[result];//取得该号产生式右部符号数量，以作弹栈用\n";
	fout<<"\t\t\tfor(int i=0;i<n;i++)\n";
	fout<<"\t\t\t{\n";
	fout<<"\t\t\t\tsymStack.pop();\n";
	fout<<"\t\t\t\tu[n-i]=valStack.top();\n";
	fout<<"\t\t\t\tvalStack.pop();\n";
	fout<<"\t\t\t}\n";
	fout<<"\t\t\trunaction(result);//执行语义动作\n";
	fout<<"\t\t\t//再将产生式左部的符号压栈，语义值一同压栈\n";
	fout<<"\t\t\tst.symbol=pLeftSection[result];\n";
	fout<<"\t\t\tst.state=searchTable(symStack.top().state,signalTable[st.symbol]);\n";
	fout<<"\t\t\tsymStack.push(st);\n";
	fout<<"\t\t\t//将产生式左部符号的语义值入栈。这个值在runaction()中已经修改\n";
	fout<<"\t\t\tvalStack.push(u[0]);\n";
	fout<<"\t\t}\n";
	fout<<"\t\telse\n";
	fout<<"\t\t{\n";
	fout<<"\t\t\tst.symbol=inputsymbol;\n";
	fout<<"\t\t\tst.state=result;\n";
	fout<<"\t\t\tsymStack.push(st);\n";
	fout<<"\t\t\tSV tu;\n";
	fout<<"\t\t\tif(yyval.ival==0)\n";
	fout<<"\t\t\t\tgetvalue(inputsymbol,tu);\n";
	fout<<"\t\t\telse tu=yyval;\n";
	fout<<"\t\t\tvalStack.push(tu);\n";
	fout<<"\t\t\tinputsymbol=readToken();\n";
	fout<<"\t\t}\n";
	fout<<"\t}\n";
	fout<<"}\n";
}

void generateMainCode()
{
	fout<<"void main()\n";
	fout<<"{\n";
	/*
	for(hash_map<string,int>::iterator pti=tsymTable.begin();pti!=tsymTable.end();pti++)
	{
		if(pti->first!="#")
		fout<<"\tconst int "<<pti->first<<"="<<pti->second<<";\n";//定义各变量，变量名用
	}*/
	fout<<"\tpair<int,int> tp;\n";
	for(hash_map<string,int>::iterator pti=tsymTable.begin();pti!=tsymTable.end();pti++)
	{
		if(pti->first!="#")
		{
			fout<<"\ttp.first="<<pti->second<<";\n";
			fout<<"\ttp.second="<<terminSet[pti->second]<<";\n";
			fout<<"\tsignalTable.insert(tp);\n";
		}
		else
		{
			fout<<"\ttp.first=40001;\n";
			fout<<"\ttp.second="<<terminSet[pti->second]<<";\n";
			fout<<"\tsignalTable.insert(tp);\n";
		}
	}
	for(hash_map<int,int>::iterator pti=nonterminSet.begin();pti!=nonterminSet.end();pti++)
	{
		fout<<"\ttp.first="<<pti->first<<";\n";
		fout<<"\ttp.second="<<pti->second<<";\n";
		fout<<"\tsignalTable.insert(tp);\n";
	}
	//以上完成signalTable的初始化段代码.
	fout<<"\tstring filename;\n";
	fout<<"\tcout<<\"Please input the file name:\"<<endl;\n";
	fout<<"\tcin>>filename;\n";
	fout<<"\tfin.open(filename.c_str());\n";
	fout<<"\tif(fin.fail())\n";
	fout<<"\t{\n";
	fout<<"\t\tcout<<\"Cannot open the file \"<<filename<<endl;\n";
	fout<<"\t\treturn;\n";
	fout<<"\t}\n";
	fout<<"\tparse();\n";
	fout<<"}\n";
}
void generateSVCode()
{
	fout<<"void getvalue(int symbol,SV & val)\n";
	fout<<"{\n";
	fout<<"\tswitch(symbol)\n";
	fout<<"\t{\n";
	for(hash_map<int,int>::iterator pi=terminSet.begin();pi!=terminSet.end();pi++)
	{
		if(symclaTable.count(pi->first))
		fout<<"\tcase "<<pi->first<<":val."<<symclaTable[pi->first]<<"="<<pi->first
			<<";break;\n";
	}
	fout<<"\t}\n";
	fout<<"}\n";


}

void generateConstCode()
{
	fout<<"using namespace std;\n";
	fout<<"extern int analysis(char *yytext,int n);\n";
	fout<<"struct Sym\n";
	fout<<"{\n";
	fout<<"\tint symbol;\n";
	fout<<"\tint state;\n";
	fout<<"};\n";
	fout<<"hash_map<int,int> signalTable;\n";
	fout<<"int producerN["<<producerSet.size()<<"]={";
	for(int i=0;i<producerSet.size();i++)
	{
		fout<<producerSet[i].right.size();
		if(i!=producerSet.size()-1)
			fout<<",";
	}
	fout<<"};\n";
	fout<<"int pLeftSection["<<producerSet.size()<<"]={";
	for(i=0;i<producerSet.size();i++)
	{
		fout<<producerSet[i].left;
		if(i!=producerSet.size()-1)
			fout<<",";
	}
	fout<<"};\n";
	fout<<"ifstream fin;\n";
}
void generateHead()
{
	fout<<"#include<iostream>\n";
	fout<<"#include<hash_map>\n";
	fout<<"#include<stack>\n";
	fout<<"#include<fstream>\n";
	fout<<"#include<string>\n";
	fout<<"#define E 40000\n";
	fout<<"#define ACCEPT 0\n";
	fout<<"#define SOURCE_END 40001\n";	
}

int readInputFile()
{
	generateHead();
	char c=fin.get();
	if(c!='%') return TERMINATE;//要求输入文件第一个字符必须为%
	int state=specSymParse();
	while(!fin.eof()&&c!=-1)
	{
		switch(state)
		{
		case SEGMENT_DELIM:
			{
				NO++;
				if(NO==2)
				{
					state=SEGMENT_REG;//进入规则段
					continue;//跳过后面的查找%的语句，直接回到switch
				}
				if(NO==3)
				{
					state=SELF_DEF;
					continue;
				}
				break;
			}
		case DEF_SEG_BEGIN://output 1
			{
				//进入%{处理，完全输出到文件
				while(1)
				{
					c=fin.get();
					if(c=='%')
					{
						state=specSymParse();
						if(state==DEF_SEG_END) break;//如果到达底部%}，则退出循环。
						else if(state!=NOMATCH)
						{
							return TERMINATE;//如果既不等于DEF_SEG_END也不等于NOMATCH，则报错。
						}
					}
					fout.put(c);///////********output to file
				}
				break;
			}
		case TOKEN:case TYPE:
			{
				string line;
				getline(fin,line);

				int lpos=0;
				int pos=0;
				while(line[pos]!='<'&&pos<line.size()) pos++;
				if(pos==line.size())
				{
					cout<<"%type formation error!"<<endl;
					return 0;
				}
				
				pos++;//往后移一个字符
				lpos=pos;
				while(line[pos]!='>'&&pos<line.size()) pos++;
				if(pos==line.size())
				{
					cout<<"%type or token formation error!"<<endl;
					return 0;
				}
				string valstr=line.substr(lpos,pos-lpos);//取得值类型

				char ntbuf[20]={0};
				int i=0;
				while(1)
				{
					pos++;
					if(pos>line.size()) break;
					if(line[pos]==' '||pos==line.size())
					{
						if(ntbuf[0]=='\0') continue;
						ntbuf[i]='\0';
						string ntstr(ntbuf);

						pair<string,int> tp;
						tp.first=ntstr;
						if(state==TYPE)
						{
							tp.second=NONTERMINS+ntsymTable.size();
						}
						else
						{
							tp.second=TERMINS+tsymTable.size();
						}
						pair<int,int> tp2;
						tp2.first=tp.second;
						tp2.second=terminSet.size()+nonterminSet.size();

						if(state==TYPE)
						{
							ntsymTable.insert(tp);
							nonterminSet.insert(tp2);
						}
						else
						{
							tsymTable.insert(tp);
							terminSet.insert(tp2);
						}

						pair<int,string> stp;
						stp.first=tp.second;
						stp.second=valstr;
						symclaTable.insert(stp);
						
						i=0;
						ntbuf[0]='\0';
					}
					else
					{
						ntbuf[i]=line[pos];