《编译原理》实验指导书.doc

武汉科技大学计算机科学与技术学院编译原理实验指导书实验一 词法分析器设计【实验目的】1熟悉词法分析的基本原理，词法分析的过程以及词法分析中要注意的问题。2复习高级语言，进一步加强用高级语言来解决实际问题的能力。3通过完成词法分析程序，了解词法分析的过程。【实验内容】用C语言编写一个PL/0词法分析器，为语法语义分析提供单词，使之能把输入的字符串形式的源程序分割成一个个单词符号传递给语法语义分析，并把分析结果（基本字，运算符，标识符，常数以及界符）输出。【实验步骤和要求】1 要求绘出词法分析过程的流程图。2 根据词法分析的目的以及内容，确定完成分析过程所需模块。3 写出每个模块的源代码，必要的部分要写明注释。4 整理程序清单及所得结果。【说明】运行成功以后，检查程序，实验报告要求分组完成个功能子程序的打印。辅助库函数scanerLib设计以及使用说明： 下面内容给出了一个辅助库函数的接口说明以及具体实现。 接口设计 /字符类 class Token TokenType type; String str; Int line; /词法分析 结果输出 操作类 class TokenWriter ArrayList tokens; /用来记录所识别出来的token TokenWriter(); /构造函数 指定输入文件名，创建文件输出流 Void Add(Token); /将词法分析器中分析得到的Token添加到tokens中 WriteXML(); /将tokens写出到目标文件.xml中 /词法分析 操作词法分析生成文件 接口 class TokenReader ArrayList tokens; TokenReader(); /构造函数 输入文件名； 初始化 Token Next(); /返回下一个Token； Token Back(); /回退一个Token，并返回回退后的当前Token ReadXML(); /从文件中读出所有Token到tokens 使用： TokenWriter tw = new TokenWriter(); While() Token tok = getToken(); Tw.Add(tok); tw.WriteXML(); TokenReader tr = new TokenReader(); Tok,ReadXML(); Token tok = new Token(); While() Tok = tr.Next(); Process(tok); 类图： TokenWriter -tokens : ArrayList -scanfile : string +TokenWriter(string) +Add(Token) : void +WriteXML() : void TokenReader -tokens : ArrayList -scanfile : string -pos : int +TokenWriter(string) +Next() : Token +Back() : Token +WriteXML() : void 操作类库源码 Token.cs /字符类 ReservedWord.cs /保留字类 TokenWriter.cs /结果输出 TokenReader.cs /操作词法分析生成文件，进行下一步的工作 使用时注意事项： 1)定义文法中涉及到的所有字符类型，修改Token.cs文件中 public enum TokenType /自己定义的所有字符类型 ; 2)对于保留字，在词法分析的过程中进行定义，例如： Hashtable reservedWords = new Hashtable(); reservedWords.Add(if,TokenType.IF); reservedWords.Add(else,TokenType.ELSE); reservedWords.Add(while,TokenType.WHILE); reservedWords.Add(return,TokenType.RETURN); reservedWords.Add(void,TokenType.VOID); reservedWords.Add(int,TokenType.INT); 可以继续添加其它的保留字；也可以讲保留字表定义为其它的类型结构进行存储。 3)进行词法分析，词法分析的过程中，可以使用Token、ReservedWord的类型定义以及TokenWriter类中给出的接口函数进行操作。 4)同时还给出了一个较复杂的语言文法的词法分析程序scanner.cs。 示例程序举例： 设置输入：prime.cm 输出：prime.xml 实验二 LL（1）语法分析程序设计 【实验目的】1熟悉判断LL（1）文法的方法及对某一输入串的分析过程。2学会构造表达式文法的预测分析表。【实验内容】编写一个语法分析程序，对于给定的输入串，能够判断识别该串是否为给定文法的句型。【实验步骤和要求】1 从键盘读入输入串，并判断正误；2 若无误，由程序自动构造FIRST、FOLLOW集以及SELECT集合，判断是否为LL（1）文法；3 若符合LL（1）文法，由程序自动构造LL（1）分析表；4 由算法判断输入符号串是否为该文法的句型。（可参考教材96页的例题1）【说明】语法分析主要是将从词法分析那里得来的记号构成一棵语法树。例：SHMA#adbe#S-aHH-aMdH-dM-AbM-A-aMA-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 rLength;/*右部长度*/*注当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 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 topAnalyse;/*分析栈顶*/*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 CheckP(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 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);/*使用产生式入栈操作*/#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)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;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+)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 = 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* collect)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 = IndexCh(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/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)Vtn+ = 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);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;/*输入产生式串*/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);/*判断产生式正确性*/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 pRNode* 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);/*加入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 = NULL;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,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 != 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);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;elseqt = 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 != pt)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);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 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(-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 = followPi.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(%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+;print