grammar.cpp

编译原理实验

#include <iostream>
#include <vector>
#include <string>
#include <stdlib.h>
#include <stack>
#include "grammar.h"

using namespace std;

void grammar::ReadVSet()
{
	string input;
	Variable temp;

	cout << "Please Input Variables File: " << endl;
	//cin >> input;
	input = "d:\\data/v.txt";
	FILE * vfile = fopen(input.c_str(),"r");

	char ch;
	while((ch=fgetc(vfile))!=EOF)
	{
		if(ch != '\n')
		{
			temp.v = ch;
			VSet.push_back(temp);
		}
	}
	fclose(vfile);
}

void grammar::ReadTSet()
{
	string input;
	Terminal temp;
	string num;

	cout << "Please Input Ternimals File: " << endl;
	//cin >> input;
	input = "d:\\data/t.txt";
	FILE * tfile = fopen(input.c_str(),"r");

	char ch;
	while((ch=fgetc(tfile))!=EOF)
	{
		temp.id = 0;
		temp.t.clear();
		while(ch!='\t')
		{
			temp.t += ch;
			ch = fgetc(tfile);
		}
		while(ch!='\n' && ch!=EOF)
		{
			num += ch;
			ch = fgetc(tfile);
		}
		temp.id = atoi(num.c_str());
		num.clear();
		TSet.push_back(temp);
	}
	fclose(tfile);
}

void grammar::ShowTSet()
{
	int i;
	cout << "Terminals Set: " << endl;
	for(i=0; i<TSet.size(); i++)
	{
		cout << TSet[i].t << '\t' << TSet[i].id << endl;
	}
}
void grammar::ShowVSet()
{
	int i;
	cout << "Variables Set: " << endl;
	for(i=0; i<VSet.size(); i++)
	{
		cout << VSet[i].v << endl;
	}
}
void grammar::ReadProduction()
{
	string input;
	Production temp;

	cout << "Please Input Productions File: " << endl;
	//cin >> input;
	input = "d:\\data/p.txt";
	FILE * pfile = fopen(input.c_str(),"r");

	char ch;
	while((ch=fgetc(pfile))!=EOF)
	{
		temp.right.clear();
		temp.left = ch;
		fseek(pfile,2,SEEK_CUR);
		ch = fgetc(pfile);
		while(ch!='\n' && ch!=EOF)
		{
			temp.right += ch;
			ch = fgetc(pfile);
		}
		production.push_back(temp);
	}
	fclose(pfile);
}

void grammar::ShowProduction()
{
	int i;
	cout << "Productions: " << endl;
	for(i=0; i<production.size(); i++)
	{
		cout << production[i].left << "->" << production[i].right << endl;
	}
}

string grammar::GetFirstTerminal(string s)
{
	int i = 0;
	string result;

	while(i<s.length())
	{
		if((s[i]!=' ') && !isupper(s[i]))
		{
			result += s[i];
		}
		else
		{
			break;
		}
		i++;
	}
	if(IsTer(result))
	{
		return result;
	}
	else
	{
		return "";
	}
}
firstfollow grammar::FirstSet(string s)
{
	firstfollow first;
	firstfollow tmp;
	firstfollow result;
	string temp;

	if(!IsVar(s[0]))
	{
		temp = GetFirstTerminal(s);
		first.Insert(temp);
	}
	else
	{
			tmp = FirstSet(s[0]);
			for(int i=0; i<tmp.set.size(); i++)
			{
				first.Insert(tmp.set[i]);
				if(tmp.set[i] == "e")
				{
					temp.assign(s,1,s.length()-1);
					result = FirstSet(temp);
					for(int j=0; j<result.set.size(); j++)
					{
						first.Insert(result.set[j]);
					}
				}
			}
	}
	return first;
}
firstfollow grammar::FirstSet(char ch)
{
	firstfollow first;
	firstfollow result;
	string temp;
	string nextV;

	first.set.clear();
	if(!IsVar(ch))
	{
		return first;
	}
	for(int i=0; i<production.size(); i++)
	{
		if(production[i].left == ch)
		{
			if(production[i].right == "e")
			{
				first.Insert("e");
			}
			else if(!isupper(production[i].right[0]))
			{
				temp = GetFirstTerminal(production[i].right);
				first.Insert(temp);
				temp.clear();
			}
			else
			{
				if(production[i].left != production[i].right[0])
				{
					result = FirstSet(production[i].right[0]);
					for(int j=0; j<result.set.size(); j++)
					{
						first.Insert(result.set[j]);
					}
				}
			}
		}
	}
	return first;
}

