《编译原理上机实验指导》

《编译原理》实验指导及报告书 / 学年第学期姓名：______________学号：______________班级：______________指导教师：______________计算机科学与工程学院2016编译原理实验初步一、实验目的1、熟练掌握使用CODEBLOCK进行C程序编程，提高阅读程序与调试程序的能力。

2、掌握堆栈与队列的应用。

3、掌握C语言中对字符串处理的常见函数与方法。

4、熟悉编程规范，养成对重要的程序段进行必要的注释说明。

二、实验内容与步骤1、下面的程序是对一个简单的算术表达式进行计算求值，并输出表达式的值与该表达式的后缀形式。

该程序在求值与转换后缀形式时使用了2个堆栈和1个队列。

请认真阅读程序和调试，并将程序补充完整。

#include<stdio.h>#include<malloc.h>#include<string.h>#define ERROR 0#define OK 1#define STACK_INT_SIZE 10 /*存储空间初始分配量*/#define Queue_Size 20typedef int ElemType; /*定义元素的类型*/typedef struct{char Qdata[Queue_Size];int front,rear;}SeqQueue;typedef struct{ElemType *base;ElemType *top;int stacksize; /*当前已分配的存储空间*/}SqStack;SqStack OPTR, OPND;SeqQueue SeQ;char PreTab[7][7]={{'>','>','<','<','<','>','>'},{'>','>','<','<','<','>','>'},{'>','>','>','>','<','>','>'},{'>','>','>','>','<','>','>'},{'<','<','<','<','<','=','x'},{'>','>','>','>','x','>','>'},{'<','<','<','<','<','x','='}}; // 该矩阵中，X字符表示不存在优先关系，在分析过程查找到这个值，表示表达式有错。

《编译原理》课程实验教学大纲课程编号：BS 课程名称：编译原理课内总学时：48 上机实验学时：8实验类别：□通识基础□学科基础□专业基础■专业一、实验课程目的和任务性质：本实验课程是计算机及其相关专业的专业课程，该实验是理论课程的课内上机实验环节。

目的和任务：编译原理是一门理论与实践结合紧密的课程。

通过实验，使学生加深对课内所学的有关编译过程各阶段所采用的主要算法、方法和技术等内容的理解，能把《编译原理》的相关理论运用到软件开发中。

在学生手动编写词法分析器及语法分析器的过程中，使学生对这些部分的工作机理有一个详细的了解，从而提高学生的应用程序设计能力，提高分析问题、解决问题的能力。

通过上机实验将所学理论知识与实践相结合，加深对课程的理解。

二、实验内容、学时分配及基本要求三、考核及实验报告（一）考核本课程非独立授课，实验成绩记入课程平时成绩，约占课程总成绩的10%，结合学生上实验课的课堂表现（如：有无缺勤、有无事先准备程序代码、课堂上是否认真实验以及实验结果等）及实验报告综合打分。

（二）实验报告实验报告的内容：实验名称、实验目的、实验任务、实验内容、实验过程描述（包括实验结果分析、实验过程遇到的问题及体会）。

实验报告的要求：实验报告以文本或电子档形式递交，实验报告书写要求如下：1. 问题描述：包括实验名称、目的、内容，以简洁明了的叙述说明本次上机实验的任务和目标，程序的输入和输出要求以及程序的功能。

2. 主要仪器设备：包括实验过程中所用的主要仪器设备、软件等。

3. 实验过程描述：包括源程序的各个组成部分以及算法分析过程，演示结果等。

4. 分析和体会：包括实验结果分析，测试、调试过程所遇到的问题，程序设计与实现的经验和体会，进一步改进的设想。

四、主要仪器设备硬件：微型计算机。

软件：Eclipse或Visual C++ 6.0（也可以是其它集成开发环境）。

