编译原理课程实践环节

《编译原理课程实践环节》由会员分享，可在线阅读，更多相关《编译原理课程实践环节（15页珍藏版）》请在金锄头文库上搜索。

1、编译原理课程实践环节如果你对本课程实践环节的题目、要求或内容等方面的设计有任何意见或建议，欢迎联系中山大学计算机科学系李文军老师（） 。实验题目：程序设计语言实验题目：程序设计语言 SP 的自动排版工具的自动排版工具在正式开始你的实验之前，请务必花足够时间仔细阅读完本文档关于实验的描述与约定！实验目的实验目的本实验是一个基于编译原理课程核心教学内容的综合性实验，利用一门简单程序设计语言的 处理工具设计与实现，帮助学生通过实践深入理解和牢固掌握编译技术中词法分析、语法分 析、语法制导翻译等重要环节。本实验的主要目标包括：1、 掌握词法分析器的工作原理与构造方法，并能够推广到对文本的串匹配搜索等其

2、他同类 型应用。2、 掌握词法分析器自动生成工具 lex 或类似工具的工作原理与使用方法，学习如何编写一 个 lex 源文件以解决词法分析或模式匹配问题，初步体会软件自动化的基本思路。3、 掌握递归下降的预测分析方法以及语法制导的翻译技术，学习如何根据 BNF 语法定义和 应用需求设计一个翻译模式，并利用高级程序设计语言的递归机制实现一个翻译模式。4、 掌握语法分析器自动生成工具 yacc 或类似工具的工作原理与使用方法，学习如何编写一 个 yacc 源文件以解决语法分析及语法制导翻译问题，进一步加深体会软件自动化的基本 思路。5、 通过加强设计方面的讨论与编程风格的实践，提高对面向对象设计的

3、认识，养成良好的 编程习惯与规范，并学会多个工程文档的组织与提交。李文军： 编译原理课程实践环节- 2 -程序设计语言程序设计语言 SPSP是一门支持简单算术功能的玩具型程序设计语言，易于分析和实现，适合作为语言实现 初学者的处理对象。SP语言是一门大小写无关语言，其程序中仅允许使用33个变量，其名字分别为X、Y、Z、 X0、X9、Y0、Y9、Z0、Z9；所有变量和表达式的类型均为整数类型。SP语 言仅支持四类语句，其语义描述如下：READ var从控制台读入一个int类型的值，并保存在变量var中WRITE expr将表达式expr的值输出到控制台LET var = expr将变量var的当

4、前值设置为表达式expr的值GOTO label IF expr跳转到指定的行；如果指定表达式expr，则仅当expr 0 时才跳转SP语言语法定义的完整BNF描述如下：:= | := : ; | ;:=READ |WRITE |LET = |GOTO |GOTO IF := | + | - := | * | / :=( ) | | := | := | :=a | b | . | z | A | B | . | Z:=0 | 1 | . | 9例如，以下SP源程序可用于计算两个非负整数X和Y的最大公约数：READ X; READ Y;100:GOTO 200 IF Y - X;LET X =

5、X - Y;GOTO 100;200:GOTO 300 IF X - Y;LET Y = Y - X;GOTO 100;300:WRITE X;李文军： 编译原理课程实践环节- 3 -实验一：熟悉实验一：熟悉 BNF 定义定义SP 语言的 BNF 定义给出了该语言语法方面的形式化规格说明。仔细阅读 SP 语言的 BNF 定 义，并完成以下实验内容。实验步骤步骤 1.1、编写 SP 源程序遵循 SP 语言的 BNF 定义，编写两个语法正确的 SP 源程序。要求在这两个源程序中，用到 SP 语言的所有语法构造，即你编写的两个源程序加在一起覆盖了 SP 语言提供的语句、表达 式、变量、数值等各种构造