void grammar::FirstSet()
{
	firstfollow temp;
	cout << "first set: " << endl;
	for(int i=0; i<VSet.size(); i++)
	{
		VSet[i].first = FirstSet(VSet[i].v);
		cout << VSet[i].v << ": ";
		for(int j=0;j<VSet[i].first.set.size();j++)
		{
			cout << VSet[i].first.set[j] << " ";
		}
		cout << endl;
	}
}

void grammar::FollowSet()
{
	firstfollow first;
	string temp;
	int pos;
	
	VSet[0].follow.Insert("$");
	for(int i=0; i<production.size(); i++)
	{
		for(int j=0; j<production[i].right.length(); j++)
		{
			if(IsVar(production[i].right[j]))
			{
				temp.assign(production[i].right,j+1,production[i].right.length()-j);
				if(temp=="" && production[i].right[j]!=production[i].left)
				{
					AddRelation(production[i].left,production[i].right[j]);
				}
				else
				{
					first = FirstSet(temp);
					for(int k=0; k<first.set.size(); k++)
					{
						if(first.set[k] != "e")
						{
							pos = FindVSetPos(production[i].right[j]);
							VSet[pos].follow.Insert(first.set[k]);
						}
						else
						{
							if(production[i].left != production[i].right[j])
							{
								AddRelation(production[i].left,production[i].right[j]);
							}
						}
					}
				}
			}
		}
	}
	int n;
	while(relation.size() > 0)
	{
		for(int m=0; m<relation.size(); m++)
		{
			for(n=0; n<relation.size(); n++)
			{
				if(relation[n].r == relation[m].l)
				{
					;
				}
			}
			if(n == relation.size())
			{
				pos = FindVSetPos(relation[m].l);
				int pos2 = FindVSetPos(relation[m].r);
				for(int x=0; x<VSet[pos].follow.set.size(); x++)
				{
					VSet[pos2].follow.Insert(VSet[pos].follow.set[x]);
				}
				DelRelation(relation[m].l,relation[m].r);
			}
		}
	}
	//print follow set
	cout << "follow set: " << endl;
	for(int i=0; i<VSet.size(); i++)
	{
		cout << VSet[i].v << ": ";
		for(int j=0;j<VSet[i].follow.set.size();j++)
		{
			cout << VSet[i].follow.set[j] << " ";
		}
		cout << endl;
	}
	
}

void grammar::AddRelation(char x1,char x2)
{
	Relation temp;
	for(int i=0; i<relation.size(); i++)
	{
		if(x1 == relation[i].l)
			if(x2 ==relation[i].r)
				return;
	}
	temp.l = x1;
	temp.r = x2;
	relation.push_back(temp);
}
void grammar::DelRelation(char x1,char x2)
{
	for(int i=0; i<relation.size(); i++)
	{
		if(x1 == relation[i].l)
		{
			if(x2 == relation[i].r)
			{
				relation.erase(relation.begin()+i);
			}
		}
	}
}

