createt.h

超好用的语法语义分析器,希望对诸位有用,简单实用!

#ifndef HEADER_CREATET
#define HEADER_CREATET

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include "LLTable.h"

typedef vector<vector<char> > Vec;

class First_Follow
{
	vector<string> strToken;//文法表达式
	vector<string> vt;//非终结符集合
	vector<string> temp;//中间变量
	Vec FIRST;//FIRST集合
	Vec FOLLOW;//FOLLOW集合
public:
	void Init();//初始化
	void first();//求FIRST集合
	void follow();//求FOLLOW集合
	void createTable(Table lltable);//创建表
};

void First_Follow::Init()
{
	ifstream in("a.txt");
	for( string str; getline(in,str); )
		strToken.push_back(str);//从文件中读出文法存到strToken中
	for( int i = 0; i < strToken.size(); i++)
	{
		int j = 0;
		string s = "";//求非终结符
		while( strToken[i][j] != '-' )//"->"以前为非终结符
		{
			s += strToken[i][j];
			j++;
		}
		vt.push_back(s);//存到vt中
	}
	FIRST.resize(vt.size());//设置大小
	FOLLOW.resize(vt.size());
	FOLLOW[0].push_back('#');//置#于开始符号的FOLLOW集合中
	temp = vt;
}

void First_Follow::first()
{
	int i;
	while( !temp.empty() )
	{
		for( i = 0; i < vt.size(); i++)
		{
			if( temp.back() == vt[i] )
				break;
		}
		if( FIRST[i].size() == 0)//当前FIRST集合为空
		{
			int flag = 0;
			for( int j = vt[i].size() + 2; j < strToken[i].size(); j++)
			{
				if( flag == 0 && ((strToken[i][j] > 'a' && strToken[i][j] < 'z') || 
					strToken[i][j] == '+' || strToken[i][j] == '*' || 
					strToken[i][j] == '(' || strToken[i][j] == ')' ||
					strToken[i][j] == '$'))//是终结符号，则FIRST(X) = {X}
				{
					FIRST[i].push_back(strToken[i][j]);
				}
				else if( flag == 0 )//为非终结符号
				{
					string s = "";//存非终结符
					s += strToken[i][j];
					if( strToken[i][j+1] == '\'')
						s += '\'';
					for( int k = 0; k < vt.size(); k++)
					{
						if( vt[k] == s )//找到该非终结符的定义
						{
							if( FIRST[k].size() != 0)//FIRST[k]不为空，把FIRST[k]加到FIRST[i]中
							{                        
								for( int m = 0; m < FIRST[k].size(); m++ )
								{
									int flag1 = 0;
									for( int n = 0; n < FIRST[i].size(); n++)
									{
										if( FIRST[i][n] == FIRST[k][m])//判断要加入的元素是否已经存在
										{
											flag1 = 1;//存在标志为置1
											break;
										}
									}
									if( flag1 == 0 || FIRST[k][m] != '$')//不存在,且不为'$'
										FIRST[i].push_back(FIRST[k][m]);
								}
							}
							else//FIRST[k]为空
							{
								temp.push_back(s);//s非终结符加到向量temp尾部
    							first();
								for( int m = 0; m < FIRST[k].size(); m++ )//把FIRST[k]加到FIRST[i]中
								{
									int flag1 = 0;
									for( int n = 0; n < FIRST[i].size(); n++)
									{
										if( FIRST[i][n] == FIRST[k][m])
										{
											flag1 = 1;
											break;
										}
									}
									if( flag1 == 0 || FIRST[k][m] != '$')
										FIRST[i].push_back(FIRST[k][m]);
								}
							}
							break;
						}
					}
				}
				if( strToken[i][j] == '|')//出现'|'则对应下一个表达式，flag恢复初始值
					flag = 0;
				else
					flag = 1;
			}
		}
		else
			temp.pop_back();//求完FIRST(X)则删除X
	}
}

