编译原理实验3《算符优先分析法设计与实现》

以你之姓@ 2021-11-11 06:40 315阅读 0赞

#### 实验3《算符优先分析法设计与实现》 ####

##### 一、实验目的 #####

加深对语法分析器工作过程的理解；加强对算符优先分析法实现语法分析程序的掌握；能够采用一种编程语言实现简单的语法分析程序；能够使用自己编写的分析程序对简单的程序段进行语法翻译。

##### 二、实验内容 #####

在实验1的基础上，用算符优先分析法编制语法分析程序，语法分析程序的实现可以采用任何一种编程语言和工具。

##### 三、实验方法 #####

1．实验采用C++程序语言进行设计，用户自定义输入文法进行分析；  
  2．开发工具为Visual Studio Code。

##### 四、实验步骤 #####

1．本程序中的文法，实质上是算数表达式的计算。  
  2．构建firstVT()和lastVT()这两个集合；  
  3．构建优先符号表；  
  4．构建词法分析的程序；  
  5．编写main函数，用户输入文法对语句利用算符优先文法进行判别。  
  6．算法的主体思想：  
  用栈存储已经看到的输入符号，用优先关系指导移动归约语法分析器的动作 ，如果栈顶的终结符和下一个输入符之间的优先关系是<或=，则语法分析器移动，表示还没有发现句柄的右端，如果是>关系，就调用归约。

##### 五、实验结果 #####

1.  运行实验代码，用户先输入文法个数，之后输入具体文法，程序根据输入进行FIRSTVT集、LASTVT集和算符优先表的计算，之后再对句子进行文法判别。  
      实验输入数据为：

6 
    S->#E# 
    P->i 
    F->P 
    T->F 
    E->T 
    E->E+T

测试结果：  
  测试结果符合预期结果，能够对句子i+i进行正确判别，用户也可以自定义其他语句进行实验。实验截图如下所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTY0NTU1_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTY0NTU1_size_16_color_FFFFFF_t_70 1]

##### 六、实验结论 #####

1．实验利用自定义的源程序进行测试，结果正确，符合预期结果，测试源码及结果截图和说明如上所示。  
  2．实验源代码如下所示：  
  **test3.cpp**

