【编译原理】LR(1)分析法:C/C++实现

这篇具有很好参考价值的文章主要介绍了【编译原理】LR(1)分析法:C/C++实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

lr1分析器 c++实现,# 【编译原理】,c语言,c++,服务器,算法,数据结构,汇编🌈个人主页:Sarapines Programmer
🔥 系列专栏:《编译原理奇遇记》
🔖墨香寄清辞:空谷幽篁风动,梦中仙鹤月明。 辗转千秋豪情在,乘风翱翔志不移。

lr1分析器 c++实现,# 【编译原理】,c语言,c++,服务器,算法,数据结构,汇编

目录结构


1. 编译原理之LR(1)分析法概念

1.1 编译原理

1.2 LR(1)分析法

2. 逆波兰式的产生及计算

2.1 实验目的

2.2 实验要求

2.3.1 算法流程图

2.3.2 参考程序代码

2.3 实验内容

2.3.1 实验解决代码

2.3.2 程序解释

2. 实验心得

3.致各位


1. 编译原理之LR(1)分析法概念

1.1 编译原理

编译原理是计算机科学领域的一个重要分支,它研究如何将高级编程语言的源代码转化成计算机能够执行的机器代码或中间代码的过程。编译原理涵盖了编译器的设计和实现,其中编译器是一种将源代码翻译成目标代码的软件工具。编译器的主要任务包括语法分析、词法分析、语义分析、优化和代码生成等环节。

1.2 LR(1)分析法

LR(1)(Left-to-Right, Rightmost derivation with 1 symbol lookahead)分析法是一种用于构建分析器的语法分析方法,通常用于分析上下文无关文法的语法结构,属于LR分析法的一种变种。它是一种强大的自底向上语法分析方法,适用于具有一定复杂性的上下文无关文法,通过使用向前查看符号来处理文法中的二义性,使得可以更精确地分析和理解输入。

🔥资源获取:关注文末公众号回复  LR(1)分析法源码


2. 逆波兰式的产生及计算

2.1 实验目的

(1)构造LR(1)分析程序,并进行语法分析,判断给出的符号串是否为该文法识别的句子;

(2)了解LR(K)分析方法是严格的从左向右扫描,和自底向上的语法分析方法。

2.2 实验要求

1.对下列文法,用LR(1)分析法对任意输入的符号串进行分析:

(0)E->S

(1)S->BB

(2)B->aB

(3)B->b

2.LR(1)分析表为:

lr1分析器 c++实现,# 【编译原理】,c语言,c++,服务器,算法,数据结构,汇编

(1)若输入

baba#

则输出为:

lr1分析器 c++实现,# 【编译原理】,c语言,c++,服务器,算法,数据结构,汇编

(2)若输入

bb#

则输出为:

lr1分析器 c++实现,# 【编译原理】,c语言,c++,服务器,算法,数据结构,汇编

2.3.1 算法流程图

lr1分析器 c++实现,# 【编译原理】,c语言,c++,服务器,算法,数据结构,汇编

2.3.2 参考程序代码

参考代码(不完整):

/* ACTION表*/
char *action[10][3]={"S3#","S4#",NULL,

		      NULL,NULL,"acc",
		      "S6#","S7#",NULL,
		      "S3#","S4#",NULL,
		      "r3#","r3#",NULL,
		       NULL,NULL,"r1#",
		      "S6#","S7#",NULL,
		       NULL,NULL,"r3#",
		      "r2#","r2#",NULL,
		       NULL,NULL,"r2#"};
/* GOTO表*/
int goto1[10][2]={1,2,
		  0,0,
		  0,5,
		  0,8,
		  0,0,
		  0,0,
		  0,9,
		  0,0,
		  0,0,
		  0,0};
