1. 首页
  2. 文章中心
  3. 编译原理

【编译原理与技术】递归下降语法分析器（C++实现）内容：具体实现：运行结果：

92 阅读 0 评论
我是靠谱客的博主 痴情老虎，最近开发中收集的这篇文章主要介绍【编译原理与技术】递归下降语法分析器（C++实现）内容：具体实现：运行结果：，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

目录

  • 内容：
    • 示例：
  • 具体实现：
    • C++代码：
  • 运行结果：

内容：

实现以下语法的递归下降分析：
在这里插入图片描述
在这里插入图片描述在这里插入图片描述

示例：

对于以下代码给出其递归下降语法分析过程：

{
	i=2;
	while(i<=100)
	{
		sum=sum+i;
		i=i+2;
	}
}

在这里插入图片描述

具体实现：

  • 首先对上下文无关文法进行检查，消除左递归和左公共因子，从逻辑上检测避免死循环和低效率处理。
  • 采用每个产生式的左边的文法符号对应一个函数或过程的形式，编写程序实现一个递归下降分析器。
  • 语法分析是在词法分析的基础上进行的（关于词法分析的实现，具体参见我的上篇博客->【编译原理与技术】词法分析器（C++实现））。

C++代码：

#include<cstdio>
#include<cstring>
#include<ctype.h>
#include<iostream>
using namespace std;
char prog[1000],ch,ch1,token[1000],filename[30];
int p=0,sym=0,n,line=1;
FILE *fpin;
const char *keyword[22]={"if","else","while","do","main","int","float","for"
 						"double","return","const","void","continue","break","char",
						 "signed","enum","long","switch","case","auto","unsigned"};
char keywordtable[20][20];                 //存放保留字
char digittable[20][20];                   //存放数字
char otherchartable[20][20];           		//存放其他字符
char idtable[20][20];                        //存放标识符
char notetable[20][20];                      //存放注释
char finaltable[100][20];              		//存放终结符
int finaltableint[100];
char word[20];
void initialize();
void alpha();
void digit();
void error();
void otherchar();
void note();
void program();
void block();
void stmts();
void stmt();
void Bool();
void expr();
void expr1();
void term();
void term1();
void factor();
void YufaBegin();
void CifaBegin();
void GetToken();
void match(string str);
int digit_num=0,keyword_num=0,otherchar_num=0,id_num=0,note_num=0;
int final_num=0,finalnum=0;
int flag_error=0;                                  //0表示没有错误，1表示有错误 
int flagerror=0;

