bool_lr.c

布尔表达式的语法分析及语义分析程序设计 初始条件： 词法分析的结果

#include "string.h"
#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"
#include "cifafenxi.h"	

	char state[20]={0} ;	//状态栈
	char yuyi[10] = "";		//语义栈
	char fuhao[30] = "$";	//符号栈
	char input[80] = "";	//输入符号栈
	int pi=0,ps=0,py=0,pf=0;	//分别是输入栈，状态栈，语义栈，符号栈的指针
	char nbl_n[10];			//逆波兰式之数字部分
	int pn=0;				//逆波兰式数字部分指针
	char nbl_s[20];			//逆波兰式之操作符部分
	int first=1;			//是否第一次规约,是则入两个数到nbl_n,否则只入一个yuyi[py-1]，因为yuyi[py]是经过计算得到的非输入中本来就有的数字
	//0--->9 文法
	const char wf1[10][2]={"S","E","E","T","T","F","F","F","F","F"};
	const char wf2[10][6]={"E","EorT","T","TandF","F","notF","(E)","AropA","iropi","i"};
	const int wf3[10]={1,3,1,3,1,2,3,3,3,1};	//各条需回退几步
	const int wf4[10]={0,9,9,11,11,10,10,10,10,10};	//各条在表中对应的坐标

	//LR分析表
	const char lr_f[19][8]={ 
						0,0,0,'S',0,'S',0,'S',
						'a',0,'S',0,0,0,0,0,
						'r','S','r',0,0,0,'r',0,
						'r','r','r',0,0,0,'r',0,
						0,0,0,'S',0,'S',0,'S',
						0,0,0,'S',0,'S',0,'S',
						0,0,0,0,'S',0,0,0,
						0,0,0,0,0,0,0,0,
						'r','r','r',0,0,0,'r',0,
						'r','r','r',0,'S',0,'r',0,
						0,0,0,0,0,0,0,'S',
						'r','r','r',0,0,0,'r',0,
						0,0,0,'S',0,'S',0,'S',
						0,0,0,'S',0,'S',0,'S',
						'r','r','r',0,0,0,'r',0,
						0,0,'S',0,0,0,'S',0,
						'r','r','r',0,0,0,'r',0,
						'r','r','r',0,0,0,'r',0,
						'r','S','r',0,0,0,'r',0}	;		//主要动作第一部分('S' or 'r' or 'a'(acc))

	const int lr_s[19][12]={
						0,0,0,4,0,5,0,9,6,1,3,2,
						0,0,12,0,0,0,0,0,0,0,0,0,
						2,13,2,0,0,0,2,0,0,0,0,0,
						4,4,4,0,0,0,4,0,0,0,0,0,
						0,0,0,4,0,5,0,9,6,0,14,0,
						0,0,0,4,0,5,0,9,6,15,3,2,
						0,0,0,0,7,0,0,0,0,0,0,0,
						0,0,0,0,0,0,0,0,8,0,0,0,
						7,7,7,0,0,0,7,0,0,0,0,0,
						9,9,9,0,10,0,9,0,0,0,0,0,
						0,0,0,0,0,0,0,11,0,0,0,0,
						8,8,8,0,0,0,8,0,0,0,0,0,
						0,0,0,4,0,5,0,9,6,0,3,18,
						0,0,0,4,0,5,0,9,6,0,17,0,
						5,5,5,0,0,0,5,0,0,0,0,0,
						0,0,12,0,0,0,16,0,0,0,0,0,
						6,6,6,0,0,0,6,0,0,0,0,0,
						3,3,3,0,0,0,3,0,0,0,0,0,
						1,12,1,0,0,0,1,0,0,0,0,0}	;	//主要部分第二部分(数字)
	/*定义必须在程序之前！！！！*/


