编译原理：实现LL(1）的语法分析，包括消除直接和间接左递归

矫情吗；* 2023-06-30 01:44 78阅读 0赞

## 实验二 预测分析算法的设计与实现 ##

（10学时）  
一、实验目的  
通过预测分析算法的设计与实现，加深对自上而下语法分析方法的理解，尤其是对自上而下分析条件的理解。  
二、实验内容  
输入文法及待分析的输入串，输出其预测分析过程及结果。

1.  参考数据结构  
    (1)/*定义产生式的语法集结构*/  
    typedef struct\{  
    char formula\[200\];//产生式  
    \}grammarElement;  
    grammarElement gramOldSet\[200\];//原始文法的产生式集  
    (2)/*变量定义*/  
    char terSymbol\[200\];//终结符号  
    char non\_ter\[200\];//非终结符号  
    char allSymbol\[400\];//所有符号  
    char firstSET\[100\]\[100\];//各产生式右部的FIRST集  
    char followSET\[100\]\[100\];//各产生式左部的FOLLOW集  
    int M\[200\]\[200\];//分析表
2.  判断文法的左递归性，将左递归文法转换成非左递归文法。（该步骤可以省略，直接输入非左递归文法）。  
    3.根据文法求FIRST集和FOLLOW集。  
    （1）/*求 First 集的算法*/  
    begin  
    if X为终结符(X)  
    在所有产生式中查找X所在的产生式  
    if 产生式右部第一个字符为终结符或空(即Xa（a）或X)  
    then 把a或加进FIRST(X)  
    if 产生式右部第一个字符为非终结符 then  
    if产生式右部的第一个符号等于当前字符 then  
    跳到下一条产生式进行查找  
    if 当前非终结符还没有求其FIRST集 then  
    查找它的FIRST集并标识此符号已求其FIRST集  
    求得结果并入到X的FIRST集  
    if 当前产生式右部符号可推出空字且当前字符不是右部的最后一个字符  
    then 获取右部符号下一个字符在所有字符集中的位置  
    if 此字符的FIRST集还未查找 then  
    找其FIRST集，并标其查找状态为1  
    把求得的FIRST集并入到X的FIRST集  
    if 当前右部符号串可推出空且是右部符号串的最后一个字符(即产生式为X,若对一切1 i k,均有 FIRST(),则将符号加进FIRST(X)) then 把空字加入到当前字符X的FIRST集  
    else  
    不能推出空字则结束循环  
    标识当前字符X已查找其FIRST集。  
    end  
    （2）/*求 FOLLOW 集的算法*/  
    begin  
    if X为开始符号 then \# FOLLOW(X)  
    对全部的产生式找一个右部含有当前字符X的产生式  
    if X在产生式右部的最后(形如产生式AX) then  
    查找非终结符A是否已经求过其FOLLOW集.避免循环递归  
    if 非终结符A已经求过其FOLLOW集 then  
    把FOLLOW(A)中的元素加入FOLLOW(X)  
    继续查下一条产生式是否含有X  
    else  
    求A的FOLLOW集，并标记为A已求其FOLLOW集  
    else if X不在产生式右部的最后(AB) then  
    if 右部X后面的符号串能推出空字 then  
    查找是否已求过其FOLLOW集.避免循环递归  
    if 已求过的FOLLOW集 then  
    把FOLLOW(A)中的元素加入FOLLOW(B)  
    结束本次循环  
    else if 不能推出空字 then  
    求 FIRST()  
    把FIRST()中所有非空元素加入到FOLLOW(B)中  
    　　　　　标识当前要求的非终结符X的FOLLOW集已求过  
    end  
    4.构造预测分析表。  
    /*构造分析表*/  
    //在A所在行,a所在列, M\[A,a\]的填写方法如下:  
    if (AP and aFIRST() ) do  
    M\[A,a\]=‘A’  
    if (\*(FIRST()) and aFOLLOW(A)) do  
    M\[A,a\]=‘A’;  
    else do M\[A,a\]=‘ERR’.

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2k2MjIzNjcx_size_16_color_FFFFFF_t_70][]

### 结果 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2k2MjIzNjcx_size_16_color_FFFFFF_t_70 1]

### 源代码 ###

