slrgrammar.cpp

编译原理代码 包括正规式匹配LR文法分析语义分析

#include <iostream.h>
#include <stdio.h>
#include <string.h>
#include <conio.h>
#include <stdlib.h>
#include <ctype.h>

/////////////////////////////////////////////////

//定义结点类
template <class Elem> class link
{
	public:
		link* next;
		Elem element;
		int sign;
		link(const Elem& elementValue,link* nextValue = NULL)
		{
			element = elementValue;
			next = nextValue;
			sign = -1;
		}
		link(link* nextValue = NUll)
		{
			next = nextValue;
			sign = -1;
		}
};

/////////////////////////////////////////////////

//定义堆栈类
template <class Elem> class stack
{
	private:
		link<Elem> *top;
		int size;
	public:
		stack(int sz = DefaultSize)
		{
			top = NULL;
			size = 0;
		}
		~stack(){	clear();	}
		void clear()
		{
			while(top!=NULL)
			{
				link<Elem>* temp = top;
				top = top->next;
				size = 0;
				delete temp;
			}
		}
		//入栈函数
		bool push(const Elem& item)
		{
			top = new link<Elem>(item,top);
			size++;
			return true;
		}
		//出栈函数
		Elem pop()
		{
			Elem item;
			if (size == 0)
				return false;
			item = top->element;
			link<Elem>* temp = top->next;
			delete top;
			top = temp;
			size--;
			return item;
		}
		//获取栈顶元素的值
		Elem GetTop() const
		{
			Elem item; 
			if(size == 0)
				return false;
			item = top->element;
			return item;
		}
		//获取堆栈的深度
		int length() const
		{	return size;	}
		//判断栈是否为空
		bool IsEmpty() const
		{	return top == NULL;	}
		//获取标志位
		int GetSign() const
		{	return top->sign;  }
		//设置标志位
		void SetSign(int s)
		{	top->sign = s;	}
};

//////////////////////////////////

//定义产生式的数据结构
class Production
{
public:
	char From;
	char To[20];
};

//////////////////////////////////

//定义输入文法数据结构
class Grammar
{
private:
	char startState;
	Production pro[30];
	int NumOfGra;
public:
	Grammar()
	{
		NumOfGra = 0;
	}
	~Grammar()
	{
	}
	//定义重载运算符 == 
	bool operator == (Grammar g)
	{
		if (g.NumOfGra == NumOfGra)
		{
			bool flag=true;
			Production p;
			for (int i=0;i<NumOfGra;i++)
			{
				p = g.GetProduction(i);
				if (!IsIn(p))
				{
					flag = false;
					break;
				}
			}
			return flag;
		}
		else
			return false;
	}
	//获取ch 在数组中的位置
	int GetPos(char * str,char ch)
	{
		int len = strlen(str);
		for (int i=0;i<len;i++)
		{
			if (ch == str[i])
				break;
		}
		return i;
	}
	//获取一个产生式的位置
	int GetPos(Production p)
	{
		for (int i=0;i<NumOfGra;i++)
		{
			if ((p.From == pro[i].From)&&(strcmp(p.To,pro[i].To) == 0))
				break;
		}
		return i;
	}
	//获取与ch相同文法左布的产生式
	int GetProDuctionOF(char ch)
	{
		for (int i=0;i<NumOfGra;i++)
		{
			if (ch == pro[i].From)
			{
				break;
			}
		}
		return i;
	}
	//插入一条文法
	bool Insert(char fr,char * temp)
	{
		NumOfGra++;
		pro[NumOfGra-1].From = fr;
		strcpy(pro[NumOfGra-1].To,temp);
		return true;
	}
	//在pos处插入一条文法
	bool Insert(int pos,char fr,char *temp)
	{
		for(int i=NumOfGra;i>pos;i--)
		{
			pro[i] = pro[i-1];
		}
		pro[pos].From = fr;
		strcpy(pro[pos].To,temp);
		NumOfGra++;
		return true;
	}
	//设置和获取开始状态
	bool SetStartState(char ch)
	{
		startState = ch;
		return true;
	}
	//获取文法开始状态
	char GetstartState()
	{
		return startState;
	}
	//获取开始的产生式
	Production GetStartProduction()
	{
		for (int i=0;i<NumOfGra;i++)
		{
			if ((pro[i].From == startState)&&(GetPos(pro[i].To,'.') == 0))
			{
				break;
			}
		}
		return pro[i];
	}
	//文法是都为空
	bool IsEmpty()
	{
		if (NumOfGra == 0)
			return true;
		else
			return false;
	}
	//删除一条文法
	bool Delete(char fr,char * temp)
	{
		for (int i=0;i<NumOfGra;i++)
		{
			if ((pro[i].From == fr)&&(strcmp(pro[i].To,temp)==0))
			{
				pro[i] = pro[NumOfGra-1];
				NumOfGra--;
			}
		}
		return true;
	}
	//删除一个文法
	bool Delete(int pos)
	{
		pro[pos] = pro[NumOfGra-1];
		NumOfGra--;
		return true;
	}
	//获取文法的条数
	int GetNumOfGra()
	{
		return NumOfGra;
	}
	//获取一条文法
	Production GetProduction(int pos)
	{
		return pro[pos];
	}
	//判断产生式是否已经在文法中
	bool IsIn(Production p)
	{
		for (int i=0;i<NumOfGra;i++)
		{
			if ((pro[i].From == p.From)&&(strcmp(pro[i].To,p.To)==0))
			{
				return true;
			}
		}
		return false;
	}
};

/////////////////////////////////////////////////

class TableElem
{
public:
	char ch;
	int state;
};

/////////////////////////////////////////////////

