预测分析法进行语法分析(编译原理)

2024-06-19 10:18

本文主要是介绍预测分析法进行语法分析(编译原理),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

预测分析法是一种表驱动的方法,它由下推栈,预测分析表和控制程序组成。实际上是一种下推自动机的实现模型。预测分析法的关键为预测分析表的构建,即文法中各非终结符first集和follow集的求得。预测分析法从开始符号开始,根据当前句型的最左边的非终结符和分析串中的当前符号,查预测分析表确定下一步推导所要选择的产生式,最终得到输入串的最左推导,完成输入串的语法检查。

其中主要建立first集,follow集合用来消除左递归(较难)

输入文本:

E T F
+ * ( ) i


E->E+T|T
T->T*F|F
F->(E)|i


(i)*i
(i)*iii


源码(C语言版)

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>#ifndef success
#define success 1
#endif#define MAX_AMOUNT 20/*定义非终结符*/
typedef struct NOterminal
{char character;int  first_number;/*FIRST集的判定,初始为0*/int  follow_number;/*FOLLOW集的判定,初始为0*/char * FIRST;/*FIRST 集合*/char * FOLLOW;/*FOLLOW集合*/struct NOterminal *next;
} noterminal;/*定义终结符*/
typedef struct Terminal
{char  character;/*当前的字符*/struct Terminal *next;
} terminal;/*定义产生式*/
typedef struct PRODUCTION
{char source;/*产生的开始*/char * result;/*产生的结果*/struct PRODUCTION *next;/*指向下一条`*/
} production;int amount=0;
char TEST_STACK[20];
char* TEST_LIST[10];
char terminal_all[10]= {0};
terminal   TERMINAL_HEAD,   *current_terminal=&TERMINAL_HEAD;
noterminal NOTERMINAL_HEAD, *current_noterminal=&NOTERMINAL_HEAD;
production PRODUCTION_HEAD, *current_production=&PRODUCTION_HEAD;/*函数申明*/
size_t read(void);
size_t test(void);
size_t write(void);
void Test_read(void);
size_t STACK_FULL();
void STACK_POP(void);
size_t STACK_EMPTY();
void init_stack(void);
void prediction(void);
void test_follow(void);
void emergency(int model);
void prediction_table(void);
void STACK_PUSH(char source);
void insert_to_terminal(char get);
void insert_to_noterminal(char get);
void eliminate_left_recursion(void);
void combine(char* destinction,char* source);
size_t is_appeared(char tobejudged,char*source);
void insert_to_production(char source , char* result);
size_t find_first(noterminal* this_noterminal,production *this_production);
size_t find_follow(noterminal* this_noterminal,production *this_production);int main(void)
{TERMINAL_HEAD.next=NULL;NOTERMINAL_HEAD.next=NULL;PRODUCTION_HEAD.next=NULL;read();Test_read();printf("\n消除左递归\n\n");eliminate_left_recursion();Test_read();printf("\n求FIRST集\n\n");prediction();printf("\n求FOLLOW集\n\n");test_follow();prediction_table();emergency(0);return 0;
}/*读文件*/
size_t read(void)
{int line=0,model=0,old_line=0;int number=0;char current_get=0,read_temp[10]= {0};FILE * read_stream=fopen("test1.txt","r");if(!read_stream){printf("error in open file ,can`t open file\n");exit(EXIT_FAILURE);}insert_to_terminal('#');/*插入栈底元素,以#表示栈底*/insert_to_terminal('^');/*插入空串元素,以^表示栈底*/while(!feof(read_stream)){current_get=fgetc(read_stream);while(current_get==' ')current_get=fgetc(read_stream);/*忽略空格*/while(current_get=='\n'){current_get=fgetc(read_stream);line++;/*跳过换行*/}switch(line){case 0:insert_to_noterminal(current_get);break;case 1:insert_to_terminal(current_get);break;case 3:ungetc(current_get,read_stream);old_line=1;break;default:perror("error in format of program \n");emergency(0);break;}if(old_line)break;}while(!feof(read_stream)){memset(read_temp,0,sizeof(read_temp));old_line=line;current_get=fgetc(read_stream);while(current_get==' ')current_get=fgetc(read_stream);/*忽略空格*/while(current_get=='\n'){current_get=fgetc(read_stream);line++;/*跳过换行*/}model=((line-old_line)>model)? (line-old_line): model;switch(model){case 0:case 1:fscanf(read_stream,"%s",read_temp);insert_to_production(current_get,read_temp);break;case 2:ungetc(current_get,read_stream);TEST_LIST[number]=(char*)malloc(20);memset(TEST_LIST[number],0,20);fscanf(read_stream,"%s",TEST_LIST[number++]);break;default:perror("error in format of program \n");emergency(1);break;}}fclose(read_stream);return success;
}
/*测试*/
size_t test(void)
{noterminal *TEMP_NOTERMINAL=NOTERMINAL_HEAD.next;for(; TEMP_NOTERMINAL!=NULL; TEMP_NOTERMINAL=TEMP_NOTERMINAL->next){printf("%c\tfirst number=%d\tfirst=%s\n",TEMP_NOTERMINAL->character,TEMP_NOTERMINAL->first_number,TEMP_NOTERMINAL->FIRST);}printf("\n");return success;
}/*求FIRST集合*/
size_t find_first(noterminal* this_noterminal,production *this_production)
{noterminal* this_noterminal_temp;char temp[2]= {0};char *TEMP2,*help;while(this_production->source!=this_noterminal->character)this_production=this_production->next;/*移向下一个产生式*//*查看是否是第一次,如果是,分配空间*/if(this_noterminal->first_number==0){this_noterminal->FIRST=(char*)malloc(MAX_AMOUNT+1);memset(this_noterminal->FIRST,0,MAX_AMOUNT+1);}while(this_production&&this_production->source==this_noterminal->character){TEMP2=this_production->result;while(*TEMP2){if(is_appeared(*TEMP2,terminal_all)){temp[0]=this_production->result[0];combine(this_noterminal->FIRST,temp);break;}else{this_noterminal_temp=NOTERMINAL_HEAD.next;while(this_noterminal_temp->character!=*TEMP2)this_noterminal_temp=this_noterminal_temp->next;if(this_noterminal_temp->first_number==0)/*没求first集*/find_first(this_noterminal_temp,PRODUCTION_HEAD.next);combine(this_noterminal->FIRST,this_noterminal_temp->FIRST);help=this_noterminal->FIRST;while(*help&&*help!='^')help++;if(*help&&*(TEMP2+1))/*包含'^'*/{while(*help){*help=*(help+1);help++;}}else break;TEMP2++;}}this_production=this_production->next;}this_noterminal->first_number=strlen(this_noterminal->FIRST);return success;
}/*求FOLLOW集合*/
size_t find_follow(noterminal* this_noterminal,production *this_production)
{char* help=NULL;char* temp_result;int symbol=0;char terminal_array[2]= {0};noterminal* FOLLOW_TEMP,*FOLLOW_HELP;if(this_noterminal->follow_number==0){this_noterminal->FOLLOW=(char* )malloc(MAX_AMOUNT+1);memset(this_noterminal->FOLLOW,0,MAX_AMOUNT+1);}/*第一个非终结符包含有#*/if(this_noterminal==NOTERMINAL_HEAD.next)*this_noterminal->FOLLOW='#';while(this_production){temp_result=this_production->result;/*一个产生式未结尾*/while(*temp_result){if(*temp_result!=this_noterminal->character){temp_result++;continue;}temp_result++;if(!*temp_result)symbol=1;while(*temp_result){if(is_appeared(*temp_result,terminal_all)){terminal_array[0]=*temp_result;combine(this_noterminal->FOLLOW,terminal_array);}else{FOLLOW_TEMP=NOTERMINAL_HEAD.next;while(FOLLOW_TEMP->character!=*temp_result)FOLLOW_TEMP=FOLLOW_TEMP->next;combine(this_noterminal->FOLLOW,FOLLOW_TEMP->FIRST);help=this_noterminal->FOLLOW;while(*help&&*help!='^')help++;if(*help)/*包含'^'*/{while(*help){*help=*(help+1);help++;}symbol=1;}else{symbol=0;break;}}temp_result++;}if(symbol&&this_production->source!=this_noterminal->character){FOLLOW_HELP=NOTERMINAL_HEAD.next;while(FOLLOW_HELP->character!=this_production->source)FOLLOW_HELP=FOLLOW_HELP->next;if(FOLLOW_HELP->follow_number==0)find_follow(FOLLOW_HELP,PRODUCTION_HEAD.next);combine(this_noterminal->FOLLOW,FOLLOW_HELP->FOLLOW);symbol=0;}}this_production=this_production->next;}this_noterminal->follow_number=strlen(this_noterminal->FOLLOW);return success;
}/*紧急退出*/
void emergency(int model)
{current_noterminal=NOTERMINAL_HEAD.next;current_terminal=TERMINAL_HEAD.next;current_production=PRODUCTION_HEAD.next;while(current_noterminal){NOTERMINAL_HEAD.next=current_noterminal->next;free(current_noterminal->FIRST);free(current_noterminal->FOLLOW);free(current_noterminal);current_noterminal=NOTERMINAL_HEAD.next;}while(current_terminal){TERMINAL_HEAD.next=current_terminal->next;free(current_terminal);current_terminal=TERMINAL_HEAD.next;}while(current_production){PRODUCTION_HEAD.next=current_production->next;free(current_production->result);free(current_production);current_production=PRODUCTION_HEAD.next;}printf("退出成功\n");exit(0);
}/*插入到终结符*/
void insert_to_terminal(char get)
{terminal *Temp_terminal=(terminal*)malloc(sizeof(terminal));if(!Temp_terminal){perror("can`t malloc for this program\n");emergency(0);}Temp_terminal->character=get;Temp_terminal->next=NULL;current_terminal->next=Temp_terminal;current_terminal=Temp_terminal;/*移向下一个节点*/return ;
}/*插入到非终结符*/
void insert_to_noterminal(char get)
{noterminal *Temp_noterminal=(noterminal*)malloc(sizeof(noterminal));if(!Temp_noterminal){perror("can`t malloc for this program\n");emergency(0);}Temp_noterminal->character=get;Temp_noterminal->next=NULL;Temp_noterminal->FIRST=NULL;Temp_noterminal->FOLLOW=NULL;Temp_noterminal->first_number=0;Temp_noterminal->follow_number=0;current_noterminal->next=Temp_noterminal;current_noterminal=Temp_noterminal;/*移向下一个节点*/return ;
}/*插入到产生式*/
void insert_to_production(char source , char* result)
{char TEMP[20]= {0};int COUNT=0,number=0,length=0,exit_condition=strlen(result);production *Temp_production;for (COUNT=0; COUNT!=exit_condition+1; COUNT++){if(*result=='-'&&*(result+1)=='>'){result+=2;COUNT+=2;}if((*result!='|')&&(*result))TEMP[number++]=*result;else{Temp_production=(production*)malloc(sizeof(production));length=strlen(TEMP)+1;Temp_production->result=(char* )malloc(length);memset(Temp_production->result,0,length);strncpy(Temp_production->result,TEMP,length-1);memset(TEMP,0,sizeof(TEMP));Temp_production->source=source;Temp_production->next=NULL;current_production->next=Temp_production;current_production=Temp_production;number=0;}result++;}return ;
}/*消除左递归*/
void eliminate_left_recursion(void)
{int number=0;char new_char[3]= {0},TEMP_RESULT[20],temp_empty[3]= {'^',0,0};production  *Temp_production=PRODUCTION_HEAD.next;production  *Temp_FREE;terminal *temp=TERMINAL_HEAD.next;while(Temp_production){if(Temp_production->source==Temp_production->result[0]){memset(TEMP_RESULT,0,sizeof(TEMP_RESULT));new_char[0]=Temp_production->source-'A'+'a';/*复制到新的产生式*/strcat(TEMP_RESULT,Temp_production->result+1);strcat(TEMP_RESULT,new_char);insert_to_noterminal(new_char[0]);insert_to_production(new_char[0],TEMP_RESULT);insert_to_production(new_char[0],temp_empty);/*修改当前的产生式*/memset(TEMP_RESULT,0,sizeof(TEMP_RESULT));strcat(TEMP_RESULT,Temp_production->next->result);strcat(TEMP_RESULT,new_char);memset(Temp_production->result,0,strlen(Temp_production->result));strncpy(Temp_production->result,TEMP_RESULT,strlen(TEMP_RESULT));Temp_FREE= Temp_production->next;Temp_production->next=Temp_production->next->next;free(Temp_FREE);continue;}Temp_production=Temp_production->next;}while(temp){terminal_all[number++]=temp->character;temp=temp->next;}return ;
}void Test_read(void)
{int number=1;production *TEMP_PRODUCTION=PRODUCTION_HEAD.next;terminal *TEMP_TERMINAL=TERMINAL_HEAD.next;noterminal *TEMP_NOTERMINAL=NOTERMINAL_HEAD.next;printf("\n产生式\n");for(number=1; TEMP_PRODUCTION!=NULL; TEMP_PRODUCTION=TEMP_PRODUCTION->next,number++){printf("%d\t%c\t%s\n",number,TEMP_PRODUCTION->source,TEMP_PRODUCTION->result);}printf("\n终结符\n");for(; TEMP_TERMINAL!=NULL; TEMP_TERMINAL=TEMP_TERMINAL->next){printf("%c\t",TEMP_TERMINAL->character);}printf("\n");printf("\n非终结符\n");for(; TEMP_NOTERMINAL!=NULL; TEMP_NOTERMINAL=TEMP_NOTERMINAL->next){printf("%c\t",TEMP_NOTERMINAL->character);}printf("\n读取测试\n%s\n%s\n",TEST_LIST[0],TEST_LIST[1]);printf("\n");return ;
}size_t is_appeared(char tobejudged,char*source)
{size_t length=strlen(source),counts=0;while((counts!=length)&&(*source!=tobejudged)){counts++;source++;}return counts==length?!success: success;
}void combine(char* destinction,char* source)
{char temp[2]= {0};while(*source){if(!is_appeared(*source,destinction)){temp[0]=*source;strcat(destinction,temp);}source++;}return ;
}void prediction(void)
{noterminal* TEMP_NOTERMINAL=NOTERMINAL_HEAD.next;while(TEMP_NOTERMINAL!=NULL){find_first(TEMP_NOTERMINAL,PRODUCTION_HEAD.next);TEMP_NOTERMINAL=TEMP_NOTERMINAL->next;}test();TEMP_NOTERMINAL=NOTERMINAL_HEAD.next;while(TEMP_NOTERMINAL!=NULL){find_follow(TEMP_NOTERMINAL,PRODUCTION_HEAD.next);TEMP_NOTERMINAL=TEMP_NOTERMINAL->next;}return ;
}void test_follow(void)
{noterminal *TEMP_NOTERMINAL=NOTERMINAL_HEAD.next;for(; TEMP_NOTERMINAL!=NULL; TEMP_NOTERMINAL=TEMP_NOTERMINAL->next){printf("%c\tfollow number=%d\tfollow=%s\n",TEMP_NOTERMINAL->character,TEMP_NOTERMINAL->follow_number,TEMP_NOTERMINAL->FOLLOW);}printf("\n");return ;
}void prediction_table(void)
{int line=0,row=0,current_character=0,number=0;char* FIRST_CLUM,*test_exper;noterminal* temp_noterminal=NOTERMINAL_HEAD.next,*temp_noterminal21;terminal*   temp_terminal=TERMINAL_HEAD.next;production* temp_production=PRODUCTION_HEAD.next;char hah[5][7];memset(hah,0,sizeof(hah));for(line=0; line<5; line++){for(row=0; row<7; row++)hah[line][row]=0;}line=0;while(temp_production){row=0;if(is_appeared(*temp_production->result,terminal_all)&&(*temp_production->result!='^')){while(terminal_all[row]!=*temp_production->result)row++;hah[current_character][row]=line+1;}else{temp_noterminal=NOTERMINAL_HEAD.next;if(*temp_production->result=='^'){while(temp_noterminal->character!=temp_production->source)temp_noterminal=temp_noterminal->next;FIRST_CLUM=temp_noterminal->FOLLOW;if(is_appeared('#',FIRST_CLUM)){row=0;while(terminal_all[row] != '#')row++;hah[current_character][row]=line+1;}while(*FIRST_CLUM){row=0;while(terminal_all[row]!=*FIRST_CLUM)row++;hah[current_character][row]=line+1;FIRST_CLUM++;}if(temp_production->next&&temp_production->source!=temp_production->next->source)current_character++;temp_production=temp_production->next;line++;continue;}/*是非终结符*/while(temp_noterminal->character!=*temp_production->result)temp_noterminal=temp_noterminal->next;FIRST_CLUM=temp_noterminal->FIRST;while(*FIRST_CLUM){row=0;while(terminal_all[row]!=*FIRST_CLUM)row++;hah[current_character][row]=line+1;FIRST_CLUM++;}temp_noterminal21=NOTERMINAL_HEAD.next;while(temp_noterminal21->character!=temp_production->source)temp_noterminal21=temp_noterminal21->next;if(is_appeared('^',temp_noterminal->FIRST)&&is_appeared('#',temp_noterminal21->FOLLOW)){row=0;while(terminal_all[row]!=*FIRST_CLUM)row++;hah[line][row]=line+1;FIRST_CLUM++;}}if(temp_production->next&&temp_production->source!=temp_production->next->source)current_character++;temp_production=temp_production->next;line++;}printf("\n预测分析表\n\n");printf(" \t");for(temp_terminal=TERMINAL_HEAD.next; temp_terminal; temp_terminal=temp_terminal->next)printf("%c\t",temp_terminal->character);temp_noterminal=NOTERMINAL_HEAD.next;for(line=0; line<5; line++){printf("\n%c\t",temp_noterminal->character);for(row=0; row<7; row++)printf("%c\t",hah[line][row]==0?' ':(hah[line][row]-0+'0'));temp_noterminal=temp_noterminal->next;}printf("\n\n");system("pause");printf("\n\n");memset(TEST_STACK,0,sizeof(TEST_STACK));init_stack();test_exper=TEST_LIST[0];test_exper[strlen(test_exper)]='#';STACK_PUSH(NOTERMINAL_HEAD.next->character);while(!STACK_EMPTY()){printf("分析栈\t");for(number=0; number<=amount; number++)printf("%c",TEST_STACK[number]);printf("\t剩余字符串\t%s\n",test_exper);if(TEST_STACK[amount]==*test_exper){STACK_POP();test_exper++;}else{line=0;row=0;temp_noterminal=NOTERMINAL_HEAD.next;while(temp_noterminal->character!=TEST_STACK[amount]){temp_noterminal=temp_noterminal->next;line++;}while(terminal_all[row]!=*test_exper)row++;row=hah[line][row];if(!row)break;temp_production=PRODUCTION_HEAD.next;while(--row)temp_production=temp_production->next;FIRST_CLUM=temp_production->result;current_character=strlen(FIRST_CLUM);FIRST_CLUM=FIRST_CLUM+current_character-1;STACK_POP();while(current_character){if(*FIRST_CLUM!='^')STACK_PUSH(*FIRST_CLUM);FIRST_CLUM--;current_character--;}}}printf("分析栈\t");for(number=0; number<=amount; number++)printf("%c",TEST_STACK[number]);printf("\t剩余字符串\t%s\n",test_exper);if(STACK_EMPTY()&&*test_exper=='#')printf("\n合法输入\n");elseprintf("\n不合法输入\n");return ;
}void STACK_POP(void)
{if(STACK_EMPTY()){printf("栈空\n");emergency(2);}amount--;return ;
}
size_t STACK_EMPTY()
{return amount==0? success:!success;
}
size_t STACK_FULL()
{return amount==19? success:!success;
}
void STACK_PUSH(char source)
{if(STACK_FULL()){printf("栈满\n");emergency(2);}TEST_STACK[++amount]=source;return ;
}void init_stack(void)
{amount=0;TEST_STACK[amount]='#';return ;
}

