编译原理LR1分析语法分析器实现（C++）

2021-01-27 10:16

阅读：636

标签：ons ace 运行 bcd test bre template not fir

输入的文法（第一行是终结符）将文法保存在txt中，命名为text.txt，与LR1.cpp放在同一目录中即可运行。

text.txt

abcde
S->aAd
S->bAc
S->aec
S->bed
A->e

实现代码：

LR1.cpp

  1 #include  2 #include  3 #includestring>
  4 #include  5 #include 
  6 #define MAX_Count 100
  7 #include set>
  8 #include   9 #include  10 #include  11 #include string>
 12 #include 13 #include  14 using namespace std;
 15 
 16  
 17 // 重载一下+号运算符
 18 template  19 vector &operator +(vector &v1,vector &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     setstring> FIRST; //First集合 
 29     setstring> FOLLOW;
 30 };
 31 struct CSS{
 32     string start;//非终结符
 33     vectorstring> next; //First集合 
 34 };
 35 struct CSS_LR1{
 36     string start;//非终结符
 37     vectorstring> next; //First集合 
 38     int num;
 39     vectorstring> 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 setstring> VN;// 非终结符集合 
 60 setstring> VT;//终结符集合 
 61 int I_count = 0;//记录LR1项目数 
 62 vector I[MAX_Count]; //项目集 
 63 mapstring,int> mark_Follow;//用于标记Follow 防止套娃 
 64 mapstring,int> GOTO[MAX_Count]; 
 65 mapstring,string> ACTION[MAX_Count]; 
 66 
 67 
 68 bool cmp_vector(vector&v1, vector&v2)
 69 {
 70     if(v1.size()!=v2.size()) return false;
 71     for (int i=0; i)
 72     {
 73         CSS_LR1 t;
 74         t = v2[i];
 75         vector::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 setstring> get_FIRST(string a){ //求First集合 
 86     setstring> T;
 87     for(int i = 0;i){
 88         if(css[i].start==a){  // a->.. 
 89             for(int j=0;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                     setstring> 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 setstring> get_FOLLOW(string a){
120     setstring> T;
121     //cout
122     mark_Follow[a]++; 
123     if(mark_Follow[a]>=2){
124         return T;
125     }
126 
127     setstring> temp;
128     if(a==css[0].start){
129         T.insert("#");
130     }
131     for(int i = 0;i){ 
132         for(int j =0;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                     setstring> tt = get_FOLLOW(css[i].start);
136                     T.insert(tt.begin(),tt.end());
137                 }
138                 for(int k=j+1;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                                 setstring> 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
165     mark_Follow[a]=0;
166     return T;
167 }
168 
169 
170 void GetFirst_and_Follow(){
171     setstring>::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‘\t‘;
187         setstring>::iterator it;
188         for(it=VN_First[count].FIRST.begin();it!=VN_First[count].FIRST.end();it++){
189             cout"";
190         }
191         cout‘\t‘"       ";
192         //----------------------------------------
193         
194         
195         
196         
197         //------------输出FOLLOW--------------
198         setstring>::iterator it1;
199         for(it1=VN_First[count].FOLLOW.begin();it1!=VN_First[count].FOLLOW.end();it1++){
200             cout" ";
201         }coutendl;
202         
203         //----------------------
204         
205         count++;
206     }cout"=========================================";
207     coutendl;
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){
228         VT.insert(temp.substr(j,1));
229     }
230     setstring>::iterator p;
231     cout"终结符号:";
232     for(p = VT.begin();p!=VT.end();p++){
233         cout",";
234     }coutendl; 
235     
236     int count = 0;//文件行数 
237     while(getline(inFile,temp)) //按行读取文件内容 
238     { 
239         css[count].start = temp[0] ;
240         for(int j=3;j){
241             css[count].next.push_back(temp.substr(j,1));
242         }
243         VN.insert(css[count].start);//非终结符 
244         
245         cout"->";
246         vectorstring>::iterator it;
247         for(it=css[count].next.begin();it!=css[count].next.end();it++){
248             coutit;
249         }
250         coutendl;
251         
252         
253         count++;
254     }
255     CSSCount = count;
256     
257     
258 } 
259 
260 bool find_in_vector(vector T,CSS_LR1 p){
261     vector::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 CLOSURE(CSS_LR1 I){//求闭包 
272     vector 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){
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                     setstring> f1;
291                     for(int j = I.num+1;j){
292                         setstring> 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                         vectorstring> 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
320                         }
321 //                        vector::iterator l;
322 //                        for(l=first_tail.begin();l!=first_tail.end();l++){
323 //                            cout324 //                        }cout
325                         p.tail=first_tail;
326                     }
327                     if(!find_in_vector(T,p)){
328                          
329                         T.push_back(p);
330                         vector ol = CLOSURE(p);
331                         vector::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 I){//展示项目集 
350     vector::iterator it;
351     for(it=I.begin();it!=I.end();it++){
352         CSS_LR1 p = *it;
353         cout"->";
354         vectorstring>::iterator s;
355         for(int j = 0;j){
356             if(j==p.num) cout".";
357             coutp.next[j];
358         }if(p.num==p.next.size())cout".";
359         cout",";
360         for(int k = 0;k){
361             coutp.tail[k];
362         }coutendl;
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(i) 
380          
381         cout"==================="endl; 
382         cout"现在在计算项目集I"endl;
383         showI(I[i]);//展示项目集 
384         cout"==================="endl; 
385         
386         //---------求ACTION的r部分-------------- 
387         vector::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){
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                 ssnum; 
401                 string s = ss.str();
402                 for(int q = 0;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         setstring>::iterator it;
415         for(it=VN.begin();it!=VN.end();it++){  //每个非终结符
416             //cout
417             vector temp;
418             //cout
419             for(int j = 0;j){
420                 CSS_LR1 lr = I[i][j];
421                 if(lr.numit){
422                     //cout
423                     vector t2;
424                     lr.num++;
425                     t2 = CLOSURE(lr);
426                     t2.push_back(lr);
427                     
428                     temp=temp+t2;
429                 }
430             }
431             //cout
432             
433             if(temp.size()>0){
434                 int k;
435                 for(k=0;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                     cout445                     cout446                     cout"447                     showI(I[I_count]);//展示项目集 
448                     cout449                     */ 
450                     cout"  I"" -- ""->""I"endl;
451                     GOTO[i][*it] = I_count;//更新goto表 
452                     I_count++;
453                 }else{
454                     //项目集已经存在，需要自己指向自己
455                     cout"  I"" -- ""->""I"endl;
456                     GOTO[i][*it] = k;
457                      
458                 }
459                 
460             }
461             
462         }
463         for(it=VT.begin();it!=VT.end();it++){  //每个终结符
464             //cout
465             vector temp;
466             
467             for(int j = 0;j){
468                 CSS_LR1 lr = I[i][j];
469                 
470                 if(lr.numit){
471                     vector 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
480             if(temp.size()>0){
481                 int k;
482                 for(k=0;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                     cout492                     cout493                     cout"494                     showI(I[I_count]);//展示项目集 
495                     cout496                     */ 
497                     cout"  I"" -- ""->""I"endl;
498                     std::stringstream ss;
499                     ssI_count; 
500                     string s = ss.str();
501                     ACTION[i][*it] = "S"+s;//更新AVTION表 
502                     I_count++;
503                 }else{
504                     //项目集已经存在，需要自己指向自己
505                     cout"  I"" -- ""->""I"endl;
506                     std::stringstream ss;
507                     ssk; 
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     setstring>::iterator it;
530     print_line();
531     cout27) "ACTION";
532     cout20) "  GOTO"endl; 
533     print_line();
534     cout8)"项目集""|";
535 
536     for(it=VT.begin();it!=VT.end();it++){
537             cout8)"|";
538     }
539         cout8)"#""|";
540     for(it=VN.begin();it!=VN.end();it++){
541             cout8)"|";
542     }
543     coutendl;
544     for(int j =0;j){
545         cout6)"I"2)"|";
546         for(it=VT.begin();it!=VT.end();it++){
547             cout8)"|";
548         }
549         cout8)"#"]"|";
550         for(it=VN.begin();it!=VN.end();it++){
551             
552             if(GOTO[j][*it])//GOTO表为0 
553                 cout8)"|";
554             else{
555                 cout8)" ""|";
556             }
557         }
558         coutendl;
559     }
560     print_line();
561     
562 }
563 
564 
565 
566 //对栈容器进行输出,i=0,返回status中的字符串,i=1,返回sign中的字符串，i=2返回inputStr中的字符串
567 string vectTrancStr(int i,vectorint> status,vectorstring> sign){
568     string buf;
569     int count = 0;
570     //输出状态栈
571     if(i == 0){
572         vectorint>::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         vectorstring>::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     vectorint>  status;//定义状态栈
602     vectorstring> 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     cout10)"步骤"10)"状态栈"10)"符号栈"10)"输入串"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 1);
635         ss >> s;//新的状态号 
636         //如果是移进 
637         if(str.substr(0,1) == "S"){
&

上一篇：线程_可能发生的问题

下一篇：python-django-查询详解

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：编译原理LR1分析语法分析器实现（C++）
文章链接：http://soscw.com/index.php/essay/47712.html

亲，登录后才可以留言！

编译原理LR1分析语法分析器实现（C++）

评论

热门文章

推荐文章

最新文章

置顶文章

编译原理LR1分析 语法分析器实现（C++）

评论

热门文章

推荐文章

最新文章

置顶文章

编译原理LR1分析语法分析器实现（C++）