《编译原理》实验指导书(程细柱)

韶关学院《编译原理》实验指导书主编：程细柱信息工程学院计算机科学系2004年2月16日1前言“编译原理”课程是计算机本科专业的必选课程，上机实验是该课程的重要环节，应开实验数约为12学时。一个编译程序把源程序翻译成等价的目标程序，一般应做词法分析、语法分析、语义分析、代码生成和代码优化等五个方面的工作，为了使学生对其有较深的理解，必须根据这五个方面设计实验。本指导书正是根据课程的内容，将实验分为前期准备阶段、基本操作阶段和技术提高阶段三个阶段进行：①前期准备阶段的实验主要是为后续实验做好准备，应围绕编译原理课程进行设计，如：学生可根据教科书的内容，设计一个源程序的输入和扫描程序，并完成相应的设计报告；②基本操作阶段的实验是围绕着编译原理的五个方面的工作来进行，其内容主要是词法分析、语法分析、语义分析、代码生成和代码优化等，如：简单的词法分析程序、LL(1)分析法算法、语义分析程序、中间代码和目标代码生成算法的实验，这些实验基本上包括了以上知识要点，学生可结合书本上有关的知识来完成；③技术提高阶段的实验是综合性课程设计实验，根据编译原理编制应用程序，不仅要求把书本上的内容掌握好，同时还需要自学一些相关的知识。2目录第1章实验的一般知识……………………………………………………………31—1软件实验室规则及安全守则……………………………………………31－2实验条件…………………………………………………………………31—3实验的基本要求…………………………………………………………3第2章实验技术及原理……………………………………………………………3第3章实验项目……………………………………………………………………4实验一：源程序的输入和扫描（2学时）……………………………………4实验二：词法分析算法（2学时）……………………………………………6实验三：LL(1)分析算法（2学时）…………………………………………8实验四：语义分析算法（2学时）……………………………………………11实验五：中间代码生成算法（2学时）………………………………………14实验六：目标代码生成算法（4学时）………………………………………14实验七：“编译原理”课程设计（8学时）……………………………………14附录：实验报告示例：有限自动机的运行实验…………………………………………16参考文献：《编译原理》吕映芝、张素琴、蒋维杜等主编清华大学出版社《编译原理与实现》..金成植编高教出版社《编译程序设计原理》..杜淑敏王永宁编北大出版社3第1章实验的一般知识1—1软件实验室规则及安全守则见《软件实验室规则及安全守则》）。1－2实验条件1、一人一台计算机，独立完成实验。2、计算机硬件的最低配置为：PentiumⅢCPU、128MRAM、CDROM、硬盘、软驱、彩显。3、计算机软件的基本要求：PL/0编译程序和软件开发工具，如TC、VC++等。1—3实验的基本要求编译原理实验目的是要求学生在理论上掌握有关形势语言和自动机的抽象概念,在技术上能够熟练地利用各种数据结构进行编程。很具有挑战性，但同时难度也较大，它除了要求学生有较强的计算机基础知识外，还要求学生有较强的逻辑思维能力、算法设计与分析能力、编程能力。并且应能达到学生在学习完本课之后，能够对形式语言和其内部结构有一个较深刻认识的目的。第2章实验技术及原理编译原理是计算机专业中的一门专业必修课程，主要介绍编译程序把源程序翻译成等价的目标程序的过程、构造原理和实现技术，它抱括以下内容：词法分析、语法分析、语义分析、代码生成和代码优化等五个方面的工作。其实验目的要求学生通过完成相关的实验项目后，能够对形式语言和其内部结构有一个较深刻的认识。因此本实验指导书正是根据以上知识要点，将实验分为前期准备阶段、基本操作阶段和技术提高阶段三个阶段进行，希望学生能结合以前所学的知识，掌握有关形势语言和自动机的抽象概念,并且能够熟练地利用各种数据结构进行编程。4第3章实验项目实验一、源程序的输入和扫描（2学时）一、实验目的熟悉TC等语言开发工具，了解被处理语言的语法特点，为后续实验做准备。二、实验内容编制一个源程序的输入过程，从键盘、文件或文本框输入若干行语句，依次存入输入缓冲区（字符型数据）；并编制一个扫描子程序，该子程序中每次调用能依次从存放源程序的输入缓冲区中读出一个有效字符。三、实验仪器、设备及材料1、一人一台计算机，独立完成实验。2、计算机硬件的最低配置为：PentiumⅢCPU、128MRAM、CDROM、硬盘、软驱、彩显。3、计算机软件的基本要求：软件开发工具，如TC、VC++等。四、实验原理该实验属于编译原理前期准备阶段的实验，主要是为后续实验做好准备。因为词法分析第一歩就是源程序的输入和扫描，且经常被调用，故需将其设计为一个单独的程序模块。五、实验步骤（一）准备：确定开发工具，如TC、VC、VC++等；花一天时间熟悉开发工具。花二天时间确定被处理的语言的语法特点（初步确定，也可使用现成语言如Pascal、C等）。写好实验报告，编好程序。（二）上机：安装所需的开发工具，输入或拷贝程序，调试。5（三）程序要求：如源程序为C语言。输入如下一段：main(){inta,b,c;a=10;b=20;c=a+b;}要求输出与输入相同。要点：读字符的子程序作为单独一个过程（函数），每调用它一次只返回缓冲区里的一个字符，主程序连续调用它就得到完整的输出。（见右图）六、实验报告要求1.写出编程思路、源代码；2.写出上机调试时发现的问题，以及解决的过程；3.写出你所使用的测试数据；4.谈谈你的体会。七、注意事项1．该实验课约准备约2小时以上；上机一次2小时；.完成实验报告2小时上交；2．需提交程序源文件。八、思考题1.程序非常简单，但要明白该程序的作用，为什么要设计成独立的子函数？要将它和在以后的实验中进行比较，可得出这样处理的目的。2.通过练习，掌握字符处理的方法。1.主程序的部分伪代码：从输入设备接收所有输入到缓冲区While读入一字符成功显示该字符endwhile2.读入一字符的部分伪代码：if缓冲区非空then读出该字符改变缓冲区指针返回该字符else返回结束标记endif6实验二、词法分析（2学时）一、实验目的熟悉正规文法、正规式和有穷自动机，了解词法分析的主要任务，掌握词法分析是如何根据正规文法规则逐一分析词法得到属性字的，即掌握了词法分析过程。二、实验内容编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。（遇到错误时可显示“Error”，然后跳过错误部分继续显示）。三、实验仪器、设备及材料1、一人一台计算机，独立完成实验。2、计算机硬件的最低配置为：PentiumⅢCPU、128MRAM、CDROM、硬盘、软驱、彩显。3、计算机软件的基本要求：软件开发工具，如TC、VC++等。四、实验原理词法分析是编译过程的第一步，要想做好该实验，必须熟悉正规文法、正规式和有穷自动机的概念和原理，实验前须先定义好语言的正规文法或正规式，构造确定的有穷自动机，然后根椐有穷自动机设计程序模块，源程序的输入和扫描可利用实验一的结果。五、实验步骤（一）准备：1.阅读课本有关章节，花二天时间明确语言的语法，写出基本保留字、标识符、常数、运算符、分隔符和程序例。2.初步编制好程序。3.准备好多组测试数据。（二）上课上机：将源代码拷贝到机上调试，发现错误，再修改完善。第二次上机调试通过。（三）程序要求：7程序输入/输出示例：如源程序为C语言。输入如下一段：main(){inta,b;a=10;b=a+20;}要求输出如右图。要求：识别保留字：if、int、for、while、do、return、break、continue;其他的都识别为标识符；常数为无符号整形数；运算符包括：+、-、*、/、=、、、=、=、!=;分隔符包括：,、;、{、}、(、)以上为参考，具体可自行增删。程序思路（仅供参考）：0.定义部分：定义常量、变量、数据结构。1.初始化：从文件将源程序全部输入到字符缓冲区中。2.取单词前：去掉多余空白。3.取单词后：去掉多余空白（可选，看着办）。4.取单词：利用实验一的成果读出单词的每一个字符，组成单词，分析类型。（关键是如何判断取单词结束？取到的单词是什么类型的单词？）5.显示结果。（四）练习该实验的目的和思路：程序开始变得复杂起来，可能是大家以前编过的程序中最复杂的，但相对于以后的程序来说还是简单的。因此要认真把握这个过渡期的练习。程序规模大概为200行。本实验和以后的实验相关。通过练习，掌握对字符进行灵活处理的方法。六、实验报告要求（1）功能描述：该程序具有什么功能？（2）程序结构描述：函数调用格式、参数含义、返回值描述、函数功能；函数之间的调用关系图、程序总体执行流程图（参考课本第二章）。（3）实验过程记录：出错次数、出错严重程度、解决办法摘要。（3，”main”）（5，”（“）（5，”）“）（5，”{“}（3，”int”）（1，”a”）（5，”,”）（1，”b”）（5，”;”）（1，”a”）（4，”=”）（2，”10”）（5，”;”）（1，”b”）（4，”=”）（1，”a”）（4，”+”）（2，”20”）（5，”;”）（5，”}“）8（4）实验总结：你在编程过程中花时多少？多少时间在纸上设计？多少时间上机输入和调试？多少时间在思考问题？遇到了哪些难题？你是怎么克服的？你对你的程序的评价？你的收获有哪些？七、注意事项1．为了能设计好程序，应做好以下工作：①模块设计：将程序分成合理的多个模块（函数），每个模块做具体的同一事情；②写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等；③编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。2.该实验课约课余准备4小时；上机2小时；完成实验报告2小时；3．需提交：①程序源代码；②已经测试通过的测试数据3组（以“第一组输入/输出/第二组输入/输出/第三组输入/输出”的顺序存放）。八、思考题1.如何根据正规式构造有穷自动机？2．该实验的难点和重点在哪里？实验三、LL（1）分析算法（2学时）一、实验目的熟悉前面所学的语法分析过程，了解语法分析是如何根据语法规则逐一分析词法分析时所得到的属性字，以及检查语法错误的，即掌握了语法分析过程；具体来说，要求学生掌握LL(1)分析法的基本原理、掌握LL(1)分析表的构造方法、掌握LL(1)驱动程序的构造方法。二、实验内容根据课本所提供的LL（1）分析算法，编写一个语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，训练学生对常用语法进行分析的能力。本实验可以算术表达式为例完成语法分析，其的文法可以是（你可以根据需要适当改变）：E→E+T|T,T→T*F|F,F→（E）|i9根据算符优先分析法，将表达式进行语法分析，判断一个表达式是否正确。三、实验仪器、设备及材料1、一人一台计算机，独立完成实验。2、计算机硬件的最低配置为：PentiumⅢCPU、128MRAM、CDROM、硬盘、软驱、彩显。3、计算机软件的基本要求：软件开发工具，如TC、VC++等。四、实验原理LL(1)是自顶向下的语法分析方法之一，它是编译过程的第二步，要想做好该实验，必须熟悉LL(1)分析方法的基本原理，掌握表达式文法的预测分析表的构造方法；且实验前须先定义好表达式的文法规则，构造预测分析表，然后设计程序模块，并进行调试和运行。五、实验步骤（一）准备：1.阅读课本有关章节，花二天时间确定算术表达式的文法，设计出表达式文法的预测分析表；2.考虑好设计方案；3.设计出模块结构、测试数据，初步编制好程序。（二）上课上机：上机调试，发现错误，分析错误，再修改完善。教师根据学生的设计方案与学生进行探讨，以修改方案和代码。（三）程序要求：程序输入/输出示例：如参考C语言的运算符。输入如下表达式（以#为结束）和输出结果：（1）10