ll(1).cpp

ll(1)语法分析器

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string>
#include<ctype.h>
#define M 22
#define N 30

using namespace std;
using std::string;

//产生式的数据结构
struct generatype
{
	char str[100];
	int length;
	int left;
};
struct generatype table[M][N];

//堆栈的数据结构
struct stacktype
{
	string content[200];
	int top;
};
struct stacktype STACK;

//编码表的数据结构
struct symboltype
{
	string symbol;
	int id;
};
struct symboltype bianma[100];


int toknum=0,fnum=0;					//token表及符号表长度
int tokc[100],tokn[100];				//token表中的内容
string vt[30],vn[22];					//终结符及非终结符数组
string inputs[657];

void init()
{
	FILE *fp1;
	int s=0,p=0;

	fp1=fopen("ftok.txt","r");

	while(!feof(fp1))
	{
		fscanf(fp1,"%d%d",&tokc[toknum],&tokn[toknum]);
		toknum++;
	}
	toknum=toknum-2;

	//初始化终结符
	vt[0]="id";
	vt[1]="{";
	vt[2]="}";
	vt[3]="while";
	vt[4]="if";
	vt[5]="int";
	vt[6]="func";
	vt[7]="else";
	vt[8]=",";
	vt[9]="true";
	vt[10]="(";
	vt[11]=")";
	vt[12]="!";
	vt[13]="&";
	vt[14]="|";
	vt[15]="<";
	vt[16]="<=";
	vt[17]="==";
	vt[18]="<>";
	vt[19]="const";
	vt[20]="+";
	vt[21]="*";
	vt[22]="false";
	vt[23]="then";
	vt[24]="do";
	vt[25]=";";
	vt[26]="=";
	vt[27]=">";
	vt[28]=">=";
	vt[29]="$";		//$为开始符号
	
	//初始化编码表
	bianma[0].symbol="func";	bianma[0].id=1;
	bianma[1].symbol="while";	bianma[1].id=2;
	bianma[2].symbol="do";		bianma[2].id=3;
	bianma[3].symbol="if";		bianma[3].id=4;
	bianma[4].symbol="then";    bianma[4].id=5;
	bianma[5].symbol="else";    bianma[5].id=6;
	bianma[6].symbol="true";    bianma[6].id=7;
	bianma[7].symbol="false";   bianma[7].id=8;
	bianma[8].symbol="const";   bianma[8].id=9;
	bianma[9].symbol="id";		bianma[9].id=10;
	bianma[10].symbol="{";		bianma[10].id=11;
	bianma[11].symbol="}";		bianma[11].id=12;
	bianma[12].symbol=";";		bianma[12].id=13;
	bianma[13].symbol=",";		bianma[13].id=14;
	bianma[14].symbol="=";		bianma[14].id=15;
	bianma[15].symbol="!";		bianma[15].id=16;
	bianma[16].symbol="&";		bianma[16].id=17;
	bianma[17].symbol="|";		bianma[17].id=18;
	bianma[18].symbol="<";		bianma[18].id=19;
	bianma[19].symbol=">";		bianma[19].id=20;
	bianma[20].symbol="<=";		bianma[20].id=21;
	bianma[21].symbol=">=";		bianma[21].id=22;
	bianma[22].symbol="<>";		bianma[22].id=23;
	bianma[23].symbol="==";		bianma[23].id=24;
	bianma[24].symbol="+";		bianma[24].id=25;
	bianma[25].symbol="*";		bianma[25].id=26;
	bianma[26].symbol="(";		bianma[26].id=27;
	bianma[27].symbol=")";		bianma[27].id=28;
	bianma[28].symbol="int";	bianma[28].id=29;

	//初始化非终结符
	vn[0]="K";
	vn[1]="L";
	vn[2]="A";
	vn[3]="S";
	vn[4]="U";
	vn[5]="W";
	vn[6]="C";
	vn[7]="F";
	vn[8]="T";
	vn[9]="D";
	vn[10]="G";
	vn[11]="B";
	vn[12]="H";
	vn[13]="I";
	vn[14]="J";
	vn[15]="M";
	vn[16]="N";
	vn[17]="E";
	vn[18]="P";
	vn[19]="Q";
	vn[20]="R";
	vn[21]="V";

	//初始化预测分析表
	for(s=0;s<M;s++)
	{
		for(p=0;p<N;p++)
		{
			table[s][p].left=0;
			strcpy(table[s][p].str,"err");
		}
	}
	
	strcpy(table[0][6].str,"func id {L}");
	strcpy(table[1][0].str,"SA");
	strcpy(table[1][1].str,"SA");
	strcpy(table[1][3].str,"SA");
	strcpy(table[1][4].str,"SA");
	strcpy(table[1][5].str,"SA");
	strcpy(table[2][0].str,"SA");
	strcpy(table[2][1].str,"SA");
	strcpy(table[2][2].str,"#");
	strcpy(table[2][3].str,"SA");
	strcpy(table[2][4].str,"SA");
	strcpy(table[2][5].str,"SA");
	strcpy(table[3][0].str,"id =E;");
	strcpy(table[3][1].str,"{L}");
	strcpy(table[3][3].str,"US");
	strcpy(table[3][4].str,"CSF");
	strcpy(table[3][5].str,"TD;");
	strcpy(table[4][3].str,"WBdo");
	strcpy(table[5][3].str,"while");
	strcpy(table[6][4].str,"ifBthen");
	strcpy(table[7][7].str,"elseS");
	strcpy(table[8][5].str,"int");
	strcpy(table[9][0].str,"idG");
	strcpy(table[10][8].str,", idG");
	strcpy(table[10][25].str,"#");
	strcpy(table[11][0].str,"IH");
	strcpy(table[11][9].str,"IH");
	strcpy(table[11][10].str,"IH");
	strcpy(table[11][12].str,"IH");
	strcpy(table[11][22].str,"IH");
	strcpy(table[12][11].str,"#");
	strcpy(table[12][14].str,"|IH");
	strcpy(table[12][23].str,"#");
	strcpy(table[12][24].str,"#");
	strcpy(table[13][0].str,"MJ");
	strcpy(table[13][9].str,"MJ");
	strcpy(table[13][10].str,"MJ");
	strcpy(table[13][12].str,"MJ");
	strcpy(table[13][22].str,"MJ");
	strcpy(table[14][11].str,"#");
	strcpy(table[14][13].str,"&MJ");
	strcpy(table[14][14].str,"#");
	strcpy(table[14][23].str,"#");
	strcpy(table[14][24].str,"#");
	strcpy(table[15][0].str,"idNE");
	strcpy(table[15][9].str,"true");
	strcpy(table[15][10].str,"(B)");
	strcpy(table[15][12].str,"!B");
	strcpy(table[15][22].str,"false");
	strcpy(table[16][15].str,"<");
	strcpy(table[16][16].str,"<=");
	strcpy(table[16][17].str,"==");
	strcpy(table[16][18].str,"<>");
	strcpy(table[16][26].str,"=");
	strcpy(table[16][27].str,">=");
	strcpy(table[16][28].str,">");
	strcpy(table[17][0].str,"QP");
	strcpy(table[17][10].str,"QP");
	strcpy(table[17][19].str,"QP");
	strcpy(table[18][11].str,"#");
	strcpy(table[18][13].str,"#");
	strcpy(table[18][14].str,"#");
	strcpy(table[18][20].str,"+QP");
	strcpy(table[18][23].str,"#");
	strcpy(table[18][24].str,"#");
	strcpy(table[18][25].str,"#");
	strcpy(table[19][0].str,"VR");
	strcpy(table[19][10].str,"VR");
	strcpy(table[19][19].str,"VR");
	strcpy(table[20][11].str,"#");
	strcpy(table[20][13].str,"#");
	strcpy(table[20][14].str,"#");
	strcpy(table[20][20].str,"#");
	strcpy(table[20][21].str,"*VR");
	strcpy(table[20][23].str,"#");
	strcpy(table[20][24].str,"#");
	strcpy(table[20][25].str,"#");
	strcpy(table[21][0].str,"id");
	strcpy(table[21][10].str,"(E)");
	strcpy(table[21][19].str,"const");

	for(s=0;s<M;s++)
	{
		for(p=0;p<N;p++)
			table[s][p].length=strlen(table[s][p].str);
	}
	fclose(fp1);
	return;
}

