C++編譯原理之怎么求解First集合

這篇文章主要介紹“C++編譯原理之怎么求解First集合”，在日常操作中，相信很多人在C++編譯原理之怎么求解First集合問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”C++編譯原理之怎么求解First集合”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

目錄

• 1、上機要求

• 2、原理

• 3、一點思路及優化

• 4、代碼

• 4.1 lan.txt文件內容

• 4.2 lan.txt文件內容

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集合”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！