6、。如果有可能，你编写的 SP 源程序最好是有其实际意义的，譬 如一个求阶乘的程序或一个求最小公因子的程序等。注意，这里仅要求你编写语法正确的 SP 源程序，并未强制要求这些源程序是语义正确的。然后，参考 SP 语言的 BNF 定义，编写两个含有语法错误的 SP 源程序。要求在这两个源程 序中，既包含一些词法错误（例如：不合法的标识符、不合法的常量等） ，也包含一些语法 错误（例如：括号不匹配、表达式缺少运算符、表达式缺少操作数、命令缺少关键字等） 。这些语法正确的和语法错误的 SP 源程序将在后述实验步骤中作为你的测试用例。步骤 1.2、讨论 SP 程序的二义性根据 SP 语言的 BNF 定义

7、，讨论 SP 程序的二义性问题，即讨论根据上述 BNF 定义的上下 文无关文法是否存在二义性。如果你认为该文法存在二义性，则举例说明在什么地方会出现二义性，并探讨如何改造文法 以消除二义性。如果你认为该文法没有二义性，则请解释：为何在其他高级程序设计语言中常见的那些二义 性问题在 SP 语言中并未出现？提交结果将实验一的所有结果存放在子目录 xxxNNNex1 中，其中 xxx 是你的学号的末 3 位，NNN 是你的中文姓名。例如，学号为“00184163” 、姓名为“范信果”的同学，应将其完成的实验一全部结果存放李文军： 编译原理课程实践环节- 4 -在“163 范信果范信果ex1”子目录中

8、，注意学号与姓名之间不要加空格、姓与名之间亦不要加空 格。实验一最终提交的实验结果应包括： (1) 两个语法正确的 SP 源程序，均以.sp 为文件扩展名。 (2) 两个含有词法或语法错误的 SP 源程序，均以.sp 为文件扩展名。 (3) 关于 SP 程序二义性讨论的文本文件 ambiguity.txt。 (4) 自述文件 readme.txt，给出你的姓名、学号、电子邮件、联系电话、完成日期、以及其 他补充说明。评分指南为了更好地分配时间与精力完成本次实验，你可参考以下评分标准： 项 目权重（%）1、语法正确的 SP 源程序25 2、含有词法或语法错误的 SP 源程序25 3、SP 语法的

9、二义性讨论40 4、文档组织及 readme 文件等10李文军： 编译原理课程实践环节- 5 -实验二：自动生成词法分析器（实验二：自动生成词法分析器（JFlex）实验二要求你下载一个词法分析器自动生成工具 JFlex，利用该工具自动产生 SP 语言的词 法分析器，该词法分析器的源代码是用 Java 语言编写的。实验步骤步骤 2.1、抽取 SP 语言的词法规则在 SP 语言的 BNF 定义中，既包括 SP 语言的语法定义部分，也包括 SP 语言的词法定义部 分。将词法定义从 SP 语言的 BNF 中分离出来，并写成正规定义式的形式。然后，讨论 SP 语言的词法规则与 C+/C、Java、Pas

10、cal 等常见高级程序设计语言的词法规 则相比，SP 语言的词法规则有何异同。步骤 2.2、下载词法分析器自动生成工具 JFlex实验二指定的词法分析器自动生成工具选用由 Gerwin Klein 开发的 JFlex。这是一个类似 Unix 平台上 lex 程序的开源（open source）软件工具，遵循 GNU General Public License （GPL） 。JFlex 本身采用 Java 语言编写，并且生成 Java 语言的词法分析器源程序。该软件 工具的前身是由美国普林斯顿大学计算机科学系 Elliot Berk 开发、C. Scott Ananian 负责维 护的 JLe

11、x。从http:/www.jflex.de/jflex- 1.4.1.zip可下载该工具的最新版本 1.4.1，这一压缩文件中已包含 了你在本实验中所需的各类资源，包括该工具的 Java 源代码、支持运行的库文件与脚本文 件、用户文档、输入源文件例子等。根据你自己的安装配置，修改 JFlex 安装目录下脚本文件 binjflex.bat 中的两个环境变量 JFLEX_HOME 和 JAVA_HOME 的设置。然后运行 JFlex 附带的输入源文件例子，以验证 你是否正确安装并配置了 JFlex。如果你觉得 JFlex 附带的用户手册仍不足以帮助你掌握 JFlex 的原理或用法，自己动手在网 上

