?這學期的編譯原理終于學完了，不愧是號稱最難的科目。要用C++從頭到尾實現一下小型編譯器，還真不容易啊。不過總算是做完了。

?

首先上文法，這個文法是根據上一篇博客簡化的，但還是有一點問題的，暫時發現有一個地方不符合LR1的規則（函數的返回類型如果是int就會報錯）。

?

有了文法就可以生成LR1分析表了，如圖所示，一共有187個項目集族，代碼跑了2分50秒才出結果，要不是我優化了一個下午，剪掉了一些不必要的循環，以及把一個o(n)的改成了lg的，大概要跑10分鐘吧。

具體的優化在代碼中有注釋。

?

生成的LR(1)表存到文件中，用err表示空格，便于從文件再讀到程序中，如圖所示：

?

接下來是輸入程序：

?

轉成Token，如果是ID或則NUM類型的，還需要存下對應的值。

?

下面的就是分析過程和“文本格式的語法樹”了

?

同時dfs語法樹生成了四元式：

?

代碼：

1 #include <map> 2 #include <set> 3 #include <list> 4 #include <ctime> 5 #include <queue> 6 #include <stack> 7 #include <string> 8 #include <vector> 9 #include <iomanip> 10 #include <fstream> 11 #include <sstream> 12 #include <iostream> 13 using namespace std; 14 #define rep(i,a,n) for(int i=a;i<n;i++) 15 #define per(i,a,n) for(int i=n-1;i>=a;i--) 16 #define all(x) (x).begin(),(x).end() 17 typedef pair<string, vector<string>> Production; //產生式 18 const int WIDTH = 16; //setw(WIDTH) 19 // head 20 21 struct Project { //項目集 22 string left; 23 vector<string> right; 24 set<string> expect; 25 26 const bool operator<(const Project &p) const { 27 if (left < p.left) return true; 28 if (left > p.left) return false; 29 if (right < p.right) return true; 30 if (right > p.right) return false; 31 if (expect < p.expect) return true; 32 return false; 33 } 34 35 const bool operator==(const Project &p) const { 36 if (left == p.left && right == p.right && expect == p.expect) return true; 37 return false; 38 } 39 }; 40 41 namespace project { //產生項目集族 42 set<string> terminal; //終結符 43 set<string> not_terminal; //非終結符 44 set<string> all_symbol; //所有的符號 45 vector<string> sss; //所有的符號 46 map<string, int> Hash; //符號哈希 47 vector<Production> vp; //所有的產生式，加·前 48 set<Production> sp; //所有的項目集，加·后 49 50 void PROJECT() { 51 ifstream fin("C:\\Users\\Flowersea\\Desktop\\Grammar.txt"); 52 string a, b; 53 vector<string> c; 54 while (fin >> a >> b) { 55 not_terminal.insert(a); 56 string str; 57 getline(fin, str); 58 stringstream ss; 59 ss.str(str); 60 c.clear(); 61 while (ss >> str) { 62 c.push_back(str); 63 int fg = 0; 64 rep(i, 0, str.size()) { 65 if (!(str[i] >= 'a' && str[i] <= 'z' || str[i] == '_')) { //文法中非終結符都是小寫字母和下劃線組成的 66 fg = 1; 67 break; 68 } 69 } 70 if (fg) terminal.insert(str); //如果含有小寫字母和下劃線以外的符號就是終結符 71 else not_terminal.insert(str); //否則是非終結符 72 } 73 vp.push_back(Production(a, c)); 74 } 75 terminal.insert("#"); 76 not_terminal.erase("program'"); //刪掉program' 77 all_symbol.insert(all(terminal)); 78 all_symbol.insert(all(not_terminal)); 79 for (auto it : terminal) sss.push_back(it); 80 for (auto it : not_terminal) sss.push_back(it); //sss其實是為了輸出lr1表的表頭 81 rep(i, 0, sss.size()) Hash[sss[i]] = i; 82 for (auto it : vp) { 83 a = it.first, c = it.second; 84 rep(i, 0, c.size() + 1) { 85 vector<string> d = c; 86 d.insert(d.begin() + i, "."); 87 sp.insert(Production(a, d)); 88 } 89 } 90 } 91 92 void main() { 93 PROJECT(); 94 } 95 } 96 97 namespace lr1 { //生成lr表 98 using namespace project; 99 100 vector<set<Project>> vsp(1); //項目集族 101 string lr1[1000][1000]; //lr1表 102 int n, m; //n行，m列 103 104 set<string> FIRST(vector<string> X) { //求FIRST集族 105 set<string> res; 106 if (terminal.find(X[0]) != terminal.end()) { 107 res.insert(X[0]); //如果是終結符，直接insert返回 108 return res; 109 } 110 else { 111 rep(j, 0, vp.size()) { //遍歷所有的產生式 112 if (vp[j].first == X[0]) { 113 if (terminal.find(vp[j].second[0]) != terminal.end()) //如果第一個是終結符 114 res.insert(vp[j].second[0]); //插入到res中 115 else { 116 set<string> t = FIRST(vp[j].second); //否則遞歸求FIRST集 117 res.insert(all(t)); 118 } 119 } 120 } 121 } 122 return res; 123 } 124 125 set<Project> GO(set<Project> I, string X) { //GO函數 126 set<Project> J; 127 for (auto it : I) { 128 vector<string> vs = it.right; 129 auto pos = find(all(vs), "."); 130 if (pos == vs.end() - 1) continue; //如果·是最后一個，continue 131 if (*(pos + 1) == X) { 132 swap(*pos, *(pos + 1)); //交換·和后面的一個字符串 133 J.insert(Project{ it.left, vs, it.expect }); 134 } 135 } 136 return J; 137 } 138 139 set<Project> CLOSURE(set<Project> I) { //求closure 140 while (1) { 141 bool update = false; //判斷此次循環是否有更新 142 for (auto it : I) { 143 vector<string> B = it.right; 144 auto pos = find(all(B), "."); //找到·的位置 145 if (pos == B.end() - 1) continue; //如果·是最后一個，continue 146 string c = *(pos + 1); //c等于·后面的字符 147 if (terminal.find(c) != terminal.end()) continue; //如果c是終結符，continue 148 B.erase(B.begin(), pos + 2); //刪掉·后面的一個字符之前的所有字符，包括它自己 149 string last; //為了剪枝，記錄上一次求FIRST集的第一個字符串 150 for (auto ite : it.expect) { 151 B.push_back(ite); //把expect插入到B的后面 152 if (last == B[0]) continue; //如果B[0]和上次的last一樣，就不求了，因為文法中沒有空產生式 153 else last = B[0]; 154 set<string> First = FIRST(B); //求B的FIRST集 155 B.pop_back(); 156 for (auto it1 : sp) { 157 if (it1.first == c && it1.second[0] == ".") { //找到·開頭的 158 set<string> ss; //ss為空，為了二分查找 159 Project p{ it1.first,it1.second,ss }; 160 auto pos = I.lower_bound(p); //查找第一個大于等于p的位置 161 if (pos != I.end() && (*pos).left == it1.first && (*pos).right == it1.second) { //如果pos指向的first，second符合 162 p = *pos; 163 I.erase(p); //因為不能直接插入，所以需要先刪除在插入 164 p.expect.insert(all(First)); 165 I.insert(p); 166 } 167 else { 168 update = true; //插入了新的一項，所以update為true。經過測試發現只更新expext可以不用設置update為true 169 I.insert(Project{ it1.first, it1.second, First }); 170 } 171 } 172 } 173 } 174 } 175 if (!update) break; //如果沒更新，跳出循環 176 } 177 return I; 178 } 179 180 void LR1() { 181 for (auto it : sp) { //先插入第一條program' -> program 182 if (it.first == "program'" && it.second[0] == ".") { 183 set<string> ss; 184 ss.insert("#"); 185 vsp[0].insert(Project{ it.first,it.second, ss }); 186 break; 187 } 188 } 189 vsp[0] = CLOSURE(vsp[0]); //然后求第一個項目集的閉包 190 rep(i, 0, vsp.size()) { 191 time_t t = time(0); //為了在控制臺顯示每個項目集計算的時間，debug 192 char tmp[64]; 193 strftime(tmp, sizeof(tmp), ": %X", localtime(&t)); 194 cout << i; 195 puts(tmp); 196 //規約 197 for (auto it : vsp[i]) { 198 int len = it.right.size(); 199 if (it.right[len - 1] == ".") { //如果最后一個字符串是·，就可以規約了 200 it.right.erase(it.right.end() - 1); //刪除那個· 201 Production p(it.left, it.right); //構造產生式p 202 rep(j, 0, vp.size()) { 203 if (vp[j] == p) { //此次循環是為了找到產生式p的編號為j 204 string t = "r" + to_string(j); //lr1表 205 if (j == 0) t = "acc"; //如果是第0條，應該是acc 206 for (auto its : it.expect) 207 lr1[i][Hash[its]] = t; //填lr1表 208 } 209 } 210 } 211 } 212 213 for (auto X : all_symbol) { //遍歷所有的符號 214 set<Project> J = GO(vsp[i], X); //J = GO(I, X) 215 if (!J.empty()) { //如果J不為空 216 J = CLOSURE(J); //求J的閉包 217 int k; 218 auto pos = find(all(vsp), J); 219 if (pos != vsp.end()) { //如果vsp中已經存在了這個項目集族 220 k = pos - vsp.begin(); //記下存在的位置 221 } 222 else { 223 k = vsp.size(); //不存在就插入，標號k就是push之前的size 224 vsp.push_back(J); 225 } 226 227 //移進和GOTO 228 int j = Hash[X]; 229 if (terminal.find(X) != terminal.end()) //如果X為終結符 230 lr1[i][j] = "s" + to_string(k); //就移進 231 else lr1[i][j] = to_string(k); //否則goto 232 } 233 } 234 } 235 } 236 237 void PRINT() { //此函數為了輸出項目集族和lr表到文件中 238 ofstream fout("C:\\Users\\Flowersea\\Desktop\\output.out"); 239 fout << " CLOSURE" << endl; 240 rep(i, 0, 20) fout << '-'; 241 fout << endl; 242 rep(i, 0, vsp.size()) { 243 fout << i << ":" << endl; 244 set<Project> sp = vsp[i]; 245 for (auto it : sp) { 246 string b; 247 rep(i, 0, it.right.size()) b += ' ' + it.right[i]; 248 b.erase(0, 1); 249 string c; 250 for (auto it : it.expect) c += it + '/'; 251 c.pop_back(); 252 fout << " " << it.left << " -> " 253 << b << ", " << c << endl; 254 } 255 rep(i, 0, 20) fout << '-'; 256 fout << endl; 257 } 258 fout << endl << endl << endl; 259 260 rep(i, 0, 3) fout << setw(WIDTH) << ' '; 261 fout << "LR(1)分析表" << endl; 262 fout << '|' << endl << '|'; 263 fout << setw(WIDTH) << "狀態"; 264 fout << '|'; 265 n = vsp.size(); 266 m = sss.size(); 267 rep(i, 0, m) { 268 fout << setw(WIDTH) << sss[i]; 269 if (i == terminal.size() - 1) fout << '|'; 270 } 271 fout << '|' << endl << '|'; 272 rep(i, 0, 200) fout << '-'; 273 fout << '|' << endl << '|'; 274 rep(i, 0, n) { 275 fout << setw(WIDTH) << i; 276 fout << '|'; 277 rep(j, 0, m) { 278 fout << setw(WIDTH) << lr1[i][j]; 279 if (j == terminal.size() - 1) fout << '|'; 280 } 281 fout << '|' << endl << '|'; 282 } 283 rep(i, 0, 200) fout << '-'; 284 fout << '|'; 285 fout << endl << endl << endl; 286 } 287 288 void OUT_LR1() { //輸出lr1表到文件中 289 ofstream fout("C:\\Users\\Flowersea\\Desktop\\LR(1).txt"); 290 fout << n << " " << m << endl; 291 rep(i, 0, n) { 292 rep(j, 0, m) { 293 if (lr1[i][j] == "") fout << "err "; //如果為空，輸出err 294 else fout << lr1[i][j] << ' '; 295 } 296 fout << endl; 297 } 298 } 299 300 void main() { 301 project::main(); 302 LR1(); 303 PRINT(); 304 OUT_LR1(); 305 } 306 } 307 308 namespace grammar { 309 using namespace project; 310 struct E { //E，記錄一下信息 311 string place; //位置 312 vector<pair<int, vector<string>>> code; //四元式 313 string name; //變量的name 314 string value; //常量的value 315 int Begin; 316 int Next; 317 int True; 318 int False;; 319 }; 320 321 string lr1[1000][1000]; 322 int n, m; 323 int cnt = 0; //Tree的節點數 324 vector<int> G[1000]; //用鄰接表存Tree 325 vector<string> symbol; //每個節點對應的符號名字 326 vector<E> attr; //每個節點對用的屬性，類型是E 327 328 void IN_LR1() { //讀入lr表 329 ifstream fin("C:\\Users\\Flowersea\\Desktop\\LR(1).txt"); 330 fin >> n >> m; 331 rep(i, 0, n) rep(j, 0, m) fin >> lr1[i][j]; 332 } 333 334 void MORPHOLOGY() { //詞法分析器 335 ifstream fin("C:\\Users\\Flowersea\\Desktop\\Program.txt"); 336 ofstream fout("C:\\Users\\Flowersea\\Desktop\\Token.txt"); 337 string keyword[27] = { "main","if","else","int","return","void","while", 338 "=","+","-","*","/","<","<=",">",">=","!=","==",",",";",":","{","}","[","]","(",")" }; 339 map<string, int> H; 340 rep(i, 0, 27) H[keyword[i]] = i + 1; 341 string s; 342 while (fin >> s) { 343 rep(i, 0, s.length()) { 344 if (isalpha(s[i])) { 345 if (s[i] == 'm' && s[i + 1] == 'a' && s[i + 2] == 'i' 346 && s[i + 3] == 'n' && !isalnum(s[i + 4])) { 347 fout << "ID" << endl; 348 i += 3; 349 } 350 else if (s[i] == 'i' && s[i + 1] == 'f' && !isalnum(s[i + 2])) { 351 fout << "IF" << endl; 352 i += 1; 353 } 354 else if (s[i] == 'e' && s[i + 1] == 'l' && s[i + 2] == 's' 355 && s[i + 3] == 'e' && !isalnum(s[i + 4])) { 356 fout << "ELSE" << endl; 357 i += 3; 358 } 359 else if (s[i] == 'i' && s[i + 1] == 'n' && s[i + 2] == 't' 360 && !isalnum(s[i + 3])) { 361 fout << "INT" << endl; 362 i += 2; 363 } 364 else if (s[i] == 'r' && s[i + 1] == 'e' && s[i + 2] == 't' && s[i + 3] == 'u' 365 && s[i + 4] == 'r' && s[i + 5] == 'n' && !isalnum(s[i + 6])) { 366 fout << "RETURN" << endl; 367 i += 5; 368 } 369 else if (s[i] == 'v' && s[i + 1] == 'o' && s[i + 2] == 'i' 370 && s[i + 3] == 'd' && !isalnum(s[i + 4])) { 371 fout << "VOID" << endl; 372 i += 3; 373 } 374 else if (s[i] == 'w' && s[i + 1] == 'h' && s[i + 2] == 'i' 375 && s[i + 3] == 'l' && s[i + 4] == 'e' && !isalnum(s[i + 5])) { 376 fout << "WHILE" << endl; 377 i += 4; 378 } 379 else { 380 string token; 381 while (isalnum(s[i])) token += s[i++]; 382 i--; 383 fout << "ID" << ' ' << token << endl; 384 } 385 } 386 else if (isdigit(s[i])) { 387 int num = 0; 388 while (isdigit(s[i])) num = num * 10 + s[i++] - '0'; 389 i--; 390 fout << "NUM" << ' ' << num << endl; 391 } 392 else { 393 if (s[i] == '!') { 394 fout << "!=" << endl; 395 i++; 396 } 397 else if (s[i] == '=' && s[i + 1] == '=') { 398 fout << "==" << endl; 399 i++; 400 } 401 else if (s[i] == '<' && s[i + 1] == '=') { 402 fout << "<=" << endl; 403 i++; 404 } 405 else if (s[i] == '>' && s[i + 1] == '=') { 406 fout << ">=" << endl; 407 i++; 408 } 409 else { 410 string t; 411 t += s[i]; 412 fout << t << endl; 413 } 414 } 415 } 416 } 417 } 418 419 void JUDGE() { //生成語法樹 420 ifstream fin("C:\\Users\\Flowersea\\Desktop\\Token.txt"); 421 ofstream fout("C:\\Users\\Flowersea\\Desktop\\Analysis.txt"); 422 423 vector<pair<string, string>> vs; //存Token 424 pair<string, string> str; 425 while (fin >> str.first) { 426 if (str.first == "NUM" || str.first == "ID") 427 fin >> str.second; //如果是NUM和ID還要讀入name或value 428 vs.push_back(str); 429 } 430 431 int a[1000], top = 1; //a位狀態棧，top為棧頂指針 432 a[0] = 0; //初始狀態 433 E e; //初始狀態 434 vector<pair<string, E>> b{ make_pair("#",e) }; //初始狀態 435 vector<pair<string, string>> c = vs; //初始狀態 436 c.push_back(make_pair("#", "")); //初始狀態 437 438 fout << left << setw(WIDTH / 2) << ""; 439 fout << left << setw(WIDTH * 4) << "狀態"; 440 fout << left << setw(WIDTH * 10) << "符號"; 441 fout << right << setw(WIDTH * 7) << "輸入串" << endl; 442 443 int id = 1; //id為行數 444 stack<int> S; //S同步每一次操作，為了生成Tree 445 while (1) { 446 string temp; 447 rep(i, 0, top) temp += to_string(a[i]) + ' '; 448 fout << left << setw(WIDTH / 2) << id++; 449 fout << left << setw(WIDTH * 4) << temp; 450 string sb, sc; 451 for (auto it : b) sb += ' ' + it.first; 452 sb.erase(0, 1); 453 for (auto it : c) sc += ' ' + it.first; 454 sc.erase(0, 1); 455 fout << left << setw(WIDTH * 10) << sb; 456 fout << right << setw(WIDTH * 7) << sc << endl; //以上都是為了輸出 457 458 string action = lr1[a[top - 1]][Hash[c[0].first]]; //查lr1表 459 if (action == "acc") break; //如果是acc表示結束，break 460 if (action == "err") { //如果是err表示出錯，直接return 461 cerr << "error" << endl; 462 return; 463 } 464 if (action[0] == 's') { //如果action第一個字符為s，表示移進 465 action.erase(0, 1); //刪掉第一個字符 466 int num = atoi(action.c_str()); //轉成數字 467 a[top++] = num; //push進棧a 468 E e; 469 if (c[0].first == "ID") e.name = c[0].second; //如果是ID，記下name 470 else if (c[0].first == "NUM") e.value = c[0].second; //如果是NUM，記下value 471 b.push_back(make_pair(c[0].first, e)); //push進棧b 472 symbol.push_back(c[0].first); //push進棧symbol 473 attr.push_back(e); //push進棧attr 474 S.push(cnt++); //S中push的當前的節點號 475 c.erase(c.begin()); //pop出棧c 476 } 477 else { 478 action.erase(0, 1); 479 int num = atoi(action.c_str()); 480 Production p = vp[num]; //用第num條產生式規約 481 int len = p.second.size(); //second的長度 482 queue<int> son; //son暫時記錄棧S中pop的節點 483 while (len--) { 484 top--; //pop棧a 485 b.pop_back(); //pop棧b 486 son.push(S.top()); //son先記錄下S需要pop的節點 487 S.pop(); //pop棧S 488 } 489 b.push_back(make_pair(p.first, e)); //push棧b 490 symbol.push_back(p.first); //push棧symbol 491 attr.push_back(e); //push棧attr 492 S.push(cnt++); //push棧S 493 while (!son.empty()) { 494 G[cnt - 1].push_back(son.front()); //構造Tree 495 son.pop(); 496 } 497 a[top++] = atoi(lr1[a[top - 1]][Hash[p.first]].c_str()); //push棧a 498 } 499 } 500 fout << endl << endl; 501 502 fout << "語法樹" << endl; //輸出語法樹 503 per(i, 1, cnt) if (!G[i].empty()) { 504 fout << '(' << i << ',' << symbol[i] << ')' << " ----> "; 505 sort(all(G[i])); 506 rep(j, 0, G[i].size()) fout << '(' << G[i][j] << ',' << symbol[G[i][j]] << ')' << ' '; 507 fout << endl; 508 } 509 fout << endl << endl; 510 } 511 512 void main() { 513 project::main(); 514 IN_LR1(); 515 MORPHOLOGY(); 516 JUDGE(); 517 } 518 } 519 520 namespace translate { //翻譯 521 using namespace grammar; 522 ofstream fout("C:\\Users\\Flowersea\\Desktop\\Code.txt"); 523 524 vector<vector<string>> table; //符號表 525 int temp_cnt = 0; //變量計數 526 int nextquad = 100; //四元式標號 527 528 void mktable() { //新建符號表 529 table.push_back(vector<string>()); 530 } 531 532 void rmtable() { //刪除符號表 533 table.pop_back(); 534 } 535 536 void enter(string name) { //聲明變量 537 table.back().push_back(name); 538 } 539 540 string lookup(string name) { //查看變量是否存在 541 per(i, 0, table.size()) rep(j, 0, table[i].size()) 542 if (table[i][j] == name) return name; 543 return "nil"; 544 } 545 546 string newtemp() { //新建一個變量 547 return "T" + to_string(++temp_cnt); 548 } 549 550 pair<int, vector<string>> gen(string a, string b, string c, string d) { //生成四元式 551 vector<string> vs{ a,b,c,d }; 552 return make_pair(nextquad++, vs); 553 } 554 555 void dfs(int u) { //遍歷語法樹 556 if (G[u].empty()) return; //如果為空直接return 557 if (symbol[G[u].front()] == "{") mktable(); //如果第一個兒子為{，新建符號表 558 rep(i, 0, G[u].size()) dfs(G[u][i]); //遍歷所有的兒子節點 559 560 E &e = attr[u]; //e為attr[u]的引用，便于直接修改 561 e = attr[G[u][0]]; //簡寫，把第一個兒子的直接賦值給attr[u] 562 attr[u].code.clear(); //先清空code四元式 563 rep(i, 0, G[u].size()) { //把所有兒子的四元式加進來 564 for (auto it : attr[G[u][i]].code) { 565 e.code.push_back(it); 566 } 567 } 568 569 if (symbol[u] == "variable_definition") {//函數定義 570 string name = attr[G[u][1]].name; 571 enter(name); 572 } 573 else if (symbol[u] == "assignment_expression" && symbol[G[u][0]] == "ID") {//賦值語句 574 string p = lookup(attr[G[u][0]].name); //查符號表 575 if (p == "nil") { 576 cerr << "變量未聲明" << endl; 577 return; 578 } 579 e.place = p; 580 e.code.push_back(gen("=", attr[G[u][2]].place, "-", e.place)); 581 } 582 else if (symbol[u] == "primary_expression" && symbol[G[u][0]] == "NUM") {//規約NUM 583 e.place = newtemp(); 584 e.value = attr[G[u][0]].value; 585 e.code.push_back(gen("=", e.value, "-", e.place)); 586 } 587 else if (symbol[u] == "primary_expression" && symbol[G[u][0]] == "ID") { //規約ID 588 string p = lookup(attr[G[u][0]].name); 589 if (p == "nil") { 590 cerr << "變量未聲明" << endl; 591 return; 592 } 593 e.place = p; 594 e.name = attr[G[u][0]].name; 595 } 596 else if (symbol[u] == "multiplicative_expression" && G[u].size() > 1 && symbol[G[u][1]] == "*") {//乘法表達式 597 E e1 = attr[G[u][0]]; 598 E e2 = attr[G[u][2]]; 599 e.place = newtemp(); 600 e.code.push_back(gen("*", e1.place, e2.place, e.place)); 601 } 602 else if (symbol[u] == "additive_expression" && G[u].size() > 1 && symbol[G[u][1]] == "+") {//加法表達式 603 E e1 = attr[G[u][0]]; 604 E e2 = attr[G[u][2]]; 605 e.place = newtemp(); 606 e.code.push_back(gen("+", e1.place, e2.place, e.place)); 607 } 608 else if (symbol[u] == "relational_expression" && G[u].size() > 1) {//關系表達式 609 E id1 = attr[G[u][0]]; 610 E id2 = attr[G[u][2]]; 611 e.code.push_back(gen("j" + symbol[G[u][1]], id1.place, id2.place, "0")); 612 e.True = e.code.back().first; 613 e.code.back().second[3] = to_string(e.code.back().first + 2); 614 e.code.push_back(gen("j", "-", "-", "0")); 615 e.False = e.code.back().first; 616 } 617 else if (symbol[G[u][0]] == "WHILE") {//WHILE語句 618 e = attr[G[u][0]]; 619 attr[u].code.clear(); 620 for (auto it : attr[G[u][2]].code) 621 e.code.push_back(it); 622 for (auto it : attr[G[u][4]].code) 623 e.code.push_back(it); 624 e.code.push_back(gen("j", "-", "-", to_string(e.code.front().first))); 625 626 for (auto &it : e.code) { 627 if (it.first == attr[G[u][2]].False) { 628 it.second[3] = to_string(e.code.back().first + 1); 629 break; 630 } 631 } 632 e.code.back().second[3] = to_string(e.code.front().first); 633 } 634 else if (symbol[G[u][0]] == "IF" && G[u].size() == 5) {//IF語句 635 e = attr[G[u][0]]; 636 attr[u].code.clear(); 637 for (auto it : attr[G[u][2]].code) 638 e.code.push_back(it); 639 for (auto it : attr[G[u][4]].code) 640 e.code.push_back(it); 641 for (auto &it : e.code) { 642 if (it.first == attr[G[u][2]].False) { 643 it.second[3] = to_string(e.code.back().first + 1); 644 break; 645 } 646 } 647 } 648 else if (symbol[G[u][0]] == "IF" && G[u].size() == 7) {//IF ELSE語句 649 e = attr[G[u][0]]; 650 attr[u].code.clear(); 651 for (auto it : attr[G[u][2]].code) 652 e.code.push_back(it); 653 for (auto it : attr[G[u][4]].code) 654 e.code.push_back(it); 655 e.code.push_back(gen("j", "-", "-", to_string(e.code.back().first + attr[G[u][6]].code.size() + 2))); 656 e.code.back().first = e.code.front().first + e.code.size() - 1; 657 for (auto &it : e.code) { 658 if (it.first == attr[G[u][2]].False) { 659 it.second[3] = to_string(e.code.back().first + 1); 660 break; 661 } 662 } 663 for (auto it : attr[G[u][6]].code) { 664 it.first++; 665 if (it.second[0][0] == 'j') { 666 int num = atoi(it.second[3].c_str()); 667 it.second[3] = to_string(num + 1); 668 } 669 e.code.push_back(it); 670 } 671 } 672 673 if (symbol[G[u].back()] == "}") rmtable(); //如果最后一個兒子為}，刪除符號表 674 } 675 676 void main() { 677 int rt = cnt - 1; //rt為根節點 678 dfs(rt); 679 for (auto it : attr[rt].code) 680 fout << it.first << " (" << it.second[0] << ", " << it.second[1] 681 << ", " << it.second[2] << ", " << it.second[3] << ")" << endl; 682 fout << nextquad << endl; //多輸出一行 683 } 684 } 685 686 int main() { 687 //lr1::main(); 688 grammar::main(); 689 translate::main(); 690 return 0; 691 }

?源碼下載：https://download.csdn.net/download/baocong1214/10511976

轉載于:https://www.cnblogs.com/baocong/p/9242321.html

總結

以上是生活随笔為你收集整理的LR(1)分析表-语法树-四元式的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。