五、教材及参考书教材[1] 王汝传．编译技术原理及其实现方法．成都科技大学出版社，1998参考书[1] 吕映芝，张素琴，蒋维杜．编译原理．清华大学出版社，1998[2] 陈火旺等．程序设计语言编译原理．国防工业出版社，2000六、说明无执笔人：蒋凌云审核人：黄海平实验院长：陈丹伟编写完成时间：2013年6月2附录1：《词法分析器的构造》综合性实验大纲一、实验目的设计、编制、调试一个词法分析程序，对单词进行识别和编码，加深对词法分析原理的理解。

《编译原理》实验指导书“编译原理”课程是计算机本科专业的必选课程，上机实验是该课程的重要环节，实验学时数为8学时。

一个编译程序把源程序翻译成等价的目标程序，一般应做词法分析、语法分析、语义分析、代码生成和代码优化等五个方面的工作，为了使学生对其有较深的理解，必须根据这五个方面设计实验。

本指导书正是根据课程的内容，将实验分为前期准备阶段、基本操作阶段和技术提高阶段三个阶段进行：①前期准备阶段的实验主要是为后续实验做好准备，应围绕编译原理课程进行设计，如：学生可根据教科书的内容，设计一个源程序的输入和扫描程序，并完成相应的设计报告；②基本操作阶段的实验是围绕着编译原理的五个方面的工作来进行，其内容主要是词法分析、语法分析、语义分析、代码生成和代码优化等，如：简单的词法分析程序、LL(1) 分析法算法、语义分析程序、中间代码和目标代码生成算法的实验，这些实验基本上包括了以上知识要点，学生可结合书本上有关的知识来完成；③技术提高阶段的实验是综合性课程设计实验，根据编译原理编制应用程序，不仅要求把书本上的内容掌握好，同时还需要自学一些相关的知识。

实验一、词法分析（2学时）一、实验目的熟悉正规文法、正规式和有穷自动机，了解词法分析的主要任务，掌握词法分析是如何根据正规文法规则逐一分析词法得到属性字的，即掌握了词法分析过程。

二、实验内容编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。

并依次输出各个单词的内部编码及单词符号自身值。

（遇到错误时可显示“Error”，然后跳过错误部分继续显示）。

三、实验原理词法分析是编译过程的第一步，要想做好该实验，必须熟悉正规文法、正规式和有穷自动机的概念和原理，实验前须先定义语言的正规文法或正规式，构造确定的有穷自动机，然后根椐有穷自动机设计程序模块，源程序的输入。

1四、实验步骤（一）准备：1.阅读课本有关章节，花二天时间明确语言的语法，写出基本保留字、标识符、常数、运算符、分隔符和程序例。

《编译原理》课程实验指导书一、使用说明《编译原理》课程实验指导书（以下简称：指导书）是针对计算机学院所开设的对应课程的上机实验而编写的教学文件，供学生上机实验时使用。

上机的工作环境要求：Windows 2000或以上操作系统、C++ 6.0或者其它高级程序设计语言。

学生应按指导教师的要求独立完成实验，并按要求撰写实验报告。

每一个实验，编程上机调试并且提交电子文档实验报告，以学号姓名作为文件名上传。

报告内容至少包含如下内容：1、学生基本情况：专业班级、学号、姓名2、实验题目、实验内容3、设计分析4、源程序代码5、测试用例（尽量覆盖所有分支）6、实验总结二、实验说明1、实验一：词法分析器设计实验类别：基础性实验实验学时：4分组人数：1人/组1、实验目的：（1）掌握词法分析器的构造过程以及基本方法。

（2）理解正规式、NFA、DFA及最小化DFA的转换过程和方法。

2、实验内容给定一个正规式R=XY*|YX*Y|XYX，请先在练习本上将此正规式转变为NFA、DFA、最小化DFA；对你所完成的最小化DFA进行编程，完成词法分析器工作。

2、实验二：算术表达式递归下降分析程序设计实验类别：设计性实验实验学时：4分组人数：1人/组1、实验目的：（1）掌握自上而下语法分析的要求与特点。

（2）掌握递归下降语法分析的基本原理和方法。

（3）掌握相应数据结构的设计方法。