12、查找其他关于 JLex、GNU Flex、lex 等类似工具的大量电子资源。步骤 2.3、生成 SP 语言的词法分析器仔细阅读 JFlex 的使用手册，根据步骤 2.1 给出的 SP 语言词法规则的正规定义式编写一个李文军： 编译原理课程实践环节- 6 -JFlex 输入源文件。生成的词法分析器须完成以下功能：逐一输出词法分析器所识别的每一个单词（token） ；输 出时，每一个单词占单独的一行；每一单词的输出信息是一个二元组，第 1 元列出该单词所 属的类别编码，第 2 元列出该单词的属性值（注意，对于一个数值类型的单词应将其字符串 转换为数值类型；尽管在屏幕上看是一样的，但你的程序中应采用

13、不同类型进行处理） 。单词的类型约定编码如下：编码单 词 类 别 01表示一个保留字。 02表示一个标识符。 03表示一个数值类型的常量。 08表示一个运算符。 09表示一个分界符。以你编写的源文件作为输入运行 JFlex，得到一个 SP 语言词法分析器的 Java 源程序；编译 该源程序生成 Java 字节码，并分别利用词法正确的和含有词法错误的 SP 源程序测试该词法 分析器。步骤 2.4、讨论不同词法分析器生成工具的差异比较以下 3 种流行的词法分析器自动生成工具之间的差异：JFlex、JLex 和 GNU Flex。主 要讨论这些软件工具接收输入源文件时，在词法规则定义方面存在的差异。

14、在网站http:/www.cs.princeton.edu/appel/modern/java/JLex/可找到关于 JLex 工具的权威 资料；关于 GNU Flex 的官方资料则位于http:/www.gnu.org/software/flex/。提交结果将实验二的所有结果存放在子目录 xxxNNNex2 中，其中 xxx 是你的学号的末 3 位，NNN 是你的中文姓名，命名规则同实验一。实验二最终提交的实验结果应包括： (1) 用正规定义式描述 SP 语言词法规则的文本文件 definition.txt；其中元符号“定义为” 用“- ”表示，空串用“epsilon”表示。紧随 SP 语言

15、词法规则之后，给出一段关于 SP 语言与其他高级语言的词法规则之异同比较。 (2) 讨论 3 种不同 lex 族软件工具词法规则定义差异的文本文件 difference.txt。 (3) 自动生成的 SP 语言词法分析器及其测试用例，包括： 3.1) 面向 SP 语言的 JFlex 输入源文件 SP.flex 以及你所需的其他相应文件。 3.2) 由 JFlex 生成的 SP 语言词法分析器的 Java 源程序 Yylex.java。 3.3) 根据 SP 词法分析器源程序编译得到的字节码文件 Yylex.class 以及其他相关的字节 码文件。李文军： 编译原理课程实践环节- 7 -3.4)

16、 以实验一给出的两个词法正确的 SP 源程序为测试用例的脚本文件 test1.bat 和 test2.bat；以实验一给出的两个含有词法错误的 SP 源程序为测试用例的脚本文件 error1.bat 和 error2.bat。 (4) 自述文件 readme.txt，给出你的姓名、学号、电子邮件、联系电话、完成日期、以及其 他补充说明。评分指南为了更好地分配时间与精力完成本次实验，你可参考以下评分标准： 项 目权重（%）1、SP 语言词法规则的正规定义式20 2、JFlex 输入源文件（正确性）30 3、生成的词法分析器的运行与测试（完整性）20 4、不同 lex 族工具差异比较20 5、文档组织及 readme 文件等10李文军： 编译原理课程实践环节- 8 -实验三：手工编写词法分析器实验三：手工编写词法分析器实验三要求你利用 Java 语言手工编写一个 SP 语言的词法