编译原理实验4《递归下降分析法设计与实现》

野性酷女 2021-11-11 06:46 455阅读 0赞

#### 实验4《递归下降分析法设计与实现》 ####

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

根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。

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

程序输入/输出示例（以下仅供参考）：

对下列文法，用递归下降分析法对任意输入的符号串进行分析：

（1）E-TG
    （2）G-+TG|—TG
    （3）G-ε
    （4）T-FS
    （5）S-*FS|/FS
    （6）S-ε
    （7）F-(E)
    （8）F-i

输出的格式如下：  
  (1)递归下降分析程序，编制人：姓名，学号，班级  
  (2)输入一以\#结束的符号串(包括+—*/（）i\#)：在此位置输入符号串例如：i+i*i\#  
  (3)输出结果：i+i*i\#为合法符号串  
备注：输入一符号串如i+i*\#,要求输出为“非法的符号串”。  
  注意：  
  1.表达式中允许使用运算符（±\*/）、分割符（括号）、字符I，结束符\#；  
  2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）。

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

1．实验采用C++程序语言进行设计，利用txt文本对源程序进行存储；  
  2．实验开发工具为Visual Studio Code。

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

1．对递归下降分析算法进行详细分析；  
  2．对文法中的每一个非终结符计算它们的Fisrt集，Follow集和Select集。  
  3．main函数编写，每遇到一个终结符，则需要判断所输入字符是否与之匹配，若匹配则读取下一个，若不匹配，则进行出错处理。

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

1.  实验测试所用语句如下所示：  
    ![在这里插入图片描述][20190804163255107.png]
2.  实验测试结果：  
    测试结果符合预期结果，程序能够利用指定的文法对指定的语句进行正误判断。实验截图如下所示：  
    ![在这里插入图片描述][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]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTY0NTU1_size_16_color_FFFFFF_t_70 2]

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

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

