博客

如果要进行递归下降分析，肯定少不了FIRST集，FOLLOW集，SELECT集和预测分析表。并根据预测分析表或者SELECT集判断该文法是不是LL（1）文法。


怎么求FIRST集？

下面的代码是第一版，不能输出语法分析树。

#include <stdio.h>
#define ERROR -1                //程序不能正确运行的返回值
char sym,a[50];                 //sym临时存放一个字符，数组a存放输入的字符串
int ip=0;                       //字符数组下标
int A();                        //函数声明
int B();
int C();
int X();
int Y();

void getNextSym()               //取字符串中的下一个字符
{
    sym=a[++ip];
    printf("  sym=%c\n",sym);   //输出当前字符
}

//================================================
void main()                     //主函数
{
	int ret;                    //存放其他函数的返回值
	while(1){
        //下面这句输出语句对用户输入的字符串作出约束
        printf("\ninput length < 50,ending with'#'; '^#' to return!\n");
        ip=0;                   //字符数组下标
        do{
            scanf("%c",&sym);//输出的最后一个字符必须是#
            a[ip++]=sym;        //将输入的字符串以数组的形式存放
        }while(sym!='#');       //#作为结束的标志

        if(a[0]=='^' && a[1]=='#')
            return;

        printf("......begin......\n");//分析开始
        ip=-1;                        //重新设置字符数组下标
        getNextSym();
        ret=A();                      //只有函数A()返回值为0，才说明分析过程正确
        if (ret != ERROR && sym=='#') //当所有函数正确执行并且分析到最后一个字符
            printf("*****ACCEPT!!!*****\n");
        else
            printf("-----!ERROR!------\n");
        getchar();
	}
}


//================================================
int A()
{
    if(sym == '['){                 //只有当输入的第一个字符为[，才能继续向下分析
        printf("A->[B\n");          //输出文法对应的产生式
        getNextSym();               //取下一个字符
        if(B()==ERROR)              //如果接下来的字符在文法中没有匹配的产生式
            return ERROR;           //结束分析过程
    }
    else                            //如果第一个字符就不是[，结束分析过程
        return ERROR;
    return 0;                       //分析成功，正常结束
}

int B()
{
    if(sym == 'a'||sym == 'b')      //当字符是a或b时，才继续向下分析
    {
        printf("B->X]C\n");         //输出文法对应的产生式
        if(X()==ERROR)              //如果接下来的字符在文法中没有匹配的产生式
            return ERROR;           //结束分析过程
        if(sym != ']')              //分析文法，此时的字符只有是]才能够继续分析
            return ERROR;
        getNextSym();
        if(C()==ERROR)              //如果接下来的字符在文法中没有匹配的产生式
            return ERROR;           //结束分析过程
    }
    else                            //如果当前字符不是a或b，结束分析过程
        return ERROR;
    return 0;                       //分析成功，正常结束
}

int C()                             //以下的程序都可以参考函数A和函数B的注释
{
    if(sym == 'a')
    {
        printf("C->aC\n");
        getNextSym();
        if(C()==ERROR)
            return ERROR;
    }
    else if(sym == '#'){            //如果当前字符是#，说明字符串已经全部分析完了
        printf("C-> \n");
    }
    else
        return ERROR;
    return 0;
}

int X()
{
    if(sym == 'a')
    {
        printf("X->aY\n");
        getNextSym();
        if(Y()==ERROR)
            return ERROR;
    }
    else if(sym == 'b')
    {
        printf("X->bY\n");
        getNextSym();
        if(Y()==ERROR)
            return ERROR;
    }
    else
        return ERROR;
    return 0;

}

int Y()
{
    if(sym == 'a')
    {
        printf("Y->aY\n");
        getNextSym();
        if(Y()==ERROR)
            return ERROR;
    }
    else if(sym == 'b')
    {
        printf("Y->bY\n");
        getNextSym();
        if(Y()==ERROR)
            return ERROR;
    }
    else if(sym == ']'){//这个地方比较关键，如果这个条件成立，因为此时已经把[取出来了
                        //所以返回到函数B就不用取这个字符了，直接到下一个字符
        printf("Y-> \n");
    }
    else
        return ERROR;
    return 0;
}

下面的代码是第二版，输出语法分析树。

#include <stdio.h>
#include <string.h>

#define ERROR -1                //程序不能正确运行的返回值
char sym,a[50];//sym临时存放一个字符，数组a存放输入的字符串
int ip=0;                       //字符数组下标
int A();                        //函数声明
int B();
int C();
int X();
int Y();
int arr[100][100];//这个数组用于辅助打印语法分析树
int row;//arr数组的行
int col;//arr数组的列
int first_C;//如果是第一次到C函数，值是1，之后为0；

