yacc.cpp

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

						i++;
					}
				}
				break;
				//此部分处理完之后，完成了表symclaTable和部分ntsymTable
			}
		case UNION://output 2
			{
				c=fin.get();
				while(c!='{'&&c!=-1) c=fin.get();
				if(c==-1) return TERMINATE;	
				hout<<"#ifndef YYVAL_H\n";//输出到头文件yyval_h.h
				hout<<"#define YYVAL_H\n";
				fout<<"union SV\n";
				hout<<"union SV\n";
				fout<<"{\n";
				hout<<"{\n";
				while((c=fin.get())!='}') {fout.put(c);hout.put(c);}
				fout<<"};\n";//此段没有做任何保存，即是说如果出现错误也不能校错。
				hout<<"};\n";
				fout<<"SV u[10];\n";//在此声明数目为10的联合数组，以便后面语义动作时调用。
				fout<<"SV yyval;\n";//在此声明全局变量yyval，用于返回lex符号的语义值
				hout<<"#endif";
				break;
			}
		case LEFT:case RIGHT:
			{
				string line;
				getline(fin,line);
				int lpos=0;
				int pos=0;
				static int priority=0;
				priority++;
				while(pos!=line.find_last_of('\''))
				{
					lpos=line.find_first_of('\'',lpos);
					pos=line.find_first_of('\'',lpos+1);
					string t=line.substr(lpos+1,pos-lpos-1);
					lpos=pos+1;	
					//存储操作符。
					pair<string,int> tp;
					tp.first=t;
					tp.second=TERMINS+tsymTable.size();
					tsymTable.insert(tp);//把操作符也放到终结符表中。
				    
					pair<int,int> tpp;
					tpp.first=tp.second;
					tpp.second=terminSet.size()+nonterminSet.size();
					terminSet.insert(tpp);
					if(state==LEFT)//加入左右结合表
					{
						leftTable.insert(tp.second);
					}
					else
					{
						rightTable.insert(tp.second);
					}

					pair<int,int> ptp;
					ptp.first=tp.second;
					ptp.second=priority;
					precedenceTable.insert(ptp);//把操作符放入优先级表中。
				}
				break;
			}
		case SEGMENT_REG:
			{
				//此处为规则段的扫描和处理输出。
				//第一步读产生式的集合，完成各种表的数据。			
				//修正producerPreTable		
				producerPreTable.push_back(0);//保证索引值访问不会出错。
				if(!readReg())
				{
					cout<<"read reg segment error!\n";
					return 0;
				}
				//修正ProducerSet;
				producerSet[0].left=NONTERMINS-1;//表示是拓展文法开始符号
				producerSet[0].right.push_back(producerSet[1].left);
				//修正tsymTable
				pair<string,int> tp1;
				string s("#");
				tp1.first=s;
				tp1.second=NONTERMINS-1;
				tsymTable.insert(tp1);
				//修正terminSet
				pair<int,int> tp2;
				tp2.first=tp1.second;
				tp2.second=terminSet.size()+nonterminSet.size();
				terminSet.insert(tp2);
				//第二步完成动作表的生成。
				genhpSet();//首先完成hpSet的生成
				if(!produce())
				{
					cout<<"produce action table error!"<<endl;
					return 0;
				}

				//输出文件定义的一些常量
				generateConstCode();
				//第三步输出查表函数及读Token的函数
				generateTableCode();
				//第四步输出执行语义动作的函数
				generateSemanticActionCode();
				//第五步输出分析函数,首先产生void getvalue()函数，给终结符赋默认初值
				generateSVCode();
				generateParseCode();
				//第六步输出主函数，应该留到最后输出。
				//generateMainCode();
				break;
			}
		case SELF_DEF://输出用户自定义子例程
			{
				c=fin.get();
				while(c!=-1)
				{
					fout.put(c);////*******output to file
					c=fin.get();
					
				}
				fout.put('\n');
				continue;//跳回while，判断结束。
			}
		}
		c=fin.get();
		while(c!='%'&&c!=-1) c=fin.get();
		if(c=='%')
			state=specSymParse();
	}
}
int specSymParse()
{
	char nextc=fin.get();
	switch(nextc)
	{
	case '%'://进入段分隔符
		{
			return SEGMENT_DELIM;
		}
	case '{':
		{
			return DEF_SEG_BEGIN;
		}
	case '}':
		{
			return DEF_SEG_END;
		}
	case 't':case 'u':case 'l':case 'r'://%token	//%union//%left
		{
			char buf[10];
			int pos=1;
			buf[0]=nextc;
			nextc=fin.get();
			while(nextc!=' '&&nextc!='\n'&&nextc!='\t')
			{
				buf[pos]=nextc;
				nextc=fin.get();
				pos++;
				if(pos==5) break;
			}
			buf[pos]='\0';
			string bbuf(buf);
			string t1("token");
			string t2("type");
			string t3("union");
			string t4("left");
			string t5("right");
			if(bbuf==t1) return TOKEN;
			if(bbuf==t2) return TYPE;
			if(bbuf==t3) return UNION;
			if(bbuf==t4) return LEFT;
			if(bbuf==t5) return RIGHT;
			else return TERMINATE;//错误，程序中止
		}

	default:
		fin.unget();
		return NOMATCH;
	}
}