#include "stdio.h"
    #include "stdlib.h"
    #define MaxRuleNum 10
    #define MaxVnNum 10
    #define MaxVtNum 10
    #define MaxStackDepth 20
    #define MaxPLength 20
    #define MaxStLength 50
    #include <windows.h>
    #include <conio.h>
    
    const WORD FORE_BLUE   = FOREGROUND_BLUE;           //蓝色文本属性
    const WORD FORE_GREEN  = FOREGROUND_GREEN;          //绿色文本属性
    const WORD FORE_RED    = FOREGROUND_RED;            //红色文本属性
    const WORD FORE_PURPLE = FORE_BLUE | FORE_RED;      //紫色文本属性
    const WORD FORE_CYAN   = FORE_BLUE | FORE_GREEN;    //青色文本属性
    const WORD FORE_YELLOW = FORE_RED | FORE_GREEN;     //黄色文本属性
    const WORD FORE_GRAY   = FOREGROUND_INTENSITY;      //灰色文本属性
    const WORD BACK_BLUE   = BACKGROUND_BLUE;           //蓝色背景属性
    const WORD BACK_GREEN  = BACKGROUND_GREEN;          //绿色背景属性
    const WORD BACK_RED    = BACKGROUND_RED;            //绿色背景属性
    const WORD BACK_PURPLE = BACK_BLUE | BACK_RED;      //紫色背景属性
    const WORD BACK_CYAN   = BACK_BLUE | BACK_GREEN;    //青色背景属性
    const WORD BACK_YELLOW = BACK_RED | BACK_GREEN;     //黄色背景属性
    const WORD BACK_GRAY   = BACKGROUND_INTENSITY;      //灰色背景属性
    const WORD FORE_WHITE   = FORE_BLUE | FORE_RED | FORE_GREEN;
    const WORD BLACK   =FOREGROUND_RED |	FOREGROUND_GREEN |FOREGROUND_BLUE;
    
    HANDLE handle_out = GetStdHandle(STD_OUTPUT_HANDLE);    //获得标准输出设备句柄
    CONSOLE_SCREEN_BUFFER_INFO csbi;
    void set(const WORD x){ 
    
           GetConsoleScreenBufferInfo(handle_out, &csbi);
            SetConsoleTextAttribute(handle_out, x);
    }
    
    struct pRNode {  //产生式右部的结构
    	int rCursor;//指向字符表的指针表示产生式右部字符
    	struct pRNode *next;//链表的组织结构
    };
    struct pNode { 
    	int lCursor; //指向产生式左边字符
    	int rLength; //产生式右部分的长度
    	struct pRNode *rHead; //产生式右部分头指针
    };
    
    char Vn[MaxVnNum + 1]; //非终结符集
    int vnNum;
    
    char Vt[MaxVtNum + 1]; // 终结符集 
    int vtNum;
    
    struct pNode P[MaxRuleNum];//产生式集
    int PNum;
    
    char buffer[MaxPLength + 1];//缓冲串集合
    char ch;
    
    char st[MaxStLength]; //要分析的符号串
    
    struct collectNode {  //定义first和follow集
    	int nVt;//字符
    	struct collectNode *next;
    };
    
    struct collectNode* first[MaxVnNum + 1]; //first 集每个元素是个指向链表的指针
    struct collectNode* follow[MaxVnNum + 1]; //follow 集
    
    int analyseTable[MaxVnNum + 1][MaxVtNum + 1 + 1];//分析表
    int analyseStack[MaxStackDepth + 1]; //分析栈
    int topAnalyse; /* 分析栈顶 */
    void Init();/* 初始化 */
    int IndexCh(char ch);
    void InputVt(); /* 输入终结符 */
    void InputVn();/* 输入非终结符 */
    void ShowChArray(char* collect, int num);/* 输出 Vn 或 Vt 的内容 */
    void InputP();/* 产生式输入 */
    bool CheckP(char * st);/* 判断产生式正确性 */
    void First(int U);
    void AddFirst(int U, int nCh); /* 加入 first 集*/
    bool HaveEmpty(int nVn);
    void Follow(int V);/* 计算 follow 集*/
    void AddFollow(int V, int nCh, int kind);
    void ShowCollect(struct collectNode **collect);/* 输出 first 或 follow集*/
    void FirstFollow();/* 计算 first 和 follow*/
    void CreateAT();/* 构造预测分析表 */
    void ShowAT();/* 输出分析表 */
    void Identify(char *st);
    void InitStack();
    void ShowStack();
    void Pop();
    void Push(int r);
    void printp();//输出所有产生式
    void isdturn();//消除直接左递归
    void isjturn();//消除间接左递归
    void length();//更新长度
    
    int main() { 
    	char todo,ch;
    	Init();
    	InputVn();
    	InputVt();
    	InputP();
    	getchar();//吃掉换行
    	isjturn();
    	isdturn();
    	length();
    	printf(" 所得不含左递归的产生式为：\n");
    	printp();
    	FirstFollow();
    	printf(" 所得 first 集为： ");
    	ShowCollect(first);
    	printf(" 所得 follow 集为： ");
    	ShowCollect(follow);
    	CreateAT();
    	ShowAT();
    	todo = 'y';
    	while('y' == todo) { 
    		printf("\n 是否继续进行句型分析？ (y / n):");
    		todo = getchar();
    		while('y' != todo && 'n' != todo) { 
    			printf("\n(y / n)? ");
    			todo = getchar();
    		}
    		if('y' == todo) { 
    			int i;
    			InitStack();
    			printf(" 请输入符号串 ( 以#结束 ) : ");
    			ch = getchar();
    			i = 0;
    			while('#' != ch && i < MaxStLength) { 
    				if(' ' != ch && '\n' != ch) { 
    					st[i++] = ch;
    				}
    				ch = getchar();
    			}
    			if('#' == ch && i < MaxStLength) { 
    				st[i] = ch;
    				Identify(st);
    			} else
    				printf(" 输入出错！ \n");
    		}
    	}
    	getchar();
    }
    void Init() { 
    	int i,j;
    	vnNum = 0;
    	vtNum = 0;
    	PNum = 0;
    	for(i = 0; i <= MaxVnNum; i++)
    		Vn[i] = '\0';//非终初始化
    	for(i = 0; i <= MaxVtNum; i++)
    		Vt[i] = '\0';//终初始化
    	for(i = 0; i < MaxRuleNum; i++) { //产生式初始化
    		P[i].lCursor = NULL;
    		P[i].rHead = NULL;
    		P[i].rLength = 0;
    	}
    	for(i = 0; i <= MaxPLength; i++)
    		buffer[i] = '\0';//字符集初始化
    	for(i = 0; i < MaxVnNum; i++) { 
    		first[i] = NULL;//first初始化
    		follow[i] = NULL;//follow初始化
    	}
    	for(i = 0; i <= MaxVnNum; i++) { 
    		for(j = 0; j <= MaxVnNum + 1; j++)
    			analyseTable[i][j] = -1;//分析表的初始化
    	}
    }
    int IndexCh(char ch) { 
    	int n;
    	n = 0; /*is Vn?*/
    	while(ch != Vn[n] && '\0' != Vn[n])
    		n++;
    	if('\0' != Vn[n])
    		return 100 + n;//非终的值是大于100的
    	n = 0; /*is Vt?*/
    	while(ch != Vt[n] && '\0' != Vt[n])
    		n++;
    	if('\0' != Vt[n])
    		return n;
    	return -1;//空返回-1
    }
    
    void ShowChArray(char* collect) { 
    	int k = 0;
    	while('\0' != collect[k]) { 
    		printf(" %c ", collect[k++]);
    	}
    	printf("\n");
    }
    
    void InputVn() { 
    	int inErr = 1;
    	int n,k;
    	char ch;
    	while(inErr) { 
    		printf(" 请输入所有的非终结符，注意： ");
    		printf(" 请将开始符放在第一位，并以 #号结束 :\n");
    		ch = ' ';
    		n = 0;
    		/* 初始化数组 */
    		while(n < MaxVnNum) { 
    			Vn[n++] = '\0';
    		}
    		n = 0;
    		while(('#' != ch) && (n < MaxVnNum)) { 
    			if(' ' != ch && '\n' != ch && -1 == IndexCh(ch)) { //排除空格,换行,已经输入的字符
    				Vn[n++] = ch;
    				vnNum++;
    			}
    			ch = getchar();
    		}
    		Vn[n] = '#'; /* 以"#" 标志结束用于判断长度是否合法 */
    		k = n;
    		if('#' != ch) { 
    			if( '#' != (ch = getchar())) { 
    				while('#' != (ch = getchar()))
    					;//清除缓冲区,一会重新输入不能在读进去了
    				printf("\n 符号数目超过限制！ \n");
    				inErr = 1;
    				continue;
    			}
    		}
    		/* 正确性确认，正确则，执行下下面，否则重新输入 */
    		Vn[k] = '\0';
    		ShowChArray(Vn);
    		ch = ' ';
    		while('y' != ch && 'n' != ch) { 
    			if('\n' != ch) { 
    				printf(" 输入正确确认 ?(y/n):");
    			}
    			scanf("%c", &ch);
    		}
    		if('n' == ch) { 
    			printf(" 录入错误重新输入！ \n");
    			inErr = 1;
    		} else { 
    			inErr = 0;
    		}
    	}
    }
    /* 输入终结符 */
    void InputVt() { 
    	int inErr = 1;
    	int n,k;
    	char ch;
    	while(inErr) { 
    		printf("\n 请输入所有的终结符，注意： ");
    		printf(" 以#号结束 :\n");
    		ch = ' ';
    		n = 0;
    		/* 初始化数组 */
    		while(n < MaxVtNum) { 
    			Vt[n++] = '\0';
    		}
    		n = 0;
    		while(('#' != ch) && (n < MaxVtNum)) { 
    			if(' ' != ch && '\n' != ch && -1 == IndexCh(ch)) { 
    				Vt[n++] = ch;
    				vtNum++;
    			}
    			ch = getchar();
    		}
    		Vt[n] = '#';//默认最后一个是#
    		k = n;
    		if('#' != ch) { 
    			if( '#' != (ch = getchar())) { 
    				while('#' != (ch = getchar()))
    					;
    				printf("\n 符号数目超过限制！ \n");
    				inErr = 1;
    				continue;
    			}
    		}
    		Vt[k] = '\0';
    		ShowChArray(Vt);
    		ch = ' ';
    		while('y' != ch && 'n' != ch) { 
    			if('\n' != ch) { 
    				printf(" 输入正确确认 ?(y/n):");
    			}
    			scanf("%c", &ch);
    		}
    		if('n' == ch) { 
    			printf(" 录入错误重新输入！ \n");
    			inErr = 1;
    		} else { 
    			inErr = 0;
    		}
    	}
    }
    /* 产生式输入 */
    void InputP() { 
    	char ch;
    	int i = 0, n,num;
    	printf(" 请输入文法产生式的个数： ");
    	scanf("%d", &num);
    	PNum = num;
    	getchar(); //删除回车
    	printf("\n 请输入文法的 %d个产生式 , 并以回车分隔每个产生式： ", num);
    	printf("\n");
    	while(i < num) { 
    		printf(" 第%d 个： ", i);
    		/* 初始化 */
    		for(n =0; n < MaxPLength; n++)
    			buffer[n] = '\0';
    		/* 输入产生式串 */
    		ch = ' ';
    		n = 0;
    		while('\n' != (ch = getchar()) && n < MaxPLength) { 
    			if(' ' != ch)//除去空格换行
    				buffer[n++] = ch;
    		}
    		buffer[n] = '\0';
    		if(CheckP(buffer)) { 
    			pRNode *pt, *qt;
    			P[i].lCursor = IndexCh(buffer[0]);//产生式左边赋值
    			pt = (pRNode*)malloc(sizeof(pRNode));//构造产生式右部
    			pt->rCursor = IndexCh(buffer[3]);
    			pt->next = NULL;
    			P[i].rHead = pt;//构造头结点
    			n = 4;
    			while('\0' != buffer[n]) { //构造链表
    				qt = (pRNode*)malloc(sizeof(pRNode));
    				qt->rCursor = IndexCh(buffer[n]);
    				qt->next = NULL;
    				pt->next = qt;
    				pt = qt;//pt跟着qt
    				n++;
    			}
    			P[i].rLength = n - 3;//产生式右部长度
    			i++;
    		} else
    			printf(" 输入符号含非法在成分，请重新输入！ \n");
    	}
    }
    /* 判断产生式正确性 */
    bool CheckP(char * st) { 
    	int n;
    	if(100 > IndexCh(st[0]))//如果第一个字符是终结符
    		return false;
    	if('-' != st[1])//终结符后面不是->则报错
    		return false;
    	if('>' != st[2])
    		return false;
    	for(n = 3; '\0' != st[n]; n ++) { 
    		if(-1 == IndexCh(st[n]))//输入了不存在的报错
    			return false;
    	}
    	return true;
    }
    //消除间接左递归
    void isjturn()
    { 
    	for(int j=0;j<vnNum;j++)
    	{ 
    	     for(int i = 0; i < PNum; i++)
    	     { 
    	     	 if(j==(P[i].lCursor-100)&&P[i].rHead->rCursor>=100&&P[i].rHead->rCursor<P[i].lCursor)
    	     	 { 
    	     	 	for(int k=0;k<i;k++)
    				{ 
    					if(P[k].lCursor==P[i].rHead->rCursor)
    					{ 
    						pRNode * p=P[k].rHead;
    						pRNode * qt=(pRNode*)malloc(sizeof(pRNode));
    						pRNode * head=qt;
    						while(p!=NULL)
    						{ 
    
    							pRNode * pt = (pRNode*)malloc(sizeof(pRNode));
    							pt->rCursor=p->rCursor;
    							qt->next=pt;
    							qt=pt;
    							p=p->next;
    						}
    				        qt->next=P[i].rHead->next;
    						P[i].rHead=head->next;
    					}
    
    				}
    
    			  }
    		 }
    	}
    }
    //消除直接左递归
    void isdturn()
    { 
    
    	int flag2=0;
    
    	struct collectNode *pa[10];//作为a的数组
    	struct collectNode *pb[10];
    	for(int i=0;i<10;i++)
    	{ 
    		pa[i]=pb[i]=NULL;
    	}
    	int n=0,m=0;
    	pRNode * p=NULL;
    	for(int j=0;j<vnNum;j++)
    	{ 
    	    int flag1=0;
    	    for(int i = 0; i < PNum; i++)
    		{ 
    
    		 	  if(j==P[i].lCursor-100&&j==P[i].rHead->rCursor-100)
    			  { flag1=1;break;}
            }
    		if(flag1==1)
    		{ 
    				for(int i = 0; i < PNum; i++)
    				{ 
    				 	  if(j==(P[i].lCursor-100)&&j==(P[i].rHead->rCursor-100))
    					  { 
    						   n++;
    						   P[i].lCursor= vnNum+100;
    						   p=P[i].rHead = P[i].rHead->next;
    			               pRNode* pt = (pRNode*)malloc(sizeof(pRNode));//构造产生式右部
    						   pt->rCursor = vnNum+100;
    						   pt->next=NULL;
    						   while(p->next!=NULL) p=p->next;
    						   p->next=pt;
    				      }
    				      if(j==(P[i].lCursor-100)&&j!=(P[i].rHead->rCursor-100)&&-1!=P[i].rHead->rCursor)
    				      { 
    			               p=P[i].rHead = P[i].rHead;
    			               pRNode* pt = (pRNode*)malloc(sizeof(pRNode));//构造产生式右部
    						   pt->rCursor = vnNum+100;
    						   pt->next=NULL;
    						   while(p->next!=NULL) p=p->next;
    						   p->next=pt;
    					  }
    			    }
    			    P[PNum++].lCursor =vnNum+100;
    			    pRNode* pt = (pRNode*)malloc(sizeof(pRNode));//构造产生式右部
    			    pt->rCursor = -1;pt->next=NULL;
    			    P[PNum-1].rHead=pt;
    			    Vn[vnNum++]=Vn[j]+32;
    		}
    
        }
    }
    
    void First(int U) { 
    	int i,j;
    	for(i = 0; i < PNum; i++) { //对于每一个产生式
    		if(P[i].lCursor == U) { //如果产生式的左边是该非
    			struct pRNode* pt;
    			pt = P[i].rHead;//找到右部产生式
    			j = 0;
    			while(j < P[i].rLength) { 
    				if(100 > pt->rCursor) { //如果是终结符
    					AddFirst(U, pt->rCursor);//加到它的first集合就不在往后看了
    					break;
    				} else { 
    					if(NULL == first[pt->rCursor - 100]) { //非终结符如果它first集合空
    						First(pt->rCursor);//求他的first集合
    					}
    					AddFirst(U, pt->rCursor);//把它的first集合加入,非空
    					if(!HaveEmpty(pt->rCursor)) { 
    						break;
    					} else { 
    						pt = pt->next;//如果该非终的first有空找下一个
    					}
    				}
    				j++;
    			}
    			if(j >= P[i].rLength) // 当产生式右部都能推出空时 才把空加进去
    				AddFirst(U, -1);
    		}
    	}
    }
    
    /* 加入 first 集*/
    void AddFirst(int U, int nCh) { //把nch加到终结符U的first集
    	struct collectNode *pt, *qt;
    	int ch; /* 用于处理 Vn*/
    	pt = NULL;
    	qt = NULL;
    	if(nCh < 100) { //对于终结符
    		pt = first[U - 100];//找到它的first集合的链表
    		while(NULL != pt) { 
    			if(pt->nVt == nCh)
    				break;
    			else { 
    				qt = pt;
    				pt = pt->next;//qt记录前一,pt一直到空
    			}
    		}
    		if(NULL == pt) { 
    			pt = (struct collectNode *)malloc(sizeof(struct collectNode));
    			pt->nVt = nCh;
    			pt->next = NULL;
    			if(NULL == first[U - 100]) { //如果本来就没有,则直接将他作为头结点
    				first[U - 100] = pt;
    			} else { 
    				qt->next = pt; //新加入到first集合的字符连到链表上
    			}
    			pt = pt->next;
    		}
    	} else { //终结符
    		pt = first[nCh - 100];
    		while(NULL != pt) { 
    			ch = pt->nVt;
    			if(-1 != ch) { 
    				AddFirst(U, ch);//将它first集合非空部分加入。
    			}
    			pt = pt->next;
    		}
    	}
    }
    bool HaveEmpty(int nVn) { //非终且能推出空则true
    	if(nVn < 100)
    		return false;
    	struct collectNode *pt;
    	pt = first[nVn - 100];
    	while(NULL != pt) { 
    		if(-1 == pt->nVt)
    			return true;
    		pt = pt->next;
    	}
    	return false;
    }
    void Follow(int V) { 
    	int i;
    	struct pRNode *pt ;
    	if(100 == V) // 当为字符是初始字符的时候
    		AddFollow(V, -1, 0 );//直接把结束符加进去
    	for(i = 0; i < PNum; i++) { 
    		pt = P[i].rHead;
    		while(NULL != pt && pt->rCursor != V)
    			pt = pt->next;//产生式的有部找V
    		if(NULL != pt) { //找到了
    			pt = pt->next;
    			if(NULL == pt) { //是最后一个字符
    				if(NULL == follow[P[i].lCursor - 100] && P[i].lCursor != V) { //把左侧非V且有follow的非的集合加进去(含空)
    					Follow(P[i].lCursor);
    				}
    				AddFollow(V, P[i].lCursor, 0);
    			} else { 
    				while(NULL != pt && HaveEmpty(pt->rCursor)) { //因为没有判断fellow集合是否不变的机制,所以需要一直看到头
    					AddFollow(V, pt->rCursor, 1);//如果后面是非终有空
    					pt = pt->next;//每一个非终的first
    				}
    				if(NULL == pt) { //如果后面没有了
    					if(NULL == follow[P[i].lCursor - 100] && P[i].lCursor != V) { 
    						Follow(P[i].lCursor);//那么说明这个非终是最后一个,那么把产生式左边的fello加进去
    					}
    					AddFollow(V, P[i].lCursor, 0);
    				} else { 
    					AddFollow(V, pt->rCursor, 1);//否则最后一个姚明是终要么是不含空非终first加入
    				}
    			}
    		}
    	}
    }
    void AddFollow(int V, int nCh, int kind) { 
    	struct collectNode *pt, *qt;
    	int ch;
    	pt = NULL;
    	qt = NULL;
    	if(nCh < 100) {  /* 为终结符时直接加入链表尾部 */
    		pt = follow[V - 100];
    		while(NULL != pt) { 
    			if(pt->nVt == nCh)
    				break;
    			else { 
    				qt = pt;
    				pt = pt->next;
    			}
    		}
    		if(NULL == pt) { 
    			pt = (struct collectNode *)malloc(sizeof(struct collectNode));
    			pt->nVt = nCh;
    			pt->next = NULL;
    			if(NULL == follow[V - 100]) { 
    				follow[V - 100] = pt;
    			} else { 
    				qt->next = pt;
    			}
    			pt = pt->next;
    		}
    	} else { //非终结符的时候
    		if(0 == kind) { //直接把follow加进去
    			pt = follow[nCh - 100];
    			while(NULL != pt) { 
    				ch = pt->nVt;
    				AddFollow(V, ch, 0);
    				pt = pt->next;
    			}
    		} else { //把不含空的first加进去
    			pt = first[nCh - 100];
    			while(NULL != pt) { 
    				ch = pt->nVt;
    				if(-1 != ch) { 
    					AddFollow(V, ch, 1);
    				}
    				pt = pt->next;
    			}
    		}
    	}
    }
    /* 输出 first 或 follow 集*/
    void ShowCollect(struct collectNode **collect) { 
    	int i;
    	struct collectNode *pt;
    	i = 0;
    	set(BACK_PURPLE);
    	while(NULL != collect[i]) { 
    		pt = collect[i];
    		printf("\n%c:\t", Vn[i]);
    		while(NULL != pt) { 
    			if(-1 != pt->nVt) { 
    				printf(" %c", Vt[pt->nVt]);
    			} else
    				printf(" #");//把空转化成"#"
    			pt = pt->next;
    		}
    		i++;
    	}
    	printf("\n");
    	set(BLACK);
    }
    /* 计算 first 和 follow*/
    void FirstFollow() { 
    	int i;
    	i = 0;
    	while('\0' != Vn[i]) { 
    		if(NULL == first[i])
    			First(100 + i);//非终结符对应的序号在100外
    		i++;
    	}
    	i = 0;
    	while('\0' != Vn[i]) { 
    		if(NULL == follow[i])
    			Follow(100 + i);
    		i++;
    	}
    }
    /* 构造预测分析表 */
    void CreateAT() { 
    	int i;
    	struct pRNode *pt;
    	struct collectNode *ct;
    	for(i = 0; i < PNum; i++) { //对每个产生式
    		pt = P[i].rHead;
    		while(NULL != pt && HaveEmpty(pt->rCursor)) { //非终且能推出空
    			ct = first[pt->rCursor - 100];
    			while(NULL != ct) { 
    				if(-1 != ct->nVt)
    					analyseTable[P[i].lCursor - 100][ct->nVt] = i;//产生式左侧遇到它的右侧第一个非终的first集合
    				ct = ct->next;
    			}
    			pt = pt->next;
    		}
    		if(NULL == pt) { //后面都可以推出空
    			ct = follow[P[i].lCursor - 100];
    			while(NULL != ct) { 
    				if(-1 != ct->nVt)
    					analyseTable[P[i].lCursor - 100][ct->nVt] = i;
    				else//follow空其实就是遇到了#
    					analyseTable[P[i].lCursor - 100][vtNum] = i;//最后一列是#
    				ct = ct->next;
    			}
    		} else { //最后一个不能推出空
    			if(100 <= pt->rCursor) {  /* 不含空的非终结符 */
    				ct = first[pt->rCursor - 100];
    				while(NULL != ct) { 
    					analyseTable[P[i].lCursor - 100][ct->nVt] = i;
    					ct = ct->next;
    				}
    			} else {  /* 非空的终结符或者空 */
    				if(-1 == pt->rCursor) { //相当于是推出了空
    					ct = follow[P[i].lCursor - 100];
    					while(NULL != ct) { 
    						if(-1 != ct->nVt)
    							//if(analyseTable[P[i].lCursor - 100][ct->nVt] ==-1 )
    							analyseTable[P[i].lCursor - 100][ct->nVt] = i;
    						else /* 当含有 # 号时 */
    							analyseTable[P[i].lCursor - 100][vtNum] = i;
    						ct = ct->next;
    					}
    				} else {  /* 为终结符 */
    					analyseTable[P[i].lCursor - 100][pt->rCursor] = i;
    				}
    			}
    		}
    	}
    }
    /* 输出分析表 */
    void ShowAT() { 
    	
    	int i,j;
    	printf(" 构造预测分析表如下： \n");
    	set(BACK_YELLOW);
    	printf("\t|\t");
    	for(i = 0; i < vtNum; i++) { 
    		printf("%c\t", Vt[i]);//行头是所有终
    	}
    	printf("#\t\n");//#单独输出
    	printf("- - -\t|- - -\t");
    	for(i = 0; i <= vtNum; i++)
    		printf("- - -\t");
    	printf("\n");
    	for(i = 0; i < vnNum; i++) { 
    		printf("%c\t|\t", Vn[i]);//列头是终结符
    		for(j = 0; j <= vtNum; j++) { 
    			if(-1 != analyseTable[i][j])
    				printf("R(%d)\t", analyseTable[i][j]);
    			else
    				printf(" \t");
    		}
    		printf("\n");
    	}
    	set(BLACK );
    }
    
    void Identify(char *st) { //构造栈
    	int current,step,r; /*r 表使用的产生式的序号 */
    	printf("\n%s 的分析过程： \n", st);
    	set(BACK_CYAN);
    	printf(" 步骤 \t 分析符号栈 \t 当前指示字符 \t 使用产生式序号 \n");
    	step = 0;//第几步
    	current = 0;//输入串指针
    	printf("%d\t",step);
    	ShowStack();//栈你初始就有#和开始符号
    	printf("\t\t%c\t\t- -\n", st[current]);
    	while('#' != st[current]) { //当输入串剩下#结束
    		if(100 > analyseStack[topAnalyse]) { 
    			if(analyseStack[topAnalyse] == IndexCh(st[current])) { 
    				Pop();//终结符匹配,则出栈
    				current++;
    				step++;
    				printf("%d\t", step);
    				ShowStack();
    				printf("\t\t%c\t\t 出栈、后移 \n", st[current]);
    			} else { 
    				printf("%c-%c 不匹配！ ", analyseStack[topAnalyse], st[current]);
    				printf(" 此串不是此文法的句子！ \n");
    				return;
    			}
    		} else {  /* 当为非终结符时 */
    			r = analyseTable[analyseStack[topAnalyse] -
    			                 100][IndexCh(st[current])];
    			if(-1 != r) { 
    				Push(r);//push里有pop
    				step++;
    				printf("%d\t", step);
    				ShowStack();
    				printf("\t\t%c\t\t%d\n", st[current], r);
    			} else { 
    				printf(" 此串不是此文法的句子！ \n");
    				return;
    			}
    		}
    		
    	}
    	if('#' == st[current]) { 
    		if(0 == topAnalyse && '#' == st[current]) { 
    			step++;
    			printf("%d\t", step);
    			ShowStack();
    			printf("\t\t%c\t\t 分析成功！ \n", st[current]);
    			printf("%s 是给定文法的句子！ \n", st);
    		} else { 
    			while(topAnalyse > 0) { 
    				if(100 > analyseStack[topAnalyse]) { //终结符肯定不是
    					printf(" 此串不是此文法的句子！ \n");
    					return;
    				} else { //虽然输入串此时是#当站内是非终是,只有遇到推出空才行
    					r = analyseTable[analyseStack[topAnalyse] - 100][vtNum];
    					if(-1 != r) { 
    						Push(r); 
    						step++;
    						printf("%d\t", step);
    						ShowStack();
    						if(0 == topAnalyse && '#' == st[current]) { //可能有多个符号条件的非
    							printf("\t\t%c\t\t 分析成功！ \n", st[current]);
    							printf("%s 是给定文法的句子！ \n", st);
    						} else
    							printf("\t\t%c\t\t%d\n", st[current], r);
    					} else { 
    						printf(" 此串不是此文法的句子！ \n");
    						return;
    					}
    				}
    			}
    		}
    	}set(BLACK);
    }
    /* 初始化栈及符号串 */
    void InitStack() { 
    	int i;
    	/* 分析栈的初始化 */
    	for(i = 0; i < MaxStLength; i++)
    		st[i] = '\0';
    	analyseStack[0] = -1; /*#(-1) 入栈 */
    	analyseStack[1] = 100; /* 初始符入栈 */
    	topAnalyse = 1;//栈顶指针,指向栈顶元素
    }
    /* 显示符号栈中内容 */
    void ShowStack() { 
    	int i;
    	for(i = 0; i <= topAnalyse; i++) { 
    		if(100 <= analyseStack[i])
    			printf("%c", Vn[analyseStack[i] - 100]);
    		else { 
    			if(-1 != analyseStack[i])
    				printf("%c", Vt[analyseStack[i]]);
    			else
    				printf("#");
    		}
    	}
    }
    /* 栈顶出栈 */
    void Pop() { 
    	topAnalyse--;
    }
    void Push(int r) { 
    	int i;
    	struct pRNode *pt;
    	Pop();//
    	pt = P[r].rHead;
    	if(-1 == pt->rCursor)
    		return;//产生式右部是空不进栈
    	topAnalyse += P[r].rLength;
    	for(i = 0; i < P[r].rLength; i++) { 
    		analyseStack[topAnalyse - i] = pt->rCursor;/* 逆序入栈 */
    		pt = pt->next;
    	}
    }
    //输出所有产生式
    void printp()
    { 
    	set(BACK_GREEN);
        for(int i = 0; i < PNum; i++)
    	{ 
            putchar(Vn[P[i].lCursor-100]);
            printf("->");
            pRNode* pt=P[i].rHead;
            while(pt!=NULL)
    		   { 
    		         if(pt->rCursor>=100)
    		   		    putchar(Vn[pt->rCursor-100]);
    				 else putchar(Vt[pt->rCursor]);
    				 pt=pt->next;
    		   }
    		printf("\n");
        }set(BLACK);
    }
    
    void length()//更新有部产生式的长度
    { 
    	for(int i = 0; i < PNum; i++)
    	{ 
            int count=0;
    	    pRNode* pt=P[i].rHead;
    		while(pt!=NULL)
    		{ 
    			pt=pt->next;
    			count++;
    		}
    		P[i].rLength=count;
        }
    	
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2k2MjIzNjcx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200113180634759.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2k2MjIzNjcx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2k2MjIzNjcx_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200113180802455.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2k2MjIzNjcx,size_16,color_FFFFFF,t_70