预测分析法

爱被打了一巴掌 2022-01-28 08:21 262阅读 0赞

设计要求：对于任意输入的一个LL(1)文法，构造其预测分析表，并对指定输入串分析其是否为该文法的句子。

思路：首先实现集合FIRST(X)构造算法和集合FOLLOW(A)构造算法，再根据FIRST和FOLLOW集合构造出预测分析表，并对指定的句子打印出分析栈的分析过程，判断是否为该文法的句子。

**（1）求FIRST集的算法思想**

如果产生式右部第一个字符为终结符，则将其计入左部first集

如果产生式右部第一个字符为非终结符

\->求该非终结符的first集

\->将该非终结符的非$first集计入左部的first集

\->若存在$，则将指向产生式的指针右移

\->若不存在$，则停止遍历该产生式，进入下一个产生式

\->若已经到达产生式的最右部的非终结符，则将$加入左部的first集

处理数组中重复的first集中的终结符

**（2）求FOLLOW集的算法思想**

对于文法G中每个非终结符A构造FOLLOW(A)的办法是,连续使用下面的规则,直到每个FOLLOW不在增大为止.  
(1) 对于文法的开始符号S,置\#于FOLLOW(S)中;  
(2) 若A->aBb是一个产生式,则把FIRST(b)\\\{ε\}加至FOLLOW(B)中;  
(3) 若A->aB是一个产生式,或A->aBb是一个产生式而b=>ε(即ε∈FIRST(b))则把FOLLOW(A)加至FOLLOW(B)中

**（3）生成预测分析表的算法思想**

构造分析表M的算法是：  
(1) 对文法G的每个产生式A->a执行第二步和第三步;  
(2) 对每个终结符a∈FIRST(a),把A->a加至M\[A,a\]中;  
(3) 若ε∈FIRST(a),则把任何b∈FOLLOW(A)把A->a加至M\[A,b\]中;  
(4) 把所有无定义的M\[A,a\]标上出错标志.

**（4）对符号串的分析过程**

预测分析程序的总控程序在任何时候都是按STACK栈顶符号X和当前的输入符号行事的,对于任何(X,a),总控程序  
每次都执行下述三种可能的动作之一;  
(1) 若X=a=”\#”,则宣布分析成功,停止分析过程.  
(2) 若X=a≠”\#”,则把X从STACK栈顶逐出,让a指向下一个输入符号.  
(3) 若X是一个非终结符,则查看分析表M,若M\[A,a\]中存放着关于X的一个产生式,那么,首先把X逐出STACK栈顶,然后  
把产生式的右部符号串按反序一一推进STACK栈(若右部符号为ε,则意味着不推什么东西进栈).在把产生式的右部  
符号推进栈的同时应做这个产生式相应得语义动作,若M\[A,a\]中存放着”出错标志”,则调用出错诊察程序ERROR.

语法：

S->a|^|(T)

T->SG

