gram.cpp

工程LRTrans1

/*LR算术表达式翻译器示例程序：*/
#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,
		"SP",$SP,
};
//文法的产生式集合
P pset[]={
		1,$SP,{$E,0},			//S'->E
		2,$E,{$E,$PLUS,$E,0},	//E->E+E
		3,$E,{$E,$MUL,$E,0},	//E->E*E
		4,$E,{$LPAR,$E,$RPAR,0},//E->(E)
		5,$E,{$INT,0,0,0},		//E->i
		0,0,0
};

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

int go[10][1] = {1,BLANK,6,BLANK,7,8,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 run(int p, rstack &rs)
{
	//运行第p个产生式的语义处理程序,返回产生式左部符号属性值
	int s, e, v1, v2;
	switch(p)
	{
		case 0://S'->E
			rs.top(s, e, v1, 0);
			printf("运算结果为%d\n", v1);
			return v1;
		case 1://E->E+E
			rs.top(s, e, v1, 2);
			rs.top(s, e, v2, 0);
			return v1+v2;
		case 2://E->E*E
			rs.top(s, e, v1, 2);
			rs.top(s, e, v2, 0);
			return v1*v2;
		case 3://E->(E)
			rs.top(s, e, v1, 1);
			return v1;
		case 4://E->i
			rs.top(s, e, v1, 0);
			return v1;
		default:
			//error
			return BLANK;
	}
}

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

	slrstack.push(0, $END, BLANK);
	token = Lex();
	while(true)
	{
		if (token == $UNKNOWN)
		{
			ProcError();
			return FAIL;
		}
		else
		{
			act = action[slrstack.top(s,e,v,0)][token-1];
			if (act == BLANK)
			{
				ProcError();
				return FAIL;
			}
			else if (act == ACC)
			{
				run(0, slrstack);
				printf("接受！");
				return SUCCESS;	
			}
			else if (act < R)
			{
				//移入
				printf("移入%s\n", vt[token-1].name);
				slrstack.push(act-S, token, lvalue);
				token = Lex();
			}
			else
			{
				//规约
				pr = pset[act-R].right;
				pl = pset[act-R].left;
				printf("规约:%s->", vn[pl-100].name);
				plv = run(act-R, slrstack);	//调用第act-R个产生式的语义处理程序
				while(*pr != 0)
				{
					if (*pr >= 100)
						printf("%s ", vn[*pr-100].name);
					else
						printf("%s ", vt[*pr-1].name);
					slrstack.pop(s, e, v);
					pr++;
				}
				printf("\n");
				s = go[slrstack.top(s,e,v,0)][pl-100];
				slrstack.push(s, pl, plv);
			}//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");
	}
}