编译原理中递归子程序法的实现 内附测试文件

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX 30	//表达式，栈等允许的最大长度
#define SEM 1   //语义
#define SYN 0	//算符

void Efun(void);
void E1fun(void);
void Ffun(void);
void Tfun(void);
void T1fun(void);
int  push(char stack[], char w, int flag);
char pop(char stack[], int flag);
void Zfun(void);

char Unit[MAX];
int iunit=0;//对Unit进行计数
char ch;

char synstack[MAX];   //算符栈数组
int  ksyn = 0 ;   //算符栈顶指针
char semstack[MAX];   //语义栈数组
int  ksem = 0 ;   //语义栈顶指针
char qout[MAX][4];   //四元式字符串
int  qoutcout ;   //四元式字符串当前个数

int main(void)
{
	int n = 0 ;
	int i = 0 ;
	char str[MAX] ;
	FILE *fi = NULL;
	fi = fopen("test.txt" , "r") ;
	if(fi == NULL)
	{
		printf("File test.txt Not Found!\n");		
		return EXIT_FAILURE;
	}

	printf("请输入表达式，不要太长（<%d）\n",MAX);
	fgets(str , MAX , fi) ;//连同'\n'一起读进来
	printf("表达式是: %s\n",str);
	n = strlen(str) ;
	if(n>MAX)
	{
		printf("表达式太长了\n") ;
		return EXIT_FAILURE ;
	}
	for(i=0; i<n; i++){
		ch = str[i] ;//提取有效单词
		if(ch>='a'&&ch<'z'||(ch>='0'&&ch<='9')||ch == '-' 
			|| ch == '/' ||ch=='+'||ch=='*'||ch=='('||ch==')')
		{
            Unit[iunit] = ch;
			iunit++;
		}
        else if(ch == '\n')//表达式完事了
		{
            break ;
		}
		else if(ch == ' '){//空格是没有用的
		}
		else{
			printf("出现了非法字符%c\n",ch);
			return EXIT_FAILURE;
		}
	}
	//结束标志
	Unit[iunit] = '#';
	iunit++;
	iunit = 0;
	Zfun() ;
	return EXIT_SUCCESS;
}
int push(char stack[], char w, int flag)
{
	if(ksyn==MAX-1||ksem == MAX-1)//最后一个不用
	{
		printf("栈满了\n") ;
		return 1 ;
	}
	else
	{
		if(SYN == flag)
		{
			stack[ksyn] = w ;
			ksyn++ ;
		}
		if(SEM == flag)
		{
			stack[ksem] = w ;
			ksem ++ ;
		}
		
	}
	return 0 ;
}

char pop(char stack[] , int flag)
{
	char w ;
	if(flag == SEM)
	{
		if(ksem == 0)
		{
			printf("语义栈空\n") ;
			return -1 ;
		}
		w = stack[ksem-1] ;
		ksem-- ;
		return w ;
	}
	if(flag == SYN)
	{
		if(ksyn == 0)
		{
			printf("算符栈空\n") ;
			return -1 ;
		}
		w = stack[ksyn-1] ;
		ksyn-- ;
		return w ;
	}
}
void record()
{
	char asem=0 , bsem= 0 , syn= 0 ;
	asem = pop(semstack , SEM) ;
	bsem = pop(semstack , SEM) ;
	syn  = pop(synstack , SYN) ;
	if(asem == -1||bsem== -1||syn==-1)
	{
		printf("记录四元式错误\n") ;
		return ;
	}
	else
	{		
		int i = 0 ;         //形如(+,a,b,t)的式子
		qout[qoutcout][i++] = syn ;
		qout[qoutcout][i++] = bsem ;
		qout[qoutcout][i++] = asem ;
		qout[qoutcout][i++] = 't' ;
		push(semstack , 't' , SEM) ;
		qoutcout++ ;
		if(qoutcout==MAX)
		{
			printf("四元式满\n") ;
			return ;
		}
	}
	return ;
}
void Show()
{
	int i = 0;
	char temp1,temp2;
	for(i =0 ; i<qoutcout ; i++)//包含了对t的处理
	{
		if(qout[i][1]=='t'&&qout[i][2]!='t')
		{
			temp1 = pop(semstack,SEM);
			printf("( %c, %c%c,  %c, %c%d)\n",qout[i][0],qout[i][1],temp1,
					qout[i][2],qout[i][3],i+1);
			push(semstack,i+1+'0',SEM);
		}
		else if(qout[i][1]!='t'&&qout[i][2]=='t')
		{
			temp1 = pop(semstack,SEM);
			printf("( %c,  %c, %c%c, %c%d)\n",qout[i][0],qout[i][1],qout[i][2],temp1,qout[i][3],i+1);
			push(semstack,i+1+'0',SEM);
		}
		else if(qout[i][1]=='t'&&qout[i][2]=='t')
		{
			temp1 = pop(semstack,SEM);
			temp2 = pop(semstack,SEM);
			printf("( %c, %c%c, %c%c, %c%d)\n",qout[i][0],qout[i][1],temp2,qout[i][2],temp1,qout[i][3],i+1);
			push(semstack,i+1+'0',SEM);
		}
		else
		{
			printf("( %c,  %c,  %c, %c%d)\n",qout[i][0],qout[i][1],qout[i][2],qout[i][3],i+1);
			push(semstack,i+1+'0',SEM);
		}
	}
}

void Zfun(void)
{
	ch = Unit[iunit];//指向了第一个字符
	Efun();
    if(ch=='#')//处理结束
    {
		printf("处理中... ...\n"); 
		printf("OK!\n");
		Show() ;
	}
    else
        printf("\n出错了!可能没有结束符号\n");
}
void Efun(void)
{
    Tfun();   //先执行t函数
    E1fun();
}
void E1fun(void)
{
	ch = Unit[iunit];
	if(ch == '+' || ch == '-')
	{
		push(synstack , ch , SYN) ;
		iunit++;
		Tfun() ;
		record() ;
		E1fun() ; 
	}
	else
		return ;
}

void Tfun(void)
{
    Ffun();  
    T1fun();
}

void T1fun(void)
{
	ch = Unit[iunit];
	if(ch == '*' || ch == '/')
	{
		push(synstack , ch , SYN) ;
		iunit++;
		Ffun() ;
		record() ;
		T1fun() ; //返回
	}
	return ;
}
void Ffun()
{
	ch = Unit[iunit];
	if(ch=='(')    //左括号
	{
		iunit++;        //下一个字符
		Efun() ;              //进入e函数
		if(ch==')')		//右括号
			iunit++ ;		//下一个字符
		else{
			printf("第 %d 个字符处出错!\n",iunit);
			exit(-1);
		}
	}
	else if(ch>='a'&&ch<='z'
		||(ch>='0'&&ch<='9'))	//如果是字母或数字
	{
		push(semstack , ch, SEM) ; //字符入栈
		iunit++;
	}
    else{
		printf("第 %d 个字符处出错!\n",iunit);
		exit(-1);
	}
}