ll1.cpp

LL1文法的实现

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
//===========================================================================================
typedef struct{
	char formule[6][15];			//用于存放产生式,从0到6对应+,*,(,),i,#;
	char word;						//用于存放非终结符
}Table;

typedef struct{						//定义栈(符号栈)
	char elem[20];					
	int top;
}SeqStack;

//==========================================================================================
char Letter[10];					 //定义全局变量，用来存放产生式里面出现的大写字母
char LessLetter[10];                 //存放产生式里面出现的终结符                  
int LetterNumber;	//存放非终结符的数目
int LessNumber;     //存放终结符的数目
int location;                        //存放express数组里的位置
int mark=0;							//作为标志位,mark=0 表示没有左递归 mark=1 表示存在左递归
char FIRST[10][15];					//存放非终结符的FIRST集合
char FOLLOW[10][15];				//存放非终结符的FOLLOW集合
int k1=0;
int step=0;                         //记录预测分析的步骤
SeqStack signStack;					//符号栈
//===========================================================================================
//函数声明
void Search(char express[][15],char a);
void First(char a[],char express[][15],int i,int s);
void Follow(char express[][15],char a);
//===========================================================================================
void init(char a[][15]){              //对数组进行初始化
	for(int i=0;i<10;i++)
		for(int j=0;j<15;j++)
			a[i][j]='\0';
}

void InitTable(Table analyse[]){//对预测分析表进行初始化
	int i,j,k;
	for(i=0;i<5;i++)
		for(j=0;j<6;j++)
			for(k=0;k<15;k++){
				analyse[i].word=' ';
				analyse[i].formule[j][k]='\0';
			}
}

void InitSeqStack(){				//对符号栈进行初始化
	int i;
	for(i=0;i<20;i++)
		signStack.elem[i]='\0';
	signStack.top=-1;
}
				
void input(char temp[][15],int number){
	for(int i=0;i<number;i++){
		printf("\n请输入第%d个产生式:",i+1);
		scanf("%s",temp[i]);
	}
}

void output(char temp[][15],int number){
	for(int i=0;i<number;i++)
		printf("%s\n",temp[i]);
}

bool IsLetter(char a){
	if((a<='Z')&&(a>='A'))
		return true;
	else
		return false;
}

bool judge(char a){					//判断字母a是否出现在终结字母表中
	int i;
	for(i=0;i<10;i++)
		if(a==Letter[i])
			return false;
	return true;
}

bool judgement(char a){				//判断字母a是否出现在终结字母表中
	int i; 
	for(i=0;i<10;i++)
		if(a==LessLetter[i])
			return false;
	return true;
}

void MakeLetter(char temp[][15],int number){  //生成非终结符字母表
	int i,j;
	for(i=0;i<number;i++)
		for(j=0;j<15;j++){
			if(IsLetter(temp[i][j])){//判断是否为非终结字符
				if(judge(temp[i][j]))
					Letter[LetterNumber++]=temp[i][j];
			}
		}
		Letter[LetterNumber]='\0';
}

void MakeLessLetter(char temp[][15],int number){			//生成终结符字母表
	int i,j;
	for(i=0;i<number;i++)
		for(j=3;j<15;j++){
			if(!IsLetter(temp[i][j])&&temp[i][j]!='|'){
				if(judgement(temp[i][j]))
					LessLetter[LessNumber++]=temp[i][j];
			}
		}
		LessLetter[LessNumber++]='#';
		LessLetter[LessNumber]='\0';
}

char DefineLetter(){						//查看还有那个大写字母没有在字母表中出现
	for(char ch='A';ch<='Z';ch++)
			if(judge(ch)){
				Letter[LetterNumber++]=ch;
				return ch;
			}
	return 'Z';
}