char vt[3]={'a','b','#'};  /*存放终结符*/
char vn[2]={'S','B'};   /*存放非终结符*/
char *LR[4]={"E->S#","S->BB#","B->aB#","B->b#"};  /*存放产生式*/
/*输出状态栈、输出符号栈、输出输入串*/
do{	    y=z;m=0;n=0;              /*y,z指向状态栈栈顶*/	             
               g=top;j=0;k=0;		
              x=c[top];		
              count++;	 printf("%d\t",count);		
             while(m<=top1)                /*输出状态栈*/	
                 {printf("%d",a[m]);    m=m+1; }	printf("\t\t");
            while(n<=top2)                  /*输出符号栈*/
                 {printf("%c",b[n]);     n=n+1;   }	printf("\t\t");
            while(g<=top3)                 /*输出输入串*/
                 {printf("%c",c[g]);   g=g+1;     }   printf("\t\t");
     ……
   }while(action[y][j]!="acc"); 

/*查动作表*/
if(x= ='a')j=0;
if(x= ='b')j=1;
if(x= ='#')j=2;
if(action[y][j]==NULL)
      { printf("error\n");	    return;	}
else			
             strcpy(copy,action[y][j]); 

/*处理移进*/
if(copy[0]=='S')
       {	z=copy[1]-'0';     
          top1=top1+1;  top2=top2+1;			a[top1]=z;	b[top2]=x;			top=top+1;	i=0;			while(copy[i]!='#')
              {printf("%c",copy[i]);i++;}			printf("\n");		
        } 

/*处理归约*/
if(copy[0]=='r')
     { 	i=0;	
          while(copy[i]!='#')
                 {  printf("%c",copy[i]);	i++; }			
                    h=copy[1]-'0';	  
          strcpy(copy1,LR[h]);			
          if(copy1[0]= ='S')k=0;	
          if(copy1[0]= ='B')k=1;		
          l=strlen(LR[h])-4;			
          top1=top1-l+1;    top2=top2-l+1;      y=a[top1-1];	
          p=goto1[y][k];    a[top1]=p;     b[top2]=copy1[0];     z=p;
          printf("\t\t");			
          printf("%d\n",p);		
     }

2.3 实验内容

2.3.1 实验解决代码

根据参考代码修改如下:

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

/* ACTION表*/
char *action_table[10][3]={"S3","S4",NULL,
		      		NULL,NULL,"acc",
		      		"S6","S7",NULL,
		      		"S3","S4",NULL,
		      		"r3","r3",NULL,
		      		 NULL,NULL,"r1",
		      		"S6","S7",NULL,
		       		NULL,NULL,"r3",
		      		"r2","r2",NULL,
		       		NULL,NULL,"r2"};

/* GOTO表*/
int goto_table[10][2]={1,2,
				  0,0,
				  0,5,
				  0,8,
				  0,0,
				  0,0,
				  0,9,
				  0,0,
				  0,0,
				  0,0};
char vt[3]={'a','b','#'};  /*存放终结符*/
char vn[2]={'S','B'};   /*存放非终结符*/

struct Production{	//产生式类型定义
  	char alp;	//大写字符
	char array[10];	//产生式右边字符
	int length;		//字符个数
};
Production production[4]; //存放产生式

int statueStack[10]; //状态栈
char symbolStack[10]; //符号栈
char input_string[10]; //输入串

int statueStackPointer = -1; //状态栈的指针 
int symbolStackPointer = -1; //符号栈的指针 
int inputStringPointer = 0; //输入串的指针 
int input_string_length = 0; //输入串的长度
int proce = 1;

bool input_judge();
void printAll();
void analyse();
void init();

int main(){
	bool input_right = false;
	while(!input_right){
		input_right = input_judge();
	}
	init();
	printf("步骤\t\t状态栈\t\t符号栈\t\t输入串\t\t");
	printf("Action\t\t");
	printf("Goto\n");
	printAll();
	analyse();
}

void printAll(){
	printf("%d\t\t",proce++);
		
	for(int i=0; i<=statueStackPointer;i++){ //输出状态栈
		printf("%d",statueStack[i]);
	}
	printf("\t\t");
	
	for(int i=0; i<=symbolStackPointer;i++){ /*输出符号栈*/
		printf("%c",symbolStack[i]);
	}
	printf("\t\t");
	
	for(int i=inputStringPointer; i<input_string_length;i++){ /*输出输入栈*/

		printf("%c",input_string[i]);
	}
	printf("\t\t");
}

