1、编译原理实验二洛阳理工学院实验报告系部计算机系班级学号姓名课程名称编译原理实验日期实验名称语法分析器成绩一、实验目的：通过预测分析算法的设计与实现，加深对自上而下语法分析方法的理解；能够采用一种编程语言实现简单的语法分析程序；能够使用自己编写的分析程序对简单的程序段进行语法翻译；加深对语法分析器工作过程的理解。二、实验内容：用预测分析法编制语法分析程序，输入文法及待分析的输入串，输出其预测分析过程及结果。三、实验要求：1.对语法规则有明确的定义； 2.编写的分析程序能够对输入的文法和待分析串进行正确的语法分析； 3.对于遇到的语法错误，能够做出简单的错误处理，给出简单的错误提示， 保证顺利完成
2、语法分析过程； 4.实验报告要求对语法定义做出详细说明，说明语法分析程序的工作过程。四、实验步骤 ：1.定义目标语言的语法规则； 2.判断文法的左递归性，将左递归文法转换成非左递归文法。（该步骤可以省略，直接输入非左递归文法）；3.根据文法求FIRST集和FOLLOW集； 4.求解预测分析方法需要的分析表； 5.输入文法及待分析的输入串，输出其预测分析过程及结果。实验内容：1. 编程思路、流程图、源代码（1）结构体的定义及结构体变量的定义（2）初始化程序，终结符与非终结符的初始化（3）构造输出分析栈函数（4）输出剩余串函数（5）预测分析表的初始化及构造（6）读入分析串，对输入串进行分析（7）输
3、出结果流程图：2.上机调试时发现的问题，以及解决的过程1.运行的结果不正确，出现输入的语法分析串不能正确的分析出来，通过修改部分输出语句实现运行结果正确2.输入的产生式出现错误，不符合输入规则，增加一项非终结符括号。运行结果：实验总结：本次实验比较复杂，但是通过上网查阅资料以及修改相应的程序，从而实现了此次的功能，这次实验让我收获了很多，学习到了语法分析相关的内容，对LL（1）文法分析的原理和过程有了进一步的巩固，也锻炼了我的编程能力，对平时所学的知识也能加深印象。也帮助复习了编译原理相关的内容。附：源程序：#include stdio.h#include stdlib.h#define Ma
4、xRuleNum 8#define MaxVnNum 5#define MaxVtNum 5#define MaxStackDepth 20#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 vnNu
5、m;char VtMaxVtNum + 1; /* 终结符集 */int vtNum;struct pNode PMaxRuleNum;int PNum;char bufferMaxPLength + 1;char ch;char stMaxStLength; /* 要分析的符号串 */struct collectNode int nVt; struct collectNode *next;struct collectNode* firstMaxVnNum + 1; /*first 集*/struct collectNode* followMaxVnNum + 1; /*follow 集*/i
6、nt analyseTableMaxVnNum + 1MaxVtNum + 1 + 1;int analyseStackMaxStackDepth + 1; /* 分析栈 */int topAnalyse; /* 分析栈顶 */void Init();/* 初始化 */int IndexCh(char ch);void InputVt(); /* 输入终结符 */void InputVn();/* 输入非终结符 */void ShowChArray(char* collect, int num);/* 输出 Vn 或 Vt 的内容 */void InputP();/* 产生式输入 */bool
7、 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 和 f
8、ollow*/void CreateAT();/* 构造预测分析表 */void ShowAT();/* 输出分析表 */void Identify(char *st);void InitStack();void ShowStack();void Pop();void Push(int r);int main() char todo,ch; Init(); InputVn(); InputVt(); InputP(); getchar(); FirstFollow(); printf( 所得 first 集为： ); ShowCollect(first); printf( 所得 follow
9、集为： ); 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 MaxS
10、tLength) 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; vtNum = 0; PNum = 0; for(i = 0; i = MaxVnNum; i+) Vni = 0; for(i = 0; i = MaxVtNum; i+) Vti = 0; for(i = 0; i MaxRuleNum; i+) P
11、i.lCursor = NULL; Pi.rHead = NULL; Pi.rLength = 0; PNum = 0; for(i = 0; i = MaxPLength; i+) bufferi = 0; for(i = 0; i MaxVnNum; i+) firsti = NULL; followi = NULL; for(i = 0; i = MaxVnNum; i+) for(j = 0; j = MaxVnNum + 1; j+) analyseTableij = -1; int IndexCh(char ch) int n; n = 0; /*is Vn?*/ while(ch
12、 != Vnn & 0 != Vnn) n+; if(0 != Vnn) return 100 + n; n = 0; /*is Vt?*/ while(ch != Vtn & 0 != Vtn) n+; if(0 != Vtn) return n; return -1;/* 输出 Vn 或 Vt 的内容 */void ShowChArray(char* collect) int k = 0; while(0 != collectk) printf( %c , collectk+); printf(n);/* 输入非终结符 */void InputVn() int inErr = 1; int
13、 n,k; char ch; while(inErr) printf(n 请输入所有的非终结符，注意： ); printf( 请将开始符放在第一位，并以 #号结束 :n); ch = ; n = 0; /* 初始化数组 */ while(n MaxVnNum) Vnn+ = 0; n = 0; while(# != ch) & (n MaxVnNum) if( != ch & n != ch & -1 = IndexCh(ch) Vnn+ = ch; vnNum+; ch = getchar(); Vnn = #; /* 以# 标志结束用于判断长度是否合法 */ k = n; if(# !=
14、ch) if( # != (ch = getchar() while(# != (ch = getchar() ; printf(n 符号数目超过限制！ n); inErr = 1; continue; /* 正确性确认，正确则，执行下下面，否则重新输入 */ Vnk = 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
15、; /* 输入终结符 */void InputVt() int inErr = 1; int n,k; char ch; while(inErr) printf(n 请输入所有的终结符，注意： ); printf( 以#号结束 :n); ch = ; n = 0; /* 初始化数组 */ while(n MaxVtNum) Vtn+ = 0; n = 0; while(# != ch) & (n MaxVtNum) if( != ch & n != ch & -1 = IndexCh(ch) Vtn+ = ch; vtNum+; ch = getchar(); Vtn = #; k = n;
16、if(# != ch) if( # != (ch = getchar() while(# != (ch = getchar() ; printf(n 符号数目超过限制！ n); inErr = 1; continue; Vtk = 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 Inp
17、utP() 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+1); /* 初始化 */ for(n =0; n MaxPLength; n+) buffern = 0; /* 输入产生式串 */ ch = ; n = 0; while(n != (ch = get
18、char() & n rCursor = IndexCh(buffer3); pt-next = NULL; Pi.rHead = pt; n = 4; while(0 != buffern) qt = (pRNode*)malloc(sizeof(pRNode); qt-rCursor = IndexCh(buffern); qt-next = NULL; pt-next = qt; pt = qt; n+; Pi.rLength = n - 3; i+; else printf( 输入符号含非法在成分，请重新输入！ n); /* 判断产生式正确性 */bool CheckP(char *
19、st) int n; if(100 IndexCh(st0) return false; if(- != st1) return false; if( != st2) return false; for(n = 3; 0 != stn; n +) if(-1 = IndexCh(stn) return false; return true;void First(int U) int i,j; for(i = 0; i PNum; i+) if(Pi.lCursor = U) struct pRNode* pt; pt = Pi.rHead; j = 0; while(j pt-rCursor)
20、 AddFirst(U, pt-rCursor); break; else if(NULL = firstpt-rCursor - 100) First(pt-rCursor); AddFirst(U, pt-rCursor); if(!HaveEmpty(pt-rCursor) break; else pt = pt-next; j+; if(j = Pi.rLength) /* 当产生式右部都能推出空时 */ AddFirst(U, -1); /* 加入 first 集*/void AddFirst(int U, int nCh) struct collectNode *pt, *qt;
21、int ch; /* 用于处理 Vn*/ pt = NULL; qt = NULL; if(nCh 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 = firstU - 100) firstU - 100 = pt; else qt-next = pt; /*qt 指向 first 集的最后一个元素 */ pt = pt-ne
22、xt; else pt = firstnCh - 100; while(NULL != pt) ch = pt-nVt; if(-1 != ch) AddFirst(U, ch); pt = pt-next; bool HaveEmpty(int nVn) if(nVn 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 rCursor != V)
23、 pt = pt-next; if(NULL != pt) pt = pt-next; if(NULL = pt) if(NULL = followPi.lCursor - 100 & Pi.lCursor != V) Follow(Pi.lCursor); AddFollow(V, Pi.lCursor, 0); else while(NULL != pt & HaveEmpty(pt-rCursor) AddFollow(V, pt-rCursor, 1); pt = pt-next; if(NULL = pt) if(NULL = followPi.lCursor - 100 & Pi.
24、lCursor != V) Follow(Pi.lCursor); AddFollow(V, Pi.lCursor, 0); else AddFollow(V, pt-rCursor, 1); void AddFollow(int V, int nCh, int kind) struct collectNode *pt, *qt; int ch; pt = NULL; qt = NULL; if(nCh 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 = followV - 100) followV - 100 = pt; else qt-next = pt; /*qt 指向 follow 集的最后一个元素 */ pt = pt-next; else if(0 = kind) pt = follownCh - 100; while(NULL != pt) ch = pt-nVt; AddFollow(V, ch, 0); pt = pt-ne