void remove(char temp[],int number,char express[][15]){   //消除左递归
	int i,j,r,k,t;
	char ch;
	for(i=0;i<15;i++)
		if(temp[i]=='|'){
			r=i;
			for(j=r+1;j<15;j++)
				if(temp[j]=='|'||temp[j]=='\0'){
					k=j;
					break;
				}
		}
	ch=DefineLetter();
	for(i=0;i<3;i++)
		express[location][i]=temp[i];
	for(t=r+1;t<k;t++)
		express[location][i++]=temp[t];
	express[location][i]=ch;
	location++;
	express[location][0]=ch;
	express[location][1]='-';
	express[location][2]='>';
	i=3;
	for(j=4;j<r;j++)
		express[location][i++]=temp[j];
	express[location][i++]=ch;
	express[location][i++]='|';
	express[location][i++]='@';
	location++;
	
}
		
void manage(char temp[][15],int number,char express[][15]){
	int i,j,t;
	int flag[10];      //作为标志位,flag=0 表示没有左递归 flag=1 表示存在左递归
	for(i=0;i<number;i++)
		flag[i]=0;//付初值，没有左递归
	for(i=0;i<number;i++)
		for(j=3;j<15;j++){
			if(temp[i][0]==temp[i][j]){//如果有左递归
				flag[i]=1;
				mark=1;
				t=j;
				remove(temp[i],number,express);
			}
		}//////////////////////////////////////////////////////////////////////////
		for(i=0;i<number;i++){
			if(flag[i]==0){
				for(j=0;j<15;j++)
					express[location][j]=temp[i][j];
				location++;
			}
		}
}

void Search(char express[][15],char a,int j){
	int i;
	for(i=0;i<location;i++)
		if(express[i][0]==a)
			First(express[i],express,i,j);
}

void First(char a[],char express[][15],int i,int s){						//求FIRST集合
	int j,k=0,t;
	if(IsLetter(a[3]))
		Search(express,a[3],s);
	else{
		FIRST[s][k++]=a[3];
		for(j=3;j<15;j++)
			if(a[j]=='|')
				FIRST[s][k++]=a[j+1];
		FIRST[s][k]='\0';
	}
	if(i!=s){	//表示求左递归时候进行了递归运算,即产生式右边第一个是非终结符
		for(t=0;t<15;t++)
			if(FIRST[s][t]=='@')
				First(a,express,i,s);
	}
}

void outFIRST(char express[][15]){						//将FIRST集合输出到屏幕上
	int i,j,k=0;
	printf("\nFIRST集合如下:\n");
	for(i=0;i<location;i++){
		printf("FIRST(%c)={",express[i][0]);
		for(j=0;j<15;j++)
			if(FIRST[i][j+1]=='\0'){
			printf("%c}\n",FIRST[i][j]);
			break;
			}
			else
				printf("%c,",FIRST[i][j]);
	
	}
}

bool estimate(char a[],char b){					//判断字母b是否在数组a中
	for(int i=0;i<15;i++)
		if(b==a[i])
			return true;
	return false;
}

void addFollow(int i,int j){						//将FOLLOW[i]加到FOLLOW[j]中
	int a;
	for(a=0;a<15;a++)
		if(!estimate(FOLLOW[j],FOLLOW[i][a]))
			FOLLOW[j][k1++]=FOLLOW[i][a];
}

void Solve(char express[][15],char a[],int p,int j){	
	int i,t,r,temp;
	k1=0;
	if(a[j+1]=='\0'){			//若FOLLOW[p]已经求出，则直接加入到FOLLOW[a[j]]中
		if(FOLLOW[p][0]!='\0'){
			for(int r=0;r<location;r++)
				if(express[r][0]==a[j]){
					temp=r;
					break;
				}
				addFollow(p,temp);
		}
		else
			Follow(express,express[p][0]);			//若FOLLOW[p]还没有求出，则先求出FOLLOW[p];
	}
	else if(!IsLetter(a[j+1])&&a[j+1]!='|'){
		if(a[j]==express[0][0]){
			k1++;
			FOLLOW[0][k1++]=a[j+1];
		}
		else{
			for(r=0;r<location;r++)
				if(express[r][0]==a[j]){
					FOLLOW[r][k1++]=a[j+1];
					break;
				}
		}
	}
	else if(IsLetter(a[j+1])){
		for(i=0;i<location;i++)
			if(express[i][0]==a[j+1]){
				for(int s=0;s<15;s++){
					if(express[i][s]=='@'&&express[i][s-1]=='|')	//若非终结符能直接推出@
						if(	FOLLOW[i][0]!='\0'){
							for(int r=0;r<location;r++)
								if(express[r][0]==a[j]){
									temp=r;
									break;
								}
							addFollow(i,temp);
						}
						else
							Follow(express,express[i][0]);
				}									          
				for(t=0;t<15;t++)				//将FIRST[a[j+1]]加入到FOLLOW[i]中    
					if(!estimate(FOLLOW[temp],FIRST[i][t]))
						if(FIRST[i][t]!='@')
							FOLLOW[temp][k1++]=FIRST[i][t];
			}
	}

}

