本文主要是介绍编译原理实验三:算符优先分析算法的设计与实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
实验三 算符优先分析算法的设计与实现
一、 实验目的
根据算符优先分析法,对表达式进行语法分析,使其能够判断一个表达式是否正确。通过算符优先分析方法的实现,加深对自下而上语法分析方法的理解。
二、 实验要求
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#
这篇关于编译原理实验三:算符优先分析算法的设计与实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!