c++实现求文法的选择集合
时间: 2024-02-11 16:09:01 浏览: 27
要实现求文法的选择集合,首先需要了解文法的定义和选择集的概念。
文法是由若干个产生式组成的,每个产生式包含一个非终结符和一个由终结符和非终结符组成的串。选择集是对于一个非终结符,它可以推出的所有串的首字符的集合。具体的计算方法如下:
1. 对于每个产生式A->α,如果α是以非终结符B开头的串,那么将FIRST(B)中的所有元素添加到FOLLOW(A)中。
2. 对于每个产生式A->α,如果α可以推导出空串,那么将FOLLOW(A)中的所有元素添加到FOLLOW(B)中。
3. 对于每个产生式A->α,如果α可以推导出非空串,那么将FIRST(α)中的所有元素添加到FOLLOW(A)中。
其中,FIRST(α)表示串α的首字符集合,FOLLOW(A)表示非终结符A的选择集合。
C++实现的伪代码如下:
```c++
// 计算文法G的选择集合
void compute_select_sets(Grammar G) {
// 初始化所有非终结符的选择集
for (auto &N : G.nonterminals) {
N.select_set.clear();
}
// 计算选择集
for (auto &P : G.productions) {
// 1. 计算 FOLLOW(A)
for (auto it = P.rhs.begin(); it != P.rhs.end(); ++it) {
if (it == P.rhs.end() - 1) {
// 最后一个符号
P.lhs.select_set.insert(P.lhs.select_set.end(),
FOLLOW(P.lhs).begin(),
FOLLOW(P.lhs).end());
} else if (is_nonterminal(*it)) {
// 非终结符
auto next_it = it + 1;
while (next_it != P.rhs.end() && is_nullable(*next_it)) {
// 如果后继符号可以推导出空串,继续向后查找
P.lhs.select_set.insert(P.lhs.select_set.end(),
FIRST(*next_it).begin(),
FIRST(*next_it).end());
++next_it;
}
if (next_it == P.rhs.end()) {
// 如果后继符号为空,将 FOLLOW(A) 添加到选择集中
P.lhs.select_set.insert(P.lhs.select_set.end(),
FOLLOW(P.lhs).begin(),
FOLLOW(P.lhs).end());
} else {
// 如果后继符号为终结符,将其添加到选择集中
P.lhs.select_set.insert(*next_it);
}
} else {
// 终结符
P.lhs.select_set.insert(*it);
break;
}
}
// 2. 计算 FOLLOW(B)
for (auto &N : G.nonterminals) {
if (N == P.lhs) {
continue;
}
for (auto it = N.productions.begin(); it != N.productions.end(); ++it) {
auto rhs_it = std::find(it->rhs.begin(), it->rhs.end(), P.lhs);
if (rhs_it == it->rhs.end()) {
continue;
}
auto next_it = rhs_it + 1;
while (next_it != it->rhs.end() && is_nullable(*next_it)) {
N.select_set.insert(N.select_set.end(),
FIRST(*next_it).begin(),
FIRST(*next_it).end());
++next_it;
}
if (next_it == it->rhs.end()) {
N.select_set.insert(N.select_set.end(),
FOLLOW(N).begin(),
FOLLOW(N).end());
} else {
N.select_set.insert(*next_it);
}
}
}
// 3. 计算 FIRST(α)
if (is_nullable(P.rhs)) {
P.lhs.select_set.insert(FOLLOW(P.lhs).begin(), FOLLOW(P.lhs).end());
} else {
P.lhs.select_set.insert(FIRST(P.rhs).begin(), FIRST(P.rhs).end());
}
}
}
```
相关推荐
![](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)
![](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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)