CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章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) | idend

运行结果 。

4.2 lan.txt文件内容

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

运行结果 。

到此这篇关于C++/编译原理之求解First集合的文章就介绍到这了,更多相关C++ 求解First集合内容请搜索我以前的文章或继续浏览下面的相关文章希望大家以后多多支持我！ 。

原文链接：https://www.cnblogs.com/liqiuxiaozhu/p/15403976.html 。

最后此篇关于C++编译原理之求解First集合的文章就讲到这里了,如果你想了解更多关于C++编译原理之求解First集合的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。