编译原理实验三:算符优先分析算法的设计与实现

2023-11-02 20:20

本文主要是介绍编译原理实验三:算符优先分析算法的设计与实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

实验三 算符优先分析算法的设计与实现

一、 实验目的
根据算符优先分析法,对表达式进行语法分析,使其能够判断一个表达式是否正确。通过算符优先分析方法的实现,加深对自下而上语法分析方法的理解。

二、 实验要求
1、输入文法。可以是如下算术表达式的文法(你可以根据需要适当改变):

E→E+T|E-T|T
T→T*F|T/F|F
F→(E)|i

2、对给定表达式进行分析,输出表达式正确与否的判断。
程序输入/输出示例:

输入:1+2;
输出:正确
输入:(1+2)/3+4-(5+6/7);
输出:正确
输入:((1-2)/3+4
输出:错误
输入:1+2-3+(*4/5)
输出:错误

三、实验步骤
1、参考数据结构

char *VN=0,*VT=0;//非终结符和终结符数组
char firstvt[N][N],lastvt[N][N],table[N][N];
typedef struct   //符号对(P,a)
{char Vn;char Vt;
} VN_VT;
typedef struct  //栈
{VN_VT *top;VN_VT *bottom;int  size;
}stack;

2、根据文法求FIRSTVT集和LASTVT集
给定一个上下文无关文法,根据算法设计一个程序,求文法中每个非终结符的FirstVT 集和LastVT 集。
算符描述如下:

/*求 FirstVT 集的算法*/ 
PROCEDURE insert(P,a); 
IF not F[P,a] then   
begin  F[P,a] = true; //(P,a)进栈  
end;  
Procedure FirstVT; 
Begin 
for 对每个非终结符 P和终结符 a do F[P,a] = false 
for 对每个形如 P		a…或 P→Qa…的产生式 do 
Insert(P,a) 
while stack  非空 
begin 
栈顶项出栈,记为(Q,a) 
for  对每条形如 P→Q…的产生式 do insert(P,a) 
end; 
end.

同理,可构造计算LASTVT的算法。
3、构造算符优先分析表
依据文法和求出的相应FirstVT和 LastVT 集生成算符优先分析表。

算法描述如下:
for  每个形如 P->X1X2…Xn的产生式  do for i =1 to n-1 do begin if Xi和Xi+1都是终结符 then  Xi   =   Xi+1 if i<= n-2, Xi和Xi+2 是终结符, 但Xi+1 为非终结符 then Xi  = Xi+2 if Xi为终结符, Xi+1为非终结符 then   for FirstVT 中的每个元素 a do Xi  <  a ; if Xi为非终结符, Xi+1为终结符 then for LastVT 中的每个元素 a do a  >  Xi+1 ; end

4、构造总控程序
算法描述如下:

  stack S;k = 1;  //符号栈S的使用深度S[k] = ‘#’REPEAT把下一个输入符号读进a中;If S[k]   VT   then  j = k  else  j = k-1;While S[j] > a  doBeginRepeatQ = S[j];if  S[j-1]   VT  then  j = j-1  else   j = j-2until  S[j] < Q;把S[j+1]…S[k]归约为某个N,并输出归约为哪个符号;K = j+1;S[k] = N;end of whileif S[j] < a  or  S[j] = a  thenbegin  k = k+1; S[k] = a      endelse  error //调用出错诊察程序until a = ‘#’

5、对给定的表达式,给出准确与否的分析过程
6、给出表达式的计算结果。(本步骤可选作)

代码

#include <bits/stdc++.h>
using namespace std;//定义一个非终结符的结构体 
typedef struct{char left;//非终结符 int rcount;//右边式子数量 char right[200][200];//右边 int fvtcount;int lvtcount;char firstvt[200];//firstvt集合 char lastvt[200];//lastvt集合 
}grammar;
grammar gramSet[200];//产生式集 //变量的定义 
int gramcount=0;//产生式数量初始化 
int tersymcount=0;//终结符数量初始化 
int nontercount=0;//非终结符数量初始化 char terSymbol[200];//终结符号
char nonter[200];//非终结符号
char table[200][200];//分析表
char test[500];//要处理的字符串 map<char, bool> isfvted;//该非终结符是否已经求过其firstvt集
map<char, bool> islvted;//是否求过lastvt集 //函数的定义
void read();//读入数据 
bool judgesymbol(char ch);//判断终结符和非终结符
void symbolsort(char ch);//字符归类
void Firstvt(char sym);//求sym的first集 
void Addfvt(char sym, char ch);//firstvt(ch)并入firstvt(sym) 
void Lastvt(char sym);//求sym的lastvt集 
void Addlvt(char sym, char  ch);//lastvt(ch)并入lastvt(sym) 
void Table();//创建算符优先分析表 
void Show();//打印分析表 
void MainControl();//总控程序int main(int argc, char** argv) {cout<<"输入文法: 以'#'结束"<<endl;read();cout<<"输入串(以'#'结束)为:"<<endl;cin>>test;for(int i=0;i<strlen(test);i++)//将输入的数字替换成i,便于分析 {if(test[i]>='0'&&test[i]<='9')test[i]='i';}for(int i=0;i<gramcount;i++){Firstvt(gramSet[i].left);}for(int i=0;i<gramcount;i++){Lastvt(gramSet[i].left);}cout<<endl;cout<<"FirstVT集如下:"<<endl;for(int i=0;i<gramcount;i++){cout<<"FirstVT("<<gramSet[i].left<<")"<<": ";for(int j=0;j<gramSet[i].fvtcount;j++)cout<<gramSet[i].firstvt[j]<<" ";cout<<endl;}cout<<endl;cout<<"LastVT集如下:"<<endl;for(int i=0;i<gramcount;i++){cout<<"LastVT("<<gramSet[i].left<<")"<<": ";for(int j=0;j<gramSet[i].lvtcount;j++)cout<<gramSet[i].lastvt[j]<<" ";cout<<endl;}cout<<endl;cout<<"算符优先分析表如下:"<<endl;Table();Show();cout<<endl;cout<<"分析步骤如下:"<<endl;MainControl();return 0;
}//读入数据 
void read()
{char str[100];while(1){cin>>str;if(str[0]=='#')break;gramSet[gramcount].left=str[0];symbolsort(str[0]);//处理左边 for(int i=3;i<strlen(str);i++)//右边从str[3]处开始;str的0-2位=‘E->’ {int j=0;char ter[100];while(str[i]!='|'&&str[i]!='\0'){symbolsort(str[i]);//处理右边 ter[j++]=str[i++];	}ter[j]='\0';strcpy(gramSet[gramcount].right[gramSet[gramcount].rcount],ter);gramSet[gramcount].rcount++;} gramcount++;	}
}
//判断终结符和非终结符
bool judgesymbol(char ch)
{if(ch>='A'&&ch<='Z')return false;return true;
}
//字符归类
void symbolsort(char ch)
{if(!judgesymbol(ch)){int flag=0;for (int i= 0;i<nontercount; i++){if (ch==nonter[i]){flag=1;break;//已在非终结符集中 }}if(flag==0){nonter[nontercount++]=ch;isfvted.insert(pair<char, bool>(ch, false));islvted.insert(pair<char,bool>(ch, false));}}else{int flag=0;for (int i=0;i<tersymcount; i++){if (ch==terSymbol[i]){flag = 1;break;//已在终结符集中 }}if (flag==0){terSymbol[tersymcount++]=ch;}}
}
//求FirstVT集
void Firstvt(char sym)
{int i;for(i=0;i<gramcount;i++){if(gramSet[i].left==sym)break;//找到了该非终结符的位置 } //处理每个产生式 for(int j=0;j<gramSet[i].rcount;j++){	 char ch=gramSet[i].right[j][0];//获取右部第一个字符 //字符为终结符if(judgesymbol(ch)){int flag=0;for (int n=0; n<gramSet[i].fvtcount;n++){if (gramSet[i].firstvt[n] == ch){flag = 1;//已在firstvt集中 break;}}if(flag==0){gramSet[i].firstvt[gramSet[i].fvtcount++]=ch;//把终结符加进FIRSTVT集 }	}//字符ch为非终结符else {if(ch!=sym){//还没有求过ch的firstvt集 if(!isfvted[ch])Firstvt(ch);//firstvt(ch)并入firstvt(sym) Addfvt(sym,ch);	}//P->Qa的情况 char ch1=gramSet[i].right[j][1];if(judgesymbol(ch1)){int flag=0;for (int n=0; n<gramSet[i].fvtcount;n++){if (gramSet[i].firstvt[n] == ch1){flag = 1;//已在firstvt集中 break;}}if(flag==0)gramSet[i].firstvt[gramSet[i].fvtcount++]=ch1;//把终结符加进FIRSTVT集 }}	}isfvted[sym]=true;
}
//firstvt(ch)并入firstvt(sym)  
void Addfvt(char sym,char ch)
{int s1,s2;int c1,c2;//找到sym的位置 for(s1=0;s1<gramcount;s1++){if(gramSet[s1].left==sym)break; }//找到ch的位置 for(c1=0;c1<gramcount;c1++){if(gramSet[c1].left==ch)break; }for(c2=0;c2<gramSet[c1].fvtcount;c2++){int flag=0;for(s2=0;s2<gramSet[s1].fvtcount;s2++){if(gramSet[s1].firstvt[s2]==gramSet[c1].firstvt[c2]){flag=1;break;//已存在 } 	 }//firstvt(ch)并入firstvt(sym) if(flag==0){	gramSet[s1].firstvt[gramSet[s1].fvtcount++]=gramSet[c1].firstvt[c2];}}
}
//求sym的lastvt集
void Lastvt(char sym){int i;for(i=0;i<gramcount;i++){if(gramSet[i].left==sym)break;}//处理每个产生式 for(int j=0;j<gramSet[i].rcount;j++){	 int length=strlen(gramSet[i].right[j]);int last=length-1;char ch=gramSet[i].right[j][last];//获取右部最后一个字符 //字符为终结符if(judgesymbol(ch)){int flag=0;for (int n=0; n<gramSet[i].lvtcount;n++){if (gramSet[i].lastvt[n] == ch){flag = 1;//已在lastvt集中 break;}}if(flag==0){gramSet[i].lastvt[gramSet[i].lvtcount++]=ch;//把终结符加进FIRSTVT集 }	}//字符ch为非终结符else {if(ch!=sym){//还没有求过ch的lastvt集 if(!islvted[ch])Lastvt(ch);//lastvt(ch)并入lastvt(sym) Addlvt(sym, ch);	}//P->aQ的情况 if(last!=0){char ch1=gramSet[i].right[j][last-1];//倒数第二位 if(judgesymbol(ch1)){int flag=0;for (int n=0; n<gramSet[i].lvtcount;n++){if (gramSet[i].lastvt[n] == ch1){flag = 1;//已在lastvt集中 break;}}if(flag==0)gramSet[i].lastvt[gramSet[i].lvtcount++]=ch1;//把终结符加进LASTVT集 }}		   		}	}islvted[sym]=true;}
//lastvt(ch)并入lastvt(sym) 
void Addlvt(char sym, char  ch)
{int  s1,s2;int  c1,c2;for(s1=0;s1<gramcount;s1++)//找到sym的位置 {if(gramSet[s1].left==sym)break;}for(c1=0;c1<gramcount;c1++)//找到ch的位置 {if(gramSet[c1].left==ch)break;}for(c2=0;c2<gramSet[c1].lvtcount;c2++){int flag=0;for(s2=0;s2<gramSet[s1].lvtcount;s2++){if(gramSet[s1].lastvt[s2]==gramSet[c1].lastvt[c2]){flag=1;break;}}if(flag==0)gramSet[s1].lastvt[gramSet[s1].lvtcount++]=gramSet[c1].lastvt[c2];}
}//创建分析表 
void Table()
{int row=tersymcount+2;//优先表的行数和列数 //分析表初始化table[0][0]=' ';table[0][row-1]='#';table[row-1][0]='#';table[row-1][row-1]='=';//第0行 int j=1;for(int i=0;i<tersymcount;i++)table[0][j++]=terSymbol[i];	//第0列 int k=1;for(int i=0;i<tersymcount;i++)table[k++][0]=terSymbol[i];int p;	 //开始分析,填充表的内容//对#特殊处理for(int i=1;i<row;i++) //分析#所在的一行 {for(int j=0;j<gramSet[0].fvtcount;j++){if(table[0][i]==gramSet[0].firstvt[j]){table[row-1][i]='<';break;}}}for(int i=1;i<row;i++) //分析#所在的一列 {for(int j=0;j<gramSet[0].lvtcount;j++){if(table[i][0]==gramSet[0].lastvt[j]){table[i][row-1]='>';break;}}}//遍历所有产生式 for(int g=0;g<gramcount;g++){//遍历一个非终结符的所有产生式 for(int i=0;i<gramSet[g].rcount;i++){int n=strlen(gramSet[g].right[i]);for(int j=0;j<n-1;j++){char xi=gramSet[g].right[i][j];char xi1=gramSet[g].right[i][j+1];//Xi和Xi+1都是终结符 if(judgesymbol(xi)&&judgesymbol(xi1)){for(int r=1;r<row;r++){if(table[r][0]==xi){p=r;//找到xi的位置 break;}}for(int l=1;l<row;l++){if(table[0][l]==xi1)//找到Xi+1的位置{table[p][l]='='; break;}}}if(j<n-2){char xi2=gramSet[g].right[i][j+2];if(!judgesymbol(xi1)&&judgesymbol(xi)&&judgesymbol(xi2)){for(int r=1;r<row;r++){if(table[r][0]==xi){p=r;//找到xi的位置 break;}}for(int l=1;l<row;l++){if(table[0][l]==xi2)//找到Xi+1的位置{table[p][l]='='; break;}}}}//Xi为终结符, Xi+1为非终结符if(!judgesymbol(xi1)&&judgesymbol(xi)){int pos;for(pos=0;pos<gramcount;pos++){if(gramSet[pos].left==xi1)break;}for(int r=1;r<row;r++){if(table[r][0]==xi){p=r;//找到xi的位置 (第p行第0列) break;}}for(int x=0;x<gramSet[pos].fvtcount;x++)//对于firstvt中的每一个元素 {char a=gramSet[pos].firstvt[x];for(int l=1;l<row;l++){if(table[0][l]==a)//找到a的位置(第0行第l列) {table[p][l]='<'; break;}}}}//if Xi为非终结符, Xi+1为终结符if(!judgesymbol(xi)&&judgesymbol(xi1)){int pos;for(pos=0;pos<gramcount;pos++){if(gramSet[pos].left==xi)break;}for(int r=1;r<row;r++){if(table[0][r]==xi1){p=r;//找到xi1的位置(第0行,p列) break;}}for(int x=0;x<gramSet[pos].lvtcount;x++)//对于lastvt中的每一个元素 {char a=gramSet[pos].lastvt[x];for(int l=1;l<row;l++){if(table[l][0]==a)//找到a的位置(第l行,第0列) {table[l][p]='>'; break;}}}}}}}} //展示分析表
void Show(){int row=tersymcount+2;//优先表的行数和列数 //打印表的内容for(int k=0;k<row*11;k++)cout<<"-";cout<<endl;for(int i=0;i<row;i++){for(int j=0;j<row;j++){cout<<table[i][j];for(int k=0;k<9;k++)cout<<" ";cout<<"|";}cout<<endl;for(int k=0;k<row*11;k++)cout<<"-";cout<<endl;}}//比较s和a优先级的函数 
char prio(char s,char a)
{int row=tersymcount+2;int i;int j;for(i=1;i<row;i++){if(table[i][0]==s)break;}for(j=1;j<row;j++){if(table[0][j]==a)break;}if(table[i][j]=='>')return '>';else if(table [i][j]=='<')return '<';else if(table[i][j]=='=')return '=';elsereturn 'e';} 
//总控程序
void MainControl()
{int flag=1;int row=tersymcount+2;int j;string str[100];//存储动作str[0]="预备"; char s[100];//符号栈for(int i=0;i<100;i++)s[i]='\0';int k;//符号栈的使用深度 k=0;s[k] = '#';char a;//存放输入串当前分析符号 int pos=0;//定位a的位置 int step=0;//步骤序号 cout << endl;cout<<"步骤\t符号栈\t\t\t输入串\t\t\t\t动作"<<endl;while(flag==1){cout<<step++<<"\t";//打印步骤序号cout<<s<<"\t\t\t";//打印当前符号栈 for(int i=pos;i<strlen(test);i++)//打印当前输入串 cout<<test[i];cout<<"\t\t\t\t";cout<<str[step-1]<<endl;a=test[pos];if(judgesymbol(s[k]))j=k;else j=k-1;if(prio(s[j],a)=='>'){string strkj;//要归约的式子 while(1){char q=s[j];if(judgesymbol(s[j-1]))j=j-1;elsej=j-2;if(prio(s[j],q)=='<')break;	}//把S[j+1]…S[k]归约为某个N,并输出归约为哪个符号;char N;int flag1=1;int flag2=1;int flag3;for(int K=j+1;K<=k;K++)strkj+=s[K];int max=strkj.length();//要归约式子的长度 for(int g=gramcount-1;g>=0;g--){for(int g1=0;g1<gramSet[g].rcount;g1++)//遍历某非终结符每个产生式 {string gram1=gramSet[g].right[g1];int m=gram1.length();//右部产生式的长度//右部产生式gram1与strkj需要非终结符对非终结符,终结符对终结符且终结符相等才能归约 if(max==m)//首先判断长度是否相等 {//判断一一对应关系int p;for(p=0;p<max;p++){if(judgesymbol(strkj[p]))//如果p位置是终结符,则需要相等 {if(strkj[p]==gram1[p])flag3=1;else flag3=0;} else//p位置是非终结符,则需要对应 {if(!judgesymbol(gram1[p]))flag3=1;else flag3=0;}if(flag3==0)break;} if(flag3==1) //一一对应,则可以跳出循环 {N=gramSet[g].left;flag1=0;flag2=0;}	 }if(flag2==0)break;		}if(flag1==0)break;} if(flag1==0)//说明可归约 {for(int K=j+1;K<=k;K++)//将s[j+1]...s[k]移除 s[K]='\0';k=j+1;s[k]=N;str[step]="归约"; 	}elseflag=-1;//说明不可归约,语法错误 }else if(prio(s[j],a)=='<'||prio(s[j],a)=='='){k++;s[k]=a;str[step]="移进"; pos++;}elseflag=-1;char start=gramSet[0].left;if(a=='#'&&!judgesymbol(s[k])&&k==1){cout<<step++<<"\t";//打印最后步骤cout<<s<<"\t\t\t";//打印当前符号栈 for(int i=pos;i<strlen(test);i++)//打印当前输入串 cout<<test[i];cout<<"\t\t\t\t";cout<<str[step-1]<<endl;flag=0;}	} if(flag==0)cout<<"success!表达式正确!"<<endl;else if(flag==-1)cout<<"error!表达式不正确!"<<endl;
}

结果

测试数据:
文法:

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

测试输入1:

i*i+i#

在这里插入图片描述

这篇关于编译原理实验三:算符优先分析算法的设计与实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

hdu1180(广搜+优先队列)

此题要求最少到达目标点T的最短时间,所以我选择了广度优先搜索,并且要用到优先队列。 另外此题注意点较多,比如说可以在某个点停留,我wa了好多两次,就是因为忽略了这一点,然后参考了大神的思想,然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<

性能分析之MySQL索引实战案例

文章目录 一、前言二、准备三、MySQL索引优化四、MySQL 索引知识回顾五、总结 一、前言 在上一讲性能工具之 JProfiler 简单登录案例分析实战中已经发现SQL没有建立索引问题,本文将一起从代码层去分析为什么没有建立索引? 开源ERP项目地址:https://gitee.com/jishenghua/JSH_ERP 二、准备 打开IDEA找到登录请求资源路径位置

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

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

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象