递归下降分析程序的设计和实现
一、实验的目的和要求
1、了解语法分析的主要任务。
2、实现基本的递归下降分析器，能够分析任意的符号串是否为该文法所定义的合法算术表达式。
二、实验环境
Windows7 + Dev-C++
三、实验准备
先将递归下降分析程序的生成认真的学习一遍，理解递归下降分析程序的构成过程。已知文法G[S]:S → aB | bDB → bCC → aS | bD | εD → aB | bD | ε
- 经观察此文法不含左公因式,也不含左递归,求出此文法的FIRST、FOLLOW以及SELECT集。
| 产生式 | FIRST | FOLLOW | SELECT |
|---|---|---|---|
| S → aB | {a} | {#} | {a} |
| S → bD | {b} | {b} | |
| B → bC | {b} | {#} | {b} |
| C → aS | {a} | {#} | {a} |
| C → bD | {b} | {#} | {b} |
| C → ε | {ε} | {#} | |
| D → aB | {a} | {#} | {a} |
| D → bD | {b} | {b} | |
| D → ε | {ε} | {#} |
-
因为S、B、C、D的SELECT集有交集且为空,所以此文法为LL(1)文法。
-
测试用例如下(文法推导所得,推导过程略)：
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;//语句是否正确用SIGNi=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 yuju\n");}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函数，遇到终结符时通过和自己在屏幕中录入的数据作比较，若相同修改数组索引，这个终结符后面若是一个非终结符则调用这个非终结符的函数。一层一层的向下分析，有时会在函数体中调用自己，这就形成了递归。
