编译原理实验Sicily--输入输出LL(1)语法分析程序_sicily 文法推导

Description

 输入开始符号，非终结符，终结符，产生式，LL(1)分析表
输出LL(1)分析表

Input

 输入开始符号；
非终结符个数，非终结符，空格符分隔；
终结符个数，终结符，空格符分隔；
产生式的个数，各产生式的序号，产生式的左边和右边符号，空格符分隔；
LL(1)分析表中的产生式个数，序号，行符号，列符号，产生式编号，空格符分隔；
输入一个算术式符号串，用#结束

Output

 输出推导过程，每一步一行，中间“ & ”前是已经识别的子串，后是栈中信息。

Sample InputCopy

E
6  E A T B F D
9  + - * / ( ) x y z 
13
1  E TA
2  A +TA
3  A -TA
4  A k
5  T FB
6  B *FB
7  B /FB
8  B k
9  F (E)
10 F D
11 D x
12 D y
13 D z
25
1  E ( 1
2  E x 1
3  E y 1
4  E z 1
5  A + 2
6  A - 3
7  A ) 4
8  A # 4
9  T ( 5
10 T x 5
11 T y 5
12 T z 5
13 B + 8
14 B - 8
15 B * 6
16 B / 7
17 B ) 8
18 B # 8
19 F ( 9
20 F x 10
21 F y 10
22 F z 10
23 D x 11
24 D y 12
25 D z 13
(x+(y-x*z)*(y+x*z))+x/z#

Sample OutputCopy

# & E#
# & TA#
# & FBA#
# & (E)BA#
#( & E)BA#
#( & TA)BA#
#( & FBA)BA#
#( & DBA)BA#
#( & xBA)BA#
#(x & BA)BA#
#(x & A)BA#
#(x & +TA)BA#
#(x+ & TA)BA#
#(x+ & FBA)BA#
#(x+ & (E)BA)BA#
#(x+( & E)BA)BA#
#(x+( & TA)BA)BA#
#(x+( & FBA)BA)BA#
#(x+( & DBA)BA)BA#
#(x+( & yBA)BA)BA#
#(x+(y & BA)BA)BA#
#(x+(y & A)BA)BA#
#(x+(y & -TA)BA)BA#
#(x+(y- & TA)BA)BA#
#(x+(y- & FBA)BA)BA#
#(x+(y- & DBA)BA)BA#
#(x+(y- & xBA)BA)BA#
#(x+(y-x & BA)BA)BA#
#(x+(y-x & *FBA)BA)BA#
#(x+(y-x* & FBA)BA)BA#
#(x+(y-x* & DBA)BA)BA#
#(x+(y-x* & zBA)BA)BA#
#(x+(y-x*z & BA)BA)BA#
#(x+(y-x*z & A)BA)BA#
#(x+(y-x*z & )BA)BA#
#(x+(y-x*z) & BA)BA#
#(x+(y-x*z) & *FBA)BA#
#(x+(y-x*z)* & FBA)BA#
#(x+(y-x*z)* & (E)BA)BA#
#(x+(y-x*z)*( & E)BA)BA#
#(x+(y-x*z)*( & TA)BA)BA#
#(x+(y-x*z)*( & FBA)BA)BA#
#(x+(y-x*z)*( & DBA)BA)BA#
#(x+(y-x*z)*( & yBA)BA)BA#
#(x+(y-x*z)*(y & BA)BA)BA#
#(x+(y-x*z)*(y & A)BA)BA#
#(x+(y-x*z)*(y & +TA)BA)BA#
#(x+(y-x*z)*(y+ & TA)BA)BA#
#(x+(y-x*z)*(y+ & FBA)BA)BA#
#(x+(y-x*z)*(y+ & DBA)BA)BA#
#(x+(y-x*z)*(y+ & xBA)BA)BA#
#(x+(y-x*z)*(y+x & BA)BA)BA#
#(x+(y-x*z)*(y+x & *FBA)BA)BA#
#(x+(y-x*z)*(y+x* & FBA)BA)BA#
#(x+(y-x*z)*(y+x* & DBA)BA)BA#
#(x+(y-x*z)*(y+x* & zBA)BA)BA#
#(x+(y-x*z)*(y+x*z & BA)BA)BA#
#(x+(y-x*z)*(y+x*z & A)BA)BA#
#(x+(y-x*z)*(y+x*z & )BA)BA#
#(x+(y-x*z)*(y+x*z) & BA)BA#
#(x+(y-x*z)*(y+x*z) & A)BA#
#(x+(y-x*z)*(y+x*z) & )BA#
#(x+(y-x*z)*(y+x*z)) & BA#
#(x+(y-x*z)*(y+x*z)) & A#
#(x+(y-x*z)*(y+x*z)) & +TA#
#(x+(y-x*z)*(y+x*z))+ & TA#
#(x+(y-x*z)*(y+x*z))+ & FBA#
#(x+(y-x*z)*(y+x*z))+ & DBA#
#(x+(y-x*z)*(y+x*z))+ & xBA#
#(x+(y-x*z)*(y+x*z))+x & BA#
#(x+(y-x*z)*(y+x*z))+x & /FBA#
#(x+(y-x*z)*(y+x*z))+x/ & FBA#
#(x+(y-x*z)*(y+x*z))+x/ & DBA#
#(x+(y-x*z)*(y+x*z))+x/ & zBA#
#(x+(y-x*z)*(y+x*z))+x/z & BA#
#(x+(y-x*z)*(y+x*z))+x/z & A#
#(x+(y-x*z)*(y+x*z))+x/z & #

Problem Source: 自上而下语法分析

程序：

#include <iostream>
#include <stack>
using namespace std;
 
string S="";                                                                                          //开始符号 
struct { int number;string sign[20]; string res_LL[20][20]; } not_endsign={0};                       //非终结符
struct { int number;string sign[20]; } end_sign={0};                                                  //终结符
struct { int number;int order[100]; string left[100],right[100]; } production={0};                    //产生式 
struct { int number;int order[100]; string rank[100],col[100];int production_num[100];  } LL={0};   //LL(1)分析表 
string test;
 
void input();
void print(string left,stack<string >  right);
 
int main(){
    input();
    
    //定义输出结果 
    string left;
    stack<string >  right;
    
    right.push(S) ;    
    print(left,right);
 
    while(!right.empty()){ 
        string top = right.top();
        string firstletter = test.substr(0,1);
        if(top==firstletter){
            left += top;
            test = test.substr(1,test.length()-1 );
            right.pop();
            print(left,right);
            
            continue;  
        }
        else {
            //替换掉 top  
            for(int i=0;i<LL.number;i++){
                 if(LL.rank[i]==top &&LL.col[i]==firstletter ){
                     right.pop();
                     string temp = production.right[LL.production_num[i]-1 ];
                    if(temp=="k") continue;
                     while(temp.length()!=0){
                        string temp0 = temp.substr( temp.length()-1,1);
                        right.push(temp0);
                        temp = temp.substr(0,temp.length()-1);  
                    }
                     
                 }
            } 
            
        }
        
        print(left,right);
    }
    
    return 0;
} 
 
void print(string left,stack<string >  right){ 
    cout<<"#"<<left<<" & ";
    string temp="";
    while(!right.empty()){
        cout<<right.top();
        temp+=right.top();
        right.pop();
    }
    cout<<"#"<<endl;
    
    while(temp.length()!=0){
        string temp0 = temp.substr( temp.length()-1,1);
        right.push(temp0);
        temp = temp.substr(0,temp.length()-1);  
    }
    
    return ;
}
 
void input(){
    cin>>S;
    cin>>not_endsign.number;
    for(int i=0;i<not_endsign.number;i++){
        cin>>not_endsign.sign[i];
    }
    
    cin>>end_sign.number;
    for(int i=0;i<end_sign.number;i++){
        cin>>end_sign.sign[i];
    }
        cin>>production.number;
    for(int i=0;i<production.number;i++){
        cin>>production.order[i]>>production.left[i]>>production.right[i];
    }
    
    cin>>LL.number;
    for(int i=0;i<LL.number;i++){
        cin>>LL.order[i]>>LL.rank[i]>>LL.col[i]>>LL.production_num[i];
    }
    
    cin>>test;
    return ;
}