void getNextSym()               //取字符串中的下一个字符
{
    sym=a[++ip];
    printf("  sym=%c\n",sym);   //输出当前字符
}
//================================================
int main()                      //主函数
{
	int ret;                    //存放其他函数的返回值
	while(1){
        //下面这句输出语句对用户输入的字符串作出约束
        int i=0;
        int j=0;
        memset(arr,' ',sizeof(arr));
        //每次进入while循环就初始化数组全为空字符
        row=0;
        col=0;
        first_C=1;
        //因为下面的二维数组中的元素无论在什么串里，只要串是正确的
        //在打印的时候都是一样的，而错误的串又没必要输出语法分析树
        //所以可以先存放到数组里
        arr[0][3]='A';
        arr[1][2]='/';          //表示父节点和子节点的从属关系
        arr[1][4]='\\';         //注意'\'是转义字符
        arr[2][1]='[';
        arr[2][4]='B';
        arr[3][3]='/';
        arr[3][4]='|';
        arr[3][5]='\\';
        arr[4][2]='X';
        arr[4][4]=']';
        arr[4][6]='C';
        arr[5][1]='/';
        arr[5][3]='\\';
        //arr[5][7]='\\';
        row=6;//在定义了上面数组元素后，数组的起始位置
        col=0;

        printf("\ninput length < 50,ending with'#'; '^#' to return!\n");
        ip=0;                         //字符数组下标
        do{
            scanf("%c",&sym);
            a[ip++]=sym;              //将输入的字符串以数组的形式存放
        }while(sym!='#');             //#作为结束的标志

        if(a[0]=='^' && a[1]=='#')
            return 0;

        printf("......begin......\n");//分析开始
        ip=-1;                        //重新设置字符数组下标
        getNextSym();
        ret=A();                      //只有函数A()返回值为0，才说明分析过程正确
        if (ret != ERROR && sym=='#') //当所有函数正确执行并且分析到最后一个字符
        {
            printf("*****ACCEPT!!!*****\n");
            for(i=0;i<30;i++)              //打印语法分析树
            {
                for(j=0;j<50;j++)
                {
                    printf("%c",arr[i][j]);
                }
                printf("\n");
            }
        }
        else
            printf("-----!ERROR!------\n");
        getchar();
	}
	return 0;
}
//================================================
int A()
{
    if(sym == '['){             //只有当输入的第一个字符为[，才能继续向下分析
        printf("A->[B\n");      //输出文法对应的产生式
        getNextSym();           //取下一个字符
        if(B()==ERROR)          //如果接下来的字符在文法中没有匹配的产生式
            return ERROR;       //结束分析过程
    }
    else                        //如果第一个字符就不是[，结束分析过程
        return ERROR;
    return 0;                   //分析成功，正常结束
}

int B()
{
    if(sym == 'a'||sym == 'b')  //当字符是a或b时，才继续向下分析
    {
        printf("B->X]C\n");     //输出文法对应的产生式
        if(X()==ERROR)          //如果接下来的字符在文法中没有匹配的产生式
            return ERROR;       //结束分析过程
        if(sym != ']')          //分析文法，此时的字符只有是]才能够继续分析
            return ERROR;
        getNextSym();
        if(C()==ERROR)          //如果接下来的字符在文法中没有匹配的产生式
            return ERROR;       //结束分析过程
    }
    else                        //如果当前字符不是a或b，结束分析过程
        return ERROR;
    return 0;                   //分析成功，正常结束
}

int C()                         //以下的程序都可以参考函数A和函数B的注释
{
    if(first_C==1)              //如果是第一次进入C函数，需要重新定位
    {
        row=5;
        col=7;
    }
    if(sym == 'a')
    {
        first_C=0;              //之后再进入C函数就不是第一次了，所以修改标记
        arr[row][col]='\\';     //接下来的四句代码就是画树和重新定位
        arr[row+1][col+1]=sym;
        row+=2;
        col+=2;
        printf("C->aC\n");
        getNextSym();
        if(C()==ERROR)
            return ERROR;
    }
    else if(sym == '#'){        //如果当前字符是#，说明字符串已经全部分析完了
        arr[row][col]='\\';
        arr[row+1][col+1]='ε';  //空
        printf("C-> \n");
    }
    else
        return ERROR;
    return 0;
}

int X()
{
    if(sym == 'a')
    {
        arr[row][col]=sym;
        arr[row][col+3]='Y';
        row+=1;
        col+=3;
        printf("X->aY\n");
        getNextSym();
        if(Y()==ERROR)
            return ERROR;
    }
    else if(sym == 'b')
{
arr[row][col]=sym;
arr[row][col+3]='Y';
row+=1;
col+=3;
        printf("X->bY\n");
        getNextSym();
        if(Y()==ERROR)
            return ERROR;
    }
    else
        return ERROR;
    return 0;

}

int Y()
{
    if(sym == 'a')
    {
        arr[row][col-1]='/';
        arr[row][col+1]='\\';
        row+=1;
        col-=2;
        arr[row][col]=sym;
        arr[row][col+3]='Y';
        row+=1;
        col+=3;
        printf("Y->aY\n");
        getNextSym();
        if(Y()==ERROR)
            return ERROR;
    }
    else if(sym == 'b')
    {
        arr[row][col-1]='/';
        arr[row][col+1]='\\';
        row+=1;
        col-=2;
        arr[row][col]=sym;
        arr[row][col+3]='Y';
        row+=1;
        col+=3;
        printf("Y->bY\n");
        getNextSym();
        if(Y()==ERROR)
            return ERROR;
    }
    else if(sym == ']'){//这个地方比较关键，如果这个条件成立，因为此时已经把[取出来了
                        //所以返回到函数B就不用取这个字符了，直接到下一个字符
        arr[row+1][col]='|';
        arr[row+2][col]='ε';
        printf("Y-> \n");
    }
    else
        return ERROR;
    return 0;
}

对于如何实现输出语法树，因为我的方法有局限性，这里就不再详谈了。

运行结果如下：（图片中的？实际是ε）