void analyse(){
	int stop =  0;
	while(!stop){
		char store[10];
		char input = input_string[inputStringPointer]; //获取输入串的第一个字符 
		int col = -1;
		int row = statueStack[statueStackPointer];
		
/*查action表*/
		if(input=='a'){
			col=0;
		}
		if(input=='b'){
			col=1;
		}
		if(input=='#'){
			col=2;
		}
		if(action_table[row][col]==NULL){
			printf("err\n");
			exit(0);
		}

		else{
			strcpy(store,action_table[row][col]);
		}

		if(strcmp(store,"acc")==0){
			printf("acc\n");
			stop = 1;
			break;//结束 
		}
		
		/*移进*/ 
		else if(store[0]=='S'){
			statueStack[++statueStackPointer]=store[1]-'0';
			symbolStack[++symbolStackPointer]=input_string[inputStringPointer];
			inputStringPointer+=1;
			printf("%s\n",store);
			printAll();
		}
		
		
		/*归约*/
		else if(store[0]=='r'){
			int col = -1;
		    int index=store[1]-'0';
			if(production[index].alp=='S'){
				col=0;
			}
			else if(production[index].alp=='B'){
				col=1;
			}
			else{
				printf("err");
				exit(0);
			}

			int length = production[index].length; //表达式的字符长度
			statueStackPointer-=length; //状态栈出栈
			symbolStackPointer-=length; //符号栈出栈
			int row = statueStack[statueStackPointer]; //获取状态栈在出栈操作后的栈顶状态
			statueStack[++statueStackPointer]=goto_table[row][col]; //goto表中的状态进入状态栈 
			symbolStack[++symbolStackPointer]=production[index].alp; //表达式的左边的大写字母进入符号栈 
			printf("%s\t\t",store); 
			printf("%d\n",goto_table[row][col]);
			printAll(); 
		}
		else{ 
			printf("err!\n");
			exit(0);
		}
	}
}

void init(){
	struct Production a1,a2,a3,a4;
	a1.alp = 'E';
	strcpy(a1.array,"S");
	a1.length = 1;
	
	a2.alp = 'S';
	a2.length = 2;
	strcpy(a3.array,"BB");
	
	a3.alp = 'B';
	a3.length = 2;
	strcpy(a3.array,"aB");
	
	a4.alp = 'B';
	a4.length = 1;
	strcpy(a4.array,"b");
	
	production[0] = a1;
	production[1] = a2;
	production[2] = a3;
	production[3] = a4;
	
	statueStack[++statueStackPointer] = 0; //0
	symbolStack[++symbolStackPointer] = '#';//#
}

bool input_judge(){
	int j=0;
	char ch;
	printf("Input:");
	while(true){
		ch = getchar();
		if(ch=='\n'){
	    	break;
		}
	    input_string[j++] = ch;
    }
	
	for(int i=0; i<j; i++){
		ch = input_string[i];
		if(!((ch=='a')||(ch=='b'))){
			printf("输入有误\n");
			return false;
		}
	}
	
	input_string[j++] = '#';
	input_string_length = j;
	return true; 
}

输入正确的输入串:

abab

运行结果

lr1分析器 c++实现,# 【编译原理】,c语言,c++,服务器,算法,数据结构,汇编

输入错误的输入串:

abbaab

运行结果

lr1分析器 c++实现,# 【编译原理】,c语言,c++,服务器,算法,数据结构,汇编

程序分析:

1.定义了ACTION表和GOTO表,用于LR分析器的移进和归约操作,ACTION表和GOTO表使用二维数组表示,每个元素对应一个状态和终结符(ACTION表)或非终结符(GOTO表),存储了相应的操作信息。

2.定义了一些变量和数据结构,包括产生式结构体struct Production、状态栈statueStack、符号栈symbolStack、输入串input_string等。这些数据结构和变量在分析过程中用于保存中间状态和结果。

3. printAll函数用于打印当前分析步骤的状态栈、符号栈和输入串等信息。在每一步分析完成后,调用该函数打印出当前的状态。

