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集合”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注网站，小编会继续努力为大家带来更多实用的文章！