c++ first follow select代码
时间: 2023-04-29 08:06:54 浏览: 54
这段代码是关于C++语言中的First集、Follow集和Select集的实现。其中,First集是某个文法符号能够推导出的终结符的集合,Follow集是在某个文法符号右侧出现的所有终结符的集合,而Select集则是在某个产生式中的某个非终结符能够推出的终结符的集合。
相关问题
c++求first和follow集代码
以下是C++代码实现First和Follow集合的算法:
First集合算法:
```
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>
using namespace std;
map<string, set<string>> first;
void compute_first(string non_terminal, vector<vector<string>> productions) {
for (auto production : productions) {
if (production[0] == non_terminal) {
if (production[1] == "epsilon") {
first[non_terminal].insert("epsilon");
} else if (islower(production[1][0])) {
first[non_terminal].insert(production[1]);
} else {
compute_first(production[1], productions);
for (auto element : first[production[1]]) {
first[non_terminal].insert(element);
}
}
}
}
}
int main() {
vector<vector<string>> productions = {
{"S", "AB"},
{"A", "aA"},
{"A", "epsilon"},
{"B", "bB"},
{"B", "epsilon"}
};
for (auto production : productions) {
compute_first(production[0], productions);
}
for (auto element : first) {
cout << "First(" << element.first << ") = { ";
for (auto value : element.second) {
cout << value << " ";
}
cout << "}" << endl;
}
return 0;
}
```
Follow集合算法:
```
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>
using namespace std;
map<string, set<string>> follow;
void compute_follow(string non_terminal, vector<vector<string>> productions) {
if (non_terminal == productions[0][0]) {
follow[non_terminal].insert("$");
}
for (auto production : productions) {
for (int i = 1; i < production.size(); i++) {
if (production[i] == non_terminal) {
if (i == production.size() - 1) {
compute_follow(production[0], productions);
for (auto element : follow[production[0]]) {
follow[non_terminal].insert(element);
}
} else {
if (islower(production[i + 1][0])) {
follow[non_terminal].insert(production[i + 1]);
} else {
compute_first(production[i + 1], productions);
for (auto element : first[production[i + 1]]) {
if (element != "epsilon") {
follow[non_terminal].insert(element);
} else {
compute_follow(production[0], productions);
for (auto element : follow[production[0]]) {
follow[non_terminal].insert(element);
}
}
}
}
}
}
}
}
}
int main() {
vector<vector<string>> productions = {
{"S", "AB"},
{"A", "aA"},
{"A", "epsilon"},
{"B", "bB"},
{"B", "epsilon"}
};
for (auto production : productions) {
compute_follow(production[0], productions);
}
for (auto element : follow) {
cout << "Follow(" << element.first << ") = { ";
for (auto value : element.second) {
cout << value << " ";
}
cout << "}" << endl;
}
return 0;
}
```
C++求FIRST和FOLLOW集合的代码
以下是求解FIRST集合和FOLLOW集合的C++代码示例:
```c++
// 计算产生式的FIRST集合
set<string> first(string symbol)
{
set<string> result;
// 如果是终结符,直接返回
if (is_terminal(symbol)) {
result.insert(symbol);
return result;
}
// 如果是非终结符,遍历所有产生式
for (int i = 0; i < productions.size(); i++) {
if (productions[i].left == symbol) {
// 如果产生式右部第一个符号是空串
if (productions[i].right.size() == 1 && productions[i].right[0] == "") {
result.insert("");
}
// 如果产生式右部第一个符号是终结符
else if (is_terminal(productions[i].right[0])) {
result.insert(productions[i].right[0]);
}
// 如果产生式右部第一个符号是非终结符
else {
set<string> right_first = first(productions[i].right[0]);
result.insert(right_first.begin(), right_first.end());
}
}
}
return result;
}
// 计算非终结符的FOLLOW集合
set<string> follow(string symbol)
{
set<string> result;
// 如果是文法开始符号,加入结束符号$
if (symbol == start_symbol) {
result.insert("$");
}
// 遍历所有产生式
for (int i = 0; i < productions.size(); i++) {
vector<string> right = productions[i].right;
for (int j = 0; j < right.size(); j++) {
// 如果该符号为当前非终结符
if (right[j] == symbol) {
// 如果该符号在产生式右部不是最后一个符号
if (j != right.size() - 1) {
// 如果下一个符号是终结符,直接加入FOLLOW集合
if (is_terminal(right[j + 1])) {
result.insert(right[j + 1]);
}
// 如果下一个符号是非终结符,加入该非终结符的FIRST集合
else {
set<string> next_first = first(right[j + 1]);
// 如果该非终结符的FIRST集合包含空串,还需加入该非终结符的FOLLOW集合
if (next_first.count("")) {
next_first.erase("");
set<string> follow_set = follow(productions[i].left);
next_first.insert(follow_set.begin(), follow_set.end());
}
result.insert(next_first.begin(), next_first.end());
}
}
// 如果该符号在产生式右部是最后一个符号,加入该非终结符的FOLLOW集合
else {
set<string> follow_set = follow(productions[i].left);
result.insert(follow_set.begin(), follow_set.end());
}
}
}
}
return result;
}
```
其中,is_terminal函数用于判断一个符号是否为终结符。productions为产生式集合,每个产生式包含左部和右部。start_symbol为文法开始符号。