4. analyse函数是LR分析的核心部分。通过一个while循环来不断执行移进和归约操作,直到达到终止条件。在每一步中,根据输入字符在ACTION表中查找相应的操作,并执行相应的移进或归约操作。如果遇到错误情况,则会输出错误信息并退出程序。

5. init函数用于初始化LR分析器的状态栈和符号栈,并定义了文法的产生式。在该函数中,首先定义了四个产生式,并将它们存储在production数组中。然后将初始状态0压入状态栈,并将终结符#压入符号栈。

6. input_judge函数用于获取输入串,并进行输入合法性检查。在函数中,首先通过getchar函数逐个读取字符,并存储在input_string数组中。读取过程会检查字符的合法性,只允许包含终结符a和b,否则会输出错误信息并返回false。最后,将终结符#添加到输入串的末尾,并更新输入串的长度。

7.在main函数中,首先进行输入串的合法性判断,然后进行初始化,并调用printAll函数打印初始状态。接着调用analyse函数执行LR分析,并且使用while循环来确保输入的字符串合法,即调用input_judge函数判断输入串是否符合要求。只有当输入串合法时,才会进行后续的初始化和分析过程。

LR分析的关键函数analyse函数:

void analyse(){
	int stop =  0;
	while(!stop){
		char store[10];
		char input = input_string[inputStringPointer]; //获取输入串的第一个字符 
		int col = -1;
		int row = statueStack[statueStackPointer];
		/*查action表*/
		if(input=='a'){
			col=0;
		}
		if(input=='b'){
			col=1;
		}
		if(input=='#'){
			col=2;
		}
		if(action_table[row][col]==NULL){
			printf("err\n");
			exit(0);
		}
		else{
			strcpy(store,action_table[row][col]);
		}

		if(strcmp(store,"acc")==0){
			printf("acc\n");
			stop = 1;
			break;//结束 
		}
		
		/*移进*/ 
		else if(store[0]=='S'){
			statueStack[++statueStackPointer]=store[1]-'0';
			symbolStack[++symbolStackPointer]=input_string[inputStringPointer];
			inputStringPointer+=1;
			printf("%s\n",store);
			printAll();
		}
		
		
		/*归约*/
		else if(store[0]=='r'){
			int col = -1;
		    int index=store[1]-'0';
			if(production[index].alp=='S'){
				col=0;
			}
			else if(production[index].alp=='B'){
				col=1;
			}
			else{
				printf("err");
				exit(0);
			}
			int length = production[index].length; //表达式的字符长度
			statueStackPointer-=length; //状态栈出栈
			symbolStackPointer-=length; //符号栈出栈
			int row = statueStack[statueStackPointer]; //获取状态栈在出栈操作后的栈顶状态
			statueStack[++statueStackPointer]=goto_table[row][col]; //goto表中的状态进入状态栈 
			symbolStack[++symbolStackPointer]=production[index].alp; //表达式的左边的大写字母进入符号栈 
			printf("%s\t\t",store); 
			printf("%d\n",goto_table[row][col]);
			printAll(); 
		}
		else{ 
			printf("err!\n");
			exit(0);
		}
	}
}

2.3.2 程序解释

1.int stop = 0; 声明并初始化一个变量stop,用于控制分析过程的终止条件。

2.while(!stop) 是一个循环,只有当stop为假时才执行循环体内的代码,即进行分析操作。

3.char store[10]; 声明一个字符数组store,用于存储从ACTION表中查找到的操作。

4.char input = input_string[inputStringPointer]; 获取输入串的第一个字符,并将其赋值给变量input。input_string[inputStringPointer]用于从输入串中获取当前位置的字符。

5.int col = -1; 初始化变量col为-1,用于记录当前字符在ACTION表中的列号。

6.int row = statueStack[statueStackPointer]; 获取状态栈的栈顶元素,即当前状态。

7.根据input的值来确定col的值,判断当前字符是终结符a、b还是结束符#。根据不同的情况,将col的值设置为相应的列号。

8.if(action_table[row][col]==NULL) 判断ACTION表中对应位置是否为空。如果为空,表示没有对应的操作,输出错误信息并退出程序。

9.else 分支执行当找到对应的操作时。

