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

#include "stdio.h"
#include "malloc.h"
#include "string.h"
#include <stdlib.h>
#define      MAX       30
#define      SEM      1             /*语义*/
#define      SYN      0				/*算符*/
void Efun();
void Ffun();
void Tfun();
void T1fun();
void E1fun();
int push(char stack[] , char w , int flag);
char pop(char stack[] , int flag);
void Zfun(void);
void freech(void);

struct Lchar{
    char char_ch;
	int pos;//位置，从1开始
    struct Lchar *next;
}lchar,*p,*h,*temp; /*全局变量*/
char ch;
int right;

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


int main()
{
	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;
	}

    right=1 ;
    h=(Lchar*)malloc(sizeof(Lchar)) ;//头结点
    h->next=NULL;
    p=h;
	
	printf("请输入表达式，不要太长（<20）\n");
	fgets(str , MAX , fi) ;//连同'\n'一起读进来
	printf("表达式是: %s\n",str);
	n = strlen(str) ;
	if(n>30)
	{
		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==')')
		{
            temp=(Lchar*)malloc(sizeof(Lchar));
            temp->next=NULL;
            temp->char_ch=ch;
			temp->pos = i+1;
            h->next=temp;
            h=h->next;
		}
        else if(ch == '\n')//表达式完事了
		{
            break ;
		}
		else if(ch == ' '){//空格是没有用的
		}
		else{
			printf("出现了非法字符%c\n",ch);
			return EXIT_FAILURE;
		}

	}
	//结束标志
	temp=(Lchar*)malloc(sizeof(Lchar));
	temp->next=NULL;
	temp->char_ch='#';
	temp->pos = i;
	h->next=temp;
	h=h->next;

	Zfun() ;
	freech() ;
	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
	{
		//形如(+,a,b,t)的式子
		int i = 0 ;
		qt[kqt][i++] = syn ;
		qt[kqt][i++] = bsem ;
		qt[kqt][i++] = asem ;
		qt[kqt][i++] = 't' ;
		push(semstack , 't' , SEM) ;
		kqt++ ;
		if(kqt==MAX)
		{
			printf("四元式数组满\n") ;
			return ;
		}
	}
	return ;
}
void Show()
{
	int i = 0;
	char temp1,temp2;
	for(i =0 ; i<kqt ; i++)//包含了对t的处理
	{
		if(qt[i][1]=='t'&&qt[i][2]!='t')
		{
			temp1 = pop(semstack,SEM);
			printf("( %c, %c%c,  %c, %c%d)\n",qt[i][0],qt[i][1],temp1,
					qt[i][2],qt[i][3],i+1);
			push(semstack,i+1+'0',SEM);
		}
		else if(qt[i][1]!='t'&&qt[i][2]=='t')
		{
			temp1 = pop(semstack,SEM);
			printf("( %c,  %c, %c%c, %c%d)\n",qt[i][0],qt[i][1],qt[i][2],temp1,qt[i][3],i+1);
			push(semstack,i+1+'0',SEM);
		}
		else if(qt[i][1]=='t'&&qt[i][2]=='t')
		{
			temp1 = pop(semstack,SEM);
			temp2 = pop(semstack,SEM);
			printf("( %c, %c%c, %c%c, %c%d)\n",qt[i][0],qt[i][1],temp2,qt[i][2],temp1,qt[i][3],i+1);
			push(semstack,i+1+'0',SEM);
		}
		else
		{
			printf("( %c,  %c,  %c, %c%d)\n",qt[i][0],qt[i][1],qt[i][2],qt[i][3],i+1);
			push(semstack,i+1+'0',SEM);
		}
	}
}
void freech()
{
	for(temp = p->next ; temp->next!=NULL ; ) 
	{
		h = temp ;
		temp = temp->next ;
		free(h) ;
	}
}
void Zfun(void)
{
    h=p->next;//指向了第一个字符
	Efun();
    if(h->char_ch=='#')/*处理结束*/
    {
		printf("处理中... ...\n"); 
		printf("OK!\n");
		Show() ;
	}
    else
        printf("\n出错了!可能无结束符号\n");
}
void Efun(void)
{
    Tfun();   /*先执行t函数*/
    E1fun();
}
void E1fun(void)
{
	if(h->char_ch == '+' || h->char_ch == '-')
	{
		push(synstack , h->char_ch , SYN) ;
		h = h->next ;
		Tfun() ;
		record() ;
		E1fun() ; 
	}
	else
		return ;
}

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

void T1fun(void)
{
	if(h->char_ch == '*' || h->char_ch == '/')
	{
		push(synstack , h->char_ch , SYN) ;
		h = h->next ;
		Ffun() ;
		record() ;
		T1fun() ; /*返回t1*/
	}
	return ;
}


/*f函数*/
void Ffun()
{
	if(h->char_ch=='(')    /*左括号*/
	{
		h=h->next ;        /*读取下一个字符*/
		Efun() ;              /*进入e函数*/
		if(h->char_ch==')')/*如果是右括号*/
			h=h->next ;
		else{
			right=0 ;      /*出错*/
			printf("第 %d 个字符处出错!\n",h->pos);
			exit(-1);
		}
	}
	else if(h->char_ch>='a'&&h->char_ch<='z'
		||(h->char_ch>='0'&&h->char_ch<='9')) /*如果是字母或数字*/
	{
		push(semstack , h->char_ch , SEM) ; //字符入栈
		h=h->next;
	}
    else{
		right=0 ;      /*出错*/
		printf("第 %d 个字符处出错!\n",h->pos);
		exit(-1);
	}
}