int main()
{
    cout<<"请输入源文件名:";
 	while(1)
 	{
 		cin>>filename;
 		if((fpin=fopen(filename,"r"))!=NULL)//只读	
 		{ 	
			break;
		}		
		else
			cout<<"文件输入错误！请输入源文件名：";	
	}
	//将文件内容存储到prog中 
	do
	{
		ch=fgetc(fpin);
	 	prog[p++]=ch;
	}while(ch!=EOF);
	//调用词法分析部分 
	printf("-----------------n");
	printf("词法分析结果如下:n");
	rewind(fpin);
	ch=fgetc(fpin);
	CifaBegin();
    //调用语法分析部分
	rewind(fpin); 
    ch=fgetc(fpin);		
	initialize();
    YufaBegin();
	return 0;
}  
void YufaBegin(){
	p=0;
	while(1)
    {	
    	ch=prog[p++];  
		if(ch==EOF) break;            
    	if(isalpha(ch)||ch=='_')                    
		                                          //a-z或A-Z时返回非零值(不一定是1)，否则返回零 
    	{
    		alpha();
    		initialize();
		}
		else if(isdigit(ch))               //用来判断字符lookahead是否为数字 
		{
			digit();
			initialize();
		}
		else if(ch=='t'||ch==' '||ch=='n')
		{
			continue;
		}
		else if(ch=='/')
		{
			ch=prog[p++];
			if(ch=='*'||ch=='/')
			{
				note();
				initialize();
			}
			else
			{
				p--;                          					//把一个字符退回到输入流中
				                                                  //lookahead是写入的字符，stdin是文件流指针 
				strcpy(finaltable[final_num],"/");                //将"/"放到终结符号表中 
				strcpy(otherchartable[otherchar_num++],"/");      //将"/"放到其他符号表中 
				finaltableint[final_num++]=2;                     //"/"的序号是2 
				initialize();
			}
		}
		/*else if(ch=='#'){
			break;
		}*/
		else
		{
			otherchar();
			initialize();
		}
	}
	if(flag_error==0)
	{
		finaltableint[final_num]='';
		printf("--------------------");
		printf("n语法分析过程如下:n");
		program();
		if(finalnum==final_num)
            printf("语法分析完成！");		
	}
}  
void alpha()
{
    int i=0,flag;
	word[i++]=ch;
	ch=prog[p++];
	while(isalpha(ch)||isdigit(ch))                                //将标识符放到word数组中 
	{
		word[i++]=ch;
		ch=prog[p++];
	}	
	p--;
	flag=0;
	for(i=0;i<21;i++)
	{
		if(strcmp(word,keyword[i])==0){
			flag=1;
			break;
		}
		
	}
	//在这里我只实现了部分保留字，大家可根据要求自行增删
	if(flag==1)
	{
		strcpy(keywordtable[keyword_num++],word);
		strcpy(finaltable[final_num],word);
		if(strcmp(word,"if")==0)
		    finaltableint[final_num++]=100;
		if(strcmp(word,"for")==0)
		    finaltableint[final_num++]=200;
		if(strcmp(word,"else")==0)
		    finaltableint[final_num++]=300;
		if(strcmp(word,"while")==0)
		    finaltableint[final_num++]=400;
		if(strcmp(word,"do")==0)
		    finaltableint[final_num++]=500;
		if(strcmp(word,"float")==0)
		    finaltableint[final_num++]=600;
		if(strcmp(word,"int")==0)
		    finaltableint[final_num++]=700;
		if(strcmp(word,"break")==0)
		    finaltableint[final_num++]=800;
	}
	else
	{
		strcpy(idtable[id_num++],word);
		strcpy(finaltable[final_num],"id");
		finaltableint[final_num++]=1;
	}
}
void initialize()
{
	for(int i=0;i<20;i++)
	{
		word[i]='';
	}
}
void digit()
{
 	int i=0,flag;
 	word[i++]=ch;
 	ch=prog[p++];
 	while(isdigit(ch))
	{
		word[i++]=ch;
		ch=prog[p++];
	}	
	p--;
	strcpy(digittable[digit_num++],word);
	strcpy(finaltable[final_num],"num");//数字数组，序号为99 
	finaltableint[final_num++]=99;
	
}	
void note()
{
	int i=0;
	while(1)
	{
		if(ch=='*')
		{
			ch=prog[p++];
			if(ch=='/')
			   break;
			else
			{
			   p--;
			   word[i++]=ch;	
			}  
		}
		else if(ch=='n'){
			break;
		}
		else
		{
			word[i++]=ch;
		}
		ch=prog[p++];
	}
	strcpy(notetable[note_num++],word);//将注释的内容放入注释表 
}
void otherchar()
{
	switch(ch){
	case '!':
		{
			ch=prog[p++];
			if(ch=='=')
			{
				strcpy(otherchartable[otherchar_num++],"!=");
				strcpy(finaltable[final_num],"!=");
				finaltableint[final_num++]=3;
			}
			else
			{
				p--;
				error();
			}
		}
		break;
	case '=':
	    {
		    ch=prog[p++];
		    if(ch=='=')
	    	{
			    strcpy(otherchartable[otherchar_num++],"==");
				strcpy(finaltable[final_num],"==");
				finaltableint[final_num++]=4;
		    }
		    else
		    {
		    	strcpy(otherchartable[otherchar_num++],"=");
				strcpy(finaltable[final_num],"=");
				finaltableint[final_num++]=5;
				p--;
			}
		}
		break;
	case '(':
		strcpy(otherchartable[otherchar_num++],"(");
		strcpy(finaltable[final_num],"(");
		finaltableint[final_num++]=6;
		break;
	case ')':
		strcpy(otherchartable[otherchar_num++],")");
		strcpy(finaltable[final_num],")");
		finaltableint[final_num++]=7;
		break;
	case ';':
		strcpy(otherchartable[otherchar_num++],";");
		strcpy(finaltable[final_num],";");
		finaltableint[final_num++]=8;
		break;
	case '{':
		strcpy(otherchartable[otherchar_num++],"{");
		strcpy(finaltable[final_num],"{");
		finaltableint[final_num++]=9;
		break;
	case '}':
		strcpy(otherchartable[otherchar_num++],"}");
		strcpy(finaltable[final_num],"}");
		finaltableint[final_num++]=10;
		break;
	case '|':
		{
			ch=prog[p++];
			if(ch=='|')
			{
				strcpy(otherchartable[otherchar_num++],"||");
				strcpy(finaltable[final_num],"||");
				finaltableint[final_num++]=11;
			}
			else
			{
				p--;
				error();
			}
		
		} 
		break;
	case '&':
		{
			ch=prog[p++];
			if(ch=='&')
			{
				strcpy(otherchartable[otherchar_num++],"&&");
				strcpy(finaltable[final_num],"&&");
				finaltableint[final_num++]=12;
			}
			else
			{
				p--;
				error();
			}
		} 
		break;
	case '+':
		strcpy(otherchartable[otherchar_num++],"+");
		strcpy(finaltable[final_num],"+");
		finaltableint[final_num++]=13;
		break;
	case '-':
		strcpy(otherchartable[otherchar_num++],"-");
		strcpy(finaltable[final_num],"-");
		finaltableint[final_num++]=19;
		break;
	case '>':
		{
			ch=prog[p++];
			if(ch=='=')
			{
				strcpy(otherchartable[otherchar_num++],">=");
		        strcpy(finaltable[final_num],">=");
				finaltableint[final_num++]=14;
			}
			else
			{
				strcpy(otherchartable[otherchar_num++],">");
				strcpy(finaltable[final_num],">");
				finaltableint[final_num++]=15;
				p--;
			}
		}
		break;
	case '<':
		{
			ch=prog[p++];
			if(ch=='=')
			{
				strcpy(otherchartable[otherchar_num++],"<=");
		        strcpy(finaltable[final_num],"<=");
				finaltableint[final_num++]=16;
			}
			else
			{
				strcpy(otherchartable[otherchar_num++],"<");
				strcpy(finaltable[final_num],"<");
				finaltableint[final_num++]=17;
				p--;
			}
		}
		break;
	case '*':
		strcpy(otherchartable[otherchar_num++],"*");
		strcpy(finaltable[final_num],"*");
		finaltableint[final_num++]=18;
		break;
	default:
		error();
		break;
	}
}
void error()
{
	flag_error=1;
	printf("出现错误，停止分析！n");
}
void program()
{
	printf("program-->blockn");
	block();
	if(flagerror==1)
	{
		error();
		return;
	}
}
void block()
{
	if(flagerror==1)
	{
		return;
	}
	printf("block-->{stmts}n");
	match("{");
	stmts();
	match("}"); 
}
void stmts()
{
	if(flagerror==1)
	{
		return;
	}
	//cout<<"stmts():"<<finaltableint[finalnum]<<endl;
	if(finaltableint[finalnum]==10)
	{
		printf("stmts-->nulln");
		return;
	}
	printf("stmts-->stmt stmtsn");
	stmt();
	stmts();
}
void stmt()
{
	if(flagerror==1)
	{
		return;
	}
	//cout<<"stmt():"<<finaltableint[finalnum]<<endl;
	switch(finaltableint[finalnum])
	{
	case 1:
		printf("stmt-->id=expr;n");
		match("id");
		match("=");
		expr();
		match(";");
		break;
	case 100:
		match("if");
		match("(");
		Bool();
		match(")");
		stmt();
		if(strcmp(finaltable[finalnum],"else")==0)
		{
			printf("stmt-->if(bool) stmt else stmtn");
			match("else");
			stmt();
			break;
		}
		else
		{
		    printf("stmt-->if(bool) stmtn");
			break;	
		}
	case 400:
		printf("stmt-->while(bool) stmtn");
		match("while");
		match("(");
		Bool();
		match(")");
		stmt();
		break;
	case 500:
		printf("stmt-->do stmt while(bool)n");
		match("do");
		stmt();
		match("while");
		match("(");
		Bool();
		match(")");
		break;
	case 800:
		printf("stmt-->breakn");
		match("break");
		break;
	default:
		printf("stmt-->blockn");
		block();
		break;
	}
}
void Bool()
{
	if(flagerror==1)
	{
		return;
	}
	expr();
	switch(finaltableint[finalnum])
	{
	case 17:
		printf("bool-->expr < exprn");
		match("<");
		expr();
		break;
	case 16:
		printf("bool-->expr <= exprn");
		match("<=");
		expr();
		break;
	case 15:
		printf("bool-->expr > exprn");
		match(">");
		expr();
		break;
	case 14:
		printf("bool-->expr >= exprn");
		match(">=");
		expr();
		break;
	default:
		printf("bool-->exprn");
		expr();
		break;
	}
}
void expr()
{
	if(flagerror==1)
	{
		return;
	}
	printf("expr-->term expr1n");
	term();
	expr1();
}
void expr1()
{
	if(flagerror==1)
	{
		return;
	}
	//cout<<"expr1():"<<finaltableint[finalnum]<<endl;
	switch(finaltableint[finalnum])
	{
	case 13:
		printf("expr1-->+term expr1n");
		match("+");
		term();
		expr1();
		break;
	case 19:
		printf("expr1-->-term expr1n");
		match("-");
		term();
		expr1();
		break;
	default:
		printf("expr1-->nulln");
		return;
	}
}
void term()
{
	if(flagerror==1)
	{
		return;
	}
	printf("term-->factor term1n");
	factor();
	term1();
} 
void term1()
{
	if(flagerror==1)
	{
		return;
	}
	//cout<<"term1():"<<finaltableint[finalnum]<<endl;
	switch(finaltableint[finalnum])
	{
	case 18:
		printf("term1-->*factor term1n");
		match("*");
		factor();
		term1();
		break;
	case 2:
		printf("term1-->/factor term1n");
		match("/");
		factor();
		term1();
		break;
	default:
		printf("term1-->nulln");
		return;
	}
}
void factor()
{
	if(flagerror==1)
	{
		return;
	}
	//cout<<"factor():"<<finaltableint[finalnum]<<endl;
	switch(finaltableint[finalnum])
	{
	case 6:
		printf("factor-->(expr)n");
		match("(");
		expr();
		match(")");
		break;
	case 1:
		printf("factor-->idn");
		match("id");
		break;
	case 99:
		printf("factor-->numn");
		match("num");
		break;
	default:
		flagerror=1;
		break;
	}
}
void match(string str)
{
	char cha[20];
	for(int i=0;i<20;i++){
		cha[i]='';
	}
	for(int k=0;k<str.length();k++){
		cha[k]=str[k];
	}
	//cout<<finaltable[finalnum]<<endl;
	//cout<<cha<<endl;
	if(strcmp(finaltable[finalnum],cha)==0){
		//cout<<"1"<<endl;
	}
	else
	{
		flagerror=1;
		return;
	}
	finalnum++;
}