void Follow(char express[][15],char a){					//求FOLLOW集合
	int i,j;
	if(a==express[0][0])				//若为开始符号则把#号加入到FOLLOW集合中
		FOLLOW[0][0]='#';
	for(i=0;i<location;i++)
		for(j=3;j<15;j++)
			if(express[i][j]==a&&express[i][0]!=a){
				Solve(express,express[i],i,j);
			}
}

void outFOLLOW(char express[][15]){						//将FIRST集合输出到屏幕上
	int i,j,k=0;
	printf("\nFOLLOW集合如下:\n");
	for(i=0;i<location;i++){
		printf("FOLLOW(%c)={",express[i][0]);
		for(j=0;j<15;j++)
			if(FOLLOW[i][j+1]=='\0'){
			printf("%c}\n",FOLLOW[i][j]);
			break;
			}
			else
				printf("%c,",FOLLOW[i][j]);
	
	}
}

bool opinion(char a,int i){							//判断字母a是否出现在FIRST集合中
	int j;
	for(j=0;j<15;j++)
		if(a==FIRST[i][j])
				return true;
	return false;
}

bool judgeFollow(char a,int i){					//判断字母a是否出现在FOLLOW集合中
	int j,k;
	for(j=0;j<15;j++)
		if(FIRST[i][j]=='@'){
			for(k=0;k<15;k++)
				if(a==FOLLOW[i][k])
					return true;
		}
	return false;
}
	
int Creat(Table &tab,char express[],int j){					//将产生式放入分析表中
	int i;
	tab.word=express[0];
	for(i=0;i<15;i++)
		if(express[i]=='|')
			if(express[i+1]==LessLetter[j]){
					tab.formule[j][0]=express[0];
					tab.formule[j][1]='-';
					tab.formule[j][2]='>';
					tab.formule[j][3]=LessLetter[j];
					return 1;
				}
	for(i=0;i<15;i++){
		if(express[i]!='|')
			tab.formule[j][i]=express[i];
		else
			break;
	}
	return 0;
}

void CreatTable(Table analyse[],char express[][15]){				//构造预测分析表
	int i,j;
	for(i=0;i<location;i++)
		for(j=0;j<LessNumber;j++)
			if(opinion(LessLetter[j],i))
				Creat(analyse[i],express[i],j);
			else{
				if(judgeFollow(LessLetter[j],i)){
					analyse[i].formule[j][0]=express[i][0];
					analyse[i].formule[j][1]='-';
					analyse[i].formule[j][2]='>';
					analyse[i].formule[j][3]='@';
				}
			}			
}

void outTable(Table analyse[]){				//输出预测分析表
	int i,j;
	printf("\n预测分析表如下:\n");
	for(j=0;j<LessNumber;j++)
		printf("\t%c",LessLetter[j]);
	printf("\n");
	for(i=0;i<5;i++){
		printf("%c\t",analyse[i].word);
		for(j=0;j<6;j++)
			printf("%s\t",analyse[i].formule[j]);
		printf("\n");
	}
}

bool judgeStack(char a){				//判断字母a与符号栈顶元素是否相同
	if(signStack.elem[signStack.top]==a)
		return true;
	return false;
}

