LL1代码,要求可以自动求first和follow集,c++实现
时间: 2023-06-25 07:08:19 浏览: 106
以下是一个简单的 LL(1) 文法的代码实现,包括自动求解 FIRST 和 FOLLOW 集合:
```c++
#include <iostream>
#include <vector>
#include <map>
#include <set>
using namespace std;
// 定义产生式结构体
struct Production {
char left; // 产生式左部
string right; // 产生式右部
};
// 定义文法结构体
struct Grammar {
vector<Production> productions; // 所有的产生式
set<char> nonTerminals; // 非终结符集合
set<char> terminals; // 终结符集合
// 构造函数
Grammar() {}
// 添加一个产生式
void addProduction(char left, string right) {
Production p = {left, right};
productions.push_back(p);
nonTerminals.insert(left);
for (char c : right) {
if (c != '|' && !isupper(c)) {
terminals.insert(c);
}
}
}
// 计算每个非终结符的 FIRST 集合
map<char, set<char>> calculateFirst() {
map<char, set<char>> first;
for (char nt : nonTerminals) {
first[nt] = {};
}
for (char t : terminals) {
first[t] = {t};
}
bool updated = true;
while (updated) {
updated = false;
for (Production p : productions) {
char left = p.left;
string right = p.right;
int i = 0;
while (i < right.size()) {
char c = right[i];
if (isupper(c)) { // 非终结符
set<char> s = first[c];
int len = s.size();
s.erase('|');
first[left].insert(s.begin(), s.end());
if (len != first[c].size()) {
updated = true;
}
if (!first[c].count('|')) {
break;
}
} else { // 终结符
first[left].insert(c);
break;
}
i++;
}
if (i == right.size()) { // 非终结符全都推出空串
first[left].insert('|');
}
}
}
return first;
}
// 计算每个非终结符的 FOLLOW 集合
map<char, set<char>> calculateFollow() {
map<char, set<char>> follow;
for (char nt : nonTerminals) {
follow[nt] = {};
}
follow[productions[0].left].insert('$');
bool updated = true;
while (updated) {
updated = false;
for (Production p : productions) {
char left = p.left;
string right = p.right;
for (int i = 0; i < right.size(); i++) {
char c = right[i];
if (isupper(c)) { // 非终结符
set<char> s;
if (i + 1 < right.size()) { // 存在 b
char b = right[i+1];
s = first[b];
if (s.count('|')) { // b 可以推出空串
s.erase('|');
s.insert(follow[left].begin(), follow[left].end());
}
} else { // 不存在 b
s = follow[left];
}
int len = follow[c].size();
follow[c].insert(s.begin(), s.end());
if (len != follow[c].size()) {
updated = true;
}
}
}
}
}
return follow;
}
};
// 输出集合
void printSet(set<char> s) {
cout << "{";
for (char c : s) {
cout << c << " ";
}
cout << "}" << endl;
}
// 输出 FIRST 集合
void printFirst(map<char, set<char>> first) {
cout << "FIRST 集合:" << endl;
for (auto p : first) {
cout << "FIRST(" << p.first << ") = ";
printSet(p.second);
}
}
// 输出 FOLLOW 集合
void printFollow(map<char, set<char>> follow) {
cout << "FOLLOW 集合:" << endl;
for (auto p : follow) {
cout << "FOLLOW(" << p.first << ") = ";
printSet(p.second);
}
}
int main() {
// 初始化文法
Grammar grammar;
grammar.addProduction('E', "T|T+E");
grammar.addProduction('T', "F|F*T");
grammar.addProduction('F', "(E)|i");
// 计算 FIRST 和 FOLLOW 集合
map<char, set<char>> first = grammar.calculateFirst();
map<char, set<char>> follow = grammar.calculateFollow();
// 输出结果
printFirst(first);
printFollow(follow);
return 0;
}
```
使用时只需要添加你需要的产生式,然后运行程序即可。该代码实现了 FIRST 和 FOLLOW 集合的自动计算,并输出结果。
相关推荐
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)