编译原理实验指导书

1、编译原理实验指导书、八前言编译原理是计算机专业的主干课和必修课， 由于这门课程相对 抽 象且内容较复杂， 一直是比较难学的一门课程。 在编译原理的学 习过 程中，实验非常重要，只有通过上机实验，才能使学生比照拟抽 象的 课程内容产生一个具体的感性认识。本书实验环境主要为 C 环境，在 C 环境下手动生成词法分析器及语法分析器， 通过这些实验，能使学生对这些部份的工作机理有一个详细的了解。由于这门课实验难度较大，所以希望在实验前学生要做好预习工 作。在上机前写好实验预习报告。目录实验一 手工生成 PL/0 语言词法分析器 1实验二 用算符优先分析法进行表达式分析 5实验一 手工生成 PL/0 语

2、言词法分析器实验名称：手工生成 PL/0 语言词法分析器实验目的：编制一个读单词过程， 从输入的源程序中， 识别出各个具有独立意义的单词， 即根本保 留 字、标识符、常数、运算符、 分隔符五大类。 并依次输出各个单词的内部编码及单词符号自身值。遇到错误时可显示 “ Error ，然后跳过错误局部继续显示实验原理：词法分析过程1 、 PL/0 的词法分析程序 Getsym 图 1是一个独立的过程，它把输入的字符串形式的源程序分割成一个个单词符号。为此 PL/0 编译程序设置了三个全程量的公用单元如下：Sym ：存放每个单词的类别，用内部编码形式表示；Id :存放用户所定义的标识符的值，即标识符字

3、符串的机内表示；Num ：存放用户定义的数。如果我们把根本字、 运算符、界符称为语言固有的单词， 而对标识符、 常数称为用户定 义 的单词，那么经词法分析程序分出的单词，对固有的单词只给出类别存放在sym 中，而 对用户定义的单词标识符或常数既给出类别又给值，其类别存放在sym 中，值放在 id 或 num 中，全部单词种类由编译程序定义的纯量类型sumbol 给出，也可称为语法的词汇表。如下面提到的 ifsym ， thensym ， ident ， number 均属 symbol 中的元素。因此词法分析程序 Getsym 将完成以下任务:滤空格: 空格在词法分析时是一种不可缺少的界符，

4、而在语法分析时那么是无用的， 必须 滤 掉； 1 识别保存字:设有一张保存字表。对每个字母打头的字母、数字串要查此表。假设查到那么为保存字，将对应的类别放在 sym 中，如 IF 对应值 IFSYM ， THEN 对应 为 THENSYM 。假设查不到，那么认为是用户定义的标识符； 2 识别标识符:对用户定义的标识符将 IDENT 放在 SYM 中，标识符本身的值放在ID 中； 3 拼数:当所取单词是数字时，将数的类别 NUMBER 放在 SYM 中，数值本身的值 存放 在 NUM 中； 4 拼复合词:对两个字符组成的算符，如 >=， :=， <=等单词，识别后将类别送 SYM中；

5、 5 输出源程序:边读入字符边输出可输出在文件中 。 由于一个单词往往是由一个或 几个字符组成的，所以在词法分析过程Getsym 中又定义了一个取字符过程 GETCH 见图 2，由词法分析需要取字符时调用。；EK H的值迭K<10fK*-K+iAK i CHGETCH三 1DENT保存字?NUMSYM < * Nl'MBER!把谨字符转檢成对应 单恻成祈复台单词. 将其类SYM P引庄保陌字类2、GETCH所用单元说明：CH :存放当前读取的字符，初值为空；LINE :为一维数组，其数组元素是字符，界对为1 : 80。用于读入一行字符的缓冲区。LL和CC为计数器，初值为 0

6、 ;GETSYM流程图的工作单元说明：A :一维数组，数组元素为字符，界对 1 :10 ；ID ：同 A ；WORD :保存字表，一维数组，数组元素为以字符为元素的一维数组，界对为1： 13，查找方式采用二分法。图2取字符过程 GETCH实验步骤：一准备：1阅读课本有关章节，花一周时间明确语言的语法，写出根本保存字、识符、常数、运算符标分隔符和程序例。2.初步编制好程序。3.准备好多组测试数据。二上课上机：将源代码拷贝到机上调试，发现错误，再修改完善。第二次上机调试 通过。三程序要求：程序输入/输出例如：如源程序为 C语言。输入如下一段：mai nint a,b;a = 10;b = a +

