搜索
《编译原理》实验指导书寿永熙编内蒙古工业大学信息工程学院计算机系2006年9月1日1《编译原理》实验教学大纲课程编号：020204006课程学时／学分：60/3实验总学时：8课程英文名称：PrinciplesCompiler课程类别：专业课开出学期：第七学期开出单位（实验室）：信息学院教学机房制定人：寿永熙教授一、制定依据根据内蒙古工业大学2003版计算机科学与技术专业培养方案和《编译原理》课程教学大纲制订本课程实验教学大纲。二、实验安排课程实验内容安排序号实验项目实验学时每组人数实验类型开出对象开出要求1实验一无符号数的有穷自动机的实现41验证本科必做２实验二语法制导把表达式翻译成逆波兰式41验证本科必做三、实验目的、内容与要求实验一无符号数的有穷自动机的实现(一)实验目的无符号数的有穷自动机的实现目的是使学生掌握文法的形式描述，穷自动机的概念。将文法转换成有穷自动机的方法，理解出错处理程序思想，如何用状态矩阵实现一个穷自动机的机内表示。(二)实验内容1．无符号数的BNF描述（0）无符号数d余留无符号数|.十进制数|e指数部分（1）余留无符号数d余留无符号数|.十进制数|e指数部分|ε（2）十进制小数d余留十进制小数（3）余留十进制小数e指数部分|d余留十进制小数|ε2（4）指数部分d余留整指数|+整指数|-整指数（5）整指数d余留整指数（6）余留整指数d余留整指数|ε2．将G[无符号数]文法转换成有穷自动机。3．构造状态矩阵；将有穷自动机的状S1S2……Sn及输入的字a1a2……am构成一个n*m的矩阵。4．用状态矩阵设计出一个词法分析程序。5．扫描无符号数，根据文法给出无符号数出错的位置。(三)实验要求1.学生课前要认真阅读实验指导，理解实验内容与相关理论知识的关系，并完成预习报告2．用C语言或其它高级语言编写程序3．写出实验报告实验二语法制导把表达式翻译成逆波兰式(一)实验目的进一步掌握语法制导翻译的概念，理解中间语言，设计出错处理程序方法，掌握把表达式翻译成中间语言的算法。(二)实验内容1．从左到右扫描中缀表达式，经语法分析找出中缀表达式出现的错误并给出错误的具体位置和类型。一个运算符栈存放暂时不能出现的运算符，逆波兰区存放逆波兰表达式。2．测试所编程序，给出正确和错误的结果。(三)实验要求1．学生课前要认真阅读实验指导，理解实验内容与相关理论知识的关系，并完成预习报告2．用C语言或其它高级语言编写程序3．写出实验报告四、考核方式及成绩评定考核方式：根据出勤、设计的程序、答辩和实验报告给出实验总成绩。成绩评定:出勤占实验总成绩的10%、程序占实验总成绩的40%、答辩占实验总成绩的30%、实验报告占实验总成绩的20%，实验总成绩占课程总成绩的10%。五、教材及主要参考资料1．教材[1]编译原理.张素琴、吕映芝编.北京:清华大学出版社，2005。3[2]编译原理实验指导书.寿永熙编.自编.2006。2．教学参考书[1]编译原理.蒋立源主编.西安:西北工业大学出版社，1998。[2]编译原理教程.寿永熙主编.呼和浩特:内蒙古大学出版社，2004。六、其它说明实验报告内容参照信息工程学院实验报告规范要求书写4实践一无符号数的有穷自动机的实现一、目的通过上机实习，熟悉词法分析程序所用的工具自动机，进一步理解自动机理论。掌握文法转换成自动机的技术及有穷自动机实现的方法。二、题目无符号数的有穷自动机的实现三、要求及提示1、无符号数的BNF描述如下：0．无符号数d余留无符号数|.十进制数|e指数部分1．余留无符号数d余留无符号数|.十进制数|e指数部分|ε2．十进制小数d余留十进制小数3．余留十进制小数e指数部分|d余留十进制小数|ε4．指数部分d余留整指数|+整指数|-整指数5．整指数d余留整指数6．余留整指数d余留整指数|ε2、将G[无符号数]文法转换成有穷自动机。3、构造状态矩阵；将有穷自动机的状S1S2……Sn及输入的字a1a2……am构成一个n*m的矩阵。1、状态矩阵设计出一个词法分析程序识别无符号数。2、扫描无符号数，根据文法给出无符号数出错的位置。3、工具：C语言或其它高级语言4、实践时间：8学时四、实践报告1、写出无符号数词法分析的思想。2、画出算法流程图。3、写出调试程序出现的问题及解决的方法。4、打印实践报告及程序清单。5、报告给出测试的结果。五、参考范例1）无符号数的文法描述如下：0．无符号数d余留无符号数|.十进制数|e指数部分51．余留无符号数d余留无符号数|.十进制数|e指数部分|ε2．十进制小数d余留十进制小数3．余留十进制小数e指数部分|d余留十进制小数|ε4．指数部分d余留整指数|+整指数|-整指数5．整指数d余留整指数6．余留整指数d余留整指数|ε2）无符号数的有穷自动机实现的思想用0-----表示无符号数；用1-----表示余留无符号数；用2----表示十进制小数；用3-----表示余留十进制小数；用4-----表示指数部分；用5-----表示整指数；用6-----表示余留整指数。输入无符号数序列，从左到右扫描，遇到“#”号结束扫描。设一个字符数组，接收输入的无符号数，对输入的无符号数逐一进行分析，用一个中间变量接收当前字符。当前字符值发生错误时，输出错误信息；当前字符值正确时，分析下一个字符，反复判断，直至分析完毕。3）无符号数的有穷自动机（Z表示结束符）无符号数有穷自动机由图1所示。图14）无符号数有穷自动机的状态转换矩阵无符号数有穷自动机的状态转换矩阵由表1所示。de·＋－ε0142ΦΦΦ1142ΦΦZ23ΦΦΦΦΦ334Φ5ΦZ46ΦΦΦ5Φ56ΦΦΦΦΦ66ΦΦΦΦZ65）算法流程图初始化读一个字符是否为#？Y是数字?读一个字符Y是#？N是小数点.NN读一个字符是数字？出错读一个字符Y是#？N是指数eN读一个字符Y出错N是符号+/-读一个字符Y是#？是数字?NY出错N是数字?N读一个字符Y是#？出错N结束YYYY76）程序清单#includestdio.hmain(){charwfh[50];/*定义数组大小为50用于存放要判断的无符号数*/inti,zf;/*定义变量*/charch1,ch2;printf(PleaseInputNumber:);/*输入要判断的无符号数*/scanf(%s,wfh);strcat(wfh,$);/*自动在输入的串末尾加入$结束符*/i=0;zf=0;/*初始时令zf=0，使得如果输入全不符合时退出*/while(wfh[i]!='$'){/*条件：输入不为结束符时执行判断*/ch1=wfh[i];/*将第一个字符送入变量ch1*/ch2=wfh[i+1];/*将次输入的字符送入变量ch2*/if(ch1='0'&&ch1='9'){/*当前字是否0-9的数字*/if((ch2='0'&&ch2='9')||ch2=='.'||ch2=='e'||ch2=='$')/*如果是数字，则判断下一个字符是否是0-9，.，E.$*/zf=1;/*输入为正确标志*/elsezf=0;/*输入为错误标志*/}if(ch1=='.'){/*如果上面条件不符合，判断是否是小数点*/if(ch2='0'&&ch2='9'||ch2=='$')/*判断小数点后是否是0-9，或为$*，否则出错?/zf=1;elsezf=0;}8if(ch1=='e'){/*判断是否是指数标志*/if(ch2='0'&&ch2='9'||ch2=='+'||ch2=='-'||ch2=='$')/*判断指数标志后是否是0-9，或是+，-，$,否则出错*/zf=1;elsezf=0;}if(ch1=='+'||ch1=='-'){/*如果以上不符，判断是否是+，-，*/if(i==0)break;/*如果是第一个输入的字符为+，-则输入错误*/if(ch2='0'&&ch2='9'||ch2=='$')/*+,-后只能为0-9，$,否则出错*/zf=1;elsezf=0;}if(zf==0)break;/*如果标志zf=0输入错，退出*/i++;/*i加1，判断下一个字符*/}if(zf==0)/*输入字符串不是无符号数*/printf(Inputnumberareerror!\n);elseprintf(Inputnumberareright!\n);/*输入字符串为无符号数*/}7）、程序运行结果测试98）调试程序出现的问题及解决的方法调试程序过程中发现一些问题主要问题如下：对于输入数据的正确与否如何表示，通过设定一个标志变量得以解决。当输入第一个字符为小数点时为正确的输入，另外还应注意到，指数的大小写输入应考虑到。9）设计体会编译原理程序是现代计算机系统的基本组成部分之一，而且多数计算机系统都有不止一个高级语言的编译程序，从功能上看，一个编译程序就是一个语言翻译程序。因此，学好编译原理这门课程对于计算机专业的学生有重要意义。通过这次实践对于无符号数有穷自动机的实现，了解了词法分析在整个编译过程中的重要作用词法分析是编译的第一个阶段，它的主要任务是从左到右扫描字符对原程序进行扫描，产生一个个单词序列，用以语法分析，其它阶段。这次实践只是对词法分析的一次模拟，词法分析阶段中分若干步骤从不确定的有穷自动机BNF到确定的有穷自动机DFA的实现，最后确定的有穷自动机DFA的最小化。本次实践只需从NFA到有穷自动机的实现。通过本次实践把理论知识转化成了实际结果，强化了理论知识的学习把课本知识生动的得到了验证。对今后从事实践工作打下了坚实的基础。10实践二语法制导把表达式翻译成逆波兰式一、目的通过上机实习加深对语法指导翻译原理的理解，掌握运算符优先权的算法，将语法分析所识别的表达式变换成中间代码的翻译方法。二、题目语法制导把表达式翻译成逆波兰式三、要求及提示1、从左到右扫描中缀表达式，经语法分析找出中缀表达式出现的错误并给出错误的具体位置和类型。2、设一个运算符栈存放暂时不能出现的运算符，逆波兰区存放逆波兰表达式。3、测试所编程序，给出正确和错误的结果。4、工具：C语言或其它高级语言5、实习时间：4学时四、实验报告1、写出逆波兰式生成的算法。2、画出算法流程图。3、写出调试程序出现的问题及解决的方法。4、打印实验报告及程序清单。5、报告给出测试的结果。五、参考范例1）表达式生成逆波兰式的算法1、初始化△送到运算符栈。2、扫描左括号“（”，把△送到运算符栈。3、扫描到变量，把它送到逆波兰区。4、扫描到运算符（1）栈内运算符比较a.栈内运算符=栈外运算符，把栈内运算符送到逆波兰区。b.栈内运算符栈外运算符，把栈外运算符入栈。(2)栈内是△把运算符入栈。5、扫描右括号“)”。(1)栈内是运算符，把栈内运算符送到逆波兰区。(2)栈内是△则△退栈，读入下一个字符。116、扫描到#（结束符）(1)栈内是运算符，把栈内运算符送到逆波兰区。(2)栈内是△结束，否则继续分析。2）表达式生成逆波兰式算法的流程图YNYNYNYNYN开始初始化运算符栈stack初始化逆波兰区exp初始化表达式区str将表达式送入表达式区str中从表达式区中取一个字符‘#’操作数‘（’运算符‘（’栈内元素送逆波兰区结束“（”入栈操作数送逆波兰区栈内运算符≥栈外运算符栈内运算符送逆波兰区栈外运算符入栈栈内元素送逆波兰区123）测试程序出现的问题及解决方法在程序的调试过程中出现了几个语法错误，根据系统的提示和查阅有关的资料改正后，程序就可以顺利的执行了。4）程序清单#defineMax100main(){charstr[Max],exp[Max],stack[Max],ch;/*定义表达式区、逆波兰区和运算