/************************** Compiler Principle test4 递归下降分析法设计与实现 author:zz vs code 2019.05.08 ***************************/
    /* 定义文法： （1）E→TG （2）G→ATG （3）G→ε （4）T→FH （5）H→MFH （6）H→ε （7）F→i （8）A→+ （9）A→- （10）M→* （11）M→/ */
    #include <iostream>
    #include <fstream>
    #include <dos.h>
    #include <cstring>
    #include <stdlib.h>
    using namespace std;
    char a[100], b[100], d[500], e[10];
    char ch;
    int n1,i1=0,flag=1,n=5;
     
    int E1();
    int E();
    int G();
    int T();
    int H();
    int F();
    int A();
    int M();
    void input();
    void input1();
    void output();
     
    //递归分析
    int main()                      
    { 
        int p;
        char x;
        d[0]='E';
        d[1]='=';
        d[2]=' ';
        d[3]='T';
        d[4]='G';
        d[5]='#';
        //从文件中读入除换行符之外的字符
        ifstream infile("test4.txt",ios::in);
        if(!infile)
        { 
            cerr<<"open error!"<<endl;
            exit(1);
        }
        char c='c',f[50]= { ""};
        int i=0,k=0,l=0;
        while(infile.peek()!=EOF)
        { 
            infile.get(c);
            if(c!='\n')
            { 
                f[i]=c;
                i++;
            }
        }
        //给操作数组a赋初值，依次进行操作
        do
        { 
            a[k]=f[l];
            if(f[l]=='#')
            { 
                cout<<"从文件读入字符串(长度<50,以#号结束）\n";
                for(int j=0; a[j]!='\0'; j++)
                    cout << a[j];
                n1=i;
                ch=b[0]=a[0];
                cout<<"\n文法\t分析串\t\t分析字符\t剩余串\n";
                E1();
                if (ch=='#')
                { 
                    cout<<"accept"<<endl;
                    p=0;
                    x=d[p];
                    while(x!='#')
                    { 
                        cout<<x;
                        p=p+1;
                        x=d[p];     //输出推导式
                    }
                }
                else
                { 
                    cout<<"error"<<endl;
                    cout<<"回车返回"<<endl;
                    return (0);
                }
                cout<<endl;
                cout<<"继续>>>>\n"<<endl;
                memset(a,'\0',sizeof(a));
                memset(b,'\0',sizeof(b));
                memset(e,'\0',sizeof(e));
                i1=0,flag=1,n=5;
                k=-1;
            }
            k++;
            l++;
        }
        while(f[l]!='\0');
        infile.close();
        return 0;
    }
     
    int E1()
    { 
        int f,t;
        cout<<"E->TG\t";
        flag=1;
        input();
        input1();
        f=T();
        if (f==0)
            return(0);
        t=G();
        if (t==0)
            return(0);
        else
            return(1);
    }
     
    int E()
    { 
        int f,t;
        cout<<"E->TG\t";
        e[0]='E';
        e[1]='=';
        e[2]=' ';
        e[3]='T';
        e[4]='G';
        e[5]='#';
        output();
        flag=1;
        input();
        input1();
        f=T();
        if (f==0)
            return(0);
        t=G();
        if (t==0)
            return(0);
        else
            return(1);
    }
     
    int G()
    { 
        int f,t,g;
        if(ch=='+'||ch=='-')
        { 
            cout<<"G→ATG\t";
            e[0]='G';
            e[1]='=';
            e[2]=' ';
            e[3]='A';
            e[4]='T';
            e[5]='G';
            e[6]='#';
            output();
            flag=1;
            input();
            input1();
            f=A();
            if (f==1)
            { 
                t=T();
                if(t==0)
                { 
                    cout<<"error"<<endl;
                    return (0);
                }
                g=G();
                if (g==0)
                    return(0);
                return(1);
            }
        }
        cout<<"G->^\t";
        e[0]='G';
        e[1]='=';
        e[2]=' ';
        e[3]='^';
        e[4]='#';
        output();
        flag=1;
        input();
        input1();
        return(1);
    }
     
    int T()
    { 
        int f,t;
        printf("T->FH\t");
        e[0]='T';
        e[1]='=';
        e[2]=' ';
        e[3]='F';
        e[4]='H';
        e[5]='#';
        output();
        flag=1;
        input();
        input1();
        f=F();
        if (f==0) return(0);
        t=H();
        if (t==0) return(0);
        else return(1);
    }
    
    int H()
    { 
        int f,t,g;
        if(ch=='*'||ch=='/')
        { 
            cout<<"H->MFH\t";
            e[0]='H';
            e[1]='=';
            e[2]=' ';
            e[3]='M';
            e[4]='F';
            e[5]='H';
            e[6]='#';
            output();
            flag=1;
            input();
            input1();
            f=M();
            if (f==1)
            { 
                t=F();
                if(t==0)
                { 
                    cout<<"error"<<endl;
                    return (0);
                }
                g=H();
                if (g==0)
                    return(0);
                return(1);
            }
        }
     
        cout<<"H->^\t";
        e[0]='H';
        e[1]='=';
        e[2]=' ';
        e[3]='^';
        e[4]='#';
        output();
        flag=1;
        a[i1]=ch;
        input();
        input1();
        return(1);
    }
     
    int F()
    { 
        if(ch=='i')
        { 
            b[i1]=ch;
            cout<<"F->i\t";
            e[0]='F';
            e[1]='=';
            e[2]=' ';
            e[3]='i';
            e[4]='#';
            output();
            flag=0;
            input();
            input1();
            ch=a[++i1];
        }
        else
        { 
            cout<<"error\n";
            return(0);
        }
        return(1);
    }
     
    int A()
    { 
        if(ch=='+')
        { 
            b[i1]=ch;
            cout<<"A->+\t";
            e[0]='A';
            e[1]='=';
            e[2]=' ';
            e[3]='+';
            e[4]='#';
            output();
            flag=0;
            input();
            input1();
            ch=a[++i1];
        }
        else if(ch=='-')
        { 
            b[i1]=ch;
            cout<<"A->-\t";
            e[0]='A';
            e[1]='=';
            e[2]=' ';
            e[3]='-';
            e[4]='#';
            output();
            flag=0;
            input();
            input1();
            ch=a[++i1];
        }
        else
        { 
            cout<<"error\n";
            return(0);
        }
        return(1);
    }
     
    int M()
    { 
        if(ch=='*')
        { 
            b[i1]=ch;
            cout<<"M->*\t";
            e[0]='M';
            e[1]='=';
            e[2]=' ';
            e[3]='*';
            e[4]='#';
            output();
            flag=0;
            input();
            input1();
            ch=a[++i1];
        }
        else if(ch=='/')
        { 
            b[i1]=ch;
            cout<<"M->/\t";
            e[0]='M';
            e[1]='=';
            e[2]=' ';
            e[3]='/';
            e[4]='#';
            output();
            flag=0;
            input();
            input1();
            ch=a[++i1];
        }
        else
        { 
            cout<<"error\n";
            return(0);
        }
        return(1);
    }
     
    void input()
    { 
        for (int j=0; j<=i1-flag; j++)
            cout<<b[j];     //输出分析串
        cout<<"\t\t";
        cout<<ch<<"\t\t";   //输出分析字符
    }
     
    void input1()
    { 
        for (int j=i1+1-flag; j<n1; j++)
            cout<<a[j];     //输出剩余字符
        cout<<endl;
    }
     
    //推导式计算
    void output()                               
    { 
        int m,k,j,q;
        int i=0;
        m=0;
        k=0;
        q=0;
        i=n;
        d[n]='=';
        d[n+1]=' ';
        d[n+2]='#';
        n=n+2;
        i=n;
        i=i-2;
        while(d[i]!=' '&&i!=0)
            i=i-1;
        i=i+1;
        while(d[i]!=e[0])
            i=i+1;
        q=i;
        m=q;
        k=q;
        while(d[m]!=' ')
            m=m-1;
        m=m+1;
        while(m!=q)
        { 
            d[n]=d[m];
            m=m+1;
            n=n+1;
        }
        d[n]='#';
        for(j=3; e[j]!='#'; j++)
        { 
            d[n]=e[j];
            n=n+1;
        }
        k=k+1;
        while(d[k]!='=')
        { 
            d[n]=d[k];
            n=n+1;
            k=k+1;
        }
        d[n]='#';
    }

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

