输入的文法（第一行是终结符）将文法保存在txt中，命名为text.txt，与LR1.cpp放在同一目录中即可运行。
text.txt
abcde
S->aAd
S->bAc
S->aec
S->bed
A->e
实现代码：
LR1.cpp
1 #include<fstream>
2 #include<iostream>
3 #include<string>
4 #include<vector>
5 #include <algorithm>
6 #define MAX_Count 100
7 #include <set>
8 #include <stack>
9 #include <iomanip>
10 #include <sstream>
11 #include <string>
12 #include<cstring>
13 #include <map>
14 using namespace std;
15
16
17 // 重载一下+号运算符
18 template <typename CSS_LR1>
19 vector<CSS_LR1> &operator +(vector<CSS_LR1> &v1,vector<CSS_LR1> &v2)
20 {
21 v1.insert(v1.end(),v2.begin(),v2.end());
22 return v1;
23 }
24
25
26 struct VN_Set{
27 string VN_name;//非终结符
28 set<string> FIRST; //First集合
29 set<string> FOLLOW;
30 };
31 struct CSS{
32 string start;//非终结符
33 vector<string> next; //First集合
34 };
35 struct CSS_LR1{
36 string start;//非终结符
37 vector<string> next; //First集合
38 int num;
39 vector<string> tail;
40 //
41 // bool operator==(CSS_LR1& rhs) const {
42 // return (start == rhs.start &&
43 // next == rhs.next &&
44 // num == rhs.num &&
45 // tail == rhs.tail);
46 // }
47 bool operator==(const CSS_LR1& rhs) {
48 return (start == rhs.start &&
49 next == rhs.next &&
50 num == rhs.num &&
51 tail == rhs.tail);
52 }
53
54 };
55
56 int CSSCount = 0;
57 CSS css[MAX_Count];//产生式
58 VN_Set VN_First[MAX_Count];//非终结符集的First集合
59 set<string> VN;// 非终结符集合
60 set<string> VT;//终结符集合
61 int I_count = 0;//记录LR1项目数
62 vector<CSS_LR1> I[MAX_Count]; //项目集
63 map<string,int> mark_Follow;//用于标记Follow 防止套娃
64 map<string,int> GOTO[MAX_Count];
65 map<string,string> ACTION[MAX_Count];
66
67
68 bool cmp_vector(vector<CSS_LR1>&v1, vector<CSS_LR1>&v2)
69 {
70 if(v1.size()!=v2.size()) return false;
71 for (int i=0; i<v2.size(); i++)
72 {
73 CSS_LR1 t;
74 t = v2[i];
75 vector<CSS_LR1>::iterator result = find(v1.begin( ), v1.end( ),t); //查找3
76 if (result == v1.end( )) //没找到
77 return false;
78 }
79 return true;
80 }
81
82 /*
83 *实现编译原理语法分析中计算非终结符的First集Follow集
84 */
85 set<string> get_FIRST(string a){ //求First集合
86 set<string> T;
87 for(int i = 0;i<CSSCount;i++){
88 if(css[i].start==a){ // a->..
89 for(int j=0;j<css[i].next.size();j++){
90 if(VT.find(css[i].next[j])!=VT.end()){ //是终结符开头
91 T.insert(css[i].next[j]);
92 // T.erase("*");
93 break;
94 }
95 else{
96 if(css[i].next[j]==css[i].start){
97 break;
98 }
99 set<string> U = get_FIRST(css[i].next[j]);
100 T.insert(U.begin(),U.end());
101 if(U.find("$")!=U.end()){ //U中含有*,继续查下个的first
102 if(j!=css[i].next.size()-1)
103 T.erase("$");
104 }else{
105
106 break;
107 }
108 }
109
110
111 }
112
113 }
114 }
115
116 return T;
117 }
118
119 set<string> get_FOLLOW(string a){
120 set<string> T;
121 //cout<<"现在在求"<<a<<" 的Follow"<<endl;
122 mark_Follow[a]++;
123 if(mark_Follow[a]>=2){
124 return T;
125 }
126
127 set<string> temp;
128 if(a==css[0].start){
129 T.insert("#");
130 }
131 for(int i = 0;i<CSSCount;i++){
132 for(int j =0;j<css[i].next.size();j++){
133 if(VT.find(css[i].next[j])==VT.end()&&a==css[i].next[j]){ //是非终结符，求FOLLOW集合
134 if(j==css[i].next.size()-1&&a!=css[i].start){//S->...a
135 set<string> tt = get_FOLLOW(css[i].start);
136 T.insert(tt.begin(),tt.end());
137 }
138 for(int k=j+1;k<css[i].next.size();k++){
139 if(VT.find(css[i].next[k])!=VT.end()){//后面一个是终结符 S->..av..
140 T.insert(css[i].next[k]);
141 break;
142 }
143 else{
144 temp = get_FIRST(css[i].next[k]);
145 if(temp.find("$")!=temp.end()){//有$ S->..a B..
146 T.insert(temp.begin(),temp.end());
147 T.erase("$");
148 if(k==css[i].next.size()-1){ //S->..a B
149 set<string> tt = get_FOLLOW(css[i].start);
150 T.insert(tt.begin(),tt.end());
151 break;
152 }
153 }else{
154 T.insert(temp.begin(),temp.end());
155 break;
156 }
157 }
158 }
159
160 }
161 }
162
163 }
164 //cout<<a<<" "<<mark_Follow[a]<<endl;
165 mark_Follow[a]=0;
166 return T;
167 }
168
169
170 void GetFirst_and_Follow(){
171 set<string>::iterator it;
172 int count = 0;
173 cout<<"========================================="<<endl;
174 cout<<'t' <<"FIRST集合"<<" "<<"FOLLOW集合"<<endl;
175 for(it=VN.begin ();it!=VN.end ();it++)
176 {
177
178 VN_First[count].VN_name = *it;
179 VN_First[count].FIRST = get_FIRST(*it);
180
181 mark_Follow[*it]=0;
182 VN_First[count].FOLLOW = get_FOLLOW(*it);
183
184 //-----------输出FIRST--------------------
185
186 cout<<VN_First[count].VN_name<<'t';
187 set<string>::iterator it;
188 for(it=VN_First[count].FIRST.begin();it!=VN_First[count].FIRST.end();it++){
189 cout<<*it<<"";
190 }
191 cout<<'t'<<" ";
192 //----------------------------------------
193
194
195
196
197 //------------输出FOLLOW--------------
198 set<string>::iterator it1;
199 for(it1=VN_First[count].FOLLOW.begin();it1!=VN_First[count].FOLLOW.end();it1++){
200 cout<<*it1<<" ";
201 }cout<<endl;
202
203 //----------------------
204
205 count++;
206 }cout<<"=========================================";
207 cout<<endl<<endl;
208 }
209
210
211
212
213
214 void input(){
215 //创建一个文件输入流对象
216 ifstream inFile;
217 //打开文件
218 inFile.open("test.txt");
219 if (inFile){ //条件成立，则说明文件打开成功
220 cout<<"FILE open scessful"<<endl;
221 }
222 else
223 cout << "file doesn't exist" << endl;
224
225 string temp;
226 getline(inFile,temp);
227 for(int j=0;j<temp.length();j++){
228 VT.insert(temp.substr(j,1));
229 }
230 set<string>::iterator p;
231 cout<<"终结符号:";
232 for(p = VT.begin();p!=VT.end();p++){
233 cout<<*p<<",";
234 }cout<<endl;
235
236 int count = 0;//文件行数
237 while(getline(inFile,temp)) //按行读取文件内容
238 {
239 css[count].start = temp[0] ;
240 for(int j=3;j<temp.length();j++){
241 css[count].next.push_back(temp.substr(j,1));
242 }
243 VN.insert(css[count].start);//非终结符
244
245 cout<<css[count].start<<"->";
246 vector<string>::iterator it;
247 for(it=css[count].next.begin();it!=css[count].next.end();it++){
248 cout<<*it;
249 }
250 cout<<endl;
251
252
253 count++;
254 }
255 CSSCount = count;
256
257
258 }
259
260 bool find_in_vector(vector<CSS_LR1> T,CSS_LR1 p){
261 vector<CSS_LR1>::iterator it;
262 for(it=T.begin();it!=T.end();it++){
263 if(*it==p){
264 return true;
265 }
266 }
267 return false;
268 }
269
270
271 vector<CSS_LR1> CLOSURE(CSS_LR1 I){//求闭包
272 vector<CSS_LR1> T;
273 //T.push_back(I);
274 if(I.num>=I.next.size()) { //规约项目A->α.或者接受项目
275 return T;
276 }
277 else{
278 string temp = I.next[I.num];
279 if(VT.find(temp)!=VT.end()){ //点后面的是终结符 ,移进项目 A→α.aβ
280 return T;
281 }
282 else{ //待约项目
283 for(int i = 0;i<CSSCount;i++){
284 if(css[i].start==temp){
285 CSS_LR1 p;
286 p.start = css[i].start;
287 p.num = 0;//点在最前面
288 p.next = css[i].next;
289
290 set<string> f1;
291 for(int j = I.num+1;j<I.next.size();j++){
292 set<string> f2;//用于暂存first
293
294 if(VT.find(I.next[j])!=VT.end()){
295
296 f2.insert(I.next[j]);
297 }else{
298 f2 = get_FIRST(I.next[j]);
299 }
300
301 f1.insert(f2.begin(),f2.end());
302 if(f2.find("$")==f2.end()){
303
304 break;
305 }
306 }
307
308 if(f1.size()==0){
309 p.tail=I.tail;
310 }
311 else{
312 vector<string> first_tail;
313 if(f1.find("$")!=f1.end()){
314 f1.erase("$");
315 copy(f1.begin(),f1.end(), back_inserter(first_tail));
316 first_tail.insert(first_tail.end(),I.tail.begin(),I.tail.end());
317 }else{
318 copy(f1.begin(),f1.end(), back_inserter(first_tail));
319 //cout<<first_tail[0]<<endl;
320 }
321 // vector<string>::iterator l;
322 // for(l=first_tail.begin();l!=first_tail.end();l++){
323 // cout<<*l<<" ";
324 // }cout<<endl;
325 p.tail=first_tail;
326 }
327 if(!find_in_vector(T,p)){
328
329 T.push_back(p);
330 vector<CSS_LR1> ol = CLOSURE(p);
331 vector<CSS_LR1>::iterator z;
332 for(z=ol.begin();z!=ol.end();z++){
333 if(find_in_vector(T,*z)){
334 }else{
335 T.push_back(*z);
336 }
337 }
338
339 }
340
341 }
342 }
343 }
344 }
345
346 return T;
347 }
348
349 void showI(vector<CSS_LR1> I){//展示项目集
350 vector<CSS_LR1>::iterator it;
351 for(it=I.begin();it!=I.end();it++){
352 CSS_LR1 p = *it;
353 cout<<p.start<<"->";
354 vector<string>::iterator s;
355 for(int j = 0;j<p.next.size();j++){
356 if(j==p.num) cout<<".";
357 cout<<p.next[j];
358 }if(p.num==p.next.size())cout<<".";
359 cout<<",";
360 for(int k = 0;k<p.tail.size();k++){
361 cout<<p.tail[k];
362 }cout<<endl;
363 }
364 }
365
366 void LR1_Analyse(){
367 CSS_LR1 p;
368 //初始项目 S’->.S ,#
369 p.start = css[0].start+"^";
370 p.num = 0;//点在最前面
371 p.tail.push_back("#");
372 p.next.push_back(css[0].start);
373
374 I[0] = CLOSURE(p);//求闭包后的I[0]
375 I[0].insert(I[0].begin(),p);///////////////求闭包遇到了一些问题
376 I_count=1;
377
378 //计算项目集
379 for(int i=0;i<I_count;i++){//每个项目集 项目集I(i)
380
381 cout<<"==================="<<endl;
382 cout<<"现在在计算项目集I"<<i<<endl;
383 showI(I[i]);//展示项目集
384 cout<<"==================="<<endl;
385
386 //---------求ACTION的r部分--------------
387 vector<CSS_LR1>::iterator t;
388 for(t=I[i].begin();t!=I[i].end();t++){
389 CSS_LR1 t2 = *t;
390 if(t2.num==t2.next.size()){
391 int num =0;
392 for(int xp=0;xp<CSSCount;xp++){
393 if(css[xp].start==t2.start&&css[xp].next==t2.next){
394 num = xp;
395 break;
396 }
397 }
398
399 std::stringstream ss;
400 ss<<num;
401 string s = ss.str();
402 for(int q = 0;q<t2.tail.size();q++){
403 ACTION[i][t2.tail[q]] = "r"+s;
404 }
405 if(t2.num==1&&t2.next[0]==css[0].start){
406 ACTION[i]["#"] = "acc";
407 }
408 }
409 }
410 //--------------------------------------
411
412
413
414 set<string>::iterator it;
415 for(it=VN.begin();it!=VN.end();it++){ //每个非终结符
416 //cout<<"项目集I"<<i<<"输入"<<*it<<endl;
417 vector<CSS_LR1> temp;
418 //cout<<"项目集大小"<<I[i].size()<<endl;
419 for(int j = 0;j<I[i].size();j++){
420 CSS_LR1 lr = I[i][j];
421 if(lr.num<lr.next.size()&&lr.next[lr.num]==*it){
422 //cout<<*it<<endl;
423 vector<CSS_LR1> t2;
424 lr.num++;
425 t2 = CLOSURE(lr);
426 t2.push_back(lr);
427
428 temp=temp+t2;
429 }
430 }
431 //cout<<"temp.size"<< temp.size()<<endl;
432
433 if(temp.size()>0){
434 int k;
435 for(k=0;k<I_count;k++){//找一找项目集是否已经存在
436 if(cmp_vector(I[k],temp)){
437 break;
438 }
439 }
440 if(k==I_count){
441 //产生了新的项目集
442 I[I_count] = temp;
443 /*
444 cout<<"---------------------"<<endl;
445 cout<<"新的项目集I"<<I_count<<endl;
446 cout<<" I"<<i<<" -- "<<*it<<"->"<<"I"<<I_count<<endl<<endl;
447 showI(I[I_count]);//展示项目集
448 cout<<"---------------------"<<endl;
449 */
450 cout<<" I"<<i<<" -- "<<*it<<"->"<<"I"<<I_count<<endl<<endl;
451 GOTO[i][*it] = I_count;//更新goto表
452 I_count++;
453 }else{
454 //项目集已经存在，需要自己指向自己
455 cout<<" I"<<i<<" -- "<<*it<<"->"<<"I"<<k<<endl<<endl;
456 GOTO[i][*it] = k;
457
458 }
459
460 }
461
462 }
463 for(it=VT.begin();it!=VT.end();it++){ //每个终结符
464 //cout<<"项目集I"<<i<<"输入"<<*it<<endl;
465 vector<CSS_LR1> temp;
466
467 for(int j = 0;j<I[i].size();j++){
468 CSS_LR1 lr = I[i][j];
469
470 if(lr.num<lr.next.size()&&lr.next[lr.num]==*it){
471 vector<CSS_LR1> t2;
472 lr.num++;
473 t2 = CLOSURE(lr);//闭包求出的结果不包含本身
474 t2.insert(t2.begin(),lr);/////////求闭包遇到了一些问题
475 //showI(t2);
476 temp=temp+t2;
477 }
478 }
479 //cout<<"temp.size"<< temp.size()<<endl;
480 if(temp.size()>0){
481 int k;
482 for(k=0;k<I_count;k++){//找一找项目集是否已经存在
483 if(cmp_vector(I[k],temp)){
484 break;
485 }
486 }
487 if(k==I_count){
488 //产生了新的项目集
489 I[I_count] = temp;
490 /*
491 cout<<"---------------------"<<endl;
492 cout<<"新的项目集I"<<I_count<<endl;
493 cout<<" I"<<i<<" -- "<<*it<<"->"<<"I"<<I_count<<endl<<endl;
494 showI(I[I_count]);//展示项目集
495 cout<<"---------------------"<<endl;
496 */
497 cout<<" I"<<i<<" -- "<<*it<<"->"<<"I"<<I_count<<endl<<endl;
498 std::stringstream ss;
499 ss<<I_count;
500 string s = ss.str();
501 ACTION[i][*it] = "S"+s;//更新AVTION表
502 I_count++;
503 }else{
504 //项目集已经存在，需要自己指向自己
505 cout<<" I"<<i<<" -- "<<*it<<"->"<<"I"<<k<<endl<<endl;
506 std::stringstream ss;
507 ss<<k;
508 string s = ss.str();
509 ACTION[i][*it] = "S"+s;
510
511 }
512
513 }
514 }
515
516
517 }
518
519
520 }
521
522 void print_line(){
523 cout<<"-----------------------------------------------------------------------------"<<endl;
524 }
525
526
527
528 void print_ACTION_GOTO(){
529 set<string>::iterator it;
530 print_line();
531 cout<<setw(27) << setiosflags(ios::right) <<"ACTION";
532 cout<<setw(20) << setiosflags(ios::left)<<" GOTO"<<endl;
533 print_line();
534 cout<<setw(8)<<"项目集"<<"|";
535
536 for(it=VT.begin();it!=VT.end();it++){
537 cout<<setw(8)<<*it<<"|";
538 }
539 cout<<setw(8)<<"#"<<"|";
540 for(it=VN.begin();it!=VN.end();it++){
541 cout<<setw(8)<<*it<<"|";
542 }
543 cout<<endl;
544 for(int j =0;j<I_count;j++){
545 cout<<setw(6)<<"I"<<setw(2)<<j<<"|";
546 for(it=VT.begin();it!=VT.end();it++){
547 cout<<setw(8)<<ACTION[j][*it]<<"|";
548 }
549 cout<<setw(8)<<ACTION[j]["#"]<<"|";
550 for(it=VN.begin();it!=VN.end();it++){
551
552 if(GOTO[j][*it])//GOTO表为0
553 cout<<setw(8)<<GOTO[j][*it]<<"|";
554 else{
555 cout<<setw(8)<<" "<<"|";
556 }
557 }
558 cout<<endl;
559 }
560 print_line();
561
562 }
563
564
565
566 //对栈容器进行输出,i=0,返回status中的字符串,i=1,返回sign中的字符串，i=2返回inputStr中的字符串
567 string vectTrancStr(int i,vector<int> status,vector<string> sign){
568 string buf;
569 int count = 0;
570 //输出状态栈
571 if(i == 0){
572 vector<int>::iterator it =status.begin();
573 //将数字转化为字符串
574 string str,tempStr;
575 for(it;it!= status.end();it++){
576 stringstream ss;
577 ss << *it;
578 ss >> tempStr;
579 str+=tempStr;
580 }
581 return str;
582 }
583 //输出符号栈
584 else if(i == 1){
585 vector<string>::iterator it = sign.begin();
586 for(it ; it != sign.end() ;it++){
587 buf += *it;
588 count++;
589 }
590 }
591
592
593 string str(buf);
594 return str;
595 }
596
597
598
599 void Input_Analyse(){//输入句子，开始分析
600
601 vector<int> status;//定义状态栈
602 vector<string> sign;//定义符号栈
603
604 int step = 1; //步骤
605 string input;
606 cout<<"请输入分析的字符串(请以#结尾)：";
607 cin>>input;//输入待分析的句子
608 input = input+"#";
609
610 status.push_back(0);//把状态0入栈
611 //把#加入符号栈
612 sign.push_back("#");
613 //输出初始栈状态
614 cout<<setw(10)<<"步骤"<<setw(10)<<"状态栈"<<setw(10)<<"符号栈"<<setw(10)<<"输入串"<<setw(25)<<"动作说明"<<endl;
615
616 int s =0;//初始状态
617
618 int oldStatus;//保存之前的状态
619
620
621 string input_s; //获取初始符号
622 input_s = input.substr(0,1);
623
624 while(ACTION[s][input_s] != "acc"){//如果action[s][input_s] =="acc" ，则分析成功
625 //获取字符串
626 string str = ACTION[s][input_s];
627 //如果str为空，报错并返回
628 if(str.size() == 0){
629 cout<<"出错";
630 return ;
631 }
632 //获取S或r后面的数字
633 stringstream ss;
634 ss << str.substr(1);
635 ss >> s;//新的状态号
636 //如果是移进
637 if(str.substr(0,1) == "S"){
638 cout<<setw(10)<<step<<setw(10)<<vectTrancStr(0,status,sign)<<setw(10)<<vectTrancStr(1,status,sign)<<setw(10)<<input<<setw(10)<<"A"<<"CTION["<<status.back()<<","<<input_s<<"]=S"<<s<<","<<"状态"<<s<<"入栈"<<endl;
639 sign.push_back(input_s); //输入符号入栈
640 input.erase(0,1);
641 status.push_back(s);//将状态数字入栈
642 }
643 //如果是规约
644 else if(str.substr(0,1) == "r"){
645 string kaitou;//产生式的头部
646 kaitou = css[s].start;
647 int pop_num = css[s].next.size();//获取符号栈的出栈次数
648
649 string r;
650 stringstream ss;
651 ss << s;
652 ss >> r;
653 int oldStatus;//保存之前的状态
654 int status_size = status.size();
655 oldStatus = status[status_size-1-pop_num];
656 s=GOTO[oldStatus][kaitou];
657 cout<<setw(10)<<step<<setw(10)<<vectTrancStr(0,status,sign)<<setw(10)<<vectTrancStr(1,status,sign)<<setw(10)<<input<<setw(10)<<(string)":产生式"+r+(string)"归约,GOTO("<<oldStatus<<","<<kaitou<<")="<<s<<"入栈"<<endl;
658 //对符号栈进行出栈和状态栈进行出栈
659 while(pop_num--){
660 sign.pop_back();
661 status.pop_back();
662 }
663
664 sign.push_back(kaitou);//再对产生式的开始符号入栈
665 status.push_back(s);//再把新的状态入栈
666 }
667 else{
668 //nothing
669 }
670
671 step++; //步骤数加1
672
673 s = status.back();//获取栈顶状态
674
675 input_s = input.substr(0,1);//获取输入的字符
676 }
677 cout<<setw(10)<<step<<setw(10)<<vectTrancStr(0,status,sign)<<setw(10)<<vectTrancStr(1,status,sign)<<setw(10)<<input<<setw(10)<<"A"<<"cc:分析成功"<<endl;
678
679
680 }
681 int main(){
682 input();//输入二型文法
683 GetFirst_and_Follow();//求First和Follow集合
684 LR1_Analyse();
685 print_ACTION_GOTO();//打印ACTION GOTO表
686 Input_Analyse();//输入句子，开始分析
687 }
LR1.cpp
代码的输入写的比较草率，可以自行修改一下，只要保存到相应的数据结构中，就不影响后面的LR1分析。
运行截图：
原文链接: https://www.cnblogs.com/MAX-ZMY/p/12845688.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/197040
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
