gram.cpp

自上而下语法分析器设计

/*LL1分析器示例程序：见课本P76*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include "gram.h"
#include "istack.h"

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

/*以下变量用于语法分析*/
//终结符符号表
V vt[]={			//注意顺序和LLTAB表列元素顺序对应一致
		"i",$INT,
		"+",$PLUS,
		"*",$MUL,
		"(",$LPAR,
		")",$RPAR,
		"-",$MINUS,
		"/",$DIV,
		"#",$END
};

//非终结符符号表
V vn[]={
		"E",$E,
		"E'",$EP,
		"T",$T,
		"T'",$TP,
		"F",$F
};
//文法的产生式集合
P pset[]={
		1,$E,{$T,$EP,0,0},//E->TE'
		2,$EP,{$PLUS,$T,$EP,0},//E'->+TE'
		3,$EP,{0,0,0,0},//E'->e
		4,$T,{$F,$TP,0,0},//T->FT'
		5,$TP,{$MUL,$F,$TP,0},//E'->-TE'
		6,$TP,{0,0,0,0},//T'->e
		7,$F,{$LPAR,$E,$RPAR,0},//F->(E)
		8,$F,{$INT,0,0,0},//F->i
        9,$EP,{$MINUS,$T,$EP,0},//T'->*FT'
		10,$TP,{$DIV,$F,$TP,0},//T'->/FT'
		0,0,0	//结束
};

//LL1分析表,表中元素为产生式的编号
int lltab[7][8] = {
	//  i,+,*,(,),#
	//	1,0,0,1,0,0,  //E
	//	0,2,0,0,3,3,  //E'
	//	4,0,0,4,0,0,   //T
	//	0,6,5,0,6,6,   //T'
	//	8,0,0,7,0,0    //F
		
    //  i,+,*,-,/,(,),#
        1,0,0,0,0,1,0,0,  //E
		0,2,0,9,0,0,3,3,  //E'
		4,0,0,0,0,4,0,0,   //T
		0,6,5,6,10,0,6,6,   //T'
	    8,0,0,0,0,7,0,0    //F
};

/*函数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 if (ch == '-')
	{
		strToken[0] = '-';
		return $MINUS;
	}
	else if (ch == '/')
	{
		strToken[0] = '/';
		return $DIV;
	}
	
	else
	{
		strToken[0] = ch;
		sym.code = $UNKNOWN;
	}
	return sym.code;
}

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 LL1()
{
	int token;//输入符号
	int vs;	//栈顶符号
	int *pr;//产生式右部
	int temp;
	istack tmpstack(10);
	//分析栈
	istack llstack(256);


	llstack.push($END);
	llstack.push($E);
	token = Lex();
	do{
		vs = llstack.pop();
		if (vs < 100)
		{//终结符
			if (vs == token)
			{
				//printf("匹配%s\n",vt[vs-1].name);
				token = Lex();
			}
			else
				ProcError();
		}
		else
		{
			temp = lltab[vs-100][token-1];	//temp为产生式编号
			if (temp > 0)
			{
				pr = pset[temp-1].right;
				printf("推导:%s->", vn[vs-100].name);
				while(*pr != 0)
				{
					tmpstack.push(*pr);
					//输出产生式
					if (*pr >= 100)
						printf("%s", vn[*pr-100].name);
					else
						printf("%s", vt[*pr-1].name);
					pr++;
				}
				printf("\n");
				while ((temp = tmpstack.pop()) != -1)
				{
					llstack.push(temp);
				}
			}
			else
			{
				ProcError();
				return FAIL;
			}
		}
	}while(vs != $END);
	return SUCCESS;
}

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 (LL1() == SUCCESS)
			printf("分析成功，没有语法错误\n");
		printf("退出吗？(y/n)");
		if (toupper(getch()) == 'Y')
			quit = true;
		printf("\n");
	}
}