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

一、实验的目的和要求

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

二、实验环境

Windows7 + Dev-C++

三、实验准备

先将递归下降分析程序的生成认真的学习一遍，理解递归下降分析程序的构成过程。 已知文法G[S]: S → aB | bD B → bC C → 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(错误用例） ab#(错误用例） 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 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函数，遇到终结符时通过和自己在屏幕中录入的数据作比较，若相同修改数组索引，这个终结符后面若是一个非终结符则调用这个非终结符的函数。一层一层的向下分析，有时会在函数体中调用自己，这就形成了递归。

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/232674.html原文链接：https://javaforall.net

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