//--------------
//词法分析器部分 
void CifaBegin()
{
	p=0;
	do 
	{
		GetToken();//启动字符识别函数 
		//if(ch==EOF) break; 
		switch(sym)//打印字符状态 
		{
			case 1:cout<<"("<<line<<" "<<token<<" "<<"标识符"<<")"<<endl;break;
			case 2:cout<<"("<<line<<" "<<token<<" "<<"保留字"<<")"<<endl;break;
			case 3:cout<<"("<<line<<" "<<token<<" "<<"整型"<<")"<<endl;break;
			case 31:cout<<"("<<line<<" "<<token<<" "<<"浮点型"<<")"<<endl;break;
			case 32:cout<<"("<<line<<" "<<token<<"S"<<" "<<"短类型"<<")"<<endl;break;
			case 33:cout<<"("<<line<<" "<<token<<"L"<<" "<<"长类型"<<")"<<endl;break;
			case 34:cout<<"("<<line<<" "<<token<<"O"<<" "<<"八进制数"<<")"<<endl;break;
			case 35:cout<<"("<<line<<" "<<token<<"H"<<" "<<"十六进制数"<<")"<<endl;break;
			case 4:cout<<"("<<line<<" "<<token<<" "<<"特殊符号"<<")"<<endl;break;
			case -1:cout<<"("<<line<<" "<<"错误！"<<")"<<endl;break;
			default:break;
		}
	}while(ch!=EOF);
	p=0;
}
void GetToken() 
{
 	sym=0;
	 //先把token[]数组清空 
 	for (n=0;n<1000;n++)
 	{
 		token[n]='';
	}
	n=0;
	ch=prog[p++];
	ch1=prog[p];
	//跳过空格，回车，tab的识别 
	while(ch==' '||ch=='t')
	{
		ch=prog[p++];
	}
	if(ch=='n'){
		line++;
		return;
	}
	if((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')||(ch=='_')) 
	{
		//标识符 状态1
		sym=1;
		do{
			token[n++]=ch;
			ch=prog[p++];
		}while ((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')||(ch>='0'&&ch<='9'));
		//比较标识符与keyword的关键字是否相同，若相同转为状态2
		for(n=0;n<2;n++)
		{
			if(strcmp(token,keyword[n])==0){
				sym=2;
				break;	
			}
		}
		p--;
		return;
	}
	
	else if (ch>='0'&&ch<='9') 
	{	
		//识别到数字，置状态为3
		sym=3;
		do
		{	
			token[n++]=ch;
			ch=prog[p++];
			if(ch=='.'){
				sym=31;
				token[n++]=ch;
				ch=prog[p++];
			}
			if(ch=='S'){
				sym=32;
				ch=prog[p++];
			} 
			if(ch=='L'){
				sym=33;
				ch=prog[p++];
			}
			if(ch=='O'){
				sym=34;
				ch=prog[p++];
			}	
			if(ch=='H'){
				sym=35;
				ch=prog[p++];
			}		
		}while(ch>='0'&&ch<='9'); 
		p--;
		return;
	}
	//跳过注释的内容 
	else if(ch=='/' && ch1=='*')
	{	
		p++;
		do{
			ch=prog[p++];
			ch1=prog[p++];
			if(ch=='n'){
				line++;
			}
		}while(ch!='*'||ch1!='/');
		return;
	}
	else if(ch=='/'&& ch1=='/')
	{
		p++;
		do{
			ch=prog[p++];
		}while(ch!='n');
		line++;
		return;
	}
	else if(ch=='='&& ch1=='='){
		p++;
		sym=4;
		token[0]='=';
		token[1]='=';
		return;
	}
	else if(ch=='<'&& ch1=='='){
		p++;
		sym=4;
		token[0]='<';
		token[1]='=';
		return;
	}
	else if(ch=='>'&& ch1=='='){
		p++;
		sym=4;
		token[0]='>';
		token[1]='=';
		return;
	}
	else if(ch=='!'&& ch1=='='){
		p++;
		sym=4;
		token[0]='!';
		token[1]='=';
		return;
	}		
	else if(ch=='&'&& ch1=='&'){
		p++;
		sym=4;
		token[0]='&';
		token[1]='&';
		return;
	}	
	else if(ch=='|'&& ch1=='|'){
		p++;
		sym=4;
		token[0]='|';
		token[1]='|';
		return;
	}
	else 
	{
		switch(ch)//识别关键符号 
		{	
			case '=':
			case '<':
			case '>':
			case '/':
			case '+':
			case '-':
			case '*':
			case '{':
			case '}':
			case ';':
			case '(':
			case ')':
			case ',':
			case ''':
			case '"':sym=4;token[0]=ch;break;
			default:sym=-1;break;
		}
	}
	return;
 }

运行结果：

在这里插入图片描述

最后

以上就是痴情老虎为你收集整理的【编译原理与技术】递归下降语法分析器（C++实现）内容：具体实现：运行结果：的全部内容，希望文章能够帮你解决【编译原理与技术】递归下降语法分析器（C++实现）内容：具体实现：运行结果：所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(61)

相关文章

编译原理-递归下降分析器
编译原理-递归下降分析器
编译原理实验二 递归下降语法分析器的构建
编译原理实验二 递归下降语法分析器的构建
编译原理实验-递归下降语法分析器的构建
编译原理实验-递归下降语法分析器的构建
编译原理｜递归下降分析子程序
编译原理｜递归下降分析子程序
【编译原理与技术】递归下降语法分析器（C++实现）内容：具体实现：运行结果：
【编译原理与技术】递归下降语法分析器（C++实现）内容：具体实现：运行结果：
消除文法的左递归和回溯1.自上而下分析2.直接左递归的消除3.直接左递归例题4.间接左递归的消除5.间接左递归例题6.消除回溯
消除文法的左递归和回溯1.自上而下分析2.直接左递归的消除3.直接左递归例题4.间接左递归的消除5.间接左递归例题6.消除回溯
回溯的消除
回溯的消除
《编译原理》实验预习报告——递归下降语法分析器的构建一、实验目的二、实验预习提示
《编译原理》实验预习报告——递归下降语法分析器的构建一、实验目的二、实验预习提示

评论列表共有 0 条评论

立即
投稿
返回
顶部