void main()
{
	int t1=0,t2=0;	//临时变量
	char ts[10]={0};	//临时字符串变量
	int bz=1;	//步骤

	/*输入待分析字符串*/
    p=0;
    printf("\n Please input string with the end of '$':\n");
    do
    {
    	ch=getchar();
    	prog[p]=ch;
    	p++;
    }while(ch!='$');
	t1=0;

    p=0;
	/*pi输入符号栈指针，ps状态，py语义，pf符号*/
	
	strcpy(input,prog);		//拷贝一份到input[]中以用作处理

	printf("步骤 状态栈            语义栈    符号栈             输入符号栈       主要动作  \n");
	scaner();	
	while(1)
	{

		printf("%-4d",bz++);
		
		t1=0,t2=0;
		do{
			printf("%d|",state[t1]);
			if(state[t1++]>=10)
				t2+=3;					//t2为状态栈显示所占位置的大小
			else
				t2+=2;
		}while(state[t1]!=0);


		for(t1=0;t1<20-t2;t1++)			//不足则补空格，保证状态栈总为22大小，方便对齐
			printf(" ");

	
		for(t1=1;t1<=py;t1++)			//打印语义栈
			printf("_%d",yuyi[t1]);

		for(t1=0;t1<8-py*2;t1++)
			printf(" ");

		printf(" %-13s%20s      %c%d\n",fuhao,input,lr_f[state[ps]][syn],lr_s[state[ps]][syn]);	
			
		if (lr_f[state[ps]][syn])	//如果在表中找得到
		{
			if (lr_f[state[ps]][syn]=='S')	//如果是Sn	注意！！'=='才是等于！'='是赋值！
			{
				t1 = lr_s[state[ps]][syn];
				state[++ps] = t1;		//Sn中n入状态栈
				state[ps+1] = 0;		//后面需置0！！！否则将会一直输出下去，已经去掉的也会输出！！

				t1=0;
				while(token[t1]&&token[t1]!='$')
				{
					fuhao[++pf]=token[t1++];
				}
				strcpy(ts,token);
				
				for(t1=strlen(token);t1>0;t1--)
					input[p-t1]=' ';

				scaner();
			}
			else if(lr_f[state[ps]][syn]=='r')
			{
				t1=lr_s[state[ps]][syn];
				switch(t1)
				{
					case 1:
						strcat(nbl_s,"or ");
						nbl_n[pn++] = yuyi[py-1];
						if(first) nbl_n[pn++] = yuyi[py];
						yuyi[py-1] = (yuyi[py] || yuyi[py-1]);
						py--;
						first=0;
						break;
					case 3:
						strcat(nbl_s,"and ");
						nbl_n[pn++] = yuyi[py-1];
						if(first) nbl_n[pn++] = yuyi[py];
						yuyi[py-1] = (yuyi[py] && yuyi[py-1]);
						py--;
						first=0;
						break;
					case 5:
						strcat(nbl_s,"not ");
						nbl_n[pn++] = yuyi[py];
						yuyi[py] = (!yuyi[py]);
						first=0;
						break;
					case 9:
						if(sum==0)
							yuyi[++py] = 0;
						else
							yuyi[++py] = 1;
						break;
				}
				
				pf = pf+1-strlen(wf2[t1]);
				fuhao[pf]=0;			//归约....(替代)
				t2=pf+1;
				while(fuhao[t2])		//将后面的无关信息全部删掉以免影响
					fuhao[t2++]=0;
				t2=0;
				strcat(fuhao,wf1[t1]);
				pf=pf+strlen(wf1[t1])-1;

				ps-=wf3[t1];							//状态栈回退
				ps++;
				state[ps] = lr_s[state[ps-1]][wf4[t1]];
				state[ps+1]=0;			//后面需置0！！！否则将会一直输出下去，已经去掉的也会输出！！
			}
			else 
			{
				printf("布尔表达式编译成功！\n");
				puts("\n逆波兰式如下:");
				for(t1=pn-1;t1>=0;t1--)
					printf("%d ",nbl_n[t1]);
				puts(nbl_s);
				puts("\n");
				break;
			}
		}
		else
		{
			printf("输入错误，不能成功通过编译。\n");
			break;
		}
	}

}