2、实验内容：编程实现给定算术表达式的递归下降分析器。

算术表达式文法如下：E→E+T | TT→T*F | FF→(E) | i3、设计说明：首先改写文法为LL(1)文法；然后为每一个非终结符，构造相应的递归过程，过程的名字表示规则左部的非终结符；过程体按规则右部符号串的顺序编写。

编写者签字：刘军审阅者签字：张俊分管实验教学领导签字：王海晖。

编译原理综合实验指导书序言《编译原理综合实验》作为《编译原理》课程的延伸，其目的是让同学动手设计和实现一个简单语言的编译器和解释器。

通过上机实践，来设计这个相对完整的编译器设计，一方面可以使学生增加对编译程序的整体认识和了解——巩固《编译原理》课程所学知识，另一方面，通过上机练习，学生也可以学到很多程序调试技巧和设计大型程序一般的原则，如模块接口的协调，数据结构的合理选择等等。

一、上机实践要求（1）综合实验的成绩占总成绩的30%；（2）本次实验的所有代码都需要自行编码实现，不能用lex、yacc、JavaCC 等软件自动生成；（3）本次实验要求单人独立完成，综合实验提交的截止日期是2016-6-20；（4）本次综合实验须经授课教师当面验收考核后才予评分，否则以缺交处理；（5）实验结束后提交：源代码和实验报告。

实验报告的格式参见“实验报告模板”。

注：实验报告中不要贴代码。

二、实验内容：（一）词法分析程序的设计与实现：20分要求：设计一个词法分析程序，每调用一次就从源程序文件中顺序识别出一个单词符号。

单词种类与识别规则○1标识符：首字符为字母或’#’，其后由字母、数字或’#’组成；○2整数：由一个或多个数字组成、带正负号的数字串，首位数字不能为0；○3小数：[+|-] 正整数1 ·正整数2[+|-]：表示可选的+或-注意：正整数1不能为空，正整数2可以为空，例如：23.○4字符串：由一对双引号括起来的文本注意：字符串不需要支持多行，即假定任意一串字符串都不能超过一行；字符串不需要支持转义符。

○5保留字：class、if、then、else、call、while、do、string、integer、float、○6单目运算符：＋－* / = < >○7双目运算符：<= >= <> ==⑧布尔运算符：&& ||⑨界符：( ) { } ，；此外，该词法分析程序还要能支持单行注释和多行注释（注释语法同C语言）。

《编译原理上机实验指导》实验一词法分析1 实验目的设计编制并调试一个词法分析程序，加深对构造词法分析器的原理和技术理解与应用。

2 实验要求选择一种计算机高级程序语言子语言，运用恰当的词法分析技术线路，设计和实现其子语言的词法分析器。

语言选择，建议为《计算机程序设计》课程所采用的语言。

技术线路建议如下两种之一：正则式→NFA→DFA→min DFA→程序设计和正则文法→NFA →DFA→min DFA→程序设计。

分析器输出结果存入到磁盘文件中。

具有出错处理功能。

选择子语言方法举例。

以教材选取的PASCAL语言为例，确定其子语言涉及的单词类如下：（1）关键字begin end if then while do（2）运算符和界符:= ＋－* ／< <= <> > >= = ; ( ) ：#（3）标识符正则式：ID=letter(letter|digit)*（4）整型常数正则式：NUM= digit(digit)*3 算法设计（1）单词种别码设计（2）输出形式设计词法分析器的输入是源程序字符串，输出是对应的单词串。

每个单词按照二元组（种别码，单词符号本身）格式输出。

例如：假设源程序为begin x:=9; if x>0 then x:=2*x+1/3;end #，则词法分析器对应输出的结果是：(1,begin)(10,x)(18,:=)(11,9)(26,;)(2,if)(10,x)(23,>)(11,0)(3,then)(10,x)(18,:=)(11,2)(15, *)(10,x)(13, ＋)(11,1)(16,／)(11,3)(26,;)(6,end)(0,#)（3）算法思想依据建立的识别单词的DFA，设计算法，其框架如下。

