递归下降分析程序的设计和实现

递归下降分析程序的设计和实现

一、实验的目的和要求

1、了解语法分析的主要任务。
2、实现基本的递归下降分析器，能够分析任意的符号串是否为该文法所定义的合法算术表达式。

二、实验环境

Windows7 + Dev-C++

三、实验准备

先将递归下降分析程序的生成认真的学习一遍，理解递归下降分析程序的构成过程。

已知文法G[S]:
		S → aB | bD
		B → bC
		C → aS | bD | ε
		D → aB | bD | ε

1. 经观察此文法不含左公因式,也不含左递归,求出此文法的FIRST、FOLLOW以及SELECT集。

2. 因为S、B、C、D的SELECT集有交集且为空,所以此文法为LL(1)文法。

3. 测试用例如下(文法推导所得,推导过程略)：

   ab
   abb
   abaab
   ababbbbbbbbb
   bbbbbbbbbbbbbbbbbbbbbbbbbbb
   baaaaabbbb(错误用例）
   a##b#(错误用例）
   abcdefg(错误用例）
   ABCDEFG(错误用例）
   

四、实验内容及步骤

1. 用递归下降分析程序测试自己写的文法

#include<stdio.h>

// 函数声明
void S(void);
void B(void);
void C(void);
void D(void);
// 定义一个长度为100的字符数组
char s[100];
// 用来作数组索引,当每次匹配成功存入数据时index自增1
int i;
//  用来标记语句是否正确
int SIGN;

int main()
{
    printf("please input a yuju ends with #n");
    // 一个死循环
    while( 1 )
    {
        SIGN = 0;//语句是否正确用SIGN
        i=0;
        
        // 类似Java中的Scanner,读取输入的字符串
        scanf("%s",&s[0]);
        
        // 当输入的第一个字符为#时,程序直接结束
        if( s[0] == '#')
            return 0;
             
        S();
        // 如果最后的字符以#结束则输出下面
        if(s[i] == '#' && SIGN == 0){
            printf("This is a right yuju!n");
        }else{
            printf("This a wrong yujun");
        }
        printf("please input a yuju ends with #n");
    }
    return 1;
}

void S()
{
    if(SIGN==0)
    {
        // 当输入的字符串中首字母为a时
        if(s[i]=='a'){
            ++i;    // 自增操作
            B();
        }else if(s[i]=='b'){
            ++i;
            D();
        }else{
            SIGN=1;
        }
    }
}

void B()
{
    if(SIGN==0){
       if(s[i]=='b'){
            ++i;
            C();
        }else if(s[i] == '#'){
            SIGN=1;
        }
    }
}

void C()
{
    if(SIGN==0){
        if(s[i]=='a'){
            ++i;
            S();
        }else if(s[i]=='b'){
            ++i;
            D();
        }else if(s[i]!='#'){
            SIGN=1;
        }
    }
}

void D()
{
    if(SIGN==0){
        if(s[i]=='a'){
            ++i;
            B();
        }else if(s[i]=='b'){
            ++i;
            D();
        }else if(s[i]!='#'){
            SIGN=1;
        }
    }
}

注: 此代码正好100行，不过可以看出代码质量很差(冗余代码很多),每个函数中的功能都是一样的，应该抽取一下，代码应该可以简洁很多。

2. 测试用例测试如下

五、实验小结

1. 遇到的主要问题
答：
刚开始测试测试用例时，根据文法推导的句子在程序中一直报错，首先我确定自己推导没有问题，又看了程序代码好像也没有问题，找了好久没有找到，最后使用Xcode(Mac平台下由apple公司维护用来开发iPhone程序和Mac程序的一款集成开发环境)打断点通过单步调试把问题找了出来，因为我把s[i] = ‘p’ 写成了s[i] = ‘P’ 将小写字母写成了大写。这就表现出调试程序的重要性，通过调试可以看计算机如何一步步来执行程序的，对程序有更好的理解。（附上一张调试图）

这是S函数，当我从控制台录入pba时，第一个字符p和s[i]相同，但是当程序执行直接从39行调到了45行，没有执行if（s[i] == ‘P’）语句，我才找到上面所说的错误！

3. 得到的经验
答：
①：C语言函数声明，这和Java以及其他编程语言不相同，当在main()函数中调用其他函数时，编译器会在main()函数上面找这些函数，如果函数没有声明就会编译报错（找不到）,若将函数写在main()函数上，就不会报错。
②：首先更加清晰的理解了语法分析的主要任务，它是在词法分析的基础上将单词组合起来,组成一些语句，比如说在Java中，public static void main(String[]args);方法中，如果void写在public前面编译器就会报错，那是因为编译器已经做好了语法分析的工作，说白了对源代码在结构是否正确这就是语法分析的任务。
③：理解了递归下降分析法，它是一种自顶向下的分析，根据文法来构造C函数，遇到终结符时通过和自己在屏幕中录入的数据作比较，若相同修改数组索引，这个终结符后面若是一个非终结符则调用这个非终结符的函数。一层一层的向下分析，有时会在函数体中调用自己，这就形成了递归。

最后

以上就是健康网络为你收集整理的递归下降分析程序的设计和实现的全部内容，希望文章能够帮你解决递归下降分析程序的设计和实现所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。