void First_Follow::follow()
{
	temp = vt;
	int i;
	for( int i2 = 0; i2 < temp.size(); i2++)
	{
		for( i = 0; i < vt.size(); i++)
		{
			if( temp[i2] == vt[i] )
				break;
		}
		for( int j = 0; j < strToken.size(); j++)
		{
			int k;
			int flag = 0;
			for( k = 3; k < strToken[j].length(); k++)//从文法中找非终结符vt[i][0]
			{
				if( strToken[j][k] == vt[i][0] )
				{
					if( vt[i].size() == 1 )//为X形式
					{
						if(	strToken[j].length() > k + 1 && strToken[j][k+1] == '\'' )
							continue;//X与X'不相等
						flag = 1;  //匹配后置1
						k++;//指向下一个非终结符
						break;
					}
					if( vt[i].size() == 2 )//为X'形式
					{
						if( strToken[j].length() > k + 1 && strToken[j][k+1] == '\'')
						{
							k += 2;  //指向下一个非终结符
							flag = 1;
							break;
						}
					}
				}
			}
			if(flag == 1)//已匹配
			{
				string s = "";  //A后面的字串
				while( k < strToken[j].length() && strToken[j][k] != '|')
				{
					s += strToken[j][k];
					k++;
				}
				if( s.length() == 0 )//s为空，即为B->@A的形式
				{
					if(FOLLOW[j].size() == 0)
					{
						temp.push_back(vt[i]);
						break;
					}
					for( int m = 0; m < FOLLOW[j].size(); m++ )//FOLLOW[j]加入FOLLOW[i]中
					{
						int flag1 = 0;
						for( int n = 0; n < FOLLOW[i].size(); n++)
						{
							if( FOLLOW[i][n] == FOLLOW[j][m])
							{
								flag1 = 1;
								break;
							}
						}
						if( flag1 == 0 )
						{
							FOLLOW[i].push_back(FOLLOW[j][m]);
						}
					}
				}
				else
				{
					if( s.length() == 1 && 
						((s[0] > 'a' && s[0] < 'z') || 
						s[0] == '+' || s[0] == '*' || 
						s[0] == '(' || s[0] == ')' ||
						s[0] == '$'))//s不为空，但是终结符，FIRST[s]加入FOLLOW[i]中
					{
						FOLLOW[i].push_back(s[0]);
						continue;
					}
					for( int i1 = 0; i1 < vt.size(); i1++)//s为非终结符
					{
						if( vt[i1] == s )
						{
							int flag2 = 0;
							for( int m = 0; m < FIRST[i1].size(); m++ )//将非'$'FIRST[s]加入到FOLLOW[i]中
							{
								int flag1 = 0;
								if( FIRST[i1][m] == '$' )
									flag2 = 1;
								for( int n = 0; n < FOLLOW[i].size(); n++)
								{
									if( FOLLOW[i][n] == FIRST[i1][m])
									{
										flag1 = 1;
										break;
									}
								}
								if( flag1 == 0 && FIRST[i1][m] != '$')
									FOLLOW[i].push_back(FIRST[i1][m]);
							}
							if( flag2 == 1)//如果'$'属于FIRST[s],则将FOLLOW[j]加入到FOLLOW[i]中
							{
								if(FOLLOW[j].size() == 0)
								{
									temp.push_back(vt[i]);
								    break;
								}
								for( int m = 0; m < FOLLOW[j].size(); m++ )
								{
									int flag1 = 0;
									for( int n = 0; n < FOLLOW[i].size(); n++)
									{
										if( FOLLOW[i][n] == FOLLOW[j][m])
										{
											flag1 = 1;
											break;
										}
									}
									if( flag1 == 0 )
										FOLLOW[i].push_back(FOLLOW[j][m]);
								}
							}
							break;
						}
					}
				}
			}
		}
	}
}

void First_Follow::createTable(Table lltable)
{
	Init();
	first();  
	follow();
	for(int i = 0; i < FIRST.size(); i++)
	{
		int k  = 3;
		vector<string> t;
		string s = "";
		string str = "";
		for( k = 2; k < strToken[i].length(); k++)
		{
			if( strToken[i][k] == '>')
				break;
		}
		k++;
		for( ; k < strToken[i].length(); k++)//将文法分成更小的表达式
		{
			if( strToken[i][k] == '|')
			{
				t.push_back(s);
				s = "";
				continue;
			}
			s += strToken[i][k];
		}
		t.push_back(s);
		for(int j = 0; j < FIRST[i].size(); j++)
		{
			str = vt[i] + "->";
			int flag = 0;
			for( int m = 0; m < t.size(); m++)//查找表达式
			{
				if( FIRST[i][j] == t[m][0] )
				{
					str += t[m];
					flag = 1;
					break;
				}
			}
			if( flag == 0 )
			{
				str += t[0];
			}
			if( FIRST[i][j] == '$' )
			{
				for( int l = 0; l < FOLLOW[i].size(); l++)
				{//A->@ 加到M[A,a]中 ，a属于FIRST(@)
					lltable.Insert_Head(str,vt[i],FOLLOW[i][l]);
				}
			}
			if( FIRST[i][j] != '$')//'$'属于FIRST(@),b属于FOLLOW(A),把A->@加到M[A,b]中
				lltable.Insert_Head(str,vt[i],FIRST[i][j]);
		}
	}
}

#endif