其中，①syn存放单词的种别码；②token存放符合标识符规则的单词；③sum存放整型常量的单词。

实现技术细节注意的几个要点：A）标识符和关键字，属于同一构词规则，识别方法是建立一个关键字表，在识别出标识符单词时，查关键字表，以确认或区别是否是关键字，还是标识符。

小型编译程序的词法设计与实现本实验设计的小型编译程序涉及到编译前端的三个阶段：词法分析、语法分析和语义分析生成中间代码（四元式），编译程序的重点放在中间代码生成阶段。

编译程序的输出结果包括词法分析后的二元式序列、变量名表；语法分析后的状态栈分析过程显示；语义分析生成中间代码后的四元式程序。

整个程序分为三个部分：（1）词法分析部分（2）语法分析、语义分析及四元式生成部分（3）输出显示部分1．词法分析器设计词法分析器的功能是输入源程序，输出单词符号。

我们规定输出的单词符号格式为如下的二元式：（单词种别编码，单词自身的值）由于我们规定的程序语句中涉及单词较少，故在词法分析阶段忽略了单词输入错误的检查。

1.1 单词符号的内部定义及在编译程序中的定义我们对常量、变量、临时变量、保留关键字（if、while、begin、end、else、#define sy_if 0#define sy_then 1#define sy_else 2#define sy_while 3#define sy_begin 4#define sy_do 5#define sy_end 6#define a 7#define semicolon 8#define e 9#define jinghao 10#define S 11#define L 12#define tempsy 15#define EA 18 /*E and*/#define E0 19 /*E or*/#define plus 34#define times 36#define becomes 38#define op_and 39#define op_or 40#define op_not 41#define rop 42#define lparent 48#define rparent 49#define ident 56#define intconst 571.2 变量及数据结构说明编译程序中涉及到的变量及数据结构说明如下：char ch='\0'; /*从字符缓冲区读取当前字符*/ int count=0; /*词法分析结果缓冲区计数器*/ static char spelling[10]={""}; /*存放识别的单词符号*/static char line[81]={""}; /*一行字符缓冲区，最多80个字符*/ char *pline; /*字符缓冲区指针*/static char ntab1[100][10]; /*变量名表，共100项，每项长度10*/ struct rwords{char sp[10];int sy;}; /*保留字表的结构，用来与输入缓冲区中的单词进行匹配*/ struct rwords reswords[10]={{"if",sy_if},{"do",sy_do},{"else",sy_else},{"while",sy_while},{"then",sy_then},{"begin",sy_begin},{"end",sy_end},{"and",op_and},{"or",op_or},{"not",op_not}}; /*保留字表初始化，大小为10*/ struct aa{int sy1; /*存放单词符号的种别编码*/int pos; /*存放单词符号自身的值*/}buf[1000]； /*词法分析结果缓冲区，保存识别出来的单词符号*/ int nlength=0; /*词法分析中记录单词的长度*/int tt1=0; /*变量名表指针*/FILE *cfile; /*源程序文件， 为结束符*/int lnum=0; /*源程序行数记数*/1.3 主函数main（）void main(){cfile=fopen("pas.dat","r"); /*打开C语言源文件*/readch(); /*从源文件读一个字符*/scan(); /*词法分析*/disp1(); /*打印词法分析结果*/disp3(); /*打印词法分析变量名表*/printf("\n程序运行结束！\n");getch();}1.4 词法分析函数说明（1）读取函数 readline( )、readch( )词法分析包含从源文件读取字符的操作，但频繁的读文件会影响程序执行效率，故实际上是从源程序文件“pas.dat”中读取一行到输入缓冲区，而词法分析过程中每次读取一个字符时则是通过执行readch（）从输入缓冲区获得的；若缓冲区已被读空，则再执行readline（）从pas.dat中读取下一行至输入缓冲区。

《编译原理》实验指导书目录编译原理一共开设了三个实验，它们是：1.词法分析程序，占2个学时2.语法分析程序，占2个学时3.扩充的PL/0分析程序（综合实验），占6个学时。

