《编译原理》实验指导书2016new

1、武汉科技大学计算机科学与技术学院编译原理实验指导书实验一 词法分析器设计【实验目的】1熟悉词法分析的基本原理，词法分析的过程以及词法分析中要注意的问题。2复习高级语言，进一步加强用高级语言来解决实际问题的能力。3通过完成词法分析程序，了解词法分析的过程。【实验内容】用C语言编写一个PL/0词法分析器，为语法语义分析提供单词，使之能把输入的字符串形式的源程序分割成一个个单词符号传递给语法语义分析，并把分析结果（基本字，运算符，标识符，常数以及界符）输出。【实验要求】1 要求绘出词法分析过程的流程图。2 根据词法分析的目的以及内容，确定完成分析过程所需模块。3 写出每个模块的源代码，并给出注释。4

2、 整理程序清单及所得结果。【参考说明】PL/0的词法分析程序GETSYM是一个独立的过程，其功能是为语法语义分析提供单词，把输入的字符串形式的源程序分割成一个个单词符号传递给语法语义分析。其主要任务为：1、滤空格；2、识别基本字；3、识别标识符；4、拼数；5、拼复合词；6、输出源程序。PL/0编译程序一般设置3个全程变量：SYM：存放每个单词的类别，用内部编码形式表示；ID： 存放用户所定义的标识别符的值；NUM：存放用户定义的数。单词的种类分成5种：基本字（亦称保留字）、运算符、标识符、常数、界符。例：const a=10;const 基本字a 标识符aHH-aMdH-dM-AbM-A-aM

3、A-e分析例句：aaabd#/*-LL(1)语法分析-*/#include stdio.h#include stdlib.h#define MaxRuleNum 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 rL

4、ength;/*右部长度*/*注当rLength = 1 时，rCursor = -1为空产生式*/struct pRNode *rHead;/*右部结点头指针*/;char VnMaxVnNum + 1;/*非终结符集*/int vnNum;char VtMaxVtNum + 1;/*终结符集*/int vtNum;struct pNode PMaxRuleNum;/*产生式*/int PNum;/*产生式实际个数*/char bufferMaxPLength + 1;char ch;/*符号或string ch;*/char stMaxStLength; /*要分析的符号串*/struct

5、 collectNode/*集合元素结点结构*/int nVt;/*在终结符集中的下标*/struct collectNode *next;struct collectNode* firstMaxVnNum + 1;/*first集*/struct collectNode* followMaxVnNum + 1;/*follow集*/int analyseTableMaxVnNum + 1MaxVtNum + 1 + 1;/*预测分析表存放为产生式的编号，+1用于存放结束符，多+1用于存放#(-1)*/int analyseStackMaxStackDepth + 1;/*分析栈*/int t

6、opAnalyse;/*分析栈顶*/*int reverseStackMaxStackDepth + 1;/*颠倒顺序栈*/*int topReverse;/*倒叙栈顶*/void Init();/*初始化*/int IndexCh(char ch);/*返回Vn在Vn表中的位置+100、Vt在Vt表中的位置，-1表示未找到*/void InputVt();/*输入终结符*/void InputVn();/*输入非终结符*/void ShowChArray(char* collect, int num);/*输出Vn或Vt的内容*/void InputP();/*产生式输入*/bool Che

7、ckP(char * st);/*判断产生式正确性*/void First(int U);/*计算first集,U-xx.*/void AddFirst(int U, int nCh);/*加入first集*/bool HaveEmpty(int nVn); /*判断first集中是否有空(-1)*/void Follow(int V);/*计算follow集*/void AddFollow(int V, int nCh, int kind);/*加入follow集，kind = 0表加入follow集，kind = 1加入first集*/void ShowCollect(struct col

8、lectNode *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);/*使用产生式入栈操作*/#

9、include LL1.hvoid main(void)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(n是否继续进行句型分析？(y / n):);todo = getchar();while(y != todo & n != todo)pri