/************************** Compiler Principle test3 算符优先分析法设计与实现 author:zz vs code 2019.05.05 ***************************/
    #include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <vector>
    #include <stack>
    #include <map>
    #include <set>
    #include <algorithm>
    #include <string>
    #include <cstdlib>
    #include <cctype>
    #define MAX 507
     
    using namespace std;
     
    class WF
    { 
        public:
        string left;
        vector<string> right;
        WF ( const string& str )
        { 
            left = str;
        }
        void insert ( char str[] )
        { 
            right.push_back(str);
        }
        void print ( )
        { 
            printf ( "%s->%s" , left.c_str() , right[0].c_str() );
            for ( int i = 1 ; i < right.size() ; i++ )
                printf ( "|%s" , right[i].c_str() );
            puts("");
        }
    };
     
    char relation[MAX][MAX];
    vector<char> VT;
    vector<WF> VN_set;
    map<string,int> VN_dic;
    set<char> first[MAX];
    set<char> last[MAX];
    int used[MAX];
    int vis[MAX];
     
    void dfs (  int x )
    { 
        if ( vis[x] ) return;
        vis[x] = 1;
        string& left = VN_set[x].left;
        for ( int i = 0 ; i < VN_set[x].right.size() ; i++ )
        { 
            string& str = VN_set[x].right[i];
            if ( isupper(str[0]) )
            { 
                int y = VN_dic[str.substr(0,1)]-1;
                if ( str.length() > 1 && !isupper(str[1] ) )
                    first[x].insert ( str[1] );
                dfs ( y );
                set<char>::iterator it = first[y].begin();
                for ( ; it!= first[y].end() ; it++ )
                    first[x].insert ( *it );
            }
            else 
                first[x].insert ( str[0] );
        }
    }
     
    void make_first ( )
    { 
        memset ( vis , 0 , sizeof ( vis ) );
        for ( int i = 0 ; i < VN_set.size() ; i++ )
            if ( vis[i] ) continue;
            else dfs ( i );
    #define DEBUG
    #ifdef DEBUG
        puts("------------FIRSTVT集-------------------");
        for ( int i = 0 ; i < VN_set.size() ; i++ )
        { 
            printf ( "%s : " , VN_set[i].left.c_str() );
            set<char>::iterator it = first[i].begin();
            for ( ; it!= first[i].end() ; it++ )
                printf ( "%c " , *it );
            puts ("" );
        }
    #endif 
    }
     
    void dfs1 ( int x )
    { 
        if ( vis[x] ) return;
        vis[x] = 1;
        string& left = VN_set[x].left;
        for ( int i = 0 ; i < VN_set[x].right.size() ; i++ )
        { 
            string& str = VN_set[x].right[i];
            int n = str.length() -1;
            if ( isupper(str[n] ) )
            { 
                int y = VN_dic[str.substr(n,1)]-1;
                if ( str.length() > 1 && !isupper(str[n-1]) )
                    last[x].insert ( str[1] );
                dfs1 ( y );
                set<char>::iterator it = last[y].begin();
                for ( ; it != last[y].end() ; it++ )
                    last[x].insert ( *it );
            }
            else 
                last[x].insert ( str[n] );
        }
    }
     
     
    void make_last ( )
    { 
        memset ( vis , 0 , sizeof ( vis ) );
        for ( int i = 0 ; i < VN_set.size() ; i++ )
            if ( vis[i] ) continue;
            else dfs1 ( i );
    #define DEBUG
    #ifdef DEBUG
        puts("--------------LASTVT集---------------------");
        for ( int i = 0 ; i < VN_set.size() ; i++ )
        { 
            printf ( "%s : " , VN_set[i].left.c_str() );
            set<char>::iterator it = last[i].begin();
            for ( ; it!= last[i].end() ; it++ )
                printf ( "%c " , *it );
            puts ("" );
        }
    #endif
    }
     
    void make_table ( )
    { 
        for ( int i = 0 ; i < MAX ; i++ )
            for ( int j = 0 ; j < MAX ; j++ )
                relation[i][j] = ' ';
        for ( int i = 0 ; i < VN_set.size() ; i++ )
            for ( int j = 0 ; j < VN_set[i].right.size() ; j++ )
            { 
                string& str = VN_set[i].right[j];
                for ( int k = 0 ; k < str.length()-1 ; k++ )
                { 
                    if ( !isupper(str[k]) && !isupper(str[k+1]) )
                        relation[str[k]][str[k+1]] = '=';
                    if ( !isupper(str[k]) && isupper(str[k+1]) )
                    { 
                        int x = VN_dic[str.substr(k+1,1)]-1;
                        set<char>::iterator it = first[x].begin();
                        for ( ; it != first[x].end() ; it++ )
                            relation[str[k]][*it] = '<';
                    }
                    if ( isupper(str[k]) && !isupper(str[k+1]) )
                    { 
                        int x = VN_dic[str.substr(k,1)]-1;
                        set<char>::iterator it = last[x].begin();
                        for ( ; it != last[x].end() ; it++ )
                            relation[*it][str[k+1]] = '>';
                    }
                    if ( k > str.length()-2 ) continue;
                    if ( !isupper(str[k]) && !isupper(str[k+2]) && isupper(str[k+1]) )
                        relation[str[k]][str[k+2]] = '=';
                }
            }
    #define DEBUG
    #ifdef DEBUG
        for ( int i = 0 ; i < VT.size()*5 ; i++ )
            printf ("-");
        printf ( "算符优先关系表" );
        for ( int i = 0 ; i < VT.size()*5 ; i++ )
            printf ( "-" );
        puts("");
        printf ( "|%8s|" , "" );
        for ( int i = 0 ; i < VT.size() ; i++ )
            printf ( "%5c%5s" , VT[i] , "|" );
        puts ("");
        for ( int i = 0 ; i < (VT.size()+1)*10 ; i++ )
            printf ("-");
        puts("");
        for ( int i = 0 ; i < VT.size() ; i++ )
        { 
            printf ( "|%4c%5s" , VT[i] , "|");
            for ( int j = 0 ; j < VT.size() ; j++ )
                printf ( "%5c%5s" , relation[VT[i]][VT[j]] , "|" );
            puts ("");
            for ( int i = 0 ; i < (VT.size()+1)*10 ; i++ )
                printf ("-");
            puts("");
        }
    #endif
    }
     
    int fa[MAX];
     
    int _find ( int x  )
    { 
        return x==fa[x]?x:fa[x] = _find ( fa[x] );
    }
     
    bool judge ( char x , char y )
    { 
        if ( _find ( x ) == _find ( y ) )
            return true;
        return false;
    }
     
    void _union ( char x , char y )
    { 
        x = _find(x);
        y = _find(y);
        fa[x] = y;
    }
     
    void print ( string s1 , string s2 , string s3 , string s4 , string s5 , string s6 )
    { 
        printf ( "%-14s|%-15s%-15s%-15s%-15s%-15s\n" , s1.c_str(), s2.c_str(), s3.c_str() ,s4.c_str(),s5.c_str() , s6.c_str() );
    }
     
    void init ( )
    { 
        for ( int i = 0 ; i < MAX ; i++ )
            fa[i] = i;
        for ( int i = 0 ; i < VN_set.size() ; i++ )
        { 
            string& left = VN_set[i].left;
            for ( int j = 0 ; j < VN_set[i].right.size() ; j++ )
            { 
                string& str = VN_set[i].right[j];
                if ( left.length() == 1 && str.length() == 1 )
                { 
                   // cout << left[0] << " " << str[0] << endl;
                    _union ( left[0] , str[0] );
                   // cout << _find(left[0]) << " " << _find ( str[0] ) << endl;
                }
            }
        }
        print("步骤","栈","优先关系","当前符号","剩余符号","动作");
    }
     
    string get_stk ( vector<char>& stk )
    { 
        string ret = "";
        for ( int i = 0 ; i < stk.size() ; i++ )
            ret += stk[i];
        return ret;
    }
     
    bool check ( const string& str1 , const string& str2 )
    { 
        if ( str1.length() != str2.length() ) 
            return false;
        for ( int i = 0 ; i < str1.length() ; i++ )
            if ( isupper(str1[i]) )
            { 
                if ( !judge(str1[i],str2[i])) return false;
            }
            else 
            { 
                if ( str1[i] != str2[i] ) return false;
            }
        return true;
    }
     
    string reduction ( string src )
    { 
        for ( int i = 0 ; i < VN_set.size() ; i++ )
            for ( int j = 0 ; j < VN_set[i].right.size() ; j++ )
                if ( check ( VN_set[i].right[j] , src ) )
                    return VN_set[i].left;
        return "";
    }
     
    void move_reduction ( string src )
    { 
        init ();
        //cout <<"flag : " << check ( "P+P" , "E+T" ) << endl;;
        vector<char> stk;
        int steps= 1;
        src += "#";
        stk.push_back ( '#' );
        for ( int i = 0 ; i < src.length() ; i++ )
        { 
            char top = stk[stk.size()-1];
            for ( int j = stk.size()-1 ; j >= 0 ; j-- )
                if ( isupper(stk[j]) ) continue;
                else   
                { 
                    top = stk[j];
                    break;
                }
            char ch = relation[top][src[i]];
            if ( ch == '<' || ch == '=' )
            { 
                string temp = "";
                if ( i == src.length() - 1 )
                    print ( temp+(char)(steps+48) , get_stk( stk ) , temp+ch , temp+src[i] , "" , "移进" );
                else
                    print ( temp+(char)(steps+48) , get_stk( stk ) , temp+ch , temp+src[i] , src.substr(i+1,src.length()-i-1) , "移进" );
                stk.push_back ( src[i] );  
            }
            else
            { 
                string temp ="";
                string str ="";
                int x = stk.size()-2;
                if ( i == src.length() )
                    print ( temp+(char)(steps+48) , get_stk(stk) , temp+ch , temp + src[i] , "" , "归约" );
                else 
                    print ( temp+(char)(steps+48) , get_stk(stk) , temp+ch , temp + src[i] , src.substr(i+1,src.length()-i-1) , "归约" );
                while ( true )
                { 
                    if ( stk.size() == 0 ) break;
                    if ( !isupper(stk[x] ) &&relation[stk[x]][top] == '<' ) 
                            break;
                    x--;
                }
                for ( int j = stk.size()-1 ; j > x; j-- )
                { 
                    str += stk[j];
                    stk.pop_back();
                }
                //cout << "YES : " << i <<" " << str << endl;
                str = reduction(str);
                //cout << "finish: " << i << " " << str << endl;
                for ( int j = 0 ; j < str.length() ; j++ )
                    stk.push_back ( str[j] );
                /*if ( i == src.length() ) print ( temp+(char)(steps+48) , get_stk(stk) , temp+ch , temp + src[i] , "" , "移进" ); else print ( temp+(char)(steps+48) , get_stk(stk) , temp+ch , temp + src[i] , src.substr(i+1,src.length()-i-1) , "移进" ); stk.push_back ( src[i] );*/
                i--;
            }  
            steps++;
        }
        //string temp ="";
        //cout << "result" << endl;
        //print ( temp+(char)(steps+48) , get_stk(stk) , "","","","");
    }
     
     
    int main ( )
    { 
        int n;
        char s[MAX];
        while ( ~scanf ( "%d" , &n ) )
        { 
            memset ( used , 0 , sizeof ( used ) );
            for ( int i = 0 ; i < n ; i++ )
            { 
                scanf ( "%s" , s );
                int len = strlen(s),j;
                for ( j = 0 ; j < len ; j++ )
                    if ( s[j] == '-' ) 
                        break;
                s[j] = 0;
                if ( !VN_dic[s] )
                { 
                    VN_set.push_back ( WF(s) );
                    VN_dic[s] = VN_set.size();
                }
                int x = VN_dic[s]-1;
                VN_set[x].insert ( s+j+2 );
                for ( int k = 0 ; k < j; k++ )
                    if ( !isupper(s[k] ) )
                    { 
                        if ( used[s[k]] ) continue;
                        used[s[k]] = 1;
                        VT.push_back ( s[k] );
                    }
                for ( int k = j+2 ; k < len; k++ )
                    if ( !isupper(s[k] ) )
                    { 
                        if ( used[s[k]] ) continue;
                        VT.push_back ( s[k] );
                        used[s[k]] = VT.size();
                    }   
            }
    #define DEBUG
    #ifdef DEBUG
            puts ("************VT集*******************");
            for ( int i = 0 ; i < VT.size() ; i++ )
                printf ( "%c " , VT[i] );
            puts ("");
            puts("*************产生式*****************");
            for ( int i = 0 ; i < VN_set.size() ; i++ )
                VN_set[i].print();
            puts("************************************");
    #endif
            make_first();
            make_last();
            make_table();
            move_reduction("i+i");
        }
    }

