背景

期末考試免考，沖！

實驗名稱

FIRSTVT集生成算法

實驗時間

2020年6月3日 到 2020年6月9日

院系

信息科學與工程學院

組員姓名

Chocolate、kry2025、鐘先生、leo、小光

實驗環境介紹

• windows 10 操作系統
• Eclipse 進行 java 編程
• CodeBlocks 進行 C++ 編程

實驗目的與要求

目的

• 深刻理解FIRSTVT集生成算法
• 掌握FIRSTVT集生成的過程
• 加強團隊合作能力
• 提高自身的編程能力和解決問題的能力

要求

• 編程實現FIRSTVT集生成算法
• 算法簡潔，不冗余

解決問題

Firstvt集的求法，有三條規則：
（1）A->a…，即以終結符開頭，該終結符入Firstvt
（2）A->B…，即以非終結符開頭，該非終結符的Firstvt入A的Firstvt
（3）A->Ba…，即先以非終結符開頭，緊跟終結符，則終結符入Firstvt

實驗結果

源代碼

#include<bits/stdc++.h> #define endl '\n' #define mst(a,b) memset(a,b,sizeof(a)) using namespace std; const int maxn=1e3+5; class node{ public:string left;vector<string> right;node(const string& str){ //類似構造函數left=str;right.clear();}void push(char str[]){ //放入產生式右部right.push_back(str);}void print(){ //打印產生式printf("%s->%s",left.c_str(),right[0].c_str());for(int i=1;i<right.size();i++)printf("|%s",right[i].c_str());puts("");} }; int n; char buf[maxn]; int used[maxn],vis[maxn]; vector<node> vnode; map<string,int> mp; vector<char> vt; set<char> firstVt[maxn]; //dfs搜索 void dfs(int x){if(vis[x]) return;vis[x]=1;string& left=vnode[x].left; //取出當前產生式左部for(int i=0;i<vnode[x].right.size();i++){string& str=vnode[x].right[i]; //取出當前產生式右部if(isupper(str[0])){ //如果產生式右部第一個為非終結符int y=mp[str.substr(0,1)]-1; //拿到對應下標if(str.length()>1 && !isupper(str[1])) //判斷第二個是否為終結符，是的話加入firstVt[x].insert(str[1]);dfs(y); //搜索當前非終結符set<char>::iterator it = firstVt[y].begin();for(;it!=firstVt[y].end();it++) //加入非終結符y的firstVt集合firstVt[x].insert(*it);}else{firstVt[x].insert(str[0]); //如果是終結符，直接加入}} } void makeFirstVt(){memset(vis,0,sizeof(vis));for(int i=0;i<vnode.size();i++){if(vis[i]) continue;else dfs(i);}puts("------------FIRSTVT集-------------------");for(int i=0;i<vnode.size();i++){printf("%s : ",vnode[i].left.c_str() );set<char>::iterator it = firstVt[i].begin();for(;it!=firstVt[i].end();it++)printf("%c ",*it);puts("");} } //初始化工作，清空數組 void init(){memset(used,0,sizeof(used)); //初始化used數組，用于記錄VT集vt.clear(); //清空VT集合vnode.clear(); //清空產生式node集mp.clear(); //清空維護產生式下標集for(int i=0;i<=maxn;i++) //清空輸出結果firstVt集firstVt[i].clear(); } int main(){while(cin>>n){init(); //初始化工作for(int i=0;i<n;i++){scanf("%s",buf); //輸入產生式int len=strlen(buf),j;for(j=0;j<len;j++)if(buf[j]=='-'){buf[j]=0;break;}string tmp=buf; //取產生式左部非終結符if(!mp[tmp]){vnode.push_back(node(tmp)); //去重操作mp[tmp]=vnode.size(); //維護下標}int idx=mp[tmp]-1;vnode[idx].push(buf+j+2); //vnode加入產生式右部for(int k=0;k<j;k++){ //檢查產生式左部是否包含終結符if(!isupper(buf[k])){if(used[buf[k]]) continue;used[buf[k]]=1;vt.push_back(buf[k]);}}for(int k=j+2;k<len;k++){ //將產生式右部加入vt集合if(!isupper(buf[k])){if(used[buf[k]]) continue;vt.push_back(buf[k]);used[buf[k]]=vt.size();}}}puts("************VT集*******************");for(int i=0;i<vt.size();i++ )printf("%c ",vt[i]);puts("");cout<<endl;puts("*************產生式*****************");for(int i=0;i<vnode.size();i++)vnode[i].print();puts("************************************");cout<<endl;makeFirstVt(); //求FirstVt集}return 0; }

輸出結果

測試樣例

8 E->E+T E->T T->T*F T->F F->P^F F->P P->(E) P->i

參考文獻

參考：編譯原理(七) 算符優先分析法(構造算符優先關系表算法及C++實現)

總結

以上是生活随笔為你收集整理的【C++实现】编译原理 免考小队 FIRSTVT集生成算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。