上機要求
-
目的：熟練掌握自上而下的語法分析方法，并能用程式實作，
-
要求：
例如，使用的文法如下：
撰寫First函式，實作其求解程序，E -> TE'
E' -> +TE' | #
T -> FT'
T' -> *FT' | #
F -> (E) | id
end -
提示：
- 非終結符為 大寫字母；或 后面帶’的大寫字母
- 終結符為 小寫字母和符號（+、*）
- 推導符號→為或->
- 用end結束文法，
-
不針對特定文法，撰寫求first函式，
原理
- 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}
一點思路及優化
- 將輸入格式化（掃描輸入）
- 將產生式轉換為哈希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（或者換個名字避免沖突）中，避免重復的迭代（本代碼沒實作，下次一定），
代碼
/**
* @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;
}
lan.txt檔案內容
E -> TE'
E' -> +TE' | #
T -> FT'
T' -> *FT' | #
F -> (E) | id
end
運行結果
lan.txt檔案內容
S -> SaRb | #
R -> RSQ | #
Q -> e
end
運行結果
本人也只是編程小白，代碼僅供參考，如有錯誤請見諒，如有疑問歡迎交流討論，歡迎提出任何建議和評價，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/311938.html
標籤：其他