10、ntf(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;vtNum = 0;

11、PNum = 0;for(i = 0; i = MaxVnNum; i+)Vni = 0;for(i = 0; i = MaxVtNum; i+)Vti = 0;for(i = 0; i MaxRuleNum; i+)Pi.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 =

12、0; j = MaxVnNum + 1; j+)analyseTableij = -1;/*返回Vn在Vn表中的位置+100、Vt在Vt表中的位置，-1表示未找到*/int IndexCh(char ch)int n;n = 0;/*is Vn?*/while(ch != 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* coll

13、ect)int k = 0;while(0 != collectk)printf( %c , collectk+);printf(n);/*输入非终结符*/void InputVn()int inErr = 1;int 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 = Index

14、Ch(ch)Vnn+ = ch;vnNum+;ch = getchar();Vnn = #;/*以“#”标志结束用于判断长度是否合法*/k = n;/*k用于记录n以便改Vnn=0*/if(# != 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

15、/n):);scanf(%c, &ch);if(n = ch)printf(录入错误重新输入！n);inErr = 1;elseinErr = 0;/*输入终结符*/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)Vt

16、n+ = ch;vtNum+;ch = getchar();Vtn = #;/*以“#”标志结束*/k = n;/*k用于记录n以便改Vtn=0*/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

