当前位置：网站首页>Compilation principle experiment IV LR (0) analysis method (automatic generation of Lr0 analysis table) complete code
Compilation principle experiment IV LR (0) analysis method (automatic generation of Lr0 analysis table) complete code
2022-07-16 04:01:00 【Zombotany Zhiyong】
Thought analysis
https://zombotany.blog.csdn.net/article/details/125714320
Complete code
#include<iostream>
#include<cstring>
#include<set>
#include<string>
#include<fstream>
#include<map>
#include<iomanip>
#include<vector>
#include<stack>
using namespace std;
char S;// Start Rune
set<char> VN, VT,V;// non-terminal , Terminator
map<char, vector<string>> expressionSet;
// The grammar is written in the document
string PATH = "F:/HOMEWORK/Compiler/Lab4/test.txt";
enum motionType {
UNKNOWN, ADDS, REDU, ACC, ERR, GOTO
};
struct cell {
motionType mt = UNKNOWN;
int nxtsid = -1;
int gid = -1;
};
cell table[100][100];
FILE* fin;
vector<string> filebuffer;// File read buffer
vector<string> inputExpression;// Finally, the expansion is completed , Grammar for analysis
int Vcnt=0;// Number of symbols
string inputStr;// Enter the string to be analyzed
int index = 0;
map<char, int> charToId;
char idToChar[100];
int gcnt = 0;
map<char, vector<int>> Gright;
vector<pair<char, string>> G;
class grammer {
public:
int gid;
char left;
string right;
grammer(const int gid, const char left, const std::string& right) :gid(gid), left(left), right(right) {
}
};
vector<grammer> Gs;
struct item {
int gid;
int i = 0; // Image theory , Period at i Characters ago ：i=3, xxx.x,i=0, .xxxx, i=4, xxxx.
bool operator < (const item& oth) const {
if (gid == oth.gid) return i < oth.i;
return gid < oth.gid;
}
}; // Project and its status
class state {
public:
int sid;
bool end = false;
vector<item> Is; // All items in this state
set<char> right_VNs;
bool findMore() {
if (end) return false;
bool found = false;
for (auto& p : Is) {
if (VN.count(Gs[p.gid].right[p.i]) && !right_VNs.count(Gs[p.gid].right[p.i])) {
// Add items to be reduced
right_VNs.insert(Gs[p.gid].right[p.i]);
found = true;
for (auto& gid : Gright[Gs[p.gid].right[p.i]]) {
Is.push_back({
gid, 0 });
}
}
}
return found;
}
};
vector<state> Ss;
int scnt =0 ;
map<vector<item>, int> IsToId;
void read(){
ifstream fin(PATH);
string str;
if (!fin.is_open()){
cout << "can not open this file" << endl;
return;
}
while (fin >> str)
filebuffer.push_back(str);
// Output the grammar read
for (string st : filebuffer)
cout << st << endl;
}
// Augmentation , Delete vertical bar |
void deleteor(){
for (string str : filebuffer){
if (str.find('|') != string::npos){
// take A->beta1|beta2 Split into A->beta1 and A->beta2
string right1 = str.substr(3, str.find('|') - 3);
string newstr1 = "";
newstr1 = str[0] + (string)"->" + right1;
inputExpression.push_back(newstr1);
string right2 = str.substr(str.find('|') + 1);
string newstr2 = "";
newstr2 += str[0] + (string)"->" + right2;
inputExpression.push_back(newstr2);
}
else
inputExpression.push_back(str);
}
string newstr = "S";
newstr = newstr + (string)"->"+inputExpression[0][0];
inputExpression.insert(inputExpression.begin(), newstr);
S = 'S';
cout << "\n Augmentation \n";
for (string str : inputExpression)
cout << str << endl;
}
void getRight(const string& gram) {
int s;
char left;
for (s = 0; s < gram.length() && gram[s] == ' '; ++s);
left = gram[s];
if (S == '\0') S = left; // Start non terminal
for (s = 1; s < gram.length() && gram[s] == ' '; ++s);
s += 2;
for (int i = s; i < gram.length(); ++i)
V.insert(gram[i]); // All symbols on the right
if (!VN.count(left)) {
VN.insert(left); // non-terminal
charToId[left] = Vcnt;
idToChar[Vcnt] = left;
++Vcnt;
}
Gs.emplace_back(gcnt, left, gram.substr(s, gram.length() - s));
Gright[left].push_back(gcnt);
++gcnt;
}
void readGrammers() {
VT.insert('#'); // Terminator '#'
charToId['#'] = Vcnt;
idToChar[Vcnt] = '#';
++Vcnt;
for (auto gram : inputExpression)
getRight(gram);
for (auto str : inputExpression) {
string strRight = str.substr(3);
G.push_back({
str[0],strRight });
}
for (auto c : V) {
if (!VN.count(c) && !VT.count(c)) {
VT.insert(c); // Terminator
charToId[c] = Vcnt;
idToChar[Vcnt] = c;
++Vcnt;
}
}
}
void displayVnVt() {
cout << "\n non-terminal \n";
for (auto c : VN)
cout << c << " ";
cout << "\n Terminator \n";
for (auto c : VT)
cout << c << " ";
}
void printState(int sid) {
cout << "\n---------state---------" << endl;
cout << "sid: " << sid << endl;
cout << "isend: " << (Ss[sid].end ? "true" : "false") << endl << endl;
for (auto& p : Ss[sid].Is) {
cout << Gs[p.gid].left << "->";
for (int i = 0; i < p.i; ++i) {
cout << Gs[p.gid].right[i];
}
cout << ".";
for (int i = p.i; i < Gs[p.gid].right.length(); ++i) {
cout << Gs[p.gid].right[i];
}
cout << endl;
}
cout << "-----------------------" << endl;
}
int derivateState(int isid, char c);
void derivateAll(int sid) {
if (Ss[sid].end) return;
std::set<char> input_c;
for (auto& p : Ss[sid].Is) {
input_c.insert(Gs[p.gid].right[p.i]);
}
for (auto& c : input_c) {
int nxtsid = derivateState(sid, c);
if (nxtsid == -1) continue;
// assert(table[sid][charToId[c]].mt == UNKNOWN);
if (VN.count(c)) {
// Yes no terminator
table[sid][charToId[c]].mt = GOTO;
table[sid][charToId[c]].nxtsid = nxtsid;
}
else {
// It's the terminator
table[sid][charToId[c]].mt = ADDS;
table[sid][charToId[c]].nxtsid = nxtsid;
}
}
}
int derivateState(int isid, char c) {
if (Ss[isid].end) return -1;
state ts;
bool isend = false;
for (auto& p : Ss[isid].Is) {
if (Gs[p.gid].right[p.i] == c) {
ts.Is.push_back({
p.gid,p.i + 1 });
if (Gs[p.gid].right.length() == p.i + 1) {
isend = ts.end = true;
}
}
}
if (ts.Is.size() == 0) return -1;
ts.findMore();
int sid;
bool rec = false;
if (IsToId.count(ts.Is)) {
sid = IsToId[ts.Is];
rec = true;
}
else {
IsToId[ts.Is] = sid = scnt++;
ts.sid = sid;
Ss.push_back(ts);
printState(sid);
}
if (!rec) derivateAll(sid); // This recursive call is a little dangerous
return sid;
}
int generateI0() {
Ss.emplace_back();
Ss[0].right_VNs.insert(S);
for (auto gid : Gright[S]) {
// In theory, after expanding with expanding grammar , There is only one entry rule
Ss[0].Is.push_back({
gid,0 });
}
while (Ss[0].findMore());
printState(0);
IsToId[Ss[0].Is] = scnt++;
return 0;
}
void fillTable() {
int ssid = generateI0();
derivateAll(ssid);
for (int sid = 0; sid < IsToId.size(); ++sid) {
if (Ss[sid].end) {
// Is the final state
if (Gs[Ss[sid].Is[0].gid].right[Ss[sid].Is[0].i - 1] == '#') {
table[sid][charToId['#']].mt = ACC;
}
else {
table[sid][0].mt = REDU;
table[sid][0].gid = Ss[sid].Is[0].gid;
for (int i = VN.size()+1; i < Vcnt; ++i) {
table[sid][i].mt = REDU;
table[sid][i].gid = Ss[sid].Is[0].gid;
}
}
}
}
}
map<char, string> LRTable[20];
void printTable() {
cout <<setw(5)<< " ";
for (int j = VT.size(); j < Vcnt; ++j) {
char ch= idToChar[j];
cout <<setw(5)<<ch;
}
for (int j = 0; j < VT.size(); ++j) {
char ch= idToChar[j];
cout << setw(5) << ch;
}
cout << endl;
for (int i = 0; i < IsToId.size(); ++i) {
cout << setw(5)<< i;
for (int j = VT.size(); j < Vcnt; ++j) {
if (table[i][j].mt == ADDS) {
string str = "s" + to_string(table[i][j].nxtsid);
LRTable[i][idToChar[j]] = str;
cout << setw(5) << str;
}
else if (table[i][j].mt == REDU) {
if (i == 1) {
if (idToChar[j] == '#') {
string str = "ACC";
LRTable[i]['#'] = str;
table[i][j].mt = ACC;
cout << setw(5) << str;
}
else cout << setw(5) << " ";
}
else {
string str = "r" + to_string(table[i][j].gid);
LRTable[i][idToChar[j]] = str;
LRTable[i]['#'] = str;
cout << setw(5) << str;
}
}
else if (table[i][j].mt == ACC) {
string str = "ACC";
LRTable[i][idToChar[j]] = str;
cout << setw(5) << str;
}
else if (table[i][j].mt == GOTO) {
string str = to_string(table[i][j].nxtsid);
LRTable[i][idToChar[j]] = str;
cout << setw(5) << str;
}
else {
string str = "";
cout << setw(5) << str;
}
}
for (int j = 0; j < VT.size(); ++j) {
if (table[i][j].mt == ADDS) {
string str = "s" + to_string(table[i][j].nxtsid);
LRTable[i][idToChar[j]] = str;
cout << setw(5) << str;
}
else if (table[i][j].mt == REDU) {
if (i == 1) {
if (idToChar[j] == '#') {
string str = "ACC";
LRTable[i]['#'] = str;
table[i][j].mt = ACC;
cout << setw(5) << str;
}
else cout << setw(5) << " ";
}
else {
string str = "r" + to_string(table[i][j].gid);
LRTable[i][idToChar[j]] = str;
LRTable[i]['#'] = str;
cout << setw(5) << str;
}
}
else if (table[i][j].mt == ACC) {
string str = "ACC";
LRTable[i][idToChar[j]] = str;
cout << setw(5) << str;
}
else if (table[i][j].mt == GOTO) {
string str = to_string(table[i][j].nxtsid);
LRTable[i][idToChar[j]] = str;
cout << setw(5) << str;
}
else {
string str = "";
cout << setw(5) << str;
}
}
cout << endl;
}
//for (int i = 0; i < IsToId.size(); i++) {
// cout << i << " ";
// for (auto node : LRTable[i]) {
// cout << node.first << ":" << node.second << " ";
// }
// cout << endl;
//}
}
stack<int> statusStack;
stack<char> symbolStack;
void display(int p, string input, string action) {
string status = "";
stack<int> tempStatusStack = statusStack;
while (!tempStatusStack.empty()) {
status += to_string(tempStatusStack.top());
tempStatusStack.pop();
}
string symbol = "";
stack<char> tempSymbolStack = symbolStack;
while (!tempSymbolStack.empty()) {
symbol += tempSymbolStack.top();
tempSymbolStack.pop();
}
string in = input.substr(p);
string actionstr = "";
if (action == "ACC")
actionstr = "acc: The analysis was successful ";
else if (action[0] == 'r') {
actionstr += action;
int st = stoi(action.substr(1));
actionstr += ": use ";
actionstr += inputExpression[st];
actionstr += " Statute ";
}
else if (action[0] == 's') {
actionstr += action;
int st = stoi(action.substr(1));
actionstr += ": state ";
actionstr += to_string(st);
actionstr += " Push ";
}
cout << setw(20) << status << setw(20) << symbol << setw(20) << in << setw(20) << actionstr << endl;
}
void LR0Analysis() {
inputStr += '#';
int p = 0;
cout << endl << inputStr << endl;
cout << setw(20) << " State stack " << setw(20) << " Symbol stack " << setw(20) << " Input string " << setw(20) << " action " << endl;
statusStack.push(0);
symbolStack.push('#');
while (1) {
int status = statusStack.top();
char nextChar = inputStr[p];
int nextStatus = -1;
if (LRTable[status].count(nextChar)) {
string info = LRTable[status][nextChar];
display(p,inputStr,info);
if (info == "ACC")
break;
if (info[0] == 's') {
// Move into the state
nextStatus = stoi(info.substr(1));
statusStack.push(nextStatus);
symbolStack.push(nextChar);
p++;
}
else if (info[0] == 'r') {
nextStatus = stoi(info.substr(1));
for (int i = 0; i < G[nextStatus].second.size(); i++) {
symbolStack.pop();
statusStack.pop();
}
char temp = G[nextStatus].first;
symbolStack.push(temp);
int s = statusStack.top();
statusStack.push(stoi(LRTable[s][temp]));
}
else {
break;
}
}
else {
cout << "ERROR";
return;
}
}
}
int main()
{
// Read grammar from file
read();
// Augmentation
deleteor();
readGrammers();
displayVnVt();
fillTable();
printTable();
cout << "\n Input statement :\n";
cin >> inputStr;
LR0Analysis();
return 0;
}
Input file (test.txt)
E->aA|bB
A->cA|d
B->cB|d
边栏推荐
- Try to live today well
- Image waterfall rendering in pure PHP
- 从ecs 自建mysql 同步到MaxCompute使用binlog的方式同步，制定了同步规则后，
- Does website moving affect website ranking? How to change the website server to avoid affecting the ranking
- leetcode：803. Make bricks
- VMware vCenter Server Appliance（VCSA）6.0安装过程
- Usage differences between isempty and isblank
- How to evaluate and compare the performance of report tools?
- ASP.NET Core 使用记录3
- 重磅发新 | 尚硅谷C4D三维设计实战教程发布
猜你喜欢
【OpenCV 例程200篇】228. 特征描述之 extendLBP 改进算子
vCenter6 vsphere无法登录故障处理记录
深入解析Kubernetes admission webhooks
手撕Gateway源码，今日撕工作流程、负载均衡源码
iMeta期刊部分文章被PubMed收录
Terra 陨落后是什么让 Tron 跻身到了公链前三？
![Golang environment installation exception [resolved]](/img/c3/ed1c635926ac75c65ff7ccb931767f.png)
Golang environment installation exception [resolved]
老板想要的简单方案 vs. 程序员理解的需求 |漫画
海南大学张家超教授—基于宏基因组的肠道微生物突变研究(今晚7点半)
教程篇(7.0) 02. 安装和许可 * FortiClient EMS * Fortinet 网络安全专家 NSE 5
随机推荐
Debezium系列之：记录数据库升级对Debezium的影响
GCC Rust 获批将被纳入主线代码库，或将于 GCC 13 中与大家见面
翔子的故事
The simple solution the boss wants vs. the needs the programmer understands | cartoon
vCenter6 vsphere无法登录故障处理记录
In depth analysis of kubernetes admission webhooks
MySQL column to row and row to column
Description of data types and member variables defined in STL mental method 4 vector class
互联网对内核模块的加载之道
UE4 指南针制作方法
flink cdc 支持sql server、达梦数据吗？
golang环境安装异常【已解决】
推荐一本免费数据分析电子书
Multiple table connections
leetcode：517. Super washing machine
Gui-pyqt5-initial 1
Prometheus Operator概述
TIA botu_ Detailed explanation of the allocation method of PROFINET device name and specific steps of media free device replacement
案例推荐｜千亿级、大规模：腾讯超大 Apache Pulsar 集群性能调优实践
龙芯派2代编译内核（失败版）