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 )，

• 将 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 #include #include #include #include #include using namespace std;unordered_map> 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 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 bodys = P[str]; // str -> bodys    unordered_set 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 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> 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 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) | idend

运行结果

4.2 lan.txt文件内容

S -> SaRb | #R -> RSQ | #Q -> eend

运行结果

到此，关于"C++编译原理之怎么求解First集合"的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注网站，小编会继续努力为大家带来更多实用的文章！