《实验2-预测分析算法的设计与实现》由会员分享，可在线阅读，更多相关《实验2-预测分析算法的设计与实现（29页珍藏版）》请在金锄头文库上搜索。
1、实验二 预测分析算法的设计与实现（8学时）一、实验目的通过预测分析算法的设计与实现，加深对自上而下语法分析方法的理解，尤其是对自上而下分析条件的理解。二、实验要求 输入文法及待分析的输入串，输出其预测分析过程及结果。 三、实验步骤1. 参考数据结构 (1)/*定义产生式的语法集结构*/typedef struct char formula200;/产生式grammarElement;grammarElement gramOldSet200;/原始文法的产生式集 (2)/*变量定义*/ char terSymbol200;/终结符号 char non_ter200;/非终结符号 char all
2、Symbol400;/所有符号 char firstSET100100;/各产生式右部的FIRST集 char followSET100100;/各产生式左部的FOLLOW集 int M200200;/分析表2. 判断文法的左递归性，将左递归文法转换成非左递归文法。（该步骤可以省略，直接输入非左递归文法）。3.根据文法求FIRST集和FOLLOW集。（1）/*求 First 集的算法*/ beginif X为终结符(XÎ) 在所有产生式中查找X所在的产生式 if 产生式右部第一个字符为终结符或空(即X®a（aÎ）或X®e) then 把a或e加进FIRS
3、T(X) if 产生式右部第一个字符为非终结符 then if产生式右部的第一个符号等于当前字符 then 跳到下一条产生式进行查找 if 当前非终结符还没有求其FIRST集 then 查找它的FIRST集并标识此符号已求其FIRST集 求得结果并入到X的FIRST集 if 当前产生式右部符号可推出空字且当前字符不是右部的最后一个字符 then 获取右部符号下一个字符在所有字符集中的位置 if 此字符的FIRST集还未查找 then 找其FIRST集，并标其查找状态为1 把求得的FIRST集并入到X的FIRST集 if 当前右部符号串可推出空且是右部符号串的最后一个字符(即产生式为X®
4、;,若对一切1£ i£ k,均有e ÎFIRST(),则将eÎ符号加进FIRST(X) then 把空字加入到当前字符X的FIRST集 else 不能推出空字则结束循环 标识当前字符X已查找其FIRST集。end（2）/*求 FOLLOW 集的算法*/begin if X为开始符号 then # ÞFOLLOW(X) 对全部的产生式找一个右部含有当前字符X的产生式 if X在产生式右部的最后(形如产生式A®aX) then 查找非终结符A是否已经求过其FOLLOW集.避免循环递归 if 非终结符A已经求过其FOLLOW集 then 把
5、FOLLOW(A)中的元素加入FOLLOW(X) 继续查下一条产生式是否含有X else 求A的FOLLOW集，并标记为A已求其FOLLOW集 else if X不在产生式右部的最后(A®aBb) then if 右部X后面的符号串b能推出空字e then 查找b是否已求过其FOLLOW集.避免循环递归 if 已求过b的FOLLOW集 then把FOLLOW(A)中的元素加入FOLLOW(B) 结束本次循环 else if b不能推出空字 then 求 FIRST(b) 把FIRST(b)中所有非空元素加入到FOLLOW(B)中标识当前要求的非终结符X的FOLLOW集已求过 end4
6、.构造预测分析表。/*构造分析表*/在AÎ所在行,aÎ所在列, MA,a的填写方法如下:if (A®dÎP and aÎFIRST(d) ) do MA,a=A®dif (dÞ*e(eÎFIRST(d) and aÎFOLLOW(A) do MA,a=A®d;else do MA,a=ERR.5.构造总控程序。程序流程图如图1所示：N$和文法开始符号进S栈第一个输入符号读进aS栈顶符号上托出去放X中XÎ?X=a?X=$?将下一个输入符号读进aX=a?查MX,a=xy1y2yn?将y1y
7、2yn逆序放入S栈中,若右部符号串为e,则e不进S栈出错正确出错出错YNYNYNYYN图16.对给定的输入串，给出分析过程及结果。四、实验报告要求1.写出编程思路、源代码（或流程图）；2.写出上机调试时发现的问题，以及解决的过程；3.写出你所使用的测试数据及结果；4.谈谈你的体会。5.上机8小时，完成实验报告2小时。程序代码:#include "stdio.h"#include "stdlib.h"#define MaxRuleNum 8#define MaxVnNum 5#define MaxVtNum 5#define MaxStackDepth 2
8、0#define MaxPLength 20#define MaxStLength 50struct pRNode /*产生式右部结构*/ int rCursor; struct pRNode *next;struct pNode int lCursor; int rLength; /*右部长度*/ struct pRNode *rHead; /*右部结点头指针*/;char VnMaxVnNum + 1; /*非终结符集*/int vnNum;char VtMaxVtNum + 1; /*终结符集*/int vtNum;struct pNode PMaxRuleNum; int PNum;
9、char bufferMaxPLength + 1;char ch; char stMaxStLength; /*要分析的符号串*/struct collectNode int nVt; struct collectNode *next;struct collectNode* firstMaxVnNum + 1; /*first集*/struct collectNode* followMaxVnNum + 1; /*follow集*/int analyseTableMaxVnNum + 1MaxVtNum + 1 + 1;int analyseStackMaxStackDepth + 1; /
10、*分析栈*/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 H
11、aveEmpty(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(
12、);void Pop();void Push(int r);int main() char todo,ch; Init(); InputVn(); InputVt(); InputP(); getchar(); FirstFollow(); printf("所得first集为："); ShowCollect(first); printf("所得follow集为："); ShowCollect(follow); CreateAT(); ShowAT(); todo = 'y' while('y' = todo) printf
13、("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) sti+ = ch; ch = getchar(); if('#' = ch && i < MaxStLength) sti = ch; Identify(st); else printf("输入出错！n"); getchar();void Init() int i,j; vnNum = 0;
