parse.cpp

用LL（1）方法分析四则运算

#include <iostream>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
#include <stack>
#include "word_analysis.h"

using namespace std;

/*四则运算的语法规则
0	E->TP   1	P->ATP  2   P->$
3	T->FQ	4	Q->MFQ	5	Q->$
6	F->(E)	7	F->i	8	A->+
9	A->-	10	M->*	11	M->/
	$表示空串
*/


void error(char *err){
	printf("Error: %s",err);
}

//显示栈中元素
void dump(stack< char > st)
{
	int i,j;
	char ch[100];
	j=st.size();
	for(i=0;i<j;i++)
	{
		ch[i]=st.top();
		st.pop();
	}
    for(i=j-1;i>=0;i--)
	{
	 printf("%c",ch[i]);
	 st.push(ch[i]);
	}
}



//检查是否在非终结符数组VN中
//如果在返回位置，否则返回-1
int checkVN(char x,char VN[7]){
	int k=0;
	for(;k<7;k++)
		if(VN[k] == x)
			return k;
	return -1;
}

//检查是否在终结符数组VT中
//如果在返回位置，否则返回-1
int checkVT(char x,char VT[8]){
	int k=0;
	for(;k<8;k++)
		if(VT[k] == x)
			return k;
	return -1;
}


void init_E_M(char Expression[12][7],int M[7][8]){
	int i,j;
	strcpy(Expression[0],"TP");		strcpy(Expression[1],"ATP");
	strcpy(Expression[2],"$");		strcpy(Expression[3],"FQ");
	strcpy(Expression[4],"MFQ");	strcpy(Expression[5],"$");
	strcpy(Expression[6],"(E)");	strcpy(Expression[7],"i");
	strcpy(Expression[8],"+");		strcpy(Expression[9],"-");
	strcpy(Expression[10],"*");		strcpy(Expression[11],"/");
	for(i=0;i<7;i++)
		for(j=0;j<8;j++)
			M[i][j] = -1;
	M[0][0]=0;	M[0][2]=0;	M[1][1]=2;	M[1][3]=1;	M[1][4]=1;	M[1][7]=2;	M[2][0]=3;
	M[2][2]=3;	M[3][1]=5;	M[3][3]=5;	M[3][4]=5;	M[3][7]=5;	M[3][5]=4;	M[3][6]=4;
	M[4][0]=6;	M[4][2]=7;	M[5][3]=8;	M[5][4]=9;	M[6][5]=10;	M[6][6]=11;
}


int syntax(char* input){
	char Expression[12][7];
	char VN[8],VT[9];//vt=" ()i+-*/# "
	int  M_VN_VT[7][8];
	unsigned int step=0;

	
	bool flag = false;
	stack< char > st;
	char X;//目前栈顶
	int xv=-1;//栈顶若为非终结符则为它在非终结符数组的位置
	int av=-1;//目前终结符在终结符数组的位置
	int expr;//表达式的标号
	int i=0;
	char* buff;
    int place=0;
	
	//初始化 终结符、非终结符数组
	strcpy(VT,"()i+-*/#");
	VT[8] = '\0';
	strcpy(VN,"EPTQFAM");
	VN[7] = '\0';

	//初始化表达式,初始化预测分析表
	init_E_M(Expression,M_VN_VT);
	

	//将#和起始非终结符压入栈
	st.push('#');
	st.push('E');

	//得到词法翻译后的输入串，以#结尾
	buff = read_sym(input);
	if(buff == NULL)
		return 0;//词法分析错误
	av= checkVT(buff[place],VT);
	
	//屏幕显示提示
	printf("Step:\tStack\tResidual inputString\n");


	while(!flag)//循环条件：没有文法匹配成功
	{
		X = st.top();
		st.pop();
		xv = checkVN(X,VN);

		if(xv < 0 && X != '#') //如果是终结符
		{	
			if(X == buff[place])
			{
				place++;
				if(buff[place]== '$')
					return 0;
				av= checkVT(buff[place],VT);
			}//if X==a
			else{
				printf("%c,%c,syntax analysis error!\n",buff[place],X);
				printf("\t\tSomething Wrong!\n");
				puts("Syntax analysis Failed!");
				return 0;
			}
		}//if symvalid(x)

		else if(X == '#')
		{
			if(X == buff[place])
			{
				flag = true;//Success!
//				printf("\t\tMatch!\n");
				break;
			}
			else 
			{
				printf("%c,%c,syntax analysis error!\n",buff[place],X);
				printf("\t\tSomething Wrong!\n");
				puts("Syntax analysis Failed!");
				return 0;
			}
		}//if(x == '#')

		else if(M_VN_VT[xv][av] != -1)
		{
			expr = M_VN_VT[xv][av];
			
			//如果产生式有部是空串
			if(Expression[expr][0] == '$')
			{
				printf("%4d:\t",step++);
				dump(st);
				printf("\t\t%10s",&buff[place]);
				printf("\n");
				continue;
			}//$

			//产生式有部所有符号逆序进栈
			for(i = strlen(Expression[expr])-1; i >= 0 ;i--)
				st.push(Expression[expr][i]);

		}//ifM_VN_VT[][]

		else{
			//出错
			error("Not Match character!");
			puts("Syntax analysis Failed!");
			return 0;
		}

		printf("%4d:\t",step++);
		dump(st);
		printf("\t\t%10s",&buff[place]);
		printf("\n");
	}
	
	if(flag = true)
		printf("Syntax analysis Succeed!\n");
	return 1; 
}


int main(){
	unsigned int len;
	char temp;
	char input[BUFSIZE];

	do{
		printf("请输入四则运算表达式,用于检测真伪:\n");
		gets(input);
	
		//初始化输入串，使之以#结尾
		len=strlen(input);
		input[len]='#';
		input[len+1]='\0';

		//语法分析
		syntax(input);


		printf("是否想继续查询?\n");
		scanf("%c",&temp);
		getchar();
	}while(temp == 'y' || temp == 'Y');
	return 0;
}