int settle(char bunch[],Table analyse[],char express[][15]){
	int i,j,t,s,r;
	int flag=0;
	for(i=0;i<location;i++)
		if(express[i][0]==signStack.elem[signStack.top]){
			j=i;
			break;
		}
	if(judgeStack(bunch[0])&&bunch[0]=='#')			//如果符号栈顶为'#'且输入串也为'#'号时候结束，分析成功了。
		return 1;
	else if(judgeStack(bunch[0])){					//如果符号栈顶和输入串第一位相同，则把符号栈的栈顶元素弹出，且输入串第一位也删除
		for(i=0;i<10;i++)
			bunch[i-1]=bunch[i];
		signStack.elem[signStack.top]='\0';
		signStack.top--;
		printf("%d\t%s\t%s\t\n",step++,signStack.elem,bunch);
	}
	
	else{
			
			for(t=0;t<LessNumber;t++){
				if(bunch[0]==LessLetter[t]){
					s=t;
					if(analyse[j].formule[s][3]=='@'){					//如果对应的产生式为X->@,则直接把栈顶元素弹出，输入串不变
							signStack.elem[signStack.top]='\0';
							signStack.top--;
							flag=1;
							break;
						}
					else{
						for(r=15;r>=3;r--){						//找到符号栈顶和输入串第一位对应的产生式，将产生式右部反序压入到符号栈中
							if(analyse[j].formule[s][r]!='\0'){
								signStack.elem[signStack.top]=analyse[j].formule[s][r];
								signStack.top++;
							}
						}
					}
					if(flag==0)
						signStack.top--;
					break;
				}
			}
		printf("%d\t%s\t%s\t%s\n",step++,signStack.elem,bunch,analyse[j].formule[s]);
	}
	return 0;
	
}
	
void inputString(char bunch[],Table analyse[],char express[][15]){
	int i,j,k;
	printf("\n请输入要分析的句子:\n");
	scanf("%s",bunch);
	printf("\n利用预测分析表进行预测分析的步骤如下:\n");
	signStack.top++;   
	signStack.elem[signStack.top]='#';			//首先将'#'号压入符号栈
	signStack.top++;
	signStack.elem[signStack.top]=express[0][0];	//将开始符号压入栈顶
	printf("步骤\t符号栈\t输入串\t所用产生式\n");
	printf("%d\t%s\t%s\t\n",step++,signStack.elem,bunch);	//找到开始符号和输入串第一位对应的产生式，将产生式右部反序压入到符号栈中
	for(i=0;i<LessNumber;i++){
		if(LessLetter[i]==bunch[0]){
			j=i;
			for(k=15;k>=3;k--)
				if(analyse[0].formule[j][k]!='\0'){
					signStack.elem[signStack.top]=analyse[0].formule[j][k];
					signStack.top++;
				}
		}
	}
	printf("%d\t%s\t%s\t%s\n",step++,signStack.elem,bunch,analyse[0].formule[j]);
	signStack.top--;
	while(signStack.elem[signStack.top]!='#')
		settle(bunch,analyse,express);
	printf("分析成功!\n");
	
}
	
	
int main(){
	char temp[10][15];
	char express[10][15];
	int number; //记录文法里面产生式的个数
	int i;
	char bunch[10];	//存放输入串
	for(i=0;i<10;i++)
		bunch[i]='\0';
	Table analyse[5];		//存放预测分析表
	init(temp);
	init(express);
	init(FIRST);
	init(FOLLOW);
	InitTable(analyse);
	InitSeqStack();
	printf("\n**********************LL(1)文法的实现**************************\n");
	for(i=0;i<10;i++)
		Letter[i]='\0';//用来存放产生式里面出现的大写字母
	printf("\n请输入文法里面的产生式个数:");
	scanf("%d",&number);
	input(temp,number);//输入文法规则
	MakeLetter(temp,number);//存储非终结字符
	MakeLessLetter(temp,number);//存储终结字符
	manage(temp,number,express);//消除左递归
	if(mark==1){
		printf("\n文法存在左递归!\n");
		printf("消除左递归后的文法如下:\n");
		output(express,location);
	}
	for(i=0;i<location;i++)
		First(express[i],express,i,i);
	for(i=0;i<location;i++)
		Follow(express,express[i][0]);
	outFIRST(express);
	outFOLLOW(express);
	CreatTable(analyse,express);
	outTable(analyse);
	inputString(bunch,analyse,express);
	return 1;
}