编译原理 非递归的预测分析（相关搜索：编译原理）

Question

/*
E::=TG
G::=＋TG
G::=
T::=FS
S::=*FS
S::=
F::=(E)
F::=i
*/

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

char stack[20];        
char input[20];        
char VT[20]={'i','+','*','(',')','#'};    
char VN[20]={'E','G','T','S','F'};        

int ip=0,top=0,len;                        

typedef struct type        /*production*/
{
    char origin;    /*left side */
    char array[5];    /*right side */
    int length;        /*length of right side */
}type;

type e,t,g,g1,s,s1,f,f1;    
type C[10][10];                /*Parsing table*/


/*--------------------------------*/
void print_stack()
{
    int i;
    for(i=0;i<=top;i++)
        printf("%c",stack[i]);
    printf("\t\t");
}

/*--------------------------------*/
void print_input()
{
    int i;
    for(i=0;i<ip;i++)    
        printf(" ");
    for(i=ip;i<len;i++)
        printf("%c",input[i]);
    printf("\t\t\t");
}


/*--------------------------------*/
void LL()
{
    int i;
    int row,col,step,flag;
    char sym,x;
    type production;   

    flag=0;
    ip=0;
    step=0;
    top=0;
    sym=input[ip];     
    stack[top]='#'; stack[++top]='E';     

    printf("step\t\tstack \t\tinput \t\tproduction \n");
    while(1){
        printf("%d",step++);     
        printf("\t\t");
        print_stack();
        print_input();

        x=stack[top--];          

        for(i=0;i<=5;i++)        
            if(x==VT[i]){
              flag=1;
              break;
            }

        if(flag==1){              
              if(x==sym){
                  if(x=='#'){
                    printf("acc!\n");     
                    return;
                  }
                  printf("%c match\n",sym);
                  sym=input[++ip];         
                  flag=0;                 
              }
              else {     
                  printf("%c error!\n",sym);  
                  return;
              }
        }
        else{         
            for(i=0;i<=4;i++)
                if(x==VN[i]){
                    row=i;     
                    break;
                }
            for(i=0;i<=5;i++)
                if(sym==VT[i]){
                    col=i;     
                    break;
                }
            if(i==6){
                printf("error...illegal input!!\n");
                return;
            }

            production=C[row][col];
            if(production.origin!='N'){  
                printf("%c->",production.origin);     
                for(i=0;i<production.length;i++)
                    printf("%c",production.array[i]);
                printf("\n");

                for(i=(production.length-1);i>=0;i--)     
                    stack[++top]=production.array[i];
            }
            else{  
                printf("%c error!\n",x); 
                return;
            }
        }
    }
}

/*--------------------------------*/
void main()
{
    int i,j;
    char c;
    e.origin='E';    strcpy(e.array,"TG");    e.length=2;
    t.origin='T';    strcpy(t.array,"FS");    t.length=2;
    g.origin='G';    strcpy(g.array,"+TG");    g.length=3;
    g1.origin='G';                            g1.length=0;
    s.origin='S';    strcpy(s.array,"*FS");    s.length=3;
    s1.origin='S';                            s1.length=0;
    f.origin='F';    strcpy(f.array,"(E)");    f.length=3;
    f1.origin='F';    f1.array[0]='i';        f1.length=1;

    /*initialize parsing table*/
    for(i=0;i<=4;i++)
        for(j=0;j<=5;j++)
            C[i][j].origin='N';  

    C[0][0]=e;    C[0][3]=e;
    C[1][1]=g;    C[1][4]=g1;    C[1][5]=g1;
    C[2][0]=t;    C[2][3]=t;
    C[3][1]=s1;    C[3][2]=s;    C[3][4]=C[3][5]=s1;
    C[4][0]=f1;    C[4][3]=f;

    while(1){
        printf("\ninput length<50,ending with'#'; '^#' to return!\n");
        len=0;
        do{
           scanf("%c",&c);
           input[len++]=c;
        }while(c!='#');
        getchar();

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

        LL();
    }
}

Answer 1

【以下回答由 GPT 生成】

很抱歉，作为一个语言模型AI助手，无法真正地运行和展示代码。但我可以给出一个示例来帮助您更好地理解预测分析表的构建过程。

假设我们有如下的文法规则和预测分析表：

文法规则：

S -> aAb
A -> a
A -> b

预测分析表：

+-----+---+---+---+
|     | a | b | # |
+-----+---+---+---+
| S   | 1 |   |   |
| A   | 2 | 3 |   |
+-----+---+---+---+

我们将使用栈来模拟预测分析的过程。

首先初始化输入串和栈为空，并向输入串末尾添加结束符号（#）：

输入串(Matching String): a a b # 栈(Stack): #

接下来，根据文法规则将文法符号推入栈中，首先推入结束符号（#）：

栈(Stack): #, S

然后开始重复执行以下步骤：

1. 检查栈顶的终结符和输入串的下一个符号是否匹配，如果是则将栈顶符号和输入符号出栈，并将指针向后移动一个位置。

当前栈顶符号：# 当前输入符号：a

由于栈顶符号和输入符号不匹配，继续执行下一步。

1. 如果栈顶的符号是非终结符，则查找预测分析表中对应的产生式。

当前栈顶符号：# 当前输入符号：a

进行预测分析表中的查找，根据表格中的S,a项对应的产生式编号为1。

1. 依次将所找到的产生式中的非终结符推入栈中，注意要按照产生式中非终结符的倒序推入。

当前栈顶符号：#, S 推入产生式1中的非终结符：b, A

更新后的栈(Stack): #, S, A

1. 如果在预测分析表中未找到对应的产生式，则产生错误。

当前栈顶符号：#, S, A 当前输入符号：a

继续重复执行步骤1。

1. 重复执行以上步骤，直到栈为空或输入串的结束符号也已经处理。

当前栈顶符号：#, S, A 当前输入符号：b

此时栈顶符号和输入符号不匹配，继续执行步骤2。

当前栈顶符号：#, S, A 当前输入符号：b

进行预测分析表中的查找，根据表格中的A,b项对应的产生式编号为3。

当前栈顶符号：#, S 推入产生式3中的非终结符：a, A

更新后的栈(Stack): #, S, A, a

继续重复执行以上步骤，直到栈为空或输入串的结束符号也已经处理。

最终，如果栈为空且输入串的结束符号也已经处理，则说明预测分析成功。否则，如果栈为空但输入串的结束符号未处理，或者栈不为空但输入串的结束符号已处理，则说明预测分析失败。

这是一个简单的预测分析表的例子，您可以根据实际的文法规则和预测分析表构建自己的代码实现。希望以上的解释能够帮助您理解预测分析表的实现过程。如果有任何疑问，请随时提问。

【相关推荐】

• 帮你找了个相似的问题, 你可以看下: https://ask.csdn.net/questions/7615108
• 这篇博客也不错, 你可以看下编译原理（词法分析器）
• 您还可以看一下 李立宗老师的讲给入门者的深度学习课程中的 原理小节, 巩固相关知识点
  
• 除此之外, 这篇博客: 编译原理实验一：词法分析程序设计实验中的 编译原理实验一 部分也许能够解决你的问题。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^