##### 七、实验小结 #####

1.  本次实验通过对文法进行处理，获取FIRSTVT()集合、LASTVT()集合和算符优先关系表，从而进一步对语句进行分析判断。通过本次实验我对语义分析有了更进一步的了解。
2.  实验过程中遇到的问题有：  
    ①FIRSTVT()和LASTVT()这两个集合的构建。  
    解决方式：对书本中两个集合进一步优先，写出伪代码，进行实现。  
    ②如何利用FIRSTVT（）和LASTVT（）集合构建算符优先关系表。  
    解决方式：多次尝试可得如下伪代码，从而实现该关系表的代码化。

FOR 每个产生式 P->X1 X2 ……Xn   
    DO  FOR  i:=1  TO   n-1    DO      
          IF  X[i]和X[i+1]均为终结符
            THEN   置 X[i]=X[i+1]        
          IF  X[i]和X[i+2]均为终结符,X[i+1]为非终结符,i≤n-2,       
            THEN   置 X[i]=X[i+2]                
          IF  X[i]为终结符, 但X[i+1]为非终结符                                    
          THEN  FOR  FIRSTVT(X[i+1])中的每个a                                    
              DO  置 X[i]<a                
          IF  Xi为非终结符, 但X i+1 为终结符                                  
              THEN  FOR  LASTVT(X i )中的每个a
                  DO   置 a>X[i+1]

1.  实验的输入输出格式可进一步调整优化，代码的注释有待增加，可读性有进一步提升空间。

参考文章：【1】[编译原理(八) 算符优先分析法(分析过程的算法和C++实现)][_C]  
     【2】[编译原理——算符优先分析文法（附源代码）][Link 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTY0NTU1_size_16_color_FFFFFF_t_70]: /images/20211109/8063f2c4df8648d195234b2736104644.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTY0NTU1_size_16_color_FFFFFF_t_70 1]: /images/20211109/f4862f400b724315a5616f66dd4a4ee8.png
[_C]: https://blog.csdn.net/github_36601823/article/details/74090399
[Link 1]: https://www.cnblogs.com/zyrblog/p/6888798.html