實驗三 算符優(yōu)先分析算法的設計與實現(xiàn)
一、 實驗目的
根據(jù)算符優(yōu)先分析法，對表達式進行語法分析，使其能夠判斷一個表達式是否正確。通過算符優(yōu)先分析方法的實現(xiàn)，加深對自下而上語法分析方法的理解。
二、 實驗要求
1、輸入文法。可以是如下算術(shù)表達式的文法（你可以根據(jù)需要適當改變）：
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、參考數(shù)據(jù)結(jié)構(gòu)
char *VN=0,*VT=0;//非終結(jié)符和終結(jié)符數(shù)組
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、根據(jù)文法求FIRSTVT集和LASTVT集
給定一個上下文無關(guān)文法，根據(jù)算法設計一個程序，求文法中每個非終結(jié)符的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 對每個非終結(jié)符 P和終結(jié)符 a do
F[P,a] = false
for 對每個形如 P a…或 P→Qa…的產(chǎn)生式 do
Insert(P,a)
while stack 非空
begin
棧頂項出棧，記為(Q,a)
for 對每條形如 P→Q…的產(chǎn)生式 do
insert(P,a)
end;
end.
同理，可構(gòu)造計算LASTVT的算法。
3、構(gòu)造算符優(yōu)先分析表
依據(jù)文法和求出的相應FirstVT和 LastVT 集生成算符優(yōu)先分析表。
算法描述如下：
for 每個形如 P->X1X2…Xn的產(chǎn)生式 do
for i =1 to n-1 do
begin
if Xi和Xi+1都是終結(jié)符 then
Xi = Xi+1
if i<= n-2, Xi和Xi+2 是終結(jié)符, 但Xi+1 為非終結(jié)符 then
Xi = Xi+2
if Xi為終結(jié)符, Xi+1為非終結(jié)符 then
for FirstVT 中的每個元素 a do
Xi < a ;
if Xi為非終結(jié)符, Xi+1為終結(jié)符 then
for LastVT 中的每個元素 a do
a > Xi+1 ;
end
4、構(gòu)造總控程序
算法描述如下：
stack S;
k = 1; //符號棧S的使用深度
S[k] = ‘#’
REPEAT
把下一個輸入符號讀進a中；
If S[k] VT then j = k else j = k-1;
While S[j] > a do
Begin
Repeat
Q = S[j];
if S[j-1] VT then j = j-1 else j = j-2
until S[j] < Q;
把S[j+1]…S[k]歸約為某個N，并輸出歸約為哪個符號；
K = j+1;
S[k] = N;
end of while
if S[j] < a or S[j] = a then
begin k = k+1; S[k] = a end
else error //調(diào)用出錯診察程序
until a = ‘#’
5、對給定的表達式，給出準確與否的分析過程
6、給出表達式的計算結(jié)果。（本步驟可選作）
代碼
#include <bits/stdc++.h>
using namespace std;
//定義一個非終結(jié)符的結(jié)構(gòu)體
typedef struct{
char left;//非終結(jié)符
int rcount;//右邊式子數(shù)量
char right[200][200];//右邊
int fvtcount;
int lvtcount;
char firstvt[200];//firstvt集合
char lastvt[200];//lastvt集合
}grammar;
grammar gramSet[200];//產(chǎn)生式集
//變量的定義
int gramcount=0;//產(chǎn)生式數(shù)量初始化
int tersymcount=0;//終結(jié)符數(shù)量初始化
int nontercount=0;//非終結(jié)符數(shù)量初始化
char terSymbol[200];//終結(jié)符號
char nonter[200];//非終結(jié)符號
char table[200][200];//分析表
char test[500];//要處理的字符串
map<char, bool> isfvted;//該非終結(jié)符是否已經(jīng)求過其firstvt集
map<char, bool> islvted;//是否求過lastvt集
//函數(shù)的定義
void read();//讀入數(shù)據(jù)
bool judgesymbol(char ch);//判斷終結(jié)符和非終結(jié)符
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();//創(chuàng)建算符優(yōu)先分析表
void Show();//打印分析表
void MainControl();//總控程序
int main(int argc, char** argv) {
cout<<"輸入文法： 以'#'結(jié)束"<<endl;
read();
cout<<"輸入串(以'#'結(jié)束)為："<<endl;
cin>>test;
for(int i=0;i<strlen(test);i++)//將輸入的數(shù)字替換成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<<"算符優(yōu)先分析表如下："<<endl;
Table();
Show();
cout<<endl;
cout<<"分析步驟如下："<<endl;
MainControl();
return 0;
}
//讀入數(shù)據(jù)
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++;
}
}
//判斷終結(jié)符和非終結(jié)符
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;//已在非終結(jié)符集中
}
}
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;//已在終結(jié)符集中
}
}
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;//找到了該非終結(jié)符的位置
}
//處理每個產(chǎn)生式
for(int j=0;j<gramSet[i].rcount;j++)
{
char ch=gramSet[i].right[j][0];//獲取右部第一個字符
//字符為終結(jié)符
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;//把終結(jié)符加進FIRSTVT集
}
}
//字符ch為非終結(jié)符
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;//把終結(jié)符加進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;
}
//處理每個產(chǎn)生式
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];//獲取右部最后一個字符
//字符為終結(jié)符
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;//把終結(jié)符加進FIRSTVT集
}
}
//字符ch為非終結(jié)符
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];//倒數(shù)第二位
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;//把終結(jié)符加進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];
}
}
//創(chuàng)建分析表
void Table()
{
int row=tersymcount+2;//優(yōu)先表的行數(shù)和列數(shù)
//分析表初始化
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;
//開始分析，填充表的內(nèi)容
//對#特殊處理
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;
}
}
}
//遍歷所有產(chǎn)生式
for(int g=0;g<gramcount;g++)
{
//遍歷一個非終結(jié)符的所有產(chǎn)生式
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都是終結(jié)符
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為終結(jié)符, Xi+1為非終結(jié)符
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為非終結(jié)符, Xi+1為終結(jié)符
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;//優(yōu)先表的行數(shù)和列數(shù)
//打印表的內(nèi)容
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優(yōu)先級的函數(shù)
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 '=';
else
return '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;
else
j=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++)//遍歷某非終結(jié)符每個產(chǎn)生式
{
string gram1=gramSet[g].right[g1];
int m=gram1.length();//右部產(chǎn)生式的長度
//右部產(chǎn)生式gram1與strkj需要非終結(jié)符對非終結(jié)符，終結(jié)符對終結(jié)符且終結(jié)符相等才能歸約
if(max==m)//首先判斷長度是否相等
{
//判斷一一對應關(guān)系
int p;
for(p=0;p<max;p++)
{
if(judgesymbol(strkj[p]))//如果p位置是終結(jié)符，則需要相等
{
if(strkj[p]==gram1[p])
flag3=1;
else
flag3=0;
}
else//p位置是非終結(jié)符，則需要對應
{
if(!judgesymbol(gram1[p]))
flag3=1;
else
flag3=0;
}
if(flag3==0)
break;
}
if(flag3==1) //一一對應，則可以跳出循環(huán)
{
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]="歸約";
}
else
flag=-1;//說明不可歸約，語法錯誤
}
else if(prio(s[j],a)=='<'||prio(s[j],a)=='=')
{
k++;
s[k]=a;
str[step]="移進";
pos++;
}
else
flag=-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;
}
結(jié)果
測試數(shù)據(jù)：
文法：
E->E+T|E-T|T
T->T*F|T/F|F
F->(E)|i
#
測試輸入1：文章來源：http://www.zghlxwxcb.cn/news/detail-457423.html
i*i+i#
文章來源地址http://www.zghlxwxcb.cn/news/detail-457423.html
到了這里，關(guān)于編譯原理實驗三：算符優(yōu)先分析算法的設計與實現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
