首页 > 其他 > 详细

编译原理的一些练习题

时间:2016-05-17 16:09:08      阅读:1531      评论:0      收藏:1      [点我收藏+]

标签:算法   class   style   log   com   http   it   si   la   

这里收集了sicily的陈炬桦老师编译原理实验课程的题目,曝上代码以供参考。

(如果这里的代码对您的思路有些许启发的话,请您点击一下推荐,给予作者写作的鼓励,不胜感谢!)

1-词法分析

题目1000:     

技术分享
 1 1000. 词法分析程序设计
 2 总提交数量:    183    通过数量:    138
 3            
 4 时间限制:1秒    内存限制:256兆
 5 题目描述
 6 设一语言的关键词、运算符、分界符的个数与单词如下: 
 7 struct { int number; string str[10]; } keywords={3,"int","main","return"} ; //关键词
 8 struct { int number; string str[10]; } operators ={5,"+","*","=","+=","*="}; //运算符
 9 struct { int number; string str[10]; } boundaries ={6,"(",")","{","}",",",";"} ; //分界符
10 struct { int number; string str[100];} identifieres={0}; //标识符
11 struct { int number; string str[100];} Unsigned_integer={0}; //无符号整数
12 以上类号分别为1~5,序号从0开始;
13 标识符是字母开头的字母数字串;常量为无符号整数;
14 用C++设计一程序实现词法分析。
15 
16 输入格式
17 输入一程序,结束符用”#”;
18 
19 输出格式
20 输出单词数对:<类号,序号>。 输出标识符表,用空格分隔; 输出无符号整数表,用空格分隔;
21 
22 样例输入
23  将样例输入复制到剪贴板
24 main()
25 { int a=2,b=3;
26   return 2*b+a;
27 }#
28 样例输出
29 <1,1><3,0><3,1><3,2><1,0><4,0><2,2><5,0><3,4><4,1><2,2><5,1><3,5><1,2><5,0><2,1>
30 <4,1><2,0><4,0><3,5><3,3>
31 identifieres:a b
32 Unsigned_integer:2 3
View Code

AC代码:

技术分享
 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 
 5 struct { int number; string str[10]; } keywords={3,"int","main","return"} ;         //关键词 
 6 struct { int number; string str[10]; } operators ={5,"+","*","=","+=","*="};        //运算符 
 7 struct { int number; string str[10]; } boundaries ={6,"(",")","{","}",",",";"} ;    //分界符 
 8 struct { int number; string str[100];} identifieres={0};                            //标识符 
 9 struct { int number; string str[100];} Unsigned_integer={0};                        //无符号整数 
