一、实验目的
理解LR（0）语法分析方法的原理，掌握LR(0)分析表的构造，设计相关数据结构和程序结构，加深对自下而上语法分析方法的理解。
二、实验内容
需要实现的功能：
1）使用LR(0)分析方法构造识别活前缀的DFA；
2）构造文法的分析表（Action表和Goto表）；
3）输入文法：文法描述存储在文本文件中，文件名作为命令行参数输入；
4）输出文法的项目集簇（标准输出设备）；
5）输出识别活前缀的DFA（标准输出设备）；
6）输出文法的Action表和Goto表（输出到创建的指定LR分析表文件，文件名与文法描述文件同名，扩展名为lrtbl）；
7）输出文法是否是LR(0)文法的判断结果（标准输出设备）；
8）构造LR语法分析器的总控程序；
9）对待分析符号串，输出其是否该文法正确句子的判断，并输出文本形式的分析过程（标准输出设备）。
三、实验过程
1.核心概念
（1）LR(0) 项目
一个 LR(0) 项目是一个产生式加上一个点（·），表示分析过程中的某个状态。例如，对于产生式 A → αβ，其 LR(0) 项目可以是 A → α·β。
点（·）表示当前分析的位置，左侧是已经识别的部分，右侧是待识别的部分。
（2）项目集规范簇
项目集规范簇是 LR(0) 分析器的核心数据结构，表示所有可能的分析状态。
每个项目集是一个 LR(0) 项目的集合，通过闭包（Closure）和转移（Goto）操作生成。
（3）ACTION 表和 GOTO 表
ACTION 表：根据当前状态和输入符号，决定下一步动作（移进、规约、接受或报错）。
GOTO 表：根据当前状态和非终结符，决定转移到的下一个状态。
2.实验步骤
（1）数据结构定义
map<char, vector<string>> grammar; // 存储文法规则，键是非终结符，值是产生式列表
set<char> ter; // 终结符集合
set<char> nonter; // 非终结符集合
char start; // 开始符号
string input; // 输入串// LR(0) 项目表示结构
struct Item {char left; // 产生式左部string right; // 产生式右部int dot; // 点的位置，表示当前分析位置// 定义比较运算符以支持在集合中存储bool operator<(const Item& other) const {if (left != other.left) return left < other.left;if (right != other.right) return right < other.right;return dot < other.dot;}bool operator==(const Item& other) const {return left == other.left && right == other.right && dot == other.dot;}
};// LR(0) 规范族
vector<set<Item>> C;
// ACTION 表：存储移进 (s)、规约 (r)、接受 (a)、错误 (e) 操作
map<pair<int, char>, pair<char, string>> actionTable;
// GOTO 表
map<pair<int, char>, int> gotoTable; （2）求解闭包函数算法
（3）求解闭包函数代码
set<Item> closure(set<Item> I){stack<Item> stk;for(auto i : I){stk.push(i);}set<Item> result = I;while(!stk.empty()){Item item = stk.top();stk.pop();if(item.dot<item.right.size()){char next = item.right[item.dot];if(nonter.count(next)){for(auto formula : grammar[next]){Item newItem = {next, formula, 0};if(!result.count(newItem)){result.insert(newItem);stk.push(newItem);}}}}}return result;
}（4）状态转换函数GO(I，X)
（5）求解状态转换函数GO(I，X)代码
set<Item> Goto(set<Item> I, char X){set<Item> J;for(auto item : I){if(item.dot<item.right.size()&&item.right[item.dot]==X){J.insert({item.left, item.right, item.dot+1});}}return closure(J);
}（6） 构建项目集规范簇算法
（7）构建项目集规范簇代码
void constructItems(){set<Item> startItem = closure({{'S', string(1, start), 0}});start='S';C.push_back(startItem);bool changed = true;while(changed){changed=false;for(auto I: C){for(char t : ter){set<Item> J = Goto(I, t);if(!J.empty()){bool sign=false;for(auto c : C){if(c==J){sign=true;break;}}if(sign==false){C.push_back(J);changed=true;}}}for(char n : nonter){set<Item> J = Goto(I, n);if(!J.empty()){bool sign=false;for(auto c : C){if(c==J){sign=true;break;}}if(sign==false){C.push_back(J);changed=true;}}}}}
}（8）求解Action表和GoTo表算法
（9）求解Action表和GoTo表实现代码
void constructActionGoto(){for(int i=0;i<C.size();i++){for(auto item : C[i]){if(item.dot == item.right.size()){if(item.left==start){actionTable[{i, '$'}]={'a', "accept"};}else{for(auto t : ter){actionTable[{i, t}] = {'r', string(1, item.left)+"->"+item.right};}actionTable[{i,'$'}] = {'r', string(1, item.left)+"->"+item.right}; }}else{char next=item.right[item.dot];if(ter.count(next)){set<Item> nextItem = Goto(C[i], next);for(int j = 0;j<C.size();j++){if(nextItem==C[j]){actionTable[{i, next}]={'s', to_string(j)};break;}}}else{set<Item> nextItems = Goto(C[i], next);for (int j = 0; j < C.size(); ++j) {if (nextItems == C[j]) {gotoTable[{i,next}]=j;break;}}}}}}for (int i = 0; i < C.size(); i++) {for (char t : ter) {if (actionTable.find({i, t}) == actionTable.end()) {actionTable[{i, t}] = {'e', "error"}; // 未定义项填充 "error"}}for (char nt : nonter) {if (gotoTable.find({i, nt}) == gotoTable.end()) {gotoTable[{i, nt}] = -1; // -1 代表 GOTO 错误}}}
}（10）构建预测分析程序算法
（11）构建预测分析程序代码
void predict() {stack<int> stateStack; // 状态栈stack<char> symbolStack; // 符号栈stateStack.push(0); // 初始状态symbolStack.push('$'); // 栈底符号input += '$'; // 输入串末尾添加 $int idx = 0; // 输入指针cout << "预测分析过程" << endl;cout << "------------+--------+----+-------------------------------------+-----------" << endl;cout << "栈顶\t\t输入\t查表\t动作\t\t\t\t注释" << endl;cout << "------------+--------+----+-------------------------------------+-----------" << endl;while (true) {int state = stateStack.top(); // 当前状态char current = input[idx]; // 当前输入符号cout<<state<<'\t'<<symbolStack.top()<<'\t'<<current<<'\t';// 查找 ACTION 表if (actionTable.find({state, current}) != actionTable.end()) {auto action = actionTable[{state, current}];char actionType = action.first;string actionValue = action.second;if (actionType == 's') { // 移进动作int nextState = stoi(actionValue);stateStack.push(nextState);symbolStack.push(current);idx++;cout << "s" << nextState << "\t移进\t进栈 " << " " << current << endl;} else if (actionType == 'r') { // 规约动作char left = actionValue[0];string right = actionValue.substr(3);int count = right.size();// 弹出栈顶的符号和状态for (int i = 0; i < count; i++) {stateStack.pop();symbolStack.pop();}// 获取规约后的状态int newState = stateStack.top();if (gotoTable.find({newState, left}) != gotoTable.end()) {int gotoState = gotoTable[{newState, left}];stateStack.push(gotoState);symbolStack.push(left);cout << "r" << gotoState << "\t规约\t出栈 " << count << " 个符号和状态，进栈 " << " " << left << "\t" << left << " -> " << right << endl;} else {cout << "error\t错误\tGOTO 表未定义" << endl;return;}} else if (actionType == 'a') { // 接受动作cout << "acc\t接受\t成功接收！" << endl;return;} else { // 其他动作cout << actionValue << "\t未知动作" << endl;return;}} else {cout << "error\t错误\tACTION 表未定义" << endl;return;}}
}四、实验结果
1.奉上全部代码
#include <bits/stdc++.h>using namespace std;map<char, vector<string>> grammar;
set<char> ter;
set<char> nonter;
char start;
string input; struct Item{char left;string right;int dot;bool operator<(const Item& other) const {if (left != other.left) return left < other.left;if (right != other.right) return right < other.right;return dot < other.dot;}bool operator==(const Item& other) const {return left == other.left && right == other.right && dot == other.dot;}
};vector<set<Item>> C;
map<pair<int,char>, pair<char, string>> actionTable;
map<pair<int,char>, int> gotoTable;// 从文件中读取文法规则和其他信息
void ReadFile() {ifstream file("C:\\Users\\24775\\Desktop\\test.txt"); // 打开文件if (!file) {cout << "文件读取错误!" << endl;return;}string line;// 读取非终结符getline(file, line);for (char c : line) {if (c != ' ') nonter.insert(c);}// 读取终结符getline(file, line);for (char c : line) {if (c != ' ') ter.insert(c);}// 读取文法规则数量int numGrammar;file >> numGrammar;file.ignore(); // 忽略换行符// 读取每条文法规则for (int i = 0; i < numGrammar; i++) {getline(file, line);char left = line[0]; // 产生式左部string right; // 产生式右部// 去掉空格，提取右部for (int j = 4; j < line.size(); j++) {if (line[j] != ' ') right += line[j];}grammar[left].push_back(right); // 存储文法规则}// 读取开始符号file >> start;file.ignore();// 读取输入串getline(file, input);file.close(); // 关闭文件
}set<Item> closure(set<Item> I){stack<Item> stk;for(auto i : I){stk.push(i);}set<Item> result = I;while(!stk.empty()){Item item = stk.top();stk.pop();if(item.dot<item.right.size()){char next = item.right[item.dot];if(nonter.count(next)){for(auto formula : grammar[next]){Item newItem = {next, formula, 0};if(!result.count(newItem)){result.insert(newItem);stk.push(newItem);}}}}}return result;
}set<Item> Goto(set<Item> I, char X){set<Item> J;for(auto item : I){if(item.dot<item.right.size()&&item.right[item.dot]==X){J.insert({item.left, item.right, item.dot+1});}}return closure(J);
}void constructItems(){set<Item> startItem = closure({{'S', string(1, start), 0}});start='S';C.push_back(startItem);bool changed = true;while(changed){changed=false;for(auto I: C){for(char t : ter){set<Item> J = Goto(I, t);if(!J.empty()){bool sign=false;for(auto c : C){if(c==J){sign=true;break;}}if(sign==false){C.push_back(J);changed=true;}}}for(char n : nonter){set<Item> J = Goto(I, n);if(!J.empty()){bool sign=false;for(auto c : C){if(c==J){sign=true;break;}}if(sign==false){C.push_back(J);changed=true;}}}}}
}void constructActionGoto(){for(int i=0;i<C.size();i++){for(auto item : C[i]){if(item.dot == item.right.size()){if(item.left==start){actionTable[{i, '$'}]={'a', "accept"};}else{for(auto t : ter){actionTable[{i, t}] = {'r', string(1, item.left)+"->"+item.right};}actionTable[{i,'$'}] = {'r', string(1, item.left)+"->"+item.right}; }}else{char next=item.right[item.dot];if(ter.count(next)){set<Item> nextItem = Goto(C[i], next);for(int j = 0;j<C.size();j++){if(nextItem==C[j]){actionTable[{i, next}]={'s', to_string(j)};break;}}}else{set<Item> nextItems = Goto(C[i], next);for (int j = 0; j < C.size(); ++j) {if (nextItems == C[j]) {gotoTable[{i,next}]=j;break;}}}}}}for (int i = 0; i < C.size(); i++) {for (char t : ter) {if (actionTable.find({i, t}) == actionTable.end()) {actionTable[{i, t}] = {'e', "error"}; // 未定义项填充 "error"}}for (char nt : nonter) {if (gotoTable.find({i, nt}) == gotoTable.end()) {gotoTable[{i, nt}] = -1; // -1 代表 GOTO 错误}}}
}void predict() {stack<int> stateStack; // 状态栈stack<char> symbolStack; // 符号栈stateStack.push(0); // 初始状态symbolStack.push('$'); // 栈底符号input += '$'; // 输入串末尾添加 $int idx = 0; // 输入指针cout << "预测分析过程" << endl;cout << "------------+--------+----+-------------------------------------+-----------" << endl;cout << "栈顶\t\t输入\t查表\t动作\t\t\t\t注释" << endl;cout << "------------+--------+----+-------------------------------------+-----------" << endl;while (true) {int state = stateStack.top(); // 当前状态char current = input[idx]; // 当前输入符号cout<<state<<'\t'<<symbolStack.top()<<'\t'<<current<<'\t';// 查找 ACTION 表if (actionTable.find({state, current}) != actionTable.end()) {auto action = actionTable[{state, current}];char actionType = action.first;string actionValue = action.second;if (actionType == 's') { // 移进动作int nextState = stoi(actionValue);stateStack.push(nextState);symbolStack.push(current);idx++;cout << "s" << nextState << "\t移进\t进栈 " << " " << current << endl;} else if (actionType == 'r') { // 规约动作char left = actionValue[0];string right = actionValue.substr(3);int count = right.size();// 弹出栈顶的符号和状态for (int i = 0; i < count; i++) {stateStack.pop();symbolStack.pop();}// 获取规约后的状态int newState = stateStack.top();if (gotoTable.find({newState, left}) != gotoTable.end()) {int gotoState = gotoTable[{newState, left}];stateStack.push(gotoState);symbolStack.push(left);cout << "r" << gotoState << "\t规约\t出栈 " << count << " 个符号和状态，进栈 " << " " << left << "\t" << left << " -> " << right << endl;} else {cout << "error\t错误\tGOTO 表未定义" << endl;return;}} else if (actionType == 'a') { // 接受动作cout << "acc\t接受\t成功接收！" << endl;return;} else { // 其他动作cout << actionValue << "\t未知动作" << endl;return;}} else {cout << "error\t错误\tACTION 表未定义" << endl;return;}}
}int main() {ReadFile(); constructItems();constructActionGoto();cout << "非终结符: ";for (const auto &nt : nonter) {cout << nt << " ";}cout << endl;cout << "终结符: ";for (const auto &t : ter) {cout << t << " ";}cout << endl;cout << "文法规则:" << endl;for (auto entry : grammar) {char lhs = entry.first;cout << lhs << " -> ";for (auto rhs : entry.second) {cout << rhs << " | ";}cout << endl;}cout << "起始符号: " << start << endl;// 打印项目集cout << "LR(0) 规范簇：" << endl;for (int i = 0; i < C.size(); i++) {cout << "I" << i << ":\n";for (const auto& item : C[i]) {cout << " " << item.left << " -> ";cout<<item.right<<" "<<item.dot<<endl;}}cout << "\nACTION 表:\n";cout << "状态\t";for (char t : ter) cout << t << "\t";cout << "$\n";for (int i = 0; i < C.size(); i++) {cout << i << "\t";for (char t : ter) {if (actionTable[{i, t}].first != 'e') {cout << actionTable[{i, t}].first << actionTable[{i, t}].second << "\t";} else {cout << "error\t";}}if (actionTable.find({i, '$'}) != actionTable.end()) {cout << actionTable[{i, '$'}].first << actionTable[{i, '$'}].second;} else {cout << "error";}cout << "\n";}cout << "\nGOTO 表:\n";cout << "状态\t";for (char nt : nonter) cout << nt << "\t";cout << "\n";for (int i = 0; i < C.size(); i++) {cout << i << "\t";for (char nt : nonter) {if (gotoTable[{i, nt}] != -1) {cout << gotoTable[{i, nt}] << "\t";} else {cout << "error\t";}}cout << "\n";}predict();return 0;
}2.测试数据
3.测试结果