7、20;要求输出如右图。要求： 识别保存字：if、int、for、while、do、return、break、continue其他的都识别为标识符；常数为无符号整形数；运算符包括：+、-、*、/、=、V、 =、v =、!=分隔符包括：，、；、估计实验时间：1.课余准备15小时；2.上机二次4小时；3.完成实验报告 5小时。(2 ,ma in)(5,( “)(5,)“)(5, “)(1 , int )(2, a)(5,，)(2, b)(5,;)(2, a)以上为参考，具体可自行增删。实验成果：1. 程序源代码 以报告形式提交 ；2. 已经测试通过的测试数据 3 组全部存在一个文本文件中附在报告后面

8、，以 输入 / 输出 /第二组输入 /输出 /第三组输入 /输出 的顺序存放 ；3. 实验报告：1功能描述：该程序具有什么功能？2程序结构描述：函数调用格式、参数含义、返回值描述、函数功能；函数之间的 关系图、程序总体执行流程图参考课本第二章 。 3 实验过程记录：出错次数、出错严重程度、解决方法摘要。4实验总结：你在编程过程中花时多少？多少时间在纸上设计？多少时间上机输入 试？多少时间在思考问题？遇到了哪些难题？你是怎么克服的？你对你的程序的评 获有哪些？第一组调用和调？你的收实验二用算符优先分析法进行表达式分析实验名称： 用算符优先法进行表达式分析实验目的 了解用算符优先分析法进行语法分析

9、的方法。实验要求从键盘输入表达式， 利用算符优先分析法求出其值，如输入表达式有错， 那么给出报错提 示表达式以；结尾。例：以于如下的输入表达式串：13+5*4 ;那么应给出结果为 33。实验原理我们要分析的表达式满足下面的算符优先矩阵0 201+-/()+>><<<>>->><<<>>>>>><>>/>>>><>>(<<<<<=)>>>>>><<<

10、;<<=实验步骤 为实现算符优先算法，可以使用两个工作栈。一个叫做OPTR，用以存放运算符，一个叫OPND,用以存放操作数或结果。算法描述如下：1 首先置操作数栈为空栈，将表达式起始符；作为运算符栈的栈底元素。2 依次读入表达式中每个单词，假设是操作数那么进OPND栈，假设是运算符那么转3。3 将此运算符 0 1与 OPTR栈顶元素0 2进行比较， 即查上表，假设e > 0 ,贝y： 0!进栈，转2。假设e 1 e,如ei为；，贝扮析成功，否那么optr栈顶元素出栈，并转。假设 01< e那么,出栈 OPND栈顶元素至 b，又出栈其栈顶元素至 a，出栈 OPTR栈顶元

11、素 至t，进行运算r=a t b (t为运算符)，并将结果r存入栈OPND后转 。假设0!和0 2之间无优先关系，那么报错。源程序提示利用以前实验生成的 Getsym ()进行单词识别，并自组织工程文件，关于算符优先算法要用到的部份函数提示如下。1 一些自定义的变量和函数的声明#defi ne MAX 255SY MBOLtitle7= PLUS,MINUS,TIMES,SLASH,LPAREN,RPAREN,SEMICOLON;用来将相应的种别码与数组下标进行映射char oo77= '>','>','<','<

12、','<','>','>',r>''<* '>I r I 5 J J 1 J 1y y i jiI)!11P>' »>f>、叩专I】JP1 TT fl'v','v','v','v','v','!','='表!'示两算符无优先; /算符优先矩阵，其中int Op关系MAX;/操作数栈 SYMBOL OPTRMAX; / 算符栈i

13、nt topd,topr;两栈的指针 void PushOp nd (int a);int PopOp nd (void);int EmptyOp nd (void);int GetTopOp nd (void);void PushOptr (S YMBOL a);SY MBOL PopOptr (void);int EmptyOptr (void);SY MBOL GetTopOptr (void);/上面为栈函数int Positio n(SY MBOL c);/将c映射至数组下标int IsOp nd(S YMBOL c);判断c是否是操作数int lsOptr(S YMBOL c);判断c是否是操作符char Precede(S YMBOL c1,S YMBOL c2);查算符优先矩阵，求出c1和c2之间的优先矩阵int Operate(i nt a,i nt b,S YMBOL o);求出a o bchar First();/算符优先分析函数2 部份函数实现的源代码(略)实验成果：1. 程序源代码(以报告形式提交)；2. 已经测试通过的测试数据3组(全部存在一个文本文件中附在报告后面，以“第一组输入/输出/第二组输入/输出/第三组