//进栈
void push(stacktype & sta,string s)
{
	sta.content[sta.top]=s;
	sta.top++;
	return;
}

//出栈
void pop(stacktype & sta)
{
	sta.content[sta.top - 1]="";
	sta.top--;
	return;
}

//判断是否为非终结符
int ISvn(string s)
{
	int i=0;
	for(i=0;i<M;i++)
	{
		if(s==vn[i])
			return i;
	}
	return -1;
}

//判断是否为终结符
int ISvt(string s)
{
	int i=0;
	for(i=0;i<N;i++)
	{
		if(s==vt[i])
			return i;
	}
	return -1;
}

//token表中的内容存进输入数组
void input()
{
	int a,b;
	for(a=0;a<=toknum;a++)
	{
		if(tokc[a]==10)
		{
			inputs[a]="id";		
		}
		else
		{
			for(b=0;b<=28;b++)
			{
				if(tokc[a]==bianma[b].id)
				{
					inputs[a]=bianma[b].symbol;
					break;
				}
			}
		}
	}
	inputs[toknum + 1] = "$";
}

//分析表中的内容进栈
void puts(int m,int n)
{
	int   i=table[m][n].length;		//生成式长度
	char  str[10],temp[10];
	int   j=0,num=9,t;
	string s = "";
	
	i=i-1;
	if(strcmp(table[m][n].str,"#")==0)
	{
		cout<<"  "<<vn[m]<<"->#"<<endl;
	}
	else
	{

	while(i>=0)
	{
		num = 9;
		if(isupper(table[m][n].str[i]))
		{
			s = "";
			s.append(table[m][n].str,i,1);
			push(STACK, s);
			i--;
		}
		else if(table[m][n].str[i] == ' ')
		{
			num = 9;
			i--;
		}
		else 
		{
			do{
				str[num]=table[m][n].str[i];
				i--;
				num--;
			}
			while(table[m][n].str[i]!=' '&&!isupper(table[m][n].str[i]) && i >=0);
			
			num++;
			j = 0;
			t = num;
			strcpy(temp,"");
			while(t<=9)
			{
				temp[j]=str[t];
				j++;
				t++;
			}
			s = "";
			s.append(temp,0,j);
			push(STACK,s);
		}
	}
	cout<<"  "<<vn[m]<<"->"<<table[m][n].str<<endl;
	}
}

//语法分析
void analyse(void)
{
	int first=0;
	int k,t;
	string x,a;	
	
	push(STACK,"$");	//$进栈
	push(STACK,"K");	//开始符号进栈
	
	input();		    //输入字符串

	a=inputs[first];					//当前输入字符
	x=STACK.content[STACK.top-1];		//栈顶
	k=ISvn(x);		//行值
	t=ISvt(a);		//列值

	while(x!="$")
	{
		//栈顶为终结符
		if(ISvt(x)!=-1)		
		{
			if(x==a)
			{
				pop(STACK);
				x=STACK.content[STACK.top-1];
				
				first++;
				a=inputs[first];
			}
		}
		//栈顶为非终结符
		else			
		{
			k=ISvn(x);			//分析表行值
			t=ISvt(a);			//分析表列值
			pop(STACK);			//释放栈顶
			puts(k,t);			//生成式进栈
			x=STACK.content[STACK.top-1];
		}
	}
	return;
}

void main(void)
{
	init();
	analyse();
	return;
}