C++代码,对输入的文法进行读取,并保存在相应的数据结构中。 计算每一个非终结符的FIRST集合。 计算每一个非终结符的FOLLOW集合。 根据FIRST集和FOLLOW集构建预测分析表。 根据分析表对输入的字符串进行分析(总控程序)。 分析过程中能对相应的错误进行处理。
时间: 2024-01-21 08:16:09 浏览: 74
数据结构,手把手教会如何编写C++程序,以及解析C++语言程序结构等方面的知识。
以下是一个简单的C++代码,可以实现对输入文法的读取、计算FIRST集和FOLLOW集、构建预测分析表并对输入字符串进行分析:
```c++
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <map>
using namespace std;
// 定义文法符号类型
enum SymbolType {
TERMINAL, // 终结符
NONTERMINAL // 非终结符
};
// 定义文法符号结构体
struct Symbol {
SymbolType type; // 符号类型
string name; // 符号名称
};
// 定义产生式结构体
struct Production {
Symbol left; // 左部
vector<Symbol> right; // 右部
};
// 读取文法
vector<Production> readGrammar(string filename) {
vector<Production> productions;
ifstream fin(filename);
string line;
while (getline(fin, line)) {
Production production;
size_t pos = line.find("->");
if (pos != string::npos) {
// 解析左部
string left = line.substr(0, pos);
production.left.type = NONTERMINAL;
production.left.name = left;
// 解析右部
string rightStr = line.substr(pos + 2);
for (size_t i = 0; i < rightStr.length(); i++) {
Symbol symbol;
if (rightStr[i] >= 'A' && rightStr[i] <= 'Z') {
// 非终结符
symbol.type = NONTERMINAL;
symbol.name = rightStr.substr(i, 1);
} else {
// 终结符
symbol.type = TERMINAL;
symbol.name = rightStr.substr(i, 1);
}
production.right.push_back(symbol);
}
}
productions.push_back(production);
}
return productions;
}
// 计算FIRST集
void calcFirstSets(vector<Production>& productions, map<string, set<string>>& firstSets) {
bool changed = true;
while (changed) {
changed = false;
for (Production& production : productions) {
Symbol& left = production.left;
vector<Symbol>& right = production.right;
size_t i = 0;
while (i < right.size() && right[i].type == TERMINAL) {
if (firstSets[left.name].insert(right[i].name).second) {
changed = true;
}
i++;
}
if (i < right.size()) {
string name = right[i].name;
set<string>& firstSet = firstSets[name];
size_t oldSize = firstSet.size();
firstSet.insert(firstSets[right[i].name].begin(), firstSets[right[i].name].end());
if (i + 1 == right.size() && firstSet.count("#")) {
firstSet.erase("#"); // 如果右部可以推导出空串,则将空串从FIRST集中删除
}
if (firstSet.size() > oldSize) {
changed = true;
}
} else {
if (firstSets[left.name].insert("#").second) {
changed = true;
}
}
}
}
}
// 计算FOLLOW集
void calcFollowSets(vector<Production>& productions, map<string, set<string>>& firstSets, map<string, set<string>>& followSets) {
bool changed = true;
while (changed) {
changed = false;
for (Production& production : productions) {
Symbol& left = production.left;
vector<Symbol>& right = production.right;
for (size_t i = 0; i < right.size(); i++) {
if (right[i].type == NONTERMINAL) {
string name = right[i].name;
set<string>& followSet = followSets[name];
size_t oldSize = followSet.size();
if (i + 1 == right.size()) {
followSet.insert(followSets[left.name].begin(), followSets[left.name].end());
} else {
set<string>& firstSet = firstSets[right[i + 1].name];
followSet.insert(firstSet.begin(), firstSet.end());
if (firstSet.count("#")) {
followSet.insert(followSets[left.name].begin(), followSets[left.name].end());
}
}
if (followSet.size() > oldSize) {
changed = true;
}
}
}
}
}
}
// 构建预测分析表
map<pair<string, string>, vector<Production>> buildParsingTable(vector<Production>& productions, map<string, set<string>>& firstSets, map<string, set<string>>& followSets) {
map<pair<string, string>, vector<Production>> parsingTable;
for (Production& production : productions) {
Symbol& left = production.left;
vector<Symbol>& right = production.right;
set<string>& firstSet = firstSets[right[0].name];
for (string& symbol : firstSet) {
if (symbol != "#") {
parsingTable[{left.name, symbol}].push_back(production);
}
}
if (firstSet.count("#")) {
set<string>& followSet = followSets[left.name];
for (string& symbol : followSet) {
parsingTable[{left.name, symbol}].push_back(production);
}
}
}
return parsingTable;
}
// 分析输入字符串
bool parseString(string str, map<pair<string, string>, vector<Production>>& parsingTable) {
vector<string> stack;
stack.push_back("$");
stack.push_back(parsingTable.begin()->first.first);
size_t i = 0;
while (!stack.empty()) {
string top = stack.back();
stack.pop_back();
if (top == "$" && i == str.length()) {
return true;
}
if (top == "$" || top == "#") {
continue;
}
if (top == str.substr(i, 1)) {
i++;
} else {
vector<Production>& productions = parsingTable[{top, str.substr(i, 1)}];
if (productions.empty()) {
return false;
} else if (productions.size() > 1) {
// 处理冲突
cout << "Conflict found at input " << i << endl;
}
for (auto it = productions.back().right.rbegin(); it != productions.back().right.rend(); ++it) {
stack.push_back(it->name);
}
}
}
return false;
}
int main() {
vector<Production> productions = readGrammar("grammar.txt");
map<string, set<string>> firstSets;
calcFirstSets(productions, firstSets);
map<string, set<string>> followSets;
calcFollowSets(productions, firstSets, followSets);
map<pair<string, string>, vector<Production>> parsingTable = buildParsingTable(productions, firstSets, followSets);
string str = "abba";
if (parseString(str, parsingTable)) {
cout << "Accepted" << endl;
} else {
cout << "Rejected" << endl;
}
return 0;
}
```
其中,`readGrammar`函数用于读取文法,返回一个`vector`类型的产生式序列;`calcFirstSets`函数用于计算FIRST集,将结果保存在一个`map`类型的变量中;`calcFollowSets`函数用于计算FOLLOW集,将结果保存在一个`map`类型的变量中;`buildParsingTable`函数用于构建预测分析表,返回一个`map`类型的变量,其中键为一个二元组,表示非终结符和终结符的组合,值为一个产生式序列;`parseString`函数用于对输入字符串进行分析,返回一个布尔值,表示输入字符串是否符合文法规则。
阅读全文