实验报告格式1.姓名班级学号2.实验名称3.实验目的4.实验要求5.实验内容(这个是实验报告的主要部分)6.实验总结(实验心得)7. 实验报告人报告时间实验一 PL/O语言的词法分析程序GETSYM过程GETSYM的说明：由于一个单词往往是由一个或几个字符组成，所以在词法分析过程GETSYM中又定义一个取字符过程GETCH，由词法分析需要取字符时调用。

实验目的：1.为了更好的配合《编译原理》有关词法分析章节的教学2.加深和巩固学生对于词法分析的了解和掌握3.让学生初步的认识PL/0语言的基础和简单的程序编写4.学生通过本实验能够初步的了解和掌握程序词法分析的整个过程5.提高学生的上机和编程过程中处理具体问题的能力实验要求:1.做本实验之前要先阅读完总体的预备知识以及本实验相关的基础知识2.实验要求自己独立的完成,不允许抄袭别人的实验结果3.编写和调试过程中出现的问题最好做一下记录4.实验程序调试完成后,用给定的PL0测试程序(test.pl0)进行测试，由老师检查测试结果，并给予相应的成绩5.实验完成后,要上交实验报告。

实验内容：1.阅读所给出的词法分析程序（pl0_lexical.c），搞懂程序中每一个变量的含义，以及每一个过程的作用，并在该过程中进行中文注释。

2.阅读完程序后，画出各过程的流程图。

3.给出的程序包含两处输入错误，利用所给的pl/0源程序(test.pl0)对程序进行调试，使其能正确对所给文件进行分析并能够解释运行。

4.在阅读懂所给出的词法分析程序后，将你对词法分析的理解写在实验报告上。

实验环境：1.操作系统为Windows 2000或Dos6.2以上2.应用软件为Pascal或C语言GETCH 所用单元说明：CH ：存放当前读取的字符，初值为空，LINE：为一维数组，其数组元素是字符；界对为1：80。

编译原理课程实验上机实习中南大学计算机0706班方文一、目的加强学生对编译过程的整体认识，而不是个别阶段的实习。