1．本次实验主要是利用递归下降分析算法对指定文法的语句进行分析，通过编程实现后加深了对递归下降分析法的理解。  
  2．实验过程中遇到的问题有：  
   ①递归下降分析法的代码实现逻辑问题。  
   解决方式：查阅书本资料与网络资源。  
   ②如何判断是否满足递归下降法分析条件。  
   解决方式：不满足用消除左递归和提取公因子等文法等价变换操作对文法进行变换，使其满足递归下降法的要求。  
  3．实验代码的可读性有待进一步提高。实验的算法的逻辑可以进一步简化。

参考文章：【1】[编译原理 实验3 递归下降语法分析程序设计][_3]  
     【2】[编译原理—递归下降分析][Link 1]

[20190804163255107.png]: /images/20211109/670c84f9c83d45da81db67f9d7a32d8a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTY0NTU1_size_16_color_FFFFFF_t_70]: /images/20211109/b59170f5fcb849f881cc74d3bb4376af.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTY0NTU1_size_16_color_FFFFFF_t_70 1]: /images/20211109/dfbfc66f85284639bdfc03637133fbbe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTY0NTU1_size_16_color_FFFFFF_t_70 2]: /images/20211109/6d39bcd24ab0455ca438e29c5df74b41.png
[_3]: https://blog.csdn.net/niu91/article/details/9155509
[Link 1]: https://blog.csdn.net/LY_624/article/details/51660761