C++編譯原理之求解First集合
1、上機要求
目的:熟練掌握自上而下的語法分析方法,並能用程序實現。
要求:
例如,使用的文法如下:
編寫First
函數,實現其求解過程。
E -> TE’
E’ -> +TE’ | #
T -> FT’
T’ -> *FT’ | #
F -> (E) | id
end
提示:
- 非終結符為 大寫字母;或 後面帶’的大寫字母
- 終結符為 小寫字母和符號(+、*)
- 推導符號→為或->
- 用end結束文法。
不針對特定文法,編寫求first函數。
2、原理
A -> a
, 則將 a 加入 First(A)
中
A -> Y1Y2···Yn
將 First(Y1)
除空串外的字符加入到First(A)中,若 1 =< i < n - 1,Y1,Y2, Yi
中均含有空串,則將First(Yi + 1)
加入到First(A)
中,若Y1
,Y2
,···,Yn都有空串,則將空串加入到First(A)
中
First(a) = {a}
3、一點思路及優化
將輸入格式化(掃描輸入)
將產生式轉換為哈希map
:
- 對任一產生式:
A -> body_1 | body_2 | ··· | body_n
, - 將 A 作為
map
的key
, - map的
value
為一個string
類的向量(vector<string>
), - 將
body_1
,body_2
,···,body_n
都加入value
中。 - 求解First(str)
- 特殊情況處理,str為空或str不在產生式的
key
中,返回空;str的首個字符是終結符,返回首個字符構成的集合。 - 一般情況,獲取str推導產生的產生體集
bodys
(其中的每個產生體為body
),遍歷產生體集合求解First集 - 針對空串,我們加入標記
hasBlank = true
,往下遍歷body的字符 body
的首個字符為終結符,直接將該字符加入first集,記hasBlank = false
以便遍歷下一body
(如果有的話)。body
的首個字符為非終結符,遞歸求解該非終結符first集,記為temp
,同時將空串標記記為false
,將temp
的中除空串外的字符加入first集;若temp
中有空串,記空串標記為true
,繼續遍歷當前body
的字符,理解上可以將body
後面的字符串視為一個新的body
繼續進行求解步驟。- body的字符遍歷結束後若空串標記
hasBlank
仍然為true
,則將空串加入first集。 - 優化:遞歸求解的中間結果可以放在全局哈希First(或者換個名字避免沖突)中,避免重復的迭代(本代碼沒實現,下次一定)。
4、代碼
/** * @brief Function for generating set of First(a) * @author 立秋小豬 * @time: 2021/10/13 * @notice: 要求產生體句型不得有空格 * 左遞歸的產生體中必須有空串(必須能夠終結) * char '#' act as varepsilon * **/ #include <iostream> #include <unordered_map> #include <vector> #include <string> #include <fstream> #include <unordered_set> using namespace std; unordered_map<string, vector<string>> P; //產生式P的集合 void scan(){ //scan函數實現從文件掃描文法,將對應的產生式加入到映射P中 fstream fs; string input; fs.open("lan.txt"); if(!fs.is_open()){ // 文件打開失敗 cout << "Error: Could not open the file" << endl; exit(-1); } fs >> input; while(input != "end"){ string VN = input; // 產生式的非終結符 fs >> input; //跳過推導符號 if (input != "->" && input != "→"){ cout << "Error: undefined symbol [" << input << "]" << endl; exit(-2); } fs >> input; //產生體拆開後加入到set集合中,默認推導符號後必有一個產生體 P[VN].emplace_back(input); while( fs >> input && input == "|"){ fs >> input; P[VN].emplace_back(input); } } } // void generate(){ // } unordered_set<char> First(const string& str){ // 終結符以及空串情況下, whether has the VN or not if(str == "" || str == "#" || P.find(str) == P.end()) return {}; if(!(str[0] >= 'A' && str[0] <= 'Z')) return {str[0]}; vector<string> bodys = P[str]; // str -> bodys unordered_set<char> res = {}; for(auto &s: bodys){ bool hasBlank = true;//是否含有空串,是否繼續讀產生體 for (int i = 0; i < s.size() && hasBlank; ++i){ if(s[i] >= 'A' && s[i] <= 'Z'){//是否為終結符 unordered_set<char> temp = {};//遞歸的臨時集 string next; if(i < s.size() - 1 && s[i + 1] == '\''){ // 大寫字母 + ' 的非終結符 next = s.substr(i, 2); ++i; }else{ //僅僅是大寫字母的終結符 next = s[i]; } if(next != str){ //避免無限遞歸,默認自身是含有空串(hasBlank為True) temp = First(next); //遞歸求解 hasBlank = false; //先默認temp中沒有空串 for(auto &c : temp) if(c == '#') hasBlank = true;//temp中發現瞭空串 else res.emplace(c); } }else{ res.emplace(s[i]); hasBlank = false;//默認連接的終結符不為空,故此終結符後不會再有新元素加入First集 } } if(hasBlank) //產生體中所有非終結符都包含空串,則將空串加入first集中 res.emplace('#'); } return res; } int main(){ // unordered_map<string, vector<char>> First; //First集合 scan(); cout << "輸入的產生式如下:\n" << "********************************\n"; for(auto &[vn, bodys]: P){ cout << vn << " -> " << bodys[0]; for (int i = 1; i < bodys.size(); ++i) cout << " | " << bodys[i]; cout << endl; } cout << "********************************\n"; for(auto &[vn,_]: P){ unordered_set<char> f = First(vn); cout << "First(" << vn << ") : "; auto iter = f.begin(); if(iter != f.end()){ cout << *iter; while(++iter != f.end()){ cout << " , " << *iter; } } cout << endl; } return 0; }
4.1 lan.txt文件內容
E -> TE' E' -> +TE' | # T -> FT' T' -> *FT' | # F -> (E) | id end
運行結果
4.2 lan.txt文件內容
S -> SaRb | # R -> RSQ | # Q -> e end
運行結果
到此這篇關於C++/編譯原理之求解First集合的文章就介紹到這瞭,更多相關C++ 求解First集合內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!
推薦閱讀:
- C++ stringstream格式化輸出輸入詳情
- C++中 Sort函數詳細解析
- c++ vector對象相關總結
- C++ vector容器 find erase的使用操作:查找並刪除指定元素
- C++實現讀寫ini配置文件的示例代碼