gram.cpp

在VC下打开SLR1.dsp

/*SLR1分析器示例程序，可识别的加法运算表达式文法为课本P111例：*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include <ctype.h>
#include "gram.h"
#include "rstack.h"

/*以下变量用于词法分析*/
char ch;            //字符变量，存放最新读进的源程序字符。
char strToken[30];  //字符数组，存放构成单词符号的字符串。
int lvalue;         //单词的内码值
char inbuf[300];            //扫描缓冲区
int sp;                     //起点指示器
int ep;                     //扫描指示器
token sym;					//向前看单词

/*以下变量用于语法分析*/
//终结符符号表
V vt[]={
		"i",$INT,
		"+",$PLUS,
		"*",$MUL,
		"(",$LPAR,
		")",$RPAR,
		"#",$END
};

//非终结符符号表
V vn[]={
		"E",$E,
		"T",$T,
		"F",$F
};
//文法的产生式集合
P pset[]={
		1,$E,{$E,$PLUS,$T,0},//E->E+T
		2,$E,{$T,0,0,0},
		3,$T,{$T,$MUL,$F,0},
		4,$T,{$F,0,0,0},
		5,$F,{$LPAR,$E,$RPAR,0},
		6,$F,{$INT,0,0,0},
		0,0,0
};

//SLR1分析表
int action[12][6] = {
	//  i,+,*,(,),#
	    S+5,BLANK,BLANK,S+4,BLANK,BLANK,
		BLANK,S+6,BLANK,BLANK,BLANK,ACC,
		BLANK,R+2,S+7,BLANK,R+2,R+2,
		BLANK,R+4,R+4,BLANK,R+4,R+4,
		S+5,BLANK,BLANK,S+4,BLANK,BLANK,
		BLANK,R+6,R+6,BLANK,R+6,R+6,
		S+5,BLANK,BLANK,S+4,BLANK,BLANK,
		S+5,BLANK,BLANK,S+4,BLANK,BLANK,
		BLANK,S+6,BLANK,S+11,BLANK,BLANK,
		BLANK,R+1,S+7,BLANK,R+1,R+1,
		BLANK,R+3,R+3,BLANK,R+3,R+3,
		BLANK,R+5,R+5,BLANK,R+5,R+5
};

int go[10][3] = {
	//E,T,F
	1,2,3,
	BLANK,BLANK,BLANK,
	BLANK,BLANK,BLANK,
	BLANK,BLANK,BLANK,
	8,2,3,
	BLANK,BLANK,BLANK,
	BLANK,9,3,
	BLANK,BLANK,10,
	BLANK,BLANK,BLANK,
	BLANK,BLANK,BLANK
};

/*函数GetChar,GetBC,Concat,isDigit,Retract,Lex用于词法分析。
词法分析器的调用接口函数为Lex(),参考实验1*/
void GetChar()
{
	ch = inbuf[ep];
	ep++;
}
void GetBC()
{
	while (ch==' ' || ch=='\t')
		GetChar();
}
void Concat()
{
	int length;
	length = ep-sp-1;
	strToken[length] = ch;
}
bool isDigit()
{
	if ((ch>='0')&&(ch<='9'))
		return true;
	return false;
}
void  Retract()
{
	if (ep==0)
		ep = 299;
	else
		ep--;
	ch = ' ';
}

int Lex()
{
	memset(strToken, 0, 30);
	GetChar();
	GetBC();
	sp = ep-1;
	lvalue = 0;
	if (isDigit())
	{
		while (isDigit())
		{
			Concat();GetChar();
		}
		Retract();
		sscanf(strToken, "%d", &lvalue);
		sym.code = $INT;
	}
	else if (ch == '+')
	{
		strToken[0] = '+';
		sym.code = $PLUS;
	}
	else if (ch == '*')
	{
		strToken[0] = '*';
		sym.code = $MUL;
	}
	else if (ch == '(')
	{
		strToken[0] = '(';
		sym.code = $LPAR;
	}
	else if (ch == ')')
	{
		strToken[0] = ')';
		sym.code = $RPAR;
	}
	else if (ch == '\n')
	{
		sym.code = $END;
	}
	else
	{
		strToken[0] = ch;
		sym.code = $UNKNOWN;
	}
	return sym.code;
/*	else if (ch == '-')
	{
		strToken[0] = '-';
		return $MINUS;
	}
	else if (ch == '/')
	{
		strToken[0] = '/';
		return $DIV;
	}
	*/
}

void ProcError()
{
	switch (sym.code)
	{
		case $UNKNOWN:
			printf("错误(1)：第%d个字符为非法字符。\n", sp+1);
			break;
		case $INT:
			printf("错误(2)：第%d个字符开始处的单词%s前缺运算符。\n", sp+1, sym.name);
			break;
		case $PLUS:
		case $MUL:
//		case $MINUS:
//		case $DIV:
			printf("错误(3)：第%d个字符开始处的单词%s前缺操作数。\n", sp+1, sym.name);
			break;
		case $END:
			printf("错误(4)：语法错，非正常输入结束。\n");
			break;
		default:
			;
	}
}

int SLR1()
{
	int token;//输入符号
	int s,e;	//状态栈顶、符号栈顶元素
	int *pr,pl;//产生式右部、左部
	int act;//动作
	//分析栈
	rstack slrstack(256);

	slrstack.push(0, $END);
	token = Lex();
	while(true)
	{
		if (token == $UNKNOWN)
		{
			ProcError();
			return FAIL;
		}
		else
		{
			act = action[slrstack.top(s,e)][token-1];
			if (act == BLANK)
			{
				ProcError();
				return FAIL;
			}
			else if (act == ACC)
			{
				printf("接受！");
				return SUCCESS;
			}
			else if (act < R)
			{
				//移入
				printf("移入%s\n", vt[token-1].name);
				slrstack.push(act-S, token);
				token = Lex();
			}
			else
			{
				//规约
				pr = pset[act-R-1].right;
				pl = pset[act-R-1].left;
				printf("规约产生式:%s->", vn[pl-100].name);
				while(*pr != 0)
				{
					if (*pr >= 100)
						printf("%s ", vn[*pr-100].name);
					else
						printf("%s ", vt[*pr-1].name);
					slrstack.pop(s, e);
					pr++;
				}
				printf("\n");
				s = go[slrstack.top(s,e)][pl-100];
				slrstack.push(s, pl);
			}//if (act == BLANK)
		}//if (token == $UNKNOWN)
	}//while
}

void main()
{
	bool quit = false;
	int i;

	while (!quit)
	{
		memset(inbuf, 0, 300);
		printf("请输入加法、乘法表达式(回车结束):");
		i = 0;
		while ((inbuf[i] = getchar()) != '\n')
			i++;
		printf("\n");
		ep = 0;
		if (SLR1() == SUCCESS)
			printf("分析成功，没有语法错误\n");
		printf("退出吗？(y/n)");
		if (toupper(getch()) == 'Y')
			quit = true;
		printf("\n");
	}
}