二、实习要求扩充语句部分：for语句、repeat语句、case语句；三、PL语言及其编译程序1．词法分析2．语法分析3．语义分析及中间代码生成4．汇编代码生成四、扩充1．扩充repeat语句扩充文法<循环语句>::=”repeat”<语句>”until”<表达式>扩充函数：详见文件夹Assignment运行示例：示例代码：program pp;var n,p:integer;procedure p2(n:integer);beginrepeatbegincall write(n);n:=n-1enduntil n=0end;begincall p2(5)end.生成中间代码：0 JMP 0 , 15 ------> 无条件跳转1 JMP 0 ,2 ------> 无条件跳转2 ENTP 2 , 4 ------> 进入过程3 LOD 2 , 3 ------> 装入变量值4 WRITE 0 , 0 ------> 写指令5 LODA 2 , 3 ------> 装入变量地址6 LOD 2 , 3 ------> 装入变量值7 LIT 0 , 1 ------> 装入常量8 SUB 0 , 0 ------> 减9 STO 0 , 0 ------> 将栈顶值存入栈顶次值所指单元10 LOD 2 , 3 ------> 装入变量值11 LIT 0 , 0 ------> 装入常量12 EQ 0 , 0 ------> ==13 JPC 0 , 3 ------> 栈顶值为0时跳转14 RETP 0 , 0 ------> 过程返回15 ENTP 1 , 4 ------> 进入过程16 OPAC 0 , 0 ------> 打开活动记录17 LIT 0 , 5 ------> 装入常量18 CALL 1 , 2 ------> 转子19 ENDP 0 , 0 ------> 程序结束解释运行结果：Your Output:5Your Output:4Your Output:3Your Output:2Your Output:12．扩充for语句扩充文法<循环语句>::=“for”“（”<赋值语句> “;”<表达式> “;”<语句> “）”扩充函数详见文件夹Assignment运行示例示例代码：program pp;var n,p:integer;procedure p1(n:integer;var p:integer);beginfor(p:=1;p<=5;p:=p+1)begincall write(p);endend;begincall read(n);call p1(n,p);call read(n);end.生成中间代码：0 JMP 0 , 19 ------> 无条件跳转1 JMP 0 ,2 ------> 无条件跳转2 ENTP 2 , 5 ------> 进入过程3 LOD 2 ,4 ------> 装入变量值4 LIT 0 , 1 ------> 装入常量5 STO 0 , 0 ------> 将栈顶值存入栈顶次值所指单元6 ILOD 2 , 4 ------> 间接装入7 LIT 0 , 5 ------> 装入常量8 LEQ 0 , 0 ------> <=9 JPC 0 , 18 ------> 栈顶值为0时跳转10 LOD 2 , 4 ------> 装入变量值11 ILOD 2 , 4 ------> 间接装入12 LIT 0 , 1 ------> 装入常量13 ADD 0 , 0 ------> 加14 STO 0 , 0 ------> 将栈顶值存入栈顶次值所指单元15 ILOD 2 , 4 ------> 间接装入16 WRITE 0 , 0 ------> 写指令17 JMP 0 , 6 ------> 无条件跳转18 RETP 0 , 0 ------> 过程返回19 ENTP 1 , 5 ------> 进入过程20 LODA 1 , 3 ------> 装入变量地址21 READ 0 , 0 ------> 读指令22 OPAC 0 , 0 ------> 打开活动记录23 LOD 1 , 3 ------> 装入变量值24 LODA 1 , 4 ------> 装入变量地址25 CALL 1 , 2 ------> 转子26 LODA 1 , 3 ------> 装入变量地址27 READ 0 , 0 ------> 读指令28 ENDP 0 , 0 ------> 程序结束解释运行结果：29翻译开始Your Output:2Your Output:3Your Output:4Your Output:5Your Output:6翻译结束。

编译原理实验报告班级：计134班姓名：***学号：******实验一词法分析程序设计与实现一、实验目的通过编写和调试一个词法分析程序，掌握在对程序设计语言的源程序进行扫描的过程中，将字符流形式的源程序转化为一个由各类单词序列的词法分析方法。

二、基本实验内容与要求假定一种高级程序设计语言中的单词主要包括五个关键字begin、end、if、then、else；标识符；无符号常数；六种关系运算符；一个赋值符和四个算术运算符，试构造能识别这些单词的词法分析程序（各类单词的分类码可参见表1）。

输入：由符合和不符合所规定的单词类别结构的各类单词组成的源程序文件。

输出：把所识别出的每一单词均按形如（CLASS，V ALUE）的二元式形式输出，并将结果放到某个文件中。

对于标识符和无符号常数，CLASS字段为相应的类别码的助记符；V ALUE字段则是该标识符、常数的具体值；对于关键字和运算符，采用一词一类的编码形式，仅需在二元式的CLASS字段上放置相应单词的类别码的助记符，V ALUE字段则为“空”。

表1 语言中的各类单词符号及其分类码表要求：1、上机前完成词法分析程序的程序流图，并选择好相应的数据结构。

2、用于测试扫描器的实例源文件中至少应包含两行以上的源代码。

3、对于输入的测试用例的源程序文件，词法正确的单词分析结果在输出文件中以二元式形式输出，错误的字符串给出错误提示信息。

例如，若输入文件中的内容为：“if myid>=1.5E−2+100 then x:=y”，则输出文件中的内容应为：（IF，）（ID，’myid’）（GE，）（UCON，0.015）（PL，）（UCON，100）（THEN，）（ID，’x’）（IS，）（ID，’y’）三、实现方法1、一般实现方法说明词法分析是编译程序的第一个处理阶段，可以通过两种途径来构造词法分析程序。

其一是根据对语言中各类单词的某种描述或定义（如BNF），用手工的方式（例如可用C语言）构造词法分析程序。