bool grammar::IsVar(char var)
{
	for(int i=0; i<VSet.size(); i++)
	{
		if(VSet[i].v == var)
			return true;
	}
	return false;
}
bool grammar::IsTer(string t)
{
	for(int i=0; i<TSet.size(); i++)
	{
		if(TSet[i].t == t)
			return true;
	}
	return false;
}
int grammar::FindVSetPos(char v)
{
	for(int i=0; i<VSet.size(); i++)
	{
		if(VSet[i].v == v)
			return i;
	}
	return -1;
}
int grammar::FindTSetPos(string t)
{
	for(int i=0; i<TSet.size(); i++)
	{
		if(TSet[i].t == t)
			return i;
	}
	return -1;
}
void grammar::InitList()
{
	Production pro;
	pro.left = 'e';
	pro.right = "error";
	for(int i=0; i<VSet.size(); i++)
	{
		for(int j=0; j<TSet.size(); j++)
		{
			list.push_back(pro);
		}
	}
}
void grammar::CreatList()
{
	InitList();
	int vNum;
	int tNum;
	firstfollow first;
	firstfollow follow;

	for(int i=0; i<production.size(); i++)
	{
		vNum = FindVSetPos(production[i].left);
		first = FirstSet(production[i].right);
		for(int j=0; j<first.set.size(); j++)
		{
			tNum = FindTSetPos(first.set[j]);
			if(first.set[j] != "e")
			{
				AddProductionToList(production[i],vNum,tNum);
			}
			else
			{
				follow = VSet[vNum].follow;
				for(int k=0; k<follow.set.size(); k++)
				{
					tNum = FindTSetPos(follow.set[k]);
					AddProductionToList(production[i],vNum,tNum);
				}
			}
		}
	}
}
void grammar::ShowList()
{
	int i;
	FILE * lfile;
	lfile = fopen("d:\\data/list.txt","w");

	cout << "  ";
	fprintf(lfile,"  ");
	for(i=0; i<TSet.size(); i++)
	{
		cout << TSet[i].t << " ";
		fprintf(lfile,"%-17s",TSet[i].t.c_str());
	}
	cout << endl;
	fprintf(lfile,"\n");
	for(i=0; i<VSet.size(); i++)
	{
		cout << VSet[i].v << " ";
		fprintf(lfile,"%c ",VSet[i].v);
		for(int j=0; j<TSet.size(); j++)
		{
			cout << list[i*TSet.size()+j].left << "->" << list[i*TSet.size()+j].right << "\t\t";
			fprintf(lfile,"%c->%-10s    ",list[i*TSet.size()+j].left,list[i*TSet.size()+j].right.c_str());
		}
		cout << endl;
		fprintf(lfile,"\n");
	}
}
void grammar::AddProductionToList(Production pro,int vNum,int tNum)
{
	int pos;
	pos = vNum * TSet.size() + tNum;
	list[pos].left = pro.left;
	list[pos].right = pro.right;
}
void grammar::GrammarAnalyzer(string sentence)
{
	FILE * output;
	int vNum;
	int tNum;
	int pos;
	int ip;
	char a;
	char x;
	string input;
	string tmp;
	stack <char> s; 

	//initialization part
	ip = 0;
	input = sentence + "$";
	s.push('$');
	s.push(VSet[0].v);
	output = fopen("d:\\data/output.txt","w");

	cout << "output stream:" << endl;
	while(s.size() > 0)
	{
		x = s.top();
		a = input[ip];

		if(IsVar(x))
		{
			vNum = FindVSetPos(x);
			tmp = a;
			tNum = FindTSetPos(tmp);
			pos = vNum * TSet.size() + tNum;
			if(list[pos].left == x)
			{
				s.pop();
				if(list[pos].right != "e")
				{
					for(int i=0; i<list[pos].right.size(); i++)
					{
						s.push(list[pos].right[list[pos].right.size()-i-1]);
					}
				}
				cout << list[pos].left << "->" << list[pos].right << endl;
				fprintf(output,"%c->%s\n",list[pos].left,list[pos].right.c_str());
			}
			else
				error();
		}
		else
		{
			if(x == a)
			{
				s.pop();
				ip++;
			}
			else
				error();
		}
	}
	fclose(output);
}

void grammar::error()
{
	cout << "error!" << endl;
}