17、);if(n = ch)printf(录入错误重新输入！n);inErr = 1;elseinErr = 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+)buffern = 0;/*输入产生

18、式串*/ch = ;n = 0;while(n != (ch = getchar() & 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+;/*调试时使用*/elseprintf(输入符号含非法在成分，请重新输入！n);/*判断产

19、生式正确性*/bool CheckP(char * 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;/*=first & follow=*/*计算first集,U-xx.*/void First(int U)int i,j;for(i = 0; i PNum; i+)if(Pi.lCursor = U)struct pRNod

20、e* pt;pt = Pi.rHead;j = 0;while(j pt-rCursor)/*注:此处因编程出错,使空产生式时rlength同样是1,故此处同样可处理空产生式*/AddFirst(U, pt-rCursor);break;elseif(NULL = firstpt-rCursor - 100)First(pt-rCursor);AddFirst(U, pt-rCursor);if(!HaveEmpty(pt-rCursor)break;elsept = pt-next;j+;if(j = Pi.rLength)/*当产生式右部都能推出空时*/AddFirst(U, -1);/*

21、加入first集*/void AddFirst(int U, int nCh)/*当数值小于100时nCh为Vt*/*当处理非终结符时,AddFirst不添加空项(-1)*/struct collectNode *pt, *qt;int ch;/*用于处理Vn*/pt = NULL;qt = NULL;if(nCh nVt = nCh)break;elseqt = pt;pt = pt-next;if(NULL = pt)pt = (struct collectNode *)malloc(sizeof(struct collectNode);pt-nVt = nCh;pt-next = NUL

22、L;if(NULL = firstU - 100)firstU - 100 = pt;elseqt-next = pt;/*qt指向first集的最后一个元素*/pt = pt-next;elsept = firstnCh - 100;while(NULL != pt)ch = pt-nVt;if(-1 != ch)AddFirst(U, ch);pt = pt-next;/*判断first集中是否有空(-1)*/bool HaveEmpty(int nVn)if(nVn nVt)return true;pt = pt-next;return false;/*计算follow集,例：U-xVy

23、,U-xV.(注：初始符必含#-1)*/void Follow(int V)int i;struct pRNode *pt;if(100 = V)/*当为初始符时*/AddFollow(V, -1, 0 );for(i = 0; i rCursor != V) /*注此不能处理：U-xVyVz的情况*/pt = pt-next;if(NULL != pt)pt = pt-next;/*V右侧的符号*/if(NULL = pt)/*当V后为空时V-xV，将左符的follow集并入V的follow集中*/if(NULL = followPi.lCursor - 100 & Pi.lCursor !

24、= V)Follow(Pi.lCursor);AddFollow(V, Pi.lCursor, 0);else/*不为空时V-xVy,(注意：y-)，调用AddFollow加入Vt或y的first集*/while(NULL != pt & HaveEmpty(pt-rCursor)AddFollow(V, pt-rCursor, 1);/*y的前缀中有空时，加如first集*/pt = pt-next;if(NULL = pt)/*当后面的字符可以推出空时*/if(NULL = followPi.lCursor - 100 & Pi.lCursor != V)Follow(Pi.lCursor

25、);AddFollow(V, Pi.lCursor, 0);else/*发现不为空的字符时*/AddFollow(V, pt-rCursor, 1);/*当数值小于100时nCh为Vt*/*#用-1表示,kind用于区分是并入符号的first集，还是follow集kind = 0表加入follow集，kind = 1加入first集*/void AddFollow(int V, int nCh, int kind)struct collectNode *pt, *qt;int ch;/*用于处理Vn*/pt = NULL;qt = NULL;if(nCh nVt = nCh)break;els

26、eqt = 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;elseqt-next = pt;/*qt指向follow集的最后一个元素*/pt = pt-next;else/*为非终结符时，要区分是加first还是follow*/if(0 = kind)pt = follownCh - 100;while(NULL != p

27、t)ch = pt-nVt;AddFollow(V, ch, 0);pt = pt-next;elsept = firstnCh - 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;while(NULL != collecti)pt = collecti;printf(n%c:t, Vni);

28、while(NULL != pt)if(-1 != pt-nVt)printf( %c, Vtpt-nVt);elseprintf( #);pt = pt-next;i+;printf(n);/*计算first和follow*/void FirstFollow()int i;i = 0;while(0 != Vni)if(NULL = firsti)First(100 + i);i+;i = 0;while(0 != Vni)if(NULL = followi)Follow(100 + i);i+;/*=构造预测分析表,例：U:xyz=*/void CreateAT()int i;struct

29、 pRNode *pt;struct collectNode *ct;for(i = 0; i rCursor)/*处理非终结符，当为终结符时，定含空为假跳出*/ct = firstpt-rCursor - 100;while(NULL != ct)if(-1 != ct-nVt)analyseTablePi.lCursor - 100ct-nVt = i;ct = ct-next;pt = pt-next;if(NULL = pt)/*NULL = pt，说明xyz-,用到follow中的符号*/ct = followPi.lCursor - 100;while(NULL != ct)if(

30、-1 != ct-nVt)analyseTablePi.lCursor - 100ct-nVt = i;else/*当含有#号时*/analyseTablePi.lCursor - 100vtNum = i;ct = ct-next;elseif(100 rCursor)/*不含空的非终结符*/ct = firstpt-rCursor - 100;while(NULL != ct)analyseTablePi.lCursor - 100ct-nVt = i;ct = ct-next;else/*终结符或者空*/if(-1 = pt-rCursor)/*-1为空产生式时*/ct = follow

31、Pi.lCursor - 100;while(NULL != ct)if(-1 != ct-nVt)analyseTablePi.lCursor - 100ct-nVt = i;else/*当含有#号时*/analyseTablePi.lCursor - 100vtNum = i;ct = ct-next;else/*为终结符*/analyseTablePi.lCursor - 100pt-rCursor = i;/*输出分析表*/void ShowAT()int i,j;printf(构造预测分析表如下：n);printf(t|t);for(i = 0; i vtNum; i+)printf

32、(%ct, Vti);printf(#tn);printf(- - -t|- - -t);for(i = 0; i = vtNum; i+)printf(- - -t);printf(n);for(i = 0; i vnNum; i+)printf(%ct|t, Vni);for(j = 0; j analyseStacktopAnalyse)/*当为终结符时*/if(analyseStacktopAnalyse = IndexCh(stcurrent)/*匹配出栈，指示器后移*/Pop();current+;step+;printf(%dt, step);ShowStack();printf(tt%ctt出栈、后移n, stcurrent);elseprintf(%c-%c不匹配！, analyseStacktopAnalyse, stcurrent);printf(此串不是此文法的句子！n);return;else/*当为非终结符时*/r = analyseT