bool readReg()
{
	//规则段的扫描程序
	char c=fin.get();
	while(c==' '||c=='\n'||c=='\r'||c=='\t') c=fin.get();
	int state=-1;
	char buf[256];
	int pos=0;
	while(1)
	{
		if(c==-1) break;
		if(c=='%')
		{
			state=specSymParse();
			if(state==SEGMENT_DELIM)
			{
				fin.unget();
				fin.unget();//连退两个字符，因为在readInputFile()里面有对%%进行处理的程序
				break;
			}
			if(state==TERMINATE) 
			{
				cout<<"Regulation Segment ERROR!"<<endl;
				return false;
			}	
			if(state==NOMATCH) fin.unget();//将%也退回，留作下面程序处理
			else
			{
				cout<<"Regulation Segment ERROR2"<<endl;
				return false;//出错，直接返回.
			}
		}


		while(c==' '||c=='\n'||c=='\r'||c=='\t') c=fin.get();//抛掉空格
		fin.unget();//退回，交给函数readAproducer()处理
		if(!readAproducer())
		{
			cout<<"producer error!see above!"<<endl;
			return false;
		}
		c=fin.get();
		while(c==' '||c=='\n'||c=='\r'||c=='\t') c=fin.get();
	}

}
bool readAproducer()//未抛掉前后的空格
{
	char c=fin.get();
	char buf[256];
	int pos=0;
	while(c!=' '&&c!='\n'&&c!='\t'&&c!='\r'&&c!=-1)
	{
		buf[pos]=c;
		pos++;
		c=fin.get();
	}
	fin.unget();
	buf[pos]='\0';
	string temp(buf);
	buf[0]='\0';//清空buf。
	pos=0;
	if(tsymTable.count(temp))
	{
		cout<<"NonTerminatedSym define error!"<<endl;
		return false;
	}
	if(!ntsymTable.count(temp))
	{
		pair<string,int> tp;
		tp.first=temp;
		tp.second=NONTERMINS+ntsymTable.size();
		ntsymTable.insert(tp);
	
		pair<int,int> tpp;
		tpp.first=tp.second;
		tpp.second=terminSet.size()+nonterminSet.size();
		nonterminSet.insert(tpp);//往非终结符表内加入内容。存储的是非终结符对应到action表的表头
	}
	c=fin.get();
	while(c==' '||c=='\n'||c=='\r'||c=='\t') c=fin.get();
	if(c!=':')
	{
		cout<<"Producer formation Error!"<<endl;
		return false;
	}
	while(1)
	{
		Producer ap;
		ap.left=ntsymTable[temp];//新建一个产生式，先保存左部的值
		int priority=0;//存储产生式的优先级，此时采取的方法是，产生式的优先级同右部符号最右的操作
	               //符优先级相同
		while(1)
		{
		//首先抛掉空格
			c=fin.get();
			while(c==' '||c=='\n'||c=='\r'||c=='\t') c=fin.get();
			if(c==';'||c=='{'||c=='|') break;//产生式结束标记或者是动作开始标记
			//读产生式的右部
			if(c=='\'')//如果遇到'，则进入操作符的读入程序
			{
				c=fin.get();
				while(c!='\'')
				{
					buf[pos]=c;
					pos++;
					c=fin.get();
				}
				buf[pos]='\0';
				string temp3(buf);
				pos=0;
				buf[0]='\0';//clear buf
				if(!tsymTable.count(temp3))
				{
					pair<string,int> tp;
					tp.first=temp3;
					tp.second=TERMINS+tsymTable.size();

					tsymTable.insert(tp);//把操作符也放到终结符表中。
				
					pair<int,int> tpp;
					tpp.first=tp.second;
					tpp.second=terminSet.size()+nonterminSet.size();
					terminSet.insert(tpp);
					//ap.right.push_back(tp.second);

					pair<int,int> ptp;
					ptp.first=tp.second;
					ptp.second=0;
					precedenceTable.insert(ptp);
				}
				ap.right.push_back(tsymTable[temp3]);
				priority=precedenceTable[tsymTable[temp3]];
				continue;
			}
			if(c=='\\')//用\e表示空
			{
				c=fin.get();
				if(c=='e')
				{
					break;
				}
				else
				{
					cout<<"epslong error!"<<endl;
					return false;
				}
			}
			else
			{
				while(c!=' '&&c!=-1&&c!='\n'&&c!='\t'&&c!='\r')
				{
					buf[pos]=c;
					pos++;
					c=fin.get();
				}
				buf[pos]='\0';
				string temp1(buf);
				pos=0;
				buf[0]='\0';//clear buf
				if(tsymTable.count(temp1))
				{
					ap.right.push_back(tsymTable[temp1]);
				}
				else
				{
					if(!ntsymTable.count(temp1))
					{
						pair<string,int> tp;
						tp.first=temp1;
						tp.second=NONTERMINS+ntsymTable.size();
						ntsymTable.insert(tp);
	
						pair<int,int> tpp;
						tpp.first=tp.second;
						tpp.second=terminSet.size()+nonterminSet.size();
						nonterminSet.insert(tpp);

					}
					ap.right.push_back(ntsymTable[temp1]);
				}
			}
		}
		char action[1000];//存储语义动作
		action[0]='\0';
		if(c=='{')
		{
			char change[4]={'u','[','0',']'};
			int pi=0;
			c=fin.get();
			while(c!='}')
			{
				if(c=='$')
				{
					c=fin.get();
					if(c=='$')//表示是产生式左部的语义值符号
					{
						//插入串"u[0]"
						for(int i=0;i<4;i++)
							action[pi+i]=change[i];
						pi+=4;
						action[pi]='.';//加上语义值的具体类型
						pi++;
						string s=symclaTable[ap.left];
						for(i=0;i<s.size();i++)
							action[pi+i]=s[i];
						pi+=i;
					}
					else 
					if(c>='1'&&c<='9')
					{
						int num=0;
						action[pi++]='u';
						action[pi++]='[';
						while(c>='0'&&c<='9')//支持更多的右部非终结符
						{
							action[pi++]=c;
							num=num*10+c-'0';
							c=fin.get();
						}
						fin.unget();
						action[pi++]=']';
						/*
						for(int i=0;i<4;i++)
						{
							action[pi+i]=change[i];
						}*/
						//action[pi+2]=c;//只需修改此处的值即可。
						//pi+=4;
						action[pi++]='.';//加上语义值的具体类型
						string s=symclaTable[ap.right[num-1]];
						for(int i=0;i<s.size();i++)
							action[pi+i]=s[i];
						pi+=i;
					}
					else
					{
						cout<<"Action definition error!"<<endl;
						return false;
					}
				}
				else
				{
					action[pi]=c;
					pi++;	
				}
				c=fin.get();
			}
			action[pi]='\0';
			c=fin.get();
			while(c==' '||c=='\n'||c=='\r'||c=='\t') c=fin.get();
		}
		if(c==';'||c=='|')
		{
			//保存语义动作。
			string oneaction(action);
			produceActionTable.push_back(oneaction);
			producerSet.push_back(ap);
			producerPreTable.push_back(priority);
			if(c==';')
				break;
		}
		else
		{
			cout<<"Producer formation error,there should be a ';' after each producer!"<<endl;
			return false;
		}
	}
	return true;
}