G->,SG|$

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<dos.h>
    
    char analyse[10];	//分析栈
    char remain[10];	//剩余串
    char vt[10] = { 'a','^','(',')',',','$','#'};//终结符
    char vn[10] = { 'S','T','G' };				//非终结符
    typedef struct shiZi				//产生式
    {
        char begin;						//左边字符
        char array[5];					//右边字符串
        int length;						//右边字符个数
    } shiZi;
    shiZi e, e1, e2, e3, e4, e5; //6个产生式
    shiZi table[10][10];	//定义预测分析表
    
    void printStack();	//输出分析栈
    void printRemain();	//输出剩余串
    
    int j = 0, b = 0, top = 0;
    int l;				//l为输入串长度
    
    int main()
    {
        int m, n, k = 0, flag = 0, finish = 0;
        char ch, x;
        shiZi now;   //目前使用的产生式
        e.begin = 'S';
        strcpy(e.array, "a");
        e.length = 1;
    
        e1.begin = 'S';
        strcpy(e1.array, "^");
        e1.length = 1;
    
        e2.begin = 'S';
        strcpy(e2.array, "(T)");
        e2.length = 3;
    
        e3.begin = 'T';
        strcpy(e3.array, "SG");
        e3.length = 2;
    
        e4.begin = 'G';
        strcpy(e4.array, ",SG");
        e4.length = 3;
    
        e5.begin = 'G';
        e5.array[0] = '$';
        e5.length = 1;
    
    
        //初始化分析表
        for (m = 0; m <= 2; m++)
            for (n = 0; n <= 5; n++)
            {
                table[m][n].begin = 'n';
            }
    
    
        //手动填写分析表
        table[0][0] = e;table[0][1] = e1;table[0][2] = e2;
        table[1][0] = e3;table[1][1] = e3;table[1][2] = e3;
        table[2][3] = e5;table[2][4] = e4;
        
    
    
        printf("文法G[S]\n");
        printf("S->a|^|(T)\n");
        printf("T->SG\n");
        printf("G->,SG|$\n");
        printf("请输入要分析的字符串(以'#'结尾):");
        //读入字符串
        do
        {
            scanf("%c", &ch);
            if ((ch != 'a') && (ch != ',') && (ch!='(')&&(ch!=')')&& (ch != '#'))
            {
                printf("输入串中有非法字符\n");
                exit(1);
            }
            remain[j] = ch;
            j++;	//字符串长度
        }
        while (ch != '#');
    
        l = j;
        ch = remain[0];	//当前字符
        printf("%c",ch);
        analyse[top] = '#';
        analyse[++top] = 'S';	//文法开始符号'S'进栈
        printf("步骤\t\t分析栈\t\t剩余字符\t\t所用产生式\n");
    
        do
        {
            x = analyse[top--];//当前栈顶字符
            printf("%d", k++);
            printf("\t\t");
    
            for (j = 0; j <= 8; j++)
                if (x == vt[j])		//如果是终结符
                {
                    if (x == '#' && ch != '#')   //没有输入字符但栈内仍有字符 ，则继续判断栈内字符是否可为空
                    {
                        flag = 0;
                        break;
                    }
                    else
                    {
                        flag = 1;	//进入终结符的判断
                        break;
                    }
                }
            if (flag == 1)
            {
                if (x == '#' && ch == '#')
                    finish = 1;//结束
                if (x == ch)
                {
                    printStack();
                    printRemain();
                    if(x == '#' && ch == '#')    //特殊情况，栈内、字符串全为'#'
                    {
                        printf("成功\n\n");
                        printf("合法字符串!");
                    }
                    else 	//其他情况:字符匹配
                    {
                        printf("%c匹配\n", ch);
                        ch = remain[++b];  //next字符
                        flag = 0;
                    }
                }
                else
                {
                    printStack();
                    printRemain();
                    printf("%c无法匹配\n\n", ch);/*输出出错终结符*/
                    printf("非法字符串!");
    
                    exit(1);
                }
            }
    
            else 					//非终结符
            {
                for (j = 0; j <= 2; j++)
                    if (x == vn[j])
                    {
                        m = j;      //分析表中匹配某一非终结符，行
                        break;
                    }
                for (j = 0; j <= 5; j++)
                    if (ch == vt[j])
                    {
                        n = j;		//分析表中匹配某一字符，列
                        break;
                    }
    
                now = table[m][n];
    
                if (now.begin != 'n')	//有产生式
                {
                    printStack();
                    printRemain();
    
                    printf("%c->", now.begin); //输出所用的产生式
                    for (j = 0; j<now.length; j++)
                        printf("%c", now.array[j]);
                    printf("\n");
    
                    for (j = (now.length - 1); j >= 0; j--) //产生式逆序入栈
                        analyse[++top] = now.array[j];
                    if (analyse[top] == '$')	//为空则不进栈
                        top--;     //指向下一个字符
                }
    
                else
                {
                    printStack();
                    printRemain();
                    printf("%c无法匹配\n", x);	//输出无法匹配的非终结符
                    printf("非法字符串!");
    
                    exit(1);
                }
            }
        }
        while (finish == 0);
    }
    
    void printStack()
    {
        int a;
        for(a=0; a <= top+1; a++)
            printf("%c", analyse[a]);   //输出栈内元素
        printf("\t\t");
    }
    
    void printRemain()
    {
        int j;
        for (j = 0; j<b; j++)
            printf(" ");	//对齐
        for (j = b; j <= l; j++)
            printf("%c", remain[j]); 	//输出剩余字符串
        printf("\t\t\t");
    }

我这里是将预测分析表写死了，如果想看FIRST集和FOLLOW集怎么去写，可以看这个博主的。

[https://blog.csdn.net/nk\_test/article/details/51476663][https_blog.csdn.net_nk_test_article_details_51476663]

[https://blog.csdn.net/qq\_41634294/article/details/89280090][https_blog.csdn.net_qq_41634294_article_details_89280090]

[https_blog.csdn.net_nk_test_article_details_51476663]: https://blog.csdn.net/nk_test/article/details/51476663
[https_blog.csdn.net_qq_41634294_article_details_89280090]: https://blog.csdn.net/qq_41634294/article/details/89280090