递归下降分析LL（1）文法

134 阅读 0 评论 89 点赞

我是靠谱客的博主狂野鞋子，最近开发中收集的这篇文章主要介绍递归下降分析LL（1）文法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

今天做了编译原理实验
【实验内容】
（1）本分析程序所分析的文法如下：
G[E]：
E→eBaA
A→a|bAcB
B→dEd|aC
C→e|dC
（2）针对上述文法编写一递归子程序分析程序，该程序的输入是任意符号串，输出是本次输入的符号串是否是该文法的句子的结论。
测试样例为：eadeaa#
edeaebd#
edeaeaadabacae#

写了两个小时这个程序，我哭了。太菜了
输入函数：

void input(char **seq)
{
	char *seq1=(char*)malloc(sizeof(char)*2048);
	cout<<"请输入需要分析的子串"<<endl;
	seq1[0]=' ';
	int i=0;
	while(1)
	{	
		cin>>seq1[i];
		if(seq1[i]=='#'){
			break;
		}
		i++;
	}
	*seq=seq1;
}

检查字符匹配函数

int matchToken(char ch,char *seq)
{
	if(ch==seq[ll])
	{
		ll++;
		lookahead=seq[ll];
		return 1;
	}
	else
	{
		cout<<"字符不匹配"<<endl;
		return 0;
	}
}

各个非终结符的递归函数

int ParseE()
{
	if(lookahead=='e')
	{
		if(!matchToken('e',seq)){
			return 0;
		}
		if(!ParseB()){
			//cout<<"字符不匹配"<<endl;
			return 0;
		}
		if(!matchToken('a',seq)){
			return 0;
		}
		if(!ParseA())
		{
			//cout<<"字符不匹配"<<endl;
			return 0;
		}
		return 1;
	}
	else
	{
		cout<<"语法分析错误"<<endl;
		return 0;
	}

}
int ParseB()
{
	if(lookahead=='d')
	{
		if(!matchToken('d',seq)){
			return 0;
		}
		if(!ParseE())
		{
			//cout<<"字符不匹配"<<endl;
			return 0;
		}
		if(!matchToken('d',seq)){
			return 0;
		}
		return 1;
	}
	else if(lookahead=='a')
	{
		if(!matchToken('a',seq))
		{
			return 0;
		}
		if(!ParseC())
		{
			//cout<<"字符不匹配"<<endl;
			return 0;
		}
		return 1;
	}
	else
	{
		cout<<"语法分析错误"<<endl;
		return 0;
	}
}
int ParseC()
{
	if(lookahead=='e')
	{
		if(!matchToken('e',seq)){
			return 0;
		}
	}
	else if(lookahead=='d')
	{
		if(!matchToken('d',seq)){
			return 0;
		}
		if(!ParseC())
		{
			//cout<<"字符不匹配"<<endl;
			return 0;
		}
	}
	else
	{
		cout<<"语法分析错误"<<endl;
		return 0;
	}
	return 1;
}
int ParseA()
{
	if(lookahead=='a')
	{
		if(!matchToken('a',seq)){
			return 0;
		}
		return 1;
	}
	else if(lookahead=='b')
	{
		if(!matchToken('b',seq)){
			return 0;
		}
		if(!ParseA())
		{
			//cout<<"字符不匹配"<<endl;
			return 0;
		}
		if(!matchToken('c',seq)){
			return 0;
		}
		if(!ParseB())
		{
			//cout<<"字符不匹配"<<endl;
			return 0;
		}
		return 1;
	}
	else
	{
		cout<<"语法分析错误"<<endl;
		return 0;
	}

}

主函数

char lookahead;
int ll;
char *seq;
int main(){
	//int ll=0;
	ll=0;
	//char *seq;
	int flag=1;
	input(&seq);
	lookahead=seq[ll];
	if(!ParseE())
	{
	}
	else
	{
		cout<<"accept"<<endl;
	}
	cout<<"是否要继续输入 1:yes,0:no"<<endl;
	cin>>flag;
	while(flag)
	{
		memset(seq,NULL,20);
		ll=0;
		input(&seq);
		lookahead=seq[ll];
		if(!ParseE())
		{
		}
		else
		{
			cout<<"accept"<<endl;
		}
		cout<<"是否要继续输入 1:yes,0:no"<<endl;
		cin>>flag;
	}
	getchar();
	return 0;
}