用c++编制一个允许规范族有冲突的项目集用向前查看一个符号的办法来进行处理,并且能够解决存在的无效归约问题,以解决冲突的分析过程。
时间: 2023-07-15 18:14:51 浏览: 46
为了解决规范族中的冲突问题,我们需要使用LR分析法。LR分析法是一种自底向上的语法分析方法,它使用一个状态机来表示文法的推导过程,并使用一个分析表来指导分析过程。在这个过程中,我们需要使用项目集来表示状态机的状态。
下面是一份C++代码,它可以允许规范族有冲突的项目集,并使用向前查看一个符号来进行处理,并且能够解决存在的无效归约问题:
```cpp
#include <iostream>
#include <vector>
#include <map>
using namespace std;
// 定义文法符号类型
enum SymbolType { TERMINAL, NONTERMINAL };
// 定义文法符号结构体
struct Symbol {
SymbolType type; // 符号类型,终结符或非终结符
string name; // 符号名称
bool operator==(const Symbol& other) const {
return type == other.type && name == other.name;
}
bool operator<(const Symbol& other) const {
if (type != other.type) {
return type < other.type;
}
return name < other.name;
}
};
// 定义产生式结构体
struct Production {
Symbol left; // 左部符号
vector<Symbol> right; // 右部符号序列
bool operator==(const Production& other) const {
return left == other.left && right == other.right;
}
};
// 定义项目结构体
struct Item {
Production prod; // 产生式
int dot_position; // 点的位置
Symbol lookahead; // 向前查看符号
bool operator==(const Item& other) const {
return prod == other.prod && dot_position == other.dot_position && lookahead == other.lookahead;
}
};
// 定义状态结构体
struct State {
int id; // 状态编号
vector<Item> items; // 项目集合
map<Symbol, int> transitions; // 转移函数
bool operator==(const State& other) const {
return id == other.id && items == other.items && transitions == other.transitions;
}
};
// 定义文法结构体
struct Grammar {
vector<Symbol> terminals; // 终结符集合
vector<Symbol> nonterminals; // 非终结符集合
Symbol start_symbol; // 开始符号
vector<Production> productions; // 产生式集合
};
// 初始化文法
Grammar init_grammar() {
Grammar g;
// 初始化终结符集合
g.terminals.push_back({ TERMINAL, "+" });
g.terminals.push_back({ TERMINAL, "-" });
g.terminals.push_back({ TERMINAL, "*" });
g.terminals.push_back({ TERMINAL, "/" });
g.terminals.push_back({ TERMINAL, "(" });
g.terminals.push_back({ TERMINAL, ")" });
g.terminals.push_back({ TERMINAL, "num" });
// 初始化非终结符集合
g.nonterminals.push_back({ NONTERMINAL, "E" });
g.nonterminals.push_back({ NONTERMINAL, "T" });
g.nonterminals.push_back({ NONTERMINAL, "F" });
// 初始化开始符号
g.start_symbol = { NONTERMINAL, "E" };
// 初始化产生式集合
g.productions.push_back({ { NONTERMINAL, "E" }, { { NONTERMINAL, "E" }, { TERMINAL, "+" }, { NONTERMINAL, "T" } } });
g.productions.push_back({ { NONTERMINAL, "E" }, { { NONTERMINAL, "E" }, { TERMINAL, "-" }, { NONTERMINAL, "T" } } });
g.productions.push_back({ { NONTERMINAL, "E" }, { { NONTERMINAL, "T" } } });
g.productions.push_back({ { NONTERMINAL, "T" }, { { NONTERMINAL, "T" }, { TERMINAL, "*" }, { NONTERMINAL, "F" } } });
g.productions.push_back({ { NONTERMINAL, "T" }, { { NONTERMINAL, "T" }, { TERMINAL, "/" }, { NONTERMINAL, "F" } } });
g.productions.push_back({ { NONTERMINAL, "T" }, { { NONTERMINAL, "F" } } });
g.productions.push_back({ { NONTERMINAL, "F" }, { { TERMINAL, "(" }, { NONTERMINAL, "E" }, { TERMINAL, ")" } } });
g.productions.push_back({ { NONTERMINAL, "F" }, { { TERMINAL, "num" } } });
return g;
}
// 判断一个符号是否为终结符
bool is_terminal(Symbol s) {
return s.type == TERMINAL;
}
// 判断一个符号是否为非终结符
bool is_nonterminal(Symbol s) {
return s.type == NONTERMINAL;
}
// 判断一个符号是否为空串
bool is_epsilon(Symbol s) {
return s.name.empty();
}
// 判断一个符号是否为文法的开始符号
bool is_start_symbol(Grammar g, Symbol s) {
return g.start_symbol == s;
}
// 判断一个文法符号是否可以产生空串
bool can_produce_epsilon(Grammar g, Symbol s) {
if (is_terminal(s)) {
return false;
}
for (auto p : g.productions) {
if (p.left == s) {
bool all_produce_epsilon = true;
for (auto r : p.right) {
if (!can_produce_epsilon(g, r)) {
all_produce_epsilon = false;
break;
}
}
if (all_produce_epsilon) {
return true;
}
}
}
return false;
}
// 计算一个符号的 FIRST 集合
vector<Symbol> compute_first(Grammar g, Symbol s) {
vector<Symbol> result;
// 如果 s 是终结符,则 FIRST(s) = { s }
if (is_terminal(s)) {
result.push_back(s);
return result;
}
// 如果 s 是非终结符,则 FIRST(s) = FIRST(第一个产生式的右部符号)
for (auto p : g.productions) {
if (p.left == s) {
if (!is_epsilon(p.right[0])) {
auto first = compute_first(g, p.right[0]);
result.insert(result.end(), first.begin(), first.end());
}
}
}
// 如果 s 可以产生空串,则 FIRST(s) = FIRST(第一个非空符号) ∪ { ε }
if (can_produce_epsilon(g, s)) {
for (auto p : g.productions) {
if (p.left == s) {
bool all_produce_epsilon = true;
for (auto r : p.right) {
if (!can_produce_epsilon(g, r)) {
auto first = compute_first(g, r);
result.insert(result.end(), first.begin(), first.end());
all_produce_epsilon = false;
break;
}
}
if (all_produce_epsilon) {
result.push_back({ NONTERMINAL, "" });
}
}
}
}
return result;
}
// 计算一个项目集的闭包
vector<Item> closure(Grammar g, vector<Item> items) {
vector<Item> result = items;
while (true) {
bool added_new_items = false;
for (auto item : result) {
if (item.dot_position >= item.prod.right.size()) {
continue;
}
auto next_symbol = item.prod.right[item.dot_position];
if (is_terminal(next_symbol)) {
continue;
}
auto lookahead = item.lookahead;
for (int i = item.dot_position + 1; i < item.prod.right.size(); i++) {
auto symbol = item.prod.right[i];
auto first = compute_first(g, symbol);
bool can_produce_epsilon = false;
for (auto f : first) {
if (!is_epsilon(f)) {
lookahead = f;
break;
} else {
can_produce_epsilon = true;
}
}
if (!can_produce_epsilon) {
break;
}
if (i == item.prod.right.size() - 1) {
lookahead = item.lookahead;
}
}
for (auto p : g.productions) {
if (p.left == next_symbol) {
auto new_item = Item{ p, 0, lookahead };
if (find(result.begin(), result.end(), new_item) == result.end()) {
result.push_back(new_item);
added_new_items = true;
}
}
}
}
if (!added_new_items) {
break;
}
}
return result;
}
// 计算一个项目集的 GOTO 集合
vector<Item> goto_set(Grammar g, vector<Item> items, Symbol symbol) {
vector<Item> result;
for (auto item : items) {
if (item.dot_position >= item.prod.right.size()) {
continue;
}
auto next_symbol = item.prod.right[item.dot_position];
if (next_symbol == symbol) {
Item new_item{ item.prod, item.dot_position + 1, item.lookahead };
result.push_back(new_item);
}
}
return closure(g, result);
}
// 计算 LR(0) 自动机
vector<State> compute_lr0_automaton(Grammar g) {
vector<State> states;
// 初始化初始状态
State initial_state{ 0, closure(g, { Item{ g.productions[0], 0, { TERMINAL, "$" } } }) };
states.push_back(initial_state);
// 计算所有状态
int next_state_id = 1;
while (true) {
bool added_new_state = false;
for (auto state : states) {
for (auto symbol : g.terminals) {
auto goto_items = goto_set(g, state.items, symbol);
if (goto_items.empty()) {
continue;
}
auto existing_state = find(states.begin(), states.end(), State{ -1, goto_items, {} });
if (existing_state != states.end()) {
state.transitions[symbol] = existing_state->id;
} else {
State new_state{ next_state_id++, goto_items, {} };
states.push_back(new_state);
state.transitions[symbol] = new_state.id;
added_new_state = true;
}
}
for (auto symbol : g.nonterminals) {
auto goto_items = goto_set(g, state.items, symbol);
if (goto_items.empty()) {
continue;
}
auto existing_state = find(states.begin(), states.end(), State{ -1, goto_items, {} });
if (existing_state != states.end()) {
state.transitions[symbol] = existing_state->id;
} else {
State new_state{ next_state_id++, goto_items, {} };
states.push_back(new_state);
state.transitions[symbol] = new_state.id;
added_new_state = true;
}
}
}
if (!added_new_state) {
break;
}
}
return states;
}
// 计算一个项目的 LR(1) 向前看集合
vector<Symbol> compute_lr1_lookahead(Grammar g, Item item, map<Item, vector<Symbol>>& lookahead_cache) {
if (lookahead_cache.find(item) != lookahead_cache.end()) {
return lookahead_cache[item];
}
vector<Symbol> result;
if (item.dot_position < item.prod.right.size()) {
auto next_symbol = item.prod.right[item.dot_position];
if (is_terminal(next_symbol)) {
result.push_back(next_symbol);
} else if (is_nonterminal(next_symbol)) {
for (auto f : compute_first(g, item.lookahead)) {
if (!is_epsilon(f)) {
result.push_back(f);
}
}
if (can_produce_epsilon(g, next_symbol)) {
auto rest_item = Item{ item.prod, item.dot_position + 1, item.lookahead };
auto rest_lookahead = compute_lr1_lookahead(g, rest_item, lookahead_cache);
result.insert(result.end(), rest_lookahead.begin(), rest_lookahead.end());
}
}
} else {
result.push_back(item.lookahead);
}
lookahead_cache[item] = result;
return result;
}
// 计算 LR(1) 自动机
vector<State> compute_lr1_automaton(Grammar g) {
vector<State> states;
// 初始化初始状态
map<Item, vector<Symbol>> lookahead_cache;
vector<Item> initial_items;
for (auto p : g.productions) {
auto first = compute_first(g, p.right[0]);
bool can_produce_epsilon = false;
for (auto f : first) {
if (!is_epsilon(f)) {
auto item = Item{ p, 0, f };
initial_items.push_back(item);
} else {
can_produce_epsilon = true;
}
}
if (can_produce_epsilon) {
auto item = Item{ p, 0, { NONTERMINAL, "" } };
initial_items.push_back(item);
}
}
State initial_state{ 0, closure(g, initial_items), {} };
states.push_back(initial_state);
// 计算所有状态
int next_state_id = 1;
while (true) {
bool added_new_state = false;
for (auto state : states) {
for (auto symbol : g.terminals) {
auto goto_items = goto_set(g, state.items, symbol);
if (goto_items.empty()) {
continue;
}
map<Item, Symbol> items_with_lookahead;
for (auto item : state.items) {
auto lookahead = compute_lr1_lookahead(g, item, lookahead_cache);
items_with_lookahead[item] = lookahead[0];
}
map<Production, vector<Symbol>> reduce_productions;
for (auto item : state.items) {
if (item.dot_position < item.prod.right.size()) {
continue;
}
reduce_productions[item.prod].push_back(item.lookahead);
}
if (!reduce_productions.empty()) {
for (auto rp : reduce_productions) {
auto new_item = Item{ rp.first, rp.first.right.size(), rp.second[0] };
auto existing_state = find(states.begin(), states.end(), State{ -1, { new_item }, {} });
if (existing_state != states.end()) {
state.transitions[symbol] = -(existing_state->id);
} else {
State new_state{ -(next_state_id++), { new_item }, {} };
states.push_back(new_state);
state.transitions[symbol] = new_state.id;
added_new_state = true;
}
}
} else {
auto existing_state = find(states.begin(), states.end(), State{ -1, goto_items, {} });
if (existing_state != states.end()) {
state.transitions[symbol] = existing_state->id;
} else {
State new_state{ next_state_id++, goto_items, {} };
states.push_back(new_state);
state.transitions[symbol] = new_state.id;
added_new_state = true;
}
}
}
for (auto symbol : g.nonterminals) {
auto goto_items = goto_set(g, state.items, symbol);
if (goto_items.empty()) {
continue;
}
auto existing_state = find(states.begin(), states.end(), State{ -1, goto_items, {} });
if (existing_state != states.end()) {
state.transitions[symbol] = existing_state->id;
} else {
State new_state{ next_state_id++, goto_items, {} };
states.push_back(new_state);
state.transitions[symbol] = new_state.id;
added_new_state = true;
}
}
}
if (!added_new_state) {
break;
}
}
return states;
}
// 判断一个符号是否为文法的结束符号
bool is_end_symbol(Symbol s) {
return s == Symbol{ TERMINAL, "$" };
}
// 打印状态集合
void print_states(vector<State> states) {
for (auto state : states) {
cout << "state " << state.id << ":" << endl;
for (auto item : state.items) {
cout << " ";
cout << item.prod.left.name << " ->";
for (int i = 0; i < item.prod.right.size(); i++) {
if (i == item.dot_position) {
cout << " .";
}
cout << " " << item.prod.right[i].name;
}
if (item.dot_position == item.prod.right.size()) {
cout << " .";
}
cout << ", " << item.lookahead.name << endl;
}
cout << endl;
}
}
// 打印 LR 分析表
void print_lr_table(Grammar g, vector<State> states) {
// 计算 ACTION 表和 GOTO 表
vector<map<Symbol, int>> action_table(states.size());
vector<map<Symbol, int>> goto_table(states.size());
for (auto state : states) {
for (auto item : state.items) {
if (item.dot_position == item.prod.right.size()) {
if (is_start_symbol(g, item.prod.left) && is_end_symbol(item.lookahead)) {