运行结果:




这篇关于预测分析法进行语法分析(编译原理)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1074750

相关文章

深入探索协同过滤:从原理到推荐模块案例

文章目录 前言一、协同过滤1. 基于用户的协同过滤(UserCF)2. 基于物品的协同过滤(ItemCF)3. 相似度计算方法 二、相似度计算方法1. 欧氏距离2. 皮尔逊相关系数3. 杰卡德相似系数4. 余弦相似度 三、推荐模块案例1.基于文章的协同过滤推荐功能2.基于用户的协同过滤推荐功能 前言     在信息过载的时代,推荐系统成为连接用户与内容的桥梁。本文聚焦于

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

hdu4407(容斥原理)

题意:给一串数字1,2,......n,两个操作:1、修改第k个数字,2、查询区间[l,r]中与n互质的数之和。 解题思路:咱一看,像线段树,但是如果用线段树做,那么每个区间一定要记录所有的素因子,这样会超内存。然后我就做不来了。后来看了题解,原来是用容斥原理来做的。还记得这道题目吗?求区间[1,r]中与p互质的数的个数,如果不会的话就先去做那题吧。现在这题是求区间[l,r]中与n互质的数的和

业务中14个需要进行A/B测试的时刻[信息图]

在本指南中,我们将全面了解有关 A/B测试 的所有内容。 我们将介绍不同类型的A/B测试,如何有效地规划和启动测试,如何评估测试是否成功,您应该关注哪些指标,多年来我们发现的常见错误等等。 什么是A/B测试? A/B测试(有时称为“分割测试”)是一种实验类型,其中您创建两种或多种内容变体——如登录页面、电子邮件或广告——并将它们显示给不同的受众群体,以查看哪一种效果最好。 本质上,A/B测