//定义项目集的类
class Item
{
private:
	int NumOfItems;
	Production StartProduction;
	Grammar gr[20];
public:
	Item()
	{
		NumOfItems = 0;
	}
	~Item()
	{
	}
	//设置初始状态的产生式
	void SetStartProduction(Production p)
	{
		StartProduction = p;
	}
	//获取初始状态的产生式
	Production GetStartProduction()
	{
		return StartProduction;
	}
	//获取项目集的数目
	int GetNumOfItems()
	{
		return NumOfItems;
	}
	//获取一个项目集
	Grammar GetItem(int pos)
	{
		return gr[pos];
	}
	//插入一个项目集
	bool Insert(Grammar g)
	{
		gr[NumOfItems] = g;
		NumOfItems++;
		return true;
	}
	//在pos处插入一个项目集
	bool Insert(int pos,Grammar g)
	{
		for(int i=NumOfItems;i>pos;i--)
		{
			gr[i] = gr[i-1];
		}
		gr[pos] = g;
		NumOfItems++;
		return true;
	}
	//删除一个项目集
	bool Delete(Grammar g)
	{
		for (int i=0;i<NumOfItems;i++)
		{
			if (g == gr[i])
			{
				gr[i] = gr[NumOfItems-1];
				NumOfItems--;
			}
		}
		return true;
	}
	//删除一个项目集
	bool Delete(int pos)
	{
		gr[pos] = gr[NumOfItems-1];
		NumOfItems--;
		return true;
	}
	//判断项目集是否已经在项目集族中
	bool IsIn(Grammar g)
	{
		for (int i=0;i<NumOfItems;i++)
		{
			if (gr[i] == g)
			{
				return true;
			}
		}
		return false;
	}
	//获取开始的项目集
	Grammar GetStartItem()
	{
		return gr[0];
	}
	//获取项目集的位置
	int GetPos(Grammar g)
	{
		for (int i=0;i<NumOfItems;i++)
		{
			if (gr[i] == g)
			{
				break;
			}
		}
		return i;
	}
};

/////////////////////////////////////////////////

//文法分析表的数据结构
class ParseTable
{
private:
	int row;
	int col_n;	
	int col_t;
	char InputSymbol[20];
	char NonTerminal[20];
	TableElem **action;
	int ** goTo;
public:
	//构造函数
	ParseTable(char * in,char * Non,int StateCount)
	{
		int i,j;
		row = StateCount;
		col_t = strlen(in);
		col_n = strlen(Non);
		strcpy(InputSymbol,in);
		strcpy(NonTerminal,Non);
		//action
		action = (TableElem **)(new TableElem * [col_t]); 
		for (i=0; i<row; i++)
		{
			action[i] = new TableElem[col_t];
		}
		for (i=0;i<row;i++)
		{
			for (j=0;j<col_t;j++)
			{
				action[i][j].ch= '\0';
				action[i][j].state = -1;
			}
		}
		//goto
		goTo = (int **)(new int *[col_n]);
		for (i=0; i<row; i++)
		{
			goTo[i] = new int[col_n];
		}
		for (i=0;i<row;i++)
		{
			for (j=0;j<col_n;j++)
			{
				goTo[i][j] = -1;
			}
		}
	}
	~ParseTable()
	{
		delete []action;
		delete []goTo;
	}
	//添加一个项
	bool Add(int itemnum,char ch,char flag,int statenum)
	{
		if (flag == 'N') //插入goto 部分
		{
			for (int i=0;i<col_n;i++)
			{
				if (NonTerminal[i] == ch)
				{
					goTo[itemnum][i] = statenum;
					return true;
				}
			}
		}
		else // 插入action部分
		{
			for (int i=0;i<col_t;i++)
			{
				if (InputSymbol[i] == ch)
				{
					if (ch == '$'&&statenum==0)
					{
						if (IsEmpty(itemnum,ch))
						{
							action[itemnum][i].ch = 'A';
							action[itemnum][i].state = 0;
							return true;
						}
						else
						{
							return false;
						}
					}
					else
					{
						if (IsEmpty(itemnum,ch))
						{
							action[itemnum][i].ch = flag;
							action[itemnum][i].state = statenum;
							return true;
						}
						else
						{
							return false;
						}
					}
				}
			}
		}
		return true;
	}
	//获取一个表达式Action
	TableElem GetAction(int itemnum,char ch)
	{
		for (int i=0;i<col_t;i++)
		{
			if (InputSymbol[i] == ch)
			{				
				break;
			}
		}	
		return action[itemnum][i];
	}
	//获取一个表达式goto
	int GetGoto(int itemnum,char ch)
	{
		if (isupper(ch))
		{
			for (int i=0;i<col_n;i++)
			{
				if (NonTerminal[i] == ch)
				{
					break;
				}
			}
			return goTo[itemnum][i];
		}
		else
			return -1;
	}
	//看表中是否有产生式
	bool IsEmpty(int itemnum,char ch)
	{
		if (isupper(ch))
		{
			for (int i=0;i<col_n;i++)
			{
				if (NonTerminal[i] == ch)
				{
					if (goTo[itemnum][i] == -1)
						return true;
					else
						return false;
				}
			}
			return false;
		}
		else
		{
			for (int i=0;i<col_t;i++)
			{
				if (InputSymbol[i] == ch)
				{
					if (action[itemnum][i].ch == '\0')
						return true;
					else
						return false;
				}
			}	
			return false;
		}
	}
	//输出分析表
	void OutPut()
	{
		int i, j;
		cout << "\n SLR文法的分析表如下：" << endl;
		cout<<"\n ";//━━━┯
		for (i=0;i<col_t;i++)