10.strcmp(store, "acc") == 0 判断是否是接受状态,即完成语法分析,成功匹配输入串。如果是接受状态,输出"acc",将stop设置为1,结束循环。

11.else if(store[0] == 'S') 判断是否是移进操作。如果是移进操作,执行以下操作:

  1. statueStack[++statueStackPointer] = store[1] - '0'; 将移进的状态压入状态栈。
  2. symbolStack[++symbolStackPointer] = input_string[inputStringPointer]; 将当前输入字符压入符号栈。
  3. inputStringPointer += 1; 将输入串指针向后移动一位。
  4. 输出移进操作的内容。
  5. 调用printAll函数打印当前分析步骤的状态。

12.else if(store[0] == 'r') 判断是否是归约操作。如果是归约操作,执行以下操作:

  1. int index = store[1] - '0'; 获取归约产生式的索引。
  2. 根据产生式的左部字符确定列号col。
  3. 获取归约产生式的长度length。
  4. 状态栈和符号栈出栈,出栈的个数为产生式的长度。
  5. 获取状态栈在出栈操作后的栈顶状态row。
  6. 将`goto_table[row][col]赋值给状态栈,表示归约后的新状态。
  7. 将产生式的左部字符压入符号栈。
  8. 输出归约操作的内容。
  9. 输出goto_table[row][col],即归约后的状态。
  10. 调用printAll函数打印当前分析步骤的状态。

13.else 分支表示无法识别的操作,输出错误信息并退出程序。

14.在循环的下一次迭代中,会继续执行分析过程,直到达到接受状态或发生错误导致程序退出。

函数analyse实现了LR分析表中的移进-归约算法。通过查找ACTION表中的操作,根据输入字符和当前状态来执行相应的操作。移进操作将状态和输入字符压入栈中,归约操作根据产生式进行出栈操作,并将新状态和产生式左部字符压入栈中。这个过程会一直进行,直到接受状态或发生错误。函数中的打印语句和调用printAll函数用于展示每一步的状态变化和操作。


2. 实验心得

在实验的代码实现过程中,定义了ACTION表和GOTO表,这两个表是LR(1)分析表的核心部分,其中ACTION表用于记录移进和归约操作,GOTO表用于记录状态之间的转移。这些表提供了对输入串和状态栈的操作指导。接着定义了产生式结构体,并初始化了产生式数组、状态栈、符号栈和输入串等变量。这些变量在分析过程中起着关键的作用。

主要的分析过程在函数analyse()中实现。这个函数使用了循环来逐步分析输入串,直到达到接受状态或发生错误。在每一步中,根据输入字符和当前状态,在ACTION表中查找相应的操作。如果是移进操作,将状态和输入字符压入栈中,并打印当前步骤的状态。如果是归约操作,根据产生式进行出栈操作,并将新状态和产生式左部字符压入栈中,并打印当前步骤的状态。如果无法识别操作,则输出错误信息并退出程序。

通过这次实验,我实现了基于LR(1)分析法的代码,深入理解了LR(1)分析法的过程和原理:LR(1)分析法能够处理具有一定复杂性的上下文无关文法,通过构建分析表和状态栈的运算来对输入串进行逐步分析和归约,最终确定是否能够根据给定的文法产生输入串。


3.致各位

许我人间三百年,更兼风雪路八千

lr1分析器 c++实现,# 【编译原理】,c语言,c++,服务器,算法,数据结构,汇编文章来源地址https://www.toymoban.com/news/detail-771758.html

到了这里,关于【编译原理】LR(1)分析法:C/C++实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【编译原理】LL(1)分析法:C/C++实现

      🌈 个人主页: Sarapines Programmer 🔥  系列专栏: 《编译原理奇遇记》 🔖墨香寄清辞:空谷幽篁风动,梦中仙鹤月明。 辗转千秋豪情在,乘风翱翔志不移。 目录结构 1. 编译原理之LL(1)分析法概念 1.1 编译原理 1.2 LL(1)分析法 2. LL(1)分析法 2.1 实验目的 2.2 实验要求 2.3 实验内

    2024年02月02日
    浏览(38)
  • 【编译原理】【C语言】实验三:递归下降分析法

    C语言 实验环境:Visual Studio 2019 author:zoxiii   用高级语言实现递归下降分析程序。使用输入串i*(i+i),输出分析栈中所有内容,并给出分析结果。   自顶向下分析就是从文法的开始符触发并寻找出这样一个推导序列:推导出的句子恰好为输入符号串;或者说,能否从根节

    2023年04月21日
    浏览(39)
  • 【编译原理】 实验三 LL(1)分析法(LL1分析表的自动生成)

    由于代码较长,csdn对文章总长度有字数限制,想只看完整代码的请移步另一篇博客。 https://blog.csdn.net/qq_46640863/article/details/125705891 理论与习题讲解移步视频 https://www.bilibili.com/video/BV1zu4y1C7SL 1.实现LL(1)分析算法 2.输入:教材中的算术表达式文法;待分析的语句(如i+i*i) 3.输

    2024年02月06日
    浏览(45)
  • [编译原理]DO-WHILE循环语句的翻译程序设计(LR(1)方法、输出四元式)C++实现

    初始条件: ​ 理论:完成编译原理,数据结构、高级编程语言、汇编语言等相关课程的学习,基于计算机专业知识进行课程设计。 ​ 实践:计算机实验室提供计算机及软件环境。如果自己有计算机及环境也可以在其上进行设计任务。 要求完成的主要任务: (包括课程设计工

    2024年02月03日
    浏览(51)
  • 层次分析法原理及实例(AHP)

    层次分析法(AHP) 层次分析法(analytic hierarchy process) ,简称AHP,是指将与决策总是有关的元素分解成目标、准则、方案等层次,在此基础之上进行定性和定量分析的决策方法。该方法是美国运筹学家匹茨堡大学教授萨蒂于20世纪70年代初,在为美国国防部研究\\\"根据各个工业

    2024年02月08日
    浏览(44)
  • 【编译原理】 实验一:词法分析器的自动实现(Lex词法分析)

    相关代码实操移步视频 https://www.bilibili.com/video/BV13x4y1o7FL 1.借助词法分析工具Flex或Lex完成(参考网络资源) 2.输入:高级语言源代码(如helloworld.c) 3.输出:以二元组表示的单词符号序列。 通过设计、编制、调试一个具体的词法分析程序,加深对词法分析原理的理解,并掌握

    2024年02月08日
    浏览(52)
  • 编译原理——语法分析器(C/C++代码实现)

    编写一个简单的LL(1)语法分析器。(注意:此实验是简化版的LL(1)文法,已给出预测分析表,不需要求FIRST和FOLLOW集,直接根据预测分析表编写程序即可) 根据编译原理理论课中学习的算术表达式文法,以及该文法LL(1)分析表,用C语言编写接受算术表达式为输入的语法

    2023年04月26日
    浏览(38)
  • 编译原理——SLR(1)语法分析器(C/C++代码实现)

    设计、编制、实现并调试SLR(1)语法分析器,加深对语法分析的理解。 根据编译原理理论课中学习的算术表达式文法以及该文法的LR分析表,用C语言编写接受算术表达式为输入的语法分析器,以控制台(或文本文件,也可以结合词法分析器完成)为输入,控制台(或文件)

    2024年02月11日
    浏览(39)
  • 【AHP层次分析法】原理+应用步骤+旅游目的地选择实例应用

    实现标准之间相对重要程度,并给出决策方案中每个标准的权重,利用权数求出各个方案的优劣次序。 1.建立层次结构模型 该层主要有三个方面: 目标层 准则层 领域层(各种解决问题的措施和方案) 这里选择了一个旅游问题的层次分析模型来直观的展示三个层的关系: 如

    2024年02月04日
    浏览(42)
  • 层次分析法(matlab实现)

           在决策理论中,层次分析法是一种以 数学 和 心理学 为基础,组织和分析复杂决策的结构化技术,它代表了一种 量化决策标准权重 的准确方法,通过成对比较,利用个别专家的经验来估计因素的相对大小        在很多情况下,我们对事物的评价,应该多维度的进

    2024年02月09日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包