10 
11 char k=0;
12 string st=""; 
13 int main(){
14     int i;    char ch;  bool nochar=1;     
15     
16     do{
17         if(nochar)cin.get(ch);
18         if(ch==(){st+="<3,0>";nochar=1;} 
19         else if(ch==)){ st+="<3,1>";nochar=1; }    
20         else if(ch=={){ st+="<3,2>";nochar=1; }  
21         else if(ch==}){ st+="<3,3>";nochar=1; }    
22         else if(ch==,){ st+="<3,4>";nochar=1; }    
23         else if(ch==;){ st+="<3,5>";nochar=1; }      
24         else if(ch==+){
25             cin.get(ch); 
26             if(ch===){    
27                 st+="<2,3>";nochar=1;  
28             } 
29             else{
30                 st+="<2,0>";nochar=1;     
31             } 
32         }
33         else if(ch==*){
34             cin.get(ch); 
35             if(ch===){
36                 st+="<2,4>";nochar=1;
37             } 
38             else{
39                 st+="<2,1>";nochar=1;     
40             } 
41         }
42         else if(ch===){
43             st+="<2,2>";nochar=1;      
44         }
45         else if(0<=ch&&ch<=9){
46             string nstring=""; nochar=0;
47             do{
48                 nstring+=ch;
49                 cin.get(ch); 
50             } while(0<=ch&&ch<=9);
51             for(k=0;k<Unsigned_integer.number&&Unsigned_integer.str[k]!=nstring;k++ );
52     
53             if(k==Unsigned_integer.number ){
54                 Unsigned_integer.str[k] = nstring;
55                 st+="<5,";st+=char(0+k); st+=">";
56                 Unsigned_integer.number++;  
57             }
58             else{ 
59                 st+="<5,";st+=char(0+k);st+=">";   
60             }
61         }
62         else if(a<=ch&&ch<=z||A<=ch&&ch<=Z){ 
63             string nstring="";nochar=0;
64             do{
65                 nstring+=ch;
66                 cin.get(ch);
67             } while(a<=ch&&ch<=z||A<=ch&&ch<=Z) ;  //读入关键字或者标示符的东西 
68             
69             for(k=0;k<= keywords.number &&keywords.str[k]!=nstring;k++ );               
70             if(k<keywords.number ){
71                 //测得输入字符是关键字之一 
72                 st+="<1,";   st+=char(0+k);st+=">";   
73             }                  
74             else{
75                 //测得输入字符不是关键字之一,而是标识符   
76                 for(k=0;k<identifieres.number && identifieres.str[k]!=nstring;k++ );    //检查是否是已经记录过的标识符 
77                 if(k==identifieres.number ){                //不是已经标识过的标识符 
78                     identifieres.str[k]=nstring;
79                     st+="<4,";st=st+char(0+k);st+=">";   
80                     identifieres.number++;  
81                 }
82                 else{
83                     st+="<4,";st=st+char(0+k);st+=">"; 
84                 }
85             }
86         }
87         else nochar=1;  
88        
89     } while(ch!=#);
90     
91     cout<<st<<endl;
92     cout<<"identifieres:";
93         for(i=0;i<identifieres.number;i++ ){cout<<identifieres.str[i]<<" ";}    cout<<endl;
94     cout<<"Unsigned_integer:"; 
95         for(i=0;i<Unsigned_integer.number;i++ ){cout<<Unsigned_integer.str[i]<<" ";}   cout<<endl;
96     
97     return 0;    
98 }               
99   
View Code

-----------------------------------

题目1001:     

技术分享
 1 1001. 输入输出文法1
 2 总提交数量:    95    通过数量:    53
 3            
 4 时间限制:1秒    内存限制:256兆
 5 题目描述
 6  
 7 
 8 设文法的非终结符,终结符,产生式为,开始符号为
 9 struct  { int Nv;string VN[10];} Vns={3,"E","T","F"};
10 struct  { int Nt;string VT[10];} Vts={7,"+","-","*","/","(",")","i"};
11 struct  { int Np;string PL[20],PR[20];} ps={0};
12 string S="E"; 
13  
14 输入产生式的个数,
15 分别输入产生式的左边和右边符号
16  
17 按非终结符顺序输出产生式
18 输入格式
19  8
20 E E+T
21 T T*F
22 E T
23 T F
24 F (E)
25 F i
26 E E-T
27 T T/F
28 
29 输出格式
30 G[E]:
31 E::=E+T | T | E-T
32 T::=T*F | F | T/F
33 F::=(E) | i
34 
35 样例输入
36  将样例输入复制到剪贴板
37 6
38 E E+T
39 T T*F
40 E T
41 T F
42 F (E)
43 F i
44 样例输出
45 G[E]:
46 E::=E+T | T
47 T::=T*F | F
48 F::=(E) | i
View Code

AC代码:

技术分享
#include <iostream>
#include <string>
using namespace std;

struct  { int Nv;string VN[10];} Vns={3,"E","T","F"};
struct  { int Nt;string VT[10];} Vts={7,"+","-","*","/","(",")","i"};
struct  { int Np;string PL[20],PR[20];} ps={0};
string S="E"; 

int main(){
    int num;    cin>>num; num++;    
    string temp;     int k;
    string result[Vns.Nv]; 
    while(num--){
        getline(cin,temp);
        for(k=0;k<Vns.Nv;k++ ){
            if(temp.substr(0,1)==Vns.VN[k] ) {
                result[k]+=temp.substr(2) + " | ";
                break;
            } 
        }
    }
    for(k=0;k<Vns.Nv;k++){
        result[k] = result[k].substr(0,result[k].length()-3 );
    }    
    
    cout<<"G["<<S<<"]:\n";
    for(k=0;k<Vns.Nv;k++){
        cout<<Vns.VN[k]<<"::="<<result[k]<<endl; 
    }
} 
View Code

-----------------------------------

题目1002:     

技术分享
 1 1002. 输入输出文法2
 2 总提交数量:    76    通过数量:    53
 3            
 4 时间限制:1秒    内存限制:256兆
 5 题目描述
 6  输入开始符号,非终结符,终结符,产生式
 7 按非终结符顺序输出产生式;
 8 
 9 输入格式
10  输入开始符号;
11 非终结符个数,非终结符,空格符分隔;
12 终结符个数,终结符,空格符分隔;
13 产生式的个数,各产生式的左边和右边符号,空格符分隔;
14 
15 输出格式
16  G[开始符号]:
17 按非终结符顺序输出各产生式;
18 
19 样例输入
20  将样例输入复制到剪贴板
21 Z
22 8 Z E F P G T Q S
23 3 + * i
24 18
25 Z E+T
26 E E
27 P G
28 F F
29 P G
30 G G
31 T T*i
32 Q E
33 S i
34 E S+F
35 F FP
36 G GG
37 Q E+F
38 E T
39 F P
40 G F
41 Q T
42 Q S
43 样例输出
44 G[Z]:
45 Z::=E+T
46 E::=E | S+F | T
47 F::=F | FP | P
48 P::=G | G
49 G::=G | GG | F
50 T::=T*i
51 Q::=E | E+F | T | S
52 S::=i
View Code

AC代码:

技术分享
 1 #include <iostream>
 2 #include <string>
 3 #include <stdlib.h>
 4 using namespace std;
 5 
 6 struct  { int Nv;string VN[10];} Vns={0};
 7 struct  { int Nt;string VT[10];} Vts={0};
 8 struct  { int Np;string PL[20],PR[20];} ps={0};
 9 string S=""; 
10 
11 int main(){
12     cin>>S;
13     cin>>Vns.Nv ;
14     for(int i=0;i<Vns.Nv;i++ ){
15         cin>>Vns.VN[i];
16     }
17     
18     cin>>Vts.Nt ;
19     for(int i=0;i<Vts.Nt;i++ ){
20         cin>>Vts.VT[i] ;
21     }  
22 
23     int num;    cin>>num; num++;    
24     string temp;     int k;
25     string result[Vns.Nv]; 
26     while(num--){
27         getline(cin,temp);
28         for(k=0;k<Vns.Nv;k++ ){
29             if(temp.substr(0,1)==Vns.VN[k] ) {
30                 result[k]+=temp.substr(2) + " | ";
31                 break;
32             } 
33         }
34     }
35     for(k=0;k<Vns.Nv;k++){
36         result[k] = result[k].substr(0,result[k].length()-3 );
37     }    
38     
39     cout<<"G["<<S<<"]:\n";
40     for(k=0;k<Vns.Nv;k++){
41         cout<<Vns.VN[k]<<"::="<<result[k]<<endl; 
42     }
43 } 
View Code

----------------------------------

题目1003:     

技术分享
 1 1003. 输入文法压缩自产生式文法和不可达文法
 2 总提交数量:    122    通过数量:    59
 3            
 4 时间限制:1秒    内存限制:256兆
 5 题目描述
 6  输入开始符号,非终结符,终结符,产生式
 7 压缩自产生式文法和不可达文法后,按非终结符顺序输出产生式;
 8 
 9 输入格式
10  
11 输入开始符号;
12 非终结符个数,非终结符,空格符分隔;
13 终结符个数,终结符,空格符分隔;
14 产生式的个数,各产生式的左边和右边符号,空格符分隔;
15 
16 输出格式
17  
18 delete self production:自产生式文法
19 unreached Vn:不可达非终结符
20 delete production:不可达产生式
21 delete VN:不可达非终结符
22 G[开始符号]:
23 压缩自产生式文法和不可达文法后,按非终结符顺序输出各产生式;
24 
25 样例输入
26  将样例输入复制到剪贴板
27 Z
28 8 Z E F P G T Q S
29 3 + * i
30 18
31 Z E+T
32 E E
33 P G
34 F F
35 P G
36 G G
37 T T*i
38 Q E
39 S i
40 E S+F
41 F FP
42 G GG
43 Q E+F
44 E T
45 F P
46 G F
47 Q T
48 Q S
49 样例输出
50 delete self production:E::=E
51 delete self production:F::=F
52 delete self production:G::=G
53 unreached Vn:Q
54 delete production:Q::=E
55 delete production:Q::=E+F
56 delete production:Q::=T
57 delete production:Q::=S
58 delete VN:Q
59 G[Z]:
60 Z::=E+T
61 E::=S+F | T
62 F::=FP | P
63 P::=G | G
64 G::=GG | F
65 T::=T*i
66 S::=i
View Code

AC代码:

技术分享
  1 #include <iostream>
  2 #include <string>
  3 #include <stdlib.h>
  4 using namespace std;
  5 
  6 struct  { int Nv;string VN[10];bool get[10]; string result[10]; } Vns={0};   //非终结符
  7 struct  { int Nt;string VT[10];} Vts={0};                  //终结符
  8 struct  { int Np;string PL[20],PR[20];} ps={0};              //产生式 
  9 struct  { int Nu;string HH[10]; } unstr={0};               //记录自产生式 
 10 string  S="";                                               //开始符号 
 11 
 12 void cinVns();                        //输入非终结符 
 13 void cinVts();                        //输入终结符 
 14 void cinps();                        //输入产生式 
 15 void print();                        //输出程序处理结果 
 16 
 17 int main(){
 18     cin>>S;                            //输入开始符号 
 19     cinVns();                        //输入非终结符 
 20     cinVts();                        //输入终结符 
 21     cinps();                        //输入产生式        
 22     
 23     //筛除自产生式
 24     unstr.Nu = 0;
 25     for(int i=0;i<ps.Np;i++){
 26         if(ps.PL[i] == ps.PR[i]){
 27             unstr.HH[unstr.Nu ] = ""+ps.PL[i]+"::="+ps.PR[i]+""; 
 28             ps.PL[i]=ps.PR[i]="#";
 29             unstr.Nu++; 
 30         }
 31     } 
 32     
 33     //筛除无“输入源”的非终结符 ,经过这个过程所有产生式中右侧出现过的非终结符都被标识为get=1 
 34     for(int i=0;i<Vns.Nv;i++){
 35         for(int j=0;j<ps.Np;j++){
 36             if( Vns.VN[i] ==ps.PR[j] )  {  //只要有右侧等于左侧,那么久说这个“左侧”非终结符有源 
 37                 Vns.get[i] = 1;
 38                 break;         
 39             }
 40         } 
 41         if(Vns.VN[i]==S )  Vns.get[i] = 1;    // 排除第一行z的影响 
 42     } 
 43     
 44     //得到输出结果产生式
 45     for( int i=0;i<ps.Np;i++ ){
 46         for(int j=0;j<Vns.Nv;j++ ){  
 47             if(ps.PL[i]==Vns.VN[j]&& ps.PL[i]!="#" )
 48             {
 49                 Vns.result[j] += ps.PR[i] +" | ";
 50             }
 51         }
 52     }
 53     
 54     print();
 55 
 56 } 
 57 
 58 void print(){
 59     for(int i=0;i<unstr.Nu;i++){
 60         cout<<"delete self production:"<<unstr.HH[i]<<endl;
 61     }
 62     
 63     cout<<"unreached Vn:";
 64     for(int i=0;i<Vns.Nv;i++){
 65         if(!Vns.get[i]){
 66             cout<<Vns.VN[i];
 67         }
 68     } 
 69     cout<<endl;
 70     
 71     for(int i=0;i<Vns.Nv;i++){
 72         if(!Vns.get[i]){
 73             for(int j=0;j<ps.Np;j++){
 74                 if(ps.PL[j]==Vns.VN[i]){
 75                     cout<<"delete production:"<<ps.PL[j]<<"::="<<ps.PR[j]<<endl;
 76                 } 
 77             }            
 78         }
 79     }
 80     
 81     cout<<"delete VN:"; 
 82     for(int i=0;i<Vns.Nv;i++){
 83         if(!Vns.get[i]){
 84             cout<<Vns.VN[i];
 85         }
 86     }
 87     cout<<endl;
 88     
 89     cout<<"G["<<S<<"]:"<<endl;        
 90     for(int i=0;i<Vns.Nv;i++){
 91         if(Vns.get[i]){
 92             cout<<Vns.VN[i]<<"::="<<Vns.result[i].substr(0,Vns.result[i].length()-3 )<<endl;
 93         }
 94     }
 95     
 96     return ;
 97 } 
 98 
 99 void cinps(){
100     cin>>ps.Np;
101     for(int i=0;i<ps.Np;i++){
102         cin>>ps.PL[i]>>ps.PR[i];
103     }  
104     return ;
105 } 
106 
107 void cinVns(){
108     cin>>Vns.Nv ;                    //非终结符的个数 
109     for(int i=0;i<Vns.Nv;i++ ){        //输入非终结符、空格符分隔 
110         cin>>Vns.VN[i];
111         Vns.get[i] = 0;                //初始化为:没有输入源   get[i] = 0 
112     }
113     return;
114 }
115  
116 void cinVts(){
117     cin>>Vts.Nt ;                    //终结符个数 
118     for(int i=0;i<Vts.Nt;i++ ){        //终结符 
119         cin>>Vts.VT[i] ;            //空格符分隔 
120     } 
121     return ;
122 } 
View Code

------------------------------------

题目1004:

技术分享
 1 1004. 压缩自产生式,不可达非终结符和无用非终结符的产生式
 2 总提交数量:    70    通过数量:    33
 3            
 4 时间限制:1秒    内存限制:256兆
 5 题目描述
 6 输入开始符号,非终结符,终结符,产生式 压缩自产生式文法,不可达文法和无用文法后,按非终结符顺序输出产生式;
 7 
 8 输入格式
 9 输入开始符号; 非终结符个数,非终结符,空格符分隔; 终结符个数,终结符,空格符分隔; 产生式的个数,各产生式的左边和右边符号,空格符分隔;
10 
11 输出格式
12 delete self production:自产生式文法 unreached Vn:不可达非终结符 delete production:不可达产生式 delete VN:不可达非终结符 unusefulNv:无用非终结符 G[开始符号]: 压缩自产生式文法和不可达文法后,按非终结符顺序输出各产生式;
13 
14 样例输入
15  将样例输入复制到剪贴板
16 Z
17 8 Z E F P G T Q S
18 3 + * i
19 18
20 Z E+T
21 E E
22 F F
23 P G
24 G G
25 T T*i
26 Q E
27 S i
28 E S+F
29 F FP
30 G GG
31 T i
32 Q E+F
33 E T
34 F P
35 G F
36 Q T
37 Q S
38 样例输出
39 delete self production:E::=E
40 delete self production:F::=F
41 delete self production:G::=G
42 unreached Vn:Q
43 delete VN:Q
44 delete production:Q::=E
45 delete production:Q::=E+F
46 delete production:Q::=T
47 delete production:Q::=S
48 unusefulNv:G
49 delete VN:G
50 delete production:P::=G
51 delete production:G::=GG
52 delete production:G::=F
53 unusefulNv:P
54 delete VN:P
55 delete production:F::=FP
56 delete production:F::=P
57 unusefulNv:F
58 delete VN:F
59 delete production:E::=S+F
60 unreached Vn:S
61 delete VN:S
62 delete production:S::=i
63 G[Z]:
64 Z::=E+T
65 E::=T
66 T::=T*i | i
View Code

AC代码:

技术分享
  1 #include <iostream>
  2 #include <string>
  3 #include <stdlib.h>
  4 using namespace std;
  5 
  6 string  S="";                                                              //开始符号 
  7 struct  { int number;string sign[20]; bool get[20];bool enable[20]; string result[20]; } not_endsign={0};   //非终结符
  8 struct  { int number;string sign[20];} end_sign={0};                      //终结符
  9 struct  { int number;string left[100],right[100];bool enable[100] ; } production={0};        //产生式 
 10 
 11 struct  { int number;string sign[20];bool exit[20]; string result[20] ;} out={0};  
 12 
 13 void input();        //输入开始符号、非终结符、终结符、产生式 
 14 void print();        //打印结果 
 15 bool into(string a,string b);
 16 bool reachable(string test);
 17 bool reach(string test);
 18 bool ceyan();
 19  
 20 int main(){
 21     input();        
 22     for(int i=0;i<production.number;i++ ){
 23         if(production.left[i]==production.right[i]){
 24             production.enable[i] = 0;
 25             cout<<"delete self production:"<<production.left[i]<<"::="<<production.right[i]<<endl;    
 26         }          
 27     } 
 28     
 29     for(int i=0;i<not_endsign.number;i++){
 30         for(int j=0;j<production.number;j++){
 31             if(not_endsign.sign[i]==production.left[j]&&production.enable[j] ){
 32                 not_endsign.result[i]+=production.right[j]+" | ";  
 33             }
 34         }  
 35         if(S==not_endsign.sign[i] ) not_endsign.enable[i] = 0;
 36     }
 37     
 38     for(int i=0;i<not_endsign.number;i++){
 39         if(S == not_endsign.sign[i]) not_endsign.enable[i] = 0;        
 40     }
 41         
 42     bool xunhuan = 1;
 43     while(xunhuan ){
 44         //每循环一次检查一次“不可达非终结符”  
 45         xunhuan = 0;       
 46         for(int i=not_endsign.number-1;i>=0;i-- ){  
 47             if(not_endsign.enable[i] && !reachable(not_endsign.sign[i]) ){
 48                 not_endsign.enable[i] = 0; 
 49                 cout<<"unreached Vn:"<<not_endsign.sign[i]<<endl;
 50                 cout<<"delete VN:"<<not_endsign.sign[i]<<endl;
 51                 xunhuan = 1; 
 52                 for(int j=0;j<production.number;j++ ){
 53                     if(into(not_endsign.sign[i],production.left[j] )|| into(not_endsign.sign[i],production.right[j] )  ){
 54                         if(production.enable[j])  {
 55                             production.enable[j] = 0;  
 56                             cout<<"delete production:"<<production.left[j]<<"::="<<production.right[j]<<endl; 
 57                         }
 58                             
 59                     }
 60                 }
 61                 
 62             }
 63         }
 64         
 65         //每次循环一次检查一次“不可用非终结符” 
 66         for(int i=not_endsign.number-1;i>=0;i-- ){
 67             bool det = 0;
 68             for(int j=0;j< not_endsign.result[i].length();j++ ){
 69                 if(reach (not_endsign.result[i].substr(j,1)) )  det = 1;
 70             }
 71             
 72             if(!det&&not_endsign.enable[i]==1){
 73                 xunhuan = 1;
 74                 not_endsign.enable[i] = 0;
 75                 cout<<"unusefulNv:"<<not_endsign.sign[i]<<endl;
 76                 cout<<"delete VN:"<<not_endsign.sign[i]<<endl;
 77                 for(int j=0;j<production.number;j++ ){
 78                     if(into(not_endsign.sign[i],production.left[j] )|| into(not_endsign.sign[i],production.right[j] )  ){
 79                         if(production.enable[j]) {  
 80                             production.enable[j] = 0;
 81                             cout<<"delete production:"<<production.left[j]<<"::="<<production.right[j]<<endl;     
 82                         } 
 83                     }
 84                 }
 85             }
 86         } 
 87         
 88     }
 89         
 90     print();
 91     return 0; 
 92 } 
 93 
 94 //测试test中是否有终结符 
 95 bool reach(string test){
 96     for(int i=0;i<end_sign.number;i++){
 97         if(test==end_sign.sign[i]) return 1;
 98     } 
 99     return 0;
100 } 
101 
102 //测试test是否可达 
103 bool reachable(string test){
104     for(int i=0;i<production.number;i++){
105         if(production.enable[i] &&into(test,production.right[i] ) )  return 1;
106     }  
107     return 0;
108 } 
109 
110 bool  into(string a,string b){
111     //a是待测试的非终结符,单字符,即产生式左边的部分 
112     for(int i=0;i<b.size();i++){
113         if(a==b.substr(i,1) ) return 1;
114     }  
115     return 0;
116 }
117 
118 void print(){
119     cout<<"G["<<S<<"]:\n";
120     for(int i=0;i<not_endsign.number;i++ ){
121         out.exit[out.number] = 0;
122         out.sign[out.number++ ] = not_endsign.sign[i];
123         
124     }
125     
126     for(int i=0;i<production.number;i++){
127         for(int j=0;j<out.number;j++){
128             if(production.enable[i]){ 
129                 if(production.left[i]==out.sign[j] ){
130                     out.result[j]+=production.right[i]+" | ";
131                     out.exit[j] = 1;
132                 }
133             } 
134         }
135     }
136     
137     for(int i=0;i<out.number;i++){
138         if(out.exit[i]){ 
139             cout<<out.sign[i]<<"::="<<out.result[i].substr(0,out.result[i].length()-3 )<<endl;
140         }
141     }
142     
143     return ;
144 } 
145 
146 void input(){
147     //输入开始符号 
148     cin>>S;
149     
150     //输入非终结符 
151     cin>>not_endsign.number;
152     for(int i=0;i<not_endsign.number;i++ ){
153         cin>>not_endsign.sign[i];
154         not_endsign.get[i] = 0;        //说明非终结符没有输入源   
155         not_endsign.enable[i] = 1;  //说明非终结符现在还可用,还没被删除 
156     }
157     
158     //输入终结符 
159     cin>>end_sign.number;
160     for(int j=0;j<end_sign.number;j++ ){
161         cin>>end_sign.sign[j];
162     }
163     
164     //输入产生式 
165     cin>>production.number;
166     for(int z=0;z<production.number;z++){
167         cin>>production.left[z]>>production.right[z];
168         production.enable[z] = 1;   //说明该产生式还可用,还没被删除   
169     }
170     return ;
171 }
View Code

------------------------------------

题目1005:

技术分享
 1 1005. NDFA 确定化
 2 总提交数量:    53    通过数量:    29
 3            
 4 时间限制:1秒    内存限制:256兆
 5 题目描述
 6  输入字母表,非确定FA状态集,映射集;用造表法算法。
 7 输出确定FA状态集,映射集;
 8 
 9 输入格式
10  输入字母个数,字母表
11 状态个数,状态表(状态名称,开始状态,终止状态:0否1是),空格符分隔;
12 映射个数,映射表(起,终,字母),空格符分隔;
13 【参考作业3.414 
15 输出格式
16  Determine State:
17 状态表: 状态名称,开始状态,终止状态,[子集]
18 Determine Mapping:
19 映射表: 起,终,字母,(顺序号
20 
21 样例输入
22  将样例输入复制到剪贴板
23 2
24 x y
25 5
26 0 1 0
27 1 0 0
28 2 0 0
29 3 0 0
30 4 0 1
31 9
32 0 1 x
33 0 2 y
34 1 2 x
35 1 3 x
36 2 1 y
37 2 3 y
38 3 3 x
39 3 3 y
40 3 4 x
41 样例输出
42 Determine State:
43 0 1 0 [0]
44 1 0 0 [1]
45 2 0 0 [2]
46 3 0 0 [23]
47 4 0 0 [13]
48 5 0 1 [34]
49 6 0 1 [234]
50 7 0 0 [3]
51 Determine Mapping:
52 0 1 x (0
53 0 2 y (1
54 1 3 x (2
55 2 4 y (3
56 3 5 x (4
57 3 4 y (5
58 4 6 x (6
59 4 7 y (7
60 5 5 x (8
61 5 7 y (9
62 6 5 x (10
63 6 4 y (11
64 7 5 x (12
65 7 7 y (13
View Code

AC代码:

技术分享
  1 #include <iostream>
  2 #include <queue>
  3 #include <stdlib.h>
  4 #include <string>
  5 #include <sstream>
  6 using namespace std;
  7 
  8 struct { int number; char zimu[100]; } letter={0};                                             //字母 
  9 struct { int number; int single_state[100];bool isstart[100];bool isend[100]; } state={0};  //状态表 
 10 struct { int number; int start[100]; int end[100]; char letter[100]; } map={0};                //映射表 
 11 
 12 struct { int number; int res_state[100]; bool isstart[100];bool isend[100];string chuan[100]; } ressta={0}; //确定化后的状态表 
 13 struct { int number; int start[100]; int end[100]; char letter[100]; } resmap={0};          //确定化后的映射表 
 14 
 15 struct ss{ int number; int ber[100]; bool isstart;bool isend;  };
 16 queue<ss> temp;        //用来 缓存造表法中的元素 
 17 struct { int number; string left[100];string right[100];char zimu[100];} haha={0};  //用来暂时记录string状态的映射关系    
 18 
 19 void input();  //输入数据 
 20 void print();  //输出结果 
 21 void init();   //初始化 
 22 string int2string(int a);
 23 string change(ss teres);
 24 bool isexist(ss a);
 25 bool isexist_start( ss a );
 26 bool isexist_end(ss a);
 27 
 28 int main(){
 29     input(); 
 30     init();
 31     while(1){ 
 32         ss te = temp.front();  temp.pop();
 33                     
 34         //刷整个映射表,得到确定化后的状态表 ,并将确定化后的映射记录在表中 
 35         for(int i=0; i< letter.number; i++ ){    //字母 
 36             ss teres;  //用来缓存将要压入队列的状态 
 37             teres.number = 0;
 38             
 39             for(int j=0;j< te.number ;j++){
 40                 for(int z=0;z<map.number ;z++){
 41                     if( letter.zimu[i] == map.letter[z]&& te.ber[j]==map.start[z] ){
 42                         bool is=1;
 43                         for(int q=0;q<teres.number;q++){
 44                             if(map.end[z]==teres.ber[q] ) is = 0;
 45                         }
 46                         
 47                         if(is){
 48                             teres.ber[teres.number ] = map.end[z];    
 49                             teres.number++;    
 50                         }   
 51                     }        
 52                 }        
 53             }
 54             
 55             //对teres做“确定化后状态表”处理 
 56             if(!isexist(teres)){
 57                 temp.push(teres);    //压到temp里面  
 58                     
 59                 ressta.res_state[ ressta.number ] = ressta.number;
 60                 ressta.chuan[ressta.number] = change(teres);
 61                 if( isexist_start(teres) ){
 62                     ressta.isstart[ressta.number] = 1;
 63                 }  
 64                 else{
 65                     ressta.isstart[ressta.number] = 0;
 66                 }
 67                 
 68                 if( isexist_end(teres)){
 69                     ressta.isend[ressta.number] = 1;
 70                 }
 71                 else{
 72                     ressta.isend[ressta.number] = 0;
 73                 }
 74                 
 75                 ressta.number++;                
 76             }
 77             
 78             //还有映射表  
 79             if(teres.number!=0){
 80                 haha.left[haha.number ] = change(te);
 81                 haha.right[haha.number] = change(teres);
 82                 haha.zimu[haha.number] = letter.zimu[i];                  
 83                 haha.number++;
 84             }
 85              
 86         }                         
 87         
 88         if(temp.empty()) break;
 89     }    
 90 
 91     for(int i=0;i<haha.number;i++){
 92         int k;
 93         for(k=0; k<ressta.number&&ressta.chuan[k] != haha.left[i]; k++ ) ;
 94         resmap.start[resmap.number] = ressta.res_state[k];
 95         
 96         int p;
 97         for(p=0;p<ressta.number&&ressta.chuan[p]!=haha.right[i];p++ );
 98         resmap.end[resmap.number ] = ressta.res_state[p];
 99             
100         resmap.letter[resmap.number] = haha.zimu[i];
101                 
102         resmap.number++;            
103     }
104 
105     print();    
106     return 0;
107 } 
108 
109 void init(){
110     ressta.number = 0;
111     
112     ss first;
113     first.number = 1;
114     first.isstart = state.isstart[0];  
115     first.isend = state.isend[0];
116     first.ber[0] = state.single_state[0]; 
117     temp.push(first);
118 
119     //相当于把 temp队列中的第一个元素记入 “确定化后的状态集” 
120     ressta.res_state[0] = state.single_state[0];
121     ressta.isstart[0] = state.isstart[0];   
122     ressta.isend[0] = state.isend[0];
123     ressta.chuan[0] = int2string( state.single_state[0] );
124     
125     ressta.number++; 
126         
127     return ;
128 } 
129 
130 bool isexist_start( ss a ){
131     for(int i=0;i<a.number;i++){
132         for(int j=0;j<state.number;j++ ){
133             if(state.isstart[j]==1&&a.ber[i]==state.single_state[j] ) return true;
134         } 
135     }
136     return false;
137 }
138 
139 bool isexist_end(ss a){
140     for(int i=0;i<a.number;i++){
141         for(int j=0;j<state.number;j++ ){
142             if(state.isend[j]==1&&a.ber[i]==state.single_state[j] ) return true;
143         }  
144     }
145     return false;    
146 }
147 
148 bool isexist(ss a){
149     if(a.number==0) return 1;
150     for(int i=0;i<ressta.number;i++){
151         if(ressta.chuan[i]==change(a) ){
152             return 1;
153         }
154     }
155     return 0;
156 }
157 
158 
159 string int2string(int a){
160     stringstream ss;
161     string str;
162     ss<<a;
163     ss>>str;
164     return str;
165 }
166 
167 string  change( ss teres){
168     string res;
169     for(int i=0;i<teres.number;i++ ){
170         res = res + int2string( teres.ber[i] );        
171     }
172     return res;
173 }
174 
175 void input(){
176     cin>>letter.number;
177     for(int i=0;i<letter.number;i++){
178         cin>>letter.zimu[i];
179     }
180     cin>>state.number;
181     for(int i=0;i<state.number;i++){
182         cin>>state.single_state[i]>>state.isstart[i]>>state.isend[i];
183     }
184     cin>>map.number;
185     for(int i=0;i<map.number;i++){
186         cin>>map.start[i]>>map.end[i]>>map.letter[i];
187     }
188     return ;
189 } 
190 
191 void print(){
192     cout<<"Determine State:"<<endl;
193     for(int i=0;i<ressta.number;i++){ 
194         cout<<ressta.res_state[i]<<" "<<ressta.isstart[i]<<" "<<ressta.isend[i]<<" ["<<ressta.chuan[i]<<"]"<<endl;
195     } 
196     
197     cout<<"Determine Mapping:"<<endl;
198     for(int i=0;i<resmap.number;i++){
199         cout<<resmap.start[i]<<" "<<resmap.end[i]<<" "<<resmap.letter[i]<<" ("<<i<<endl;
200     }
201     
202     return ;
203 }
View Code

------------------------------------

题目1006:

技术分享
 1 1006. εNDFA 确定化
 2 总提交数量:    50    通过数量:    29
 3            
 4 时间限制:1秒    内存限制:256兆
 5 题目描述
 6  输入字母表,非确定εNDFA 确定化FA状态集,映射集;用造表法算法。
 7 输出确定FA状态集,映射集;
 8 
 9 输入格式
10  输入字母个数,字母表
11 状态个数,状态表(状态名称,开始状态,终止状态:0否1是),空格符分隔;
12 映射个数,映射表(起,终,字母),空格符分隔,k表示ε;
13 【参考作业3.2<1>14 
15 输出格式
16  Determine State:
17 状态表: 状态名称,开始状态,终止状态,[子集]
18 Determine Mapping:
19 映射表: 起,终,字母,(顺序号
20 
21 样例输入
22  将样例输入复制到剪贴板
23 2
24 x y
25 9
26 0 1 0
27 1 0 0
28 2 0 0
29 3 0 0
30 4 0 0
31 5 0 0
32 6 0 0
33 7 0 0
34 8 0 1
35 12
36 0 1 x
37 0 3 y
38 0 6 x
39 1 2 k
40 2 2 y
41 2 8 k
42 3 4 k
43 4 4 x
44 4 5 k
45 5 8 y
46 6 7 y
47 7 8 x
48 样例输出
49 Determine State:
50 0 1 0 [0]
51 1 0 1 [1268]
52 2 0 0 [345]
53 3 0 1 [278]
54 4 0 0 [45]
55 5 0 1 [8]
56 6 0 1 [28]
57 Determine Mapping:
58 0 1 x (0
59 0 2 y (1
60 1 3 y (2
61 2 4 x (3
62 2 5 y (4
63 3 5 x (5
64 3 6 y (6
65 4 4 x (7
66 4 5 y (8
67 6 6 y (9
View Code

AC代码:

技术分享
  1 #include <iostream>
  2 #include <queue>
  3 #include <stdlib.h>
  4 #include <string>
  5 #include <sstream>
  6 using namespace std;
  7 
  8 struct { int number; char zimu[100]; } letter={0};                                          //字母 
  9 struct { int number; int single_state[100];bool isstart[100];bool isend[100]; } state={0};  //状态表 
 10 struct { int number; int start[100]; int end[100]; char letter[100]; } map={0};             //映射表 
 11 
 12 struct { int number; int res_state[100]; bool isstart[100];bool isend[100];string chuan[100]; } ressta={0}; //确定化后的状态表 
 13 struct { int number; int start[100]; int end[100]; char letter[100]; } resmap={0};          //确定化后的映射表 
 14 
 15 struct ss{ int number; int ber[100]; bool isstart;bool isend;  };
 16 queue<ss> temp;          //用来 缓存造表法中的元素 
 17 struct { int number; string left[100];string right[100];char zimu[100];} haha={0};  //用来暂时记录string状态的映射关系    
 18 queue<int > letter_kong; //用来实现映射的 “深搜”的队列 
 19 
 20 void input();  //输入数据 
 21 void print();  //输出结果 
 22 void init();   //初始化 
 23 string int2string(int a);
 24 string change(ss teres);
 25 bool isexist(ss a);
 26 bool isexist_start( ss a );
 27 bool isexist_end(ss a);
 28 void sort(ss a); 
 29 
 30 int main(){
 31     input(); 
 32     init();
 33  
 34     while(1){ 
 35         ss te = temp.front();  temp.pop();
 36                     
 37         //刷整个映射表,得到确定化后的状态表 ,并将确定化后的映射记录在表中 
 38         for(int i=0; i< letter.number; i++ ){    //字母 
 39             ss teres;  //用来缓存将要压入队列的状态 
 40             teres.number = 0;
 41             
 42             for(int j=0;j< te.number ;j++){
 43                 for(int z=0;z<map.number ;z++){
 44                     if( letter.zimu[i] == map.letter[z]&& te.ber[j]==map.start[z] ){
 45                         bool is=1;
 46                         for(int q=0;q<teres.number;q++){
 47                             if(map.end[z]==teres.ber[q] ) is = 0;
 48                         }
 49                         
 50                         if(is){
 51                             //先把确定的这个放进去 
 52                             teres.ber[teres.number ] = map.end[z];  
 53                             teres.number++; 
 54                                                         
 55                             //处理有可能是空的需要深搜的情况 
 56                             letter_kong.push( map.end[z] ); 
 57                             while(1){
 58                                 int temp = letter_kong.front();letter_kong.pop();
 59                                 for(int r=0;r<map.number;r++ ){
 60                                     if(temp==map.start[r]&&map.letter[r]==k ){
 61                                         //判断重复
 62                                         bool iss=1;
 63                                         for(int qq=0;qq<teres.number;qq++){
 64                                             if(map.end[r ]==teres.ber[qq] ) is = 0;
 65                                         }
 66                                                         
 67                                         if(iss){
 68                                             teres.ber[teres.number ] = map.end[r];
 69                                             teres.number++;
 70                                             letter_kong.push(map.end[r]); //将新的节点放进去    
 71                                         } 
 72                                         
 73                                     }
 74                                 }
 75                                 
 76                                 if(letter_kong.empty()) break;
 77                             }
 78                             
 79                             
 80                             
 81                         //  */
 82                             
 83                         }   
 84                     }       
 85                 }       
 86             }
 87             
 88             //对teres中的元素按大小排序   
 89             int tempq;
 90             for(int ii=0;ii<teres.number - 1;ii++ ){
 91                 for(int jj=ii+1;jj<teres.number;jj++ ){
 92                     if(teres.ber[jj]<teres.ber[ii] ){
 93                         
 94                         tempq = teres.ber[ii];
 95                         teres.ber[ii] = teres.ber[jj];
 96                         teres.ber[jj] = tempq;
 97                     } 
 98                 }  
 99             }
100                     
101             //对teres做“确定化后状态表”处理 
102             if(!isexist(teres)){
103                 temp.push(teres);   //压到temp里面  
104                     
105                 ressta.res_state[ ressta.number ] = ressta.number;
106                 ressta.chuan[ressta.number] = change(teres);
107                 if( isexist_start(teres) ){
108                     ressta.isstart[ressta.number] = 1;
109                 }  
110                 else{
111                     ressta.isstart[ressta.number] = 0;
112                 }
113                 
114                 if( isexist_end(teres)){
115                     ressta.isend[ressta.number] = 1;
116                 }
117                 else{
118                     ressta.isend[ressta.number] = 0;
119                 }
120                 
121                 ressta.number++;                
122             }
123             
124             //还有映射表  
125             if(teres.number!=0){
126                 haha.left[haha.number ] = change(te);
127                 haha.right[haha.number] = change(teres);
128                 haha.zimu[haha.number] = letter.zimu[i];                
129                 haha.number++;
130             }
131              
132         }                       
133         
134         if(temp.empty()) break;
135     }   
136 
137     for(int i=0;i<haha.number;i++){
138         int k;
139         for(k=0; k<ressta.number&&ressta.chuan[k] != haha.left[i]; k++ ) ;
140         resmap.start[resmap.number] = ressta.res_state[k];
141         
142         int p;
143         for(p=0;p<ressta.number&&ressta.chuan[p]!=haha.right[i];p++ );
144         resmap.end[resmap.number ] = ressta.res_state[p];
145             
146         resmap.letter[resmap.number] = haha.zimu[i];
147                 
148         resmap.number++;            
149     }
150 
151     print();    
152     return 0;
153 } 
154 
155 void init(){
156     ressta.number = 0;
157     
158     ss first;
159     first.number = 1;
160     first.isstart = state.isstart[0];  
161     first.isend = state.isend[0];
162     first.ber[0] = state.single_state[0]; 
163     temp.push(first);
164 
165     //相当于把 temp队列中的第一个元素记入 “确定化后的状态集” 
166     ressta.res_state[0] = state.single_state[0];
167     ressta.isstart[0] = state.isstart[0];   
168     ressta.isend[0] = state.isend[0];
169     ressta.chuan[0] = int2string( state.single_state[0] );
170     
171     ressta.number++; 
172         
173     return ;
174 } 
175 
176 bool isexist_start( ss a ){
177     for(int i=0;i<a.number;i++){
178         for(int j=0;j<state.number;j++ ){
179             if(state.isstart[j]==1&&a.ber[i]==state.single_state[j] ) return true;
180         } 
181     }
182     return false;
183 }
184 
185 bool isexist_end(ss a){
186     for(int i=0;i<a.number;i++){
187         for(int j=0;j<state.number;j++ ){
188             if(state.isend[j]==1&&a.ber[i]==state.single_state[j] ) return true;
189         }  
190     }
191     return false;   
192 }
193 
194 bool isexist(ss a){
195     if(a.number==0) return 1;
196     for(int i=0;i<ressta.number;i++){
197         if(ressta.chuan[i]==change(a) ){
198             return 1;
199         }
200     }
201     return 0;
202 }
203 
204 
205 string int2string(int a){
206     stringstream ss;
207     string str;
208     ss<<a;
209     ss>>str;
210     return str;
211 }
212 
213 string  change( ss teres){
214     string res;
215     for(int i=0;i<teres.number;i++ ){
216         res = res + int2string( teres.ber[i] );     
217     }
218     return res;
219 }
220 
221 void input(){
222     cin>>letter.number;
223     for(int i=0;i<letter.number;i++){
224         cin>>letter.zimu[i];
225     }
226     cin>>state.number;
227     for(int i=0;i<state.number;i++){
228         cin>>state.single_state[i]>>state.isstart[i]>>state.isend[i];
229     }
230     cin>>map.number;
231     for(int i=0;i<map.number;i++){
232         cin>>map.start[i]>>map.end[i]>>map.letter[i];
233     }
234     return ;
235 } 
236 
237 void print(){
238     cout<<"Determine State:"<<endl;
239     for(int i=0;i<ressta.number;i++){ 
240         cout<<ressta.res_state[i]<<" "<<ressta.isstart[i]<<" "<<ressta.isend[i]<<" ["<<ressta.chuan[i]<<"]"<<endl;
241     } 
242     
243     cout<<"Determine Mapping:"<<endl;
244     for(int i=0;i<resmap.number;i++){
245         cout<<resmap.start[i]<<" "<<resmap.end[i]<<" "<<resmap.letter[i]<<" ("<<i<<endl;
246     }
247     
248     return ;
249 }                                 
View Code

 

2-自上而下语法分析

题目1000:

技术分享
 1 1000. 输入输出LL(1)语法分析程序
 2 总提交数量:    57    通过数量:    30
 3            
 4 时间限制:1秒    内存限制:256兆
 5 题目描述
 6  输入开始符号,非终结符,终结符,产生式,LL(1)分析表
 7 输出LL(1)分析表
 8 
 9 G[E]:E →E+T | E-T | T
10 
11 T →T*F | T/F | F
12 F →(E) | D
13 D →x | y | z  
14 消除左递归G1[E]: 
15 E →TA 
16 A →+TA | -TA | e 
17 T →FB 
18 B →*FB | /FB | e 
19 F →(E) | D 
20 D →x | y | z  
21 输入格式
22  输入开始符号;
23 非终结符个数,非终结符,空格符分隔;
24 终结符个数,终结符,空格符分隔;
25 产生式的个数,各产生式的序号,产生式的左边和右边符号,空格符分隔;
26 LL(1)分析表中的产生式个数,序号,行符号,列符号,产生式编号,空格符分隔;
27 
28 输出格式
29  第一行:空,安终结符循序输出终结符,结束符‘#’,每个符号占5格;
30 其余行:非终结符符号,各对应终结符的产生式的右边,每个符号占5格;
31 
32 样例输入
33  将样例输入复制到剪贴板
34 E
35 6  E A T B F D
36 9 + - * / ( ) x y z 
37 13
38 1  E TA
39 2  A +TA
40 3  A -TA
41 4  A k
42 5  T FB
43 6  B *FB
44 7  B /FB
45 8  B k
46 9  F (E)
47 10 F D
48 11 D x
49 12 D y
50 13 D z
51 25
52 1  E ( 1
53 2  E x 1
54 3  E y 1
55 4  E z 1
56 5  A + 2
57 6  A - 3
58 7  A ) 4
59 8  A # 4
60 9  T ( 5
61 10 T x 5
62 11 T y 5
63 12 T z 5
64 13 B + 8
65 14 B - 8
66 15 B * 6
67 16 B / 7
68 17 B ) 8
69 18 B # 8
70 19 F ( 9
71 20 F x 10
72 21 F y 10
73 22 F z 10
74 23 D x 11
75 24 D y 12
76 25 D z 13
77 样例输出
78          +    -    *    /    (    )    x    y    z    #
79     E                       TA        TA   TA   TA     
80     A  +TA  -TA                   k                   k
81     T                       FB        FB   FB   FB     
82     B    k    k  *FB  /FB         k                   k
83     F                      (E)         D    D    D     
84     D                                  x    y    z  
View Code

AC代码:

技术分享
 1 #include <iostream>
 2 using namespace std;
 3 
 4 string S="";                                                                                          //开始符号 
 5 struct { int number;string sign[20]; string res_LL[20][20]; } not_endsign={0};                       //非终结符
 6 struct { int number;string sign[20]; } end_sign={0};                                                  //终结符
 7 struct { int number;int order[100]; string left[100],right[100]; } production={0};                    //产生式 
 8 struct { int number;int order[100]; string rank[100],col[100];int production_num[100];  } LL={0};   //LL(1)分析表 
 9 
10 void input();
11 void print(string a);
12 
13 int main(){
14     input();
15     end_sign.sign[end_sign.number] = "#";
16     end_sign.number++;
17     
18     //刷整个的分析表,将分析表中的数据填入到not_endsign中去 
19     for(int i=0;i<LL.number;i++){
20         //得到LL一条数据的“行”对应的“非终结符” 
21         int j;
22         for(j=0;j<not_endsign.number&& not_endsign.sign[j]!=LL.rank[i];j++ ); 
23         
24         //得到LL一条数据的“列”对应的“终结符” 
25         int z;
26         for(z=0;z<end_sign.number&&end_sign.sign[z]!=LL.col[i];z++ ); 
27         
28         //得到LL一条数据的要赋予的值   
29         not_endsign.res_LL[j][z] = production.right[LL.production_num[i]-1 ];
30     }
31     
32     //单独处理“#” 
33     
34     cout<<"     ";
35     for(int i=0;i<end_sign.number;i++){
36         cout<<"    "<<end_sign.sign[i];
37     }
38     cout<<endl;  
39     
40     for(int i=0;i<not_endsign.number;i++){
41         print(not_endsign.sign[i]); 
42         cout<<not_endsign.sign[i];
43         for(int j=0;j<end_sign.number ;j++){
44             print(not_endsign.res_LL[i][j] );
45             cout<<not_endsign.res_LL[i][j];
46         }
47         cout<<endl;
48     }
49     
50     return 0;
51 } 
52 
53 void print(string a){
54     for(int i=0;i<5-a.length();i++){
55         cout<<" ";
56     }
57     return ;
58 }
59 void input(){
60     cin>>S;
61     cin>>not_endsign.number;
62     for(int i=0;i<not_endsign.number;i++){
63         cin>>not_endsign.sign[i];
64     }
65     
66     cin>>end_sign.number;
67     for(int i=0;i<end_sign.number;i++){
68         cin>>end_sign.sign[i];
69     }
70     
71     cin>>production.number;
72     for(int i=0;i<production.number;i++){
73         cin>>production.order[i]>>production.left[i]>>production.right[i];
74     }
75     
76     cin>>LL.number;
77     for(int i=0;i<LL.number;i++){
78         cin>>LL.order[i]>>LL.rank[i]>>LL.col[i]>>LL.production_num[i];
79     }
80     return ;
81 }
View Code

-----------------------------------------------

题目1001:

技术分享
  1 1001. 输入输出LL(1)语法分析程序
  2 总提交数量:    55    通过数量:    37
  3            
  4 时间限制:1秒    内存限制:256兆
  5 题目描述
  6  输入开始符号,非终结符,终结符,产生式,LL(1)分析表
  7 输出LL(1)分析表
  8 
  9 输入格式
 10  输入开始符号;
 11 非终结符个数,非终结符,空格符分隔;
 12 终结符个数,终结符,空格符分隔;
 13 产生式的个数,各产生式的序号,产生式的左边和右边符号,空格符分隔;
 14 LL(1)分析表中的产生式个数,序号,行符号,列符号,产生式编号,空格符分隔;
 15 输入一个算术式符号串,用#结束
 16 
 17 输出格式
 18  输出推导过程,每一步一行,中间“ & ”前是已经识别的子串,后是栈中信息。
 19 
 20 样例输入
 21  将样例输入复制到剪贴板
 22 E
 23 6  E A T B F D
 24 9  + - * / ( ) x y z 
 25 13
 26 1  E TA
 27 2  A +TA
 28 3  A -TA
 29 4  A k
 30 5  T FB
 31 6  B *FB
 32 7  B /FB
 33 8  B k
 34 9  F (E)
 35 10 F D
 36 11 D x
 37 12 D y
 38 13 D z
 39 25
 40 1  E ( 1
 41 2  E x 1
 42 3  E y 1
 43 4  E z 1
 44 5  A + 2
 45 6  A - 3
 46 7  A ) 4
 47 8  A # 4
 48 9  T ( 5
 49 10 T x 5
 50 11 T y 5
 51 12 T z 5
 52 13 B + 8
 53 14 B - 8
 54 15 B * 6
 55 16 B / 7
 56 17 B ) 8
 57 18 B # 8
 58 19 F ( 9
 59 20 F x 10
 60 21 F y 10
 61 22 F z 10
 62 23 D x 11
 63 24 D y 12
 64 25 D z 13
 65 (x+(y-x*z)*(y+x*z))+x/z#
 66 样例输出
 67 # & E#
 68 # & TA#
 69 # & FBA#
 70 # & (E)BA#
 71 #( & E)BA#
 72 #( & TA)BA#
 73 #( & FBA)BA#
 74 #( & DBA)BA#
 75 #( & xBA)BA#
 76 #(x & BA)BA#
 77 #(x & A)BA#
 78 #(x & +TA)BA#
 79 #(x+ & TA)BA#
 80 #(x+ & FBA)BA#
 81 #(x+ & (E)BA)BA#
 82 #(x+( & E)BA)BA#
 83 #(x+( & TA)BA)BA#
 84 #(x+( & FBA)BA)BA#
 85 #(x+( & DBA)BA)BA#
 86 #(x+( & yBA)BA)BA#
 87 #(x+(y & BA)BA)BA#
 88 #(x+(y & A)BA)BA#
 89 #(x+(y & -TA)BA)BA#
 90 #(x+(y- & TA)BA)BA#
 91 #(x+(y- & FBA)BA)BA#
 92 #(x+(y- & DBA)BA)BA#
 93 #(x+(y- & xBA)BA)BA#
 94 #(x+(y-x & BA)BA)BA#
 95 #(x+(y-x & *FBA)BA)BA#
 96 #(x+(y-x* & FBA)BA)BA#
 97 #(x+(y-x* & DBA)BA)BA#
 98 #(x+(y-x* & zBA)BA)BA#
 99 #(x+(y-x*z & BA)BA)BA#
100 #(x+(y-x*z & A)BA)BA#
101 #(x+(y-x*z & )BA)BA#
102 #(x+(y-x*z) & BA)BA#
103 #(x+(y-x*z) & *FBA)BA#
104 #(x+(y-x*z)* & FBA)BA#
105 #(x+(y-x*z)* & (E)BA)BA#
106 #(x+(y-x*z)*( & E)BA)BA#
107 #(x+(y-x*z)*( & TA)BA)BA#
108 #(x+(y-x*z)*( & FBA)BA)BA#
109 #(x+(y-x*z)*( & DBA)BA)BA#
110 #(x+(y-x*z)*( & yBA)BA)BA#
111 #(x+(y-x*z)*(y & BA)BA)BA#
112 #(x+(y-x*z)*(y & A)BA)BA#
113 #(x+(y-x*z)*(y & +TA)BA)BA#
114 #(x+(y-x*z)*(y+ & TA)BA)BA#
115 #(x+(y-x*z)*(y+ & FBA)BA)BA#
116 #(x+(y-x*z)*(y+ & DBA)BA)BA#
117 #(x+(y-x*z)*(y+ & xBA)BA)BA#
118 #(x+(y-x*z)*(y+x & BA)BA)BA#
119 #(x+(y-x*z)*(y+x & *FBA)BA)BA#
120 #(x+(y-x*z)*(y+x* & FBA)BA)BA#
121 #(x+(y-x*z)*(y+x* & DBA)BA)BA#
122 #(x+(y-x*z)*(y+x* & zBA)BA)BA#
123 #(x+(y-x*z)*(y+x*z & BA)BA)BA#
124 #(x+(y-x*z)*(y+x*z & A)BA)BA#
125 #(x+(y-x*z)*(y+x*z & )BA)BA#
126 #(x+(y-x*z)*(y+x*z) & BA)BA#
127 #(x+(y-x*z)*(y+x*z) & A)BA#
128 #(x+(y-x*z)*(y+x*z) & )BA#
129 #(x+(y-x*z)*(y+x*z)) & BA#
130 #(x+(y-x*z)*(y+x*z)) & A#
131 #(x+(y-x*z)*(y+x*z)) & +TA#
132 #(x+(y-x*z)*(y+x*z))+ & TA#
133 #(x+(y-x*z)*(y+x*z))+ & FBA#
134 #(x+(y-x*z)*(y+x*z))+ & DBA#
135 #(x+(y-x*z)*(y+x*z))+ & xBA#
136 #(x+(y-x*z)*(y+x*z))+x & BA#
137 #(x+(y-x*z)*(y+x*z))+x & /FBA#
138 #(x+(y-x*z)*(y+x*z))+x/ & FBA#
139 #(x+(y-x*z)*(y+x*z))+x/ & DBA#
140 #(x+(y-x*z)*(y+x*z))+x/ & zBA#
141 #(x+(y-x*z)*(y+x*z))+x/z & BA#
142 #(x+(y-x*z)*(y+x*z))+x/z & A#
143 #(x+(y-x*z)*(y+x*z))+x/z & #
View Code

AC代码:

技术分享
  1 #include <iostream>
  2 #include <stack>
  3 using namespace std;
  4 
  5 string S="";                                                                                          //开始符号 
  6 struct { int number;string sign[20]; string res_LL[20][20]; } not_endsign={0};                       //非终结符
  7 struct { int number;string sign[20]; } end_sign={0};                                                  //终结符
  8 struct { int number;int order[100]; string left[100],right[100]; } production={0};                    //产生式 
  9 struct { int number;int order[100]; string rank[100],col[100];int production_num[100];  } LL={0};   //LL(1)分析表 
 10 string test;
 11 
 12 void input();
 13 void print(string left,stack<string >  right);
 14 
 15 int main(){
 16     input();
 17     
 18     //定义输出结果 
 19     string left;
 20     stack<string >  right;
 21     
 22     right.push(S) ;    
 23     print(left,right);
 24 
 25     while(!right.empty()){ 
 26         string top = right.top();
 27         string firstletter = test.substr(0,1);
 28         if(top==firstletter){
 29             left += top;
 30             test = test.substr(1,test.length()-1 );
 31             right.pop();
 32             print(left,right);
 33             
 34             continue;  
 35         }
 36         else {
 37             //替换掉 top  
 38             for(int i=0;i<LL.number;i++){
 39                  if(LL.rank[i]==top &&LL.col[i]==firstletter ){
 40                      right.pop();
 41                      string temp = production.right[LL.production_num[i]-1 ];
 42                     if(temp=="k") continue;
 43                      while(temp.length()!=0){
 44                         string temp0 = temp.substr( temp.length()-1,1);
 45                         right.push(temp0);
 46                         temp = temp.substr(0,temp.length()-1);  
 47                     }
 48                      
 49                  }
 50             } 
 51             
 52         }
 53         
 54         print(left,right);
 55     }
 56     
 57     return 0;
 58 } 
 59 
 60 void print(string left,stack<string >  right){ 
 61     cout<<"#"<<left<<" & ";
 62     string temp="";
 63     while(!right.empty()){
 64         cout<<right.top();
 65         temp+=right.top();
 66         right.pop();
 67     }
 68     cout<<"#"<<endl;
 69     
 70     while(temp.length()!=0){
 71         string temp0 = temp.substr( temp.length()-1,1);
 72         right.push(temp0);
 73         temp = temp.substr(0,temp.length()-1);  
 74     }
 75     
 76     return ;
 77 }
 78 
 79 void input(){
 80     cin>>S;
 81     cin>>not_endsign.number;
 82     for(int i=0;i<not_endsign.number;i++){
 83         cin>>not_endsign.sign[i];
 84     }
 85     
 86     cin>>end_sign.number;
 87     for(int i=0;i<end_sign.number;i++){
 88         cin>>end_sign.sign[i];
 89     }
 90     
 91     cin>>production.number;
 92     for(int i=0;i<production.number;i++){
 93         cin>>production.order[i]>>production.left[i]>>production.right[i];
 94     }
 95     
 96     cin>>LL.number;
 97     for(int i=0;i<LL.number;i++){
 98         cin>>LL.order[i]>>LL.rank[i]>>LL.col[i]>>LL.production_num[i];
 99     }
100     
101     cin>>test;
102     return ;
103 }
View Code

 

3-优先法语法分析

 

编译原理的一些练习题

标签:算法   class   style   log   com   http   it   si   la   

原文:http://www.cnblogs.com/liugl7/p/5501935.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号