maven 编译构建可以执行的jar包

💝💝💝欢迎莅临我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:「stormsha的主页」👈,「stormsha的知识库」👈持续学习,不断总结,共同进步,为了踏实,做好当下事儿~ 专栏导航 Python系列: Python面试题合集,剑指大厂Git系列: Git操作技巧GO

hdu4407容斥原理

题意: 有一个元素为 1~n 的数列{An},有2种操作(1000次): 1、求某段区间 [a,b] 中与 p 互质的数的和。 2、将数列中某个位置元素的值改变。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.Inpu

hdu4059容斥原理

求1-n中与n互质的数的4次方之和 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWrit

遮罩,在指定元素上进行遮罩

废话不多说,直接上代码: ps:依赖 jquer.js 1.首先,定义一个 Overlay.js  代码如下: /*遮罩 Overlay js 对象*/function Overlay(options){//{targetId:'',viewHtml:'',viewWidth:'',viewHeight:''}try{this.state=false;//遮罩状态 true 激活,f

利用matlab bar函数绘制较为复杂的柱状图,并在图中进行适当标注

示例代码和结果如下:小疑问:如何自动选择合适的坐标位置对柱状图的数值大小进行标注?😂 clear; close all;x = 1:3;aa=[28.6321521955954 26.2453660695847 21.69102348512086.93747104431360 6.25442246899816 3.342835958564245.51365061796319 4.87

寻迹模块TCRT5000的应用原理和功能实现(基于STM32)

目录 概述 1 认识TCRT5000 1.1 模块介绍 1.2 电气特性 2 系统应用 2.1 系统架构 2.2 STM32Cube创建工程 3 功能实现 3.1 代码实现 3.2 源代码文件 4 功能测试 4.1 检测黑线状态 4.2 未检测黑线状态 概述 本文主要介绍TCRT5000模块的使用原理,包括该模块的硬件实现方式,电路实现原理,还使用STM32类