【Java开源代码栏目提醒】:网学会员为广大网友收集整理了,《编译原理》课程实践环节--程序设计语言Wren的自动排版工具 - 课程设计,希望对大家有所帮助!
《编译原理》课程实践环节如果你对本课程实践环节的题目、要求或内容等方面的设计有任何意见或建议,欢迎联系中山大学计算机科学系李文军老师(lnslwjzsu.edu.cn)。
实验题目:程序设计语言 Wren 的自动排版工具在正式开始你的实验之前,请务必花足够时间仔细阅读完本文档关于实验的描述与约定!实验目的本实验是一个基于编译原理课程核心教学内容的综合性实验,利用一门简单程序设计语言的处理工具设计与实现,帮助学生通过实践深入理解和牢固掌握编译技术中词法分析、语法分析、语法制导翻译等重要环节。
本实验的主要目标包括:1、掌握词法分析器的工作原理与构造方法,并能够推广到对文本的串匹配操作等其他同类 型应用。
2、掌握词法分析器自动生成工具 lex 或类似工具的工作原理与使用方法,学习如何编写一 个 lex 源文件以解决词法分析或模式匹配问题,初步体会软件自动化的基本思路。
3、掌握递归下降的预测分析方法以及语法制导的翻译技术,学习如何根据 BNF 语法定义和 应用需求设计一个翻译模式,并利用高级程序设计语言的递归机制实现一个翻译模式。
4、掌握语法分析器自动生成工具 yacc 或类似工具的工作原理与使用方法,学习如何编写一 个 yacc 源文件以解决语法分析及语法制导翻译问题,进一步加深体会软件自动化的基本 思路。
5、通过加强设计方面的讨论与编程风格的实践,提高对面向对象设计的认识,养成良好的 编程习惯,并学会多个工程文档的组织与提交。
李文军:《编译原理》课程实践环节程序设计语言 Wren程序设计语言Wren是一门颇为简单的命令式(imperative)语言,这类风格的语言又称为过程式(procedural)语言。
Kenneth Slonneger和Barry Kurtz设计了这门语言,并以它为实例介绍程序设计语言语法处理与语义处理的形式化途径。
对此有兴趣的同学可参考: Kenneth Slonneger and Barry Kurtz. Formal Syntax and Semantics of Programming Languages: A Laboratory Based Approach. Addison- Wesley Publishing 1995 ISBN 0-201-65697-3Wren语言的语法定义如下:ltprogramgt :: program ltidentifiergt is ltblockgtltblockgt :: ltdecl_seqgt begin ltcommand_seqgt endltdecl_seqgt :: ε ltdeclarationgt ltdecl_seqgtltdeclarationgt :: var ltvariable_listgt : lttypegt lttypegt :: integer booleanltvariable_listgt :: ltvariablegt ltvariablegt ltvariable_listgtltcommand_seqgt :: ltcommandgt ltcommandgt ltcommand_seqgtltcommandgt :: ltvariablegt : ltexprgt skip read ltvariablegt write ltinteger_exprgt while ltbool_exprgt do ltcommand_seqgt end while if ltbool_exprgt then ltcommand_seqgt end if if ltbool_exprgt then ltcommand_seqgt else ltcommand_seqgt end ifltexprgt :: ltinteger_exprgt ltbool_exprgtltinteger_exprgt :: lttermgt ltinteger_exprgt ltweak_opgt lttermgtlttermgt :: ltelementgt lttermgt ltstrong_opgt ltelementgtltelementgt :: ltnumeralgt ltvariablegt ltinteger_exprgt – ltelementgtltbool_exprgt :: ltbool_termgt ltbool_exprgt or ltbool_termgtltbool_termgt :: ltbool_elementgt ltbool_termgt and ltbool_elementgtltbool_elementgt :: true false ltvariablegt ltcomparisongt not ltbool_exprgt ltbool_exprgt ltcomparisongt :: ltinteger_exprgt ltrelationgt ltinteger_exprgtltvariablegt :: ltidentifiergtltrelationgt :: lt lt gt gt ltgtltweak_opgt :: –ltstrong_opgt :: /ltidentifiergt :: ltlettergt ltidentifiergt ltlettergt ltidentifiergt ltdigitgtltlettergt :: a b c d e f g h i j k l m n o p q r s t u v w x y zltnumeralgt :: ltdigitgt ltdigitgt ltnumeralgtltdigitgt :: 0 1 2 3 4 5 6 7 8 9 -2- 李文军:《编译原理》课程实践环节实验一:熟悉 BNF 定义 仔细阅读 Wren 语言的 BNFWren 语言的 BNF 定义给出了该语言语法方面的形式化规格说明。
定义,并完成以下实验内容。
实验步骤步骤 1.1、编写 Wren 源程序遵循 Wren 语言的 BNF 定义,编写两个语法正确的 Wren 源程序。
要求在这两个源程序中,用到 Wren 语言的所有语法构造,即你编写的两个源程序加在一起覆盖了 Wren 语言提供的声明、类型、表达式、命令、单词等各种构造。
如果有可能,你编写的 Wren 源程序最好是有其实际意义的,譬如一个求阶乘的程序、一个求最大公约数的程序等。
注意,这里仅要求你编写语法正确的 Wren 源程序,并未强制要求这些源程序是语义正确的。
然后,参考 Wren 语言的 BNF 定义,编写两个含有语法错误的 Wren 源程序。
要求在这两个源程序中,既包含一些词法错误(例如:不合法的标识符、不合法的常量等) ,也包含一些 。
语法错误(例如:括号不匹配、表达式缺少运算符、表达式缺少操作数、命令缺少关键字等)这些语法正确的和语法错误的 Wren 源程序将在后述实验步骤中作为你的测试用例。
步骤 1.2、讨论 Wren 程序的二义性根据 Wren 语言的 BNF 定义,讨论 Wren 程序的二义性问题,即讨论根据上述 BNF 定义的上下文无关文法是否存在二义性。
如果你认为该文法存在二义性,则举例说明在什么地方会出现二义性,并探讨如何改造文法以消除二义性。
如果你认为该文法没有二义性,则请解释:为何在其他高级程序设计语言中常见的那些二义性问题在 Wren 语言中并未出现?提交结果将实验一的所有结果存放在子目录 xxxNNNex1 中,其中 xxx 是你的学号的末 3 位,NNN是你的中文姓名。
例如,学号为“00184163”、姓名为“范信果”的同学,应将其完成的实验一全部结果存放在“163 范信果ex1”子目录中,注意学号与姓名之间不要加空格、姓与名之间亦不要加空格。
-3- 李文军:《编译原理》课程实践环节实验一最终提交的实验结果应包括:1 两个语法正确的 Wren 源程序,均以.wren 为文件扩展名。
2 两个含有词法或语法错误的 Wren 源程序,均以.wren 为文件扩展名。
3 关于 Wren 程序二义性讨论的文本文件 ambiguity.txt。
4 自述文件 readme.txt,给出你的姓名、学号、电子邮件、联系电话、完成日期、以及 其他补充说明。
评分指南为了更好地分配时间与精力完成本次实验,你可参考以下评分标准: 项 目 权重() 1、语法正确的 Wren 源程序 25 2、含有词法或语法错误的 Wren 源程序 25 3、Wren 语法的二义性讨论 40 4、文档组织及 readme 文件等 10 -4- 李文军:《编译原理》课程实践环节实验二:自动生成词法分析器(JFlex)实验二要求你下载一个词法分析器自动生成工具 JFlex,利用该工具自动产生 Wren 语言的词法分析器,该词法分析器的源
代码是用
Java 语言编写的。
实验步骤步骤 2.1、抽取 Wren 语言的词法规则在 Wren 语言的 BNF 定义中,既包括 Wren 语言的语法定义部分,也包括 Wren 语言的词法定义部分。
将词法定义从 Wren 语言的 BNF 中分离出来,并写成正规定义式的形式。
然后,讨论 Wren 语言的词法规则与 C/C、
Java、Pascal 等常见高级程序设计语言的词法规则相比,Wren 语言的词法规则有何异同。
步骤 2.2、下载词法分析器自动生成工具 JFlex实验二指定的词法分析器自动生成工具选用由 Gerwin Klein 开发的 JFlex。
这是一个类似 Unix平台上 lex 程序的
开源(open source)软件工具,遵循 GNU General Public License(GPL) 。
JFlex 本身采用
Java 语言编写,并且生成
Java 语言的词法分析器源程序。
该软件工具的前身是由美国普林斯顿大学计算机科学系 Elliot Berk 开发、C. Scott Ananian 负责维护的 JLex。
从http://www.jflex.de/jflex-1.4.1.zip可下载该工具的最新版本 1.4.1,这一压缩文件中已包含了你在本实验中所需的各类资源,包括该工具的
Java 源
代码、支持运行的库文件与脚本文件、用户文档、输入源文件例子等。
根据你自己的安装配置,修改 JFlex 安装目录下脚本文件 binjflex.bat 中的两个环境变量 JFLEX_HOME 和
JAVA_HOME 的设置。
然后运行 JFlex 附带的输入源文件例子,以验证你是否正确安装并配置了 JFlex。
如果你觉得 JFlex 附带的用户手册仍不足以帮助你掌握 JFlex 的原理或用法,自己动手在网上查找其他关于 JLex、GNU Flex、lex 等类似工具的大量电子资源。
步骤 2.3、生成 Wren 语言的词法分析器仔细阅读 JFlex 的使用手册,根据步骤 2.1 给出的 Wren 语言词法规则的正规定义式编写一个 JFlex 输入源文件。
生成的词法分析器须完成以下功能:逐一输出词法分析器所识别的每一个单词(token);输出时,每一个单词占单独的一行;每一单词的输出信息是一个二元组,第 1 元列出该单词所 -5- 李文军:《编译原理》课程实践环节属的类别编码,第 2 元列出该单词的属性值(注意,对于一个数值类型的单词应将其字符串 。
转换为数值类型)单词的类型约定编码如下: 编码 单 词 类 别 01 表示一个保留字。
02 表示一个标识符。
03 表示一个数值类型的常量。
04 表示一个布尔类型的常量。
08 表示一个运算符。
09 表示一个分界符。
以你编写的源文件作为输入运行 JFlex,得到一个 Wren 语言词法分析器的
Java 源程序;编译该源程序生成
Java 字节码,并分别利用词法正确的和含有词法错误的 Wren 源程序测试该词法分析器。
步骤 2.4、讨论不同词法分析器生成工具的差异比较以下 3 种流行的词法分析器自动生成工具之间的差异:JFlex、JLex 和 GNU Flex。
主要讨论这些软件工具接收输入源文件时,在词法规则定义方面存在的差异。
在网站http://www.cs.princeton.edu/appel/modern/
java/JLex/可找到关于 JLex 工具的权威资料;关于 GNU Flex 的官方资料则位于http://www.gnu.org/software/flex/。
提交结果将实验二的所有结果存放在子目录 xxxNNNex2 中,其中 xxx 是你的学号的末 3 位,NNN是你的中文姓名,命名规则同实验一。
实验二最终提交的实验结果应包括:1 用正规定义式描述 Wren 语言词法规则的文本文件 regularDef.txt;其中元符号“定 义为”用“-gt”表示,空串用“epsilon”表示。
紧随 Wren 语言词法规则之后,给出 一段关于 Wren 语言与其他高级语言的词法规则之异同比较。
2 讨论 3 种不同 lex 族软件工具词法规则定义差异的文本文件 lexDiff.txt。
3 自动生成的 Wren 语言词法分析器及其测试用例,包括: 3.1 面向 Wren 语言的 JFlex 输入源文件 wren.flex 以及你所需的其他相应文件。
3.2 由 JFlex 生成的 Wren 语言词法分析器的
Java 源程序 Yylex.
java。
3.3 根据 Wren 词法分析器源程序编译得到的字节码文件 Yylex.class 以及其他相关 的字节码文件。
3.4 以实验一给出的两个词法正确的 Wren 源程序为测试用例的脚本文件 test1.bat 和 test2.bat;以实验一给出的两个含有词法错误的 Wren 源程序为测试用例的脚本 文件 error1.bat 和 error2.bat。
4 自述文件 readme.txt,给出你的姓名、学号、电子邮件、联系电话、完成日期、以及 -6- 李文军:《编译原理》课程实践环节 其他补充说明。
评分指南为了更好地分配时间与精力完成本次实验,你可参考以下评分标准: 项 目 权重() 1、Wren 语言词法规则的正规定义式 20 2、JFlex 输入源文件(正确性) 30 3、生成的词法分析器的运行与测试(完整性) 20 4、不同 lex 族工具差异比较 20 5、文档组织及 readme 文件等 10 -7- 李文军:《编译原理》课程实践环节实验三:手工编写词法分析器实验三要求你利用
Java 语言手工编写一个 Wren 语言的词法分析器,该词法分析器执行与实验二自动生成的词法分析器完全相同的功能。
实验步骤步骤 3.1、设计程序蓝图根据实验步骤 2.1 给出的正规定义式,绘制 Wren 语言词法分析器的状态转换图。
完成这一实验步骤的正规途径是:将正规定义式转换为正规表达式,再将正规表达式转换为一个ε-NFA;经过确定化和极小化后,最终得到的 DFA(即状态转换图)可用作设计词法分析器的程序蓝图。
有能力的同学可考虑编写程序完成上述过程的自动化实现,即通过你的程序实现从正规定义式到极小化 DFA 的转换,这相当于完成了一个简化的 lex 软件工具的主要部分。
如果你想简化实验过程,可以参考课本或其他文献中类似程序设计语言(如 Pascal 语言)的词法分析器的状态转换图,手工直接画出一个编写 Wren 语言词法分析器的状态转换图。
步骤 3.2、编写词法分析器以上一步骤获得的状态转换图作为设计蓝图,利用
Java 语言手工编写一个 Wren 语言的词法分析器。
你可以直接基于命令行方式完成
Java 程序的编译与运行,也可借助 Eclipse、JBuilder、VisualCafe 一类的 IDE 环境。
但注意提交实验结果时,不要附加任何特定 IDE 的东东。
设计与编码实验三要求采用
Java 语言实现,基于面向对象风格来设计实验中的所有类,并遵循一种良好的程序设计习惯。
例如,如果你将一个程序的所有功能全部放在一个大大的 main方法中实现,这样的设计与编码风格会被扣分。
使用 JDK 提供的
java.util.StringTokenizer 类或复用类似的程序包会大大简化你的实验工作,但注意:本实验禁止使用这些现成的工具。
本实验的程序设计风格要求严格遵循 Sun 公司建议的
Java 编码习惯(具体建议请参阅 。
完成后的
代码应使用 JDK 附带的文档工具 javadoc 根据http://
java.sun.com/docs/codeconv/) -8- 李文军:《编译原理》课程实践环节源程序中的文档化注释生成相应的文档。
提交结果将实验三的所有结果存放在子目录 xxxNNNex3 中,其中 xxx 是你的学号的末 3 位,NNN是你的中文姓名,命名规则同实验一。
实验三最终提交的实验结果应包括:1 描述词法分析器状态转换图及其构造过程的一个 Word 97 兼容格式(或 PDF 格式)文档 lexerDesign.doc(或 lexerDesign.pdf) 。
2 你手工编写的 Wren 语言词法分析器及其测试用例,包括: 2.1 面向 Wren 语言的词法分析器的
Java 源程序 Lexer.
java,以及你在考虑面向对象 设计时引入的其他
Java 类的源
代码。
2.2 根据词法分析器源程序编译得到的字节码文件 Lexer.class 以及其它相关的字节 码文件。
2.3 以实验一给出的两个词法正确的 Wren 源程序为测试用例的脚本文件 test1.bat 和 test2.bat;以实验一给出的两个含有词法错误的 Wren 源程序为测试用例的脚本 文件 error1.bat 和 error2.bat。
2.4 在 doc 子目录中存放根据
Java 源
代码生成的所有 javadoc 文档。
3 自述文件 readme.txt,给出你的姓名、学号、电子邮件、联系电话、完成日期、以及 其他补充说明。
评分指南为了更好地分配时间与精力完成本次实验,你可参考以下评分标准: 项 目 权重() 1、状态转换图设计 30 2、词法分析器的源程序(正确性) 30 3、词法分析器的运行与测试(完整性) 20 4、面向对象设计与编码风格 15 5、文档组织及 readme 文件等 5 -9- 李文军:《编译原理》课程实践环节实验四:自动生成语法分析器(JavaCUP)实验四要求你下载一个语法分析器自动生成工具 JavaCUP,利用该工具自动产生一个 Wren语言的语法分析器,该语法分析器的源
代码是
Java 语言编写的。
实验步骤步骤 4.1、下载语法分析器自动生成工具 JavaCUP实验四选用由美国卡内基梅隆大学的 Scott E. Hudson 开发的一个语法分析器自动生成工具 JavaCUP。
这是一个类似 Unix 平台上 yacc 程序的
开源 (open source)软件工具,遵循 GNUGeneral Public License(GPL)。
JavaCUP 本身采用
Java 编写,并且生成
Java 语言的语法分析器源程序。
该软件工具经由美国普林斯顿大学计算机科学系 Andrew W. Appel 教授指导Frank Flannery 等人改进,目前由 C. Scott Ananian 负责维护。
从http://www.cs.princeton.edu/appel/modern/
java/CUP/
java_cup_v10k.zip可下载该软件工具的最新版本 0.10k,该压缩文件中已包含了你在实验中所需的各类资源,包括该工具的
Java 源
代码、已编译生成的字节码、简明的用户手册、以及一个简单的命令行计算器例子等。
下载后运行 JavaCUP 附带的输入源文件例子(一个基于命令行的简单计算器应用) ,以保证你正确安装并配置了 JavaCUP。
如果你觉得 JavaCUP 附带的用户手册仍不足以帮助你掌握 JavaCUP 的原理与用法,自己动手在网上查找其他关于 GNU Bison、yacc 等类似工具的大量电子资源。
步骤 4.2、生成 Wren 语言的语法分析器仔细阅读 JavaCUP 使用手册,根据 Wren 语言的 BNF 定义编写一个 JavaCUP 输入源文件。
根据你的 JavaCUP 输入源文件生成的语法分析器须完成以下功能:对于一个语法完全正确的 Wren 源程序(该源程序的排版可能很乱,但仍是语法正确的!,输出该源程序经过排版 )之后的等价
代码;排版的样式由你自己设计,例如 if-then-else 语句的两个子句如何放置、二元运算符两边是否有 1 个空格等;你可以将排版样式硬编码在你的源
代码中,但推荐你支持更灵活的用户定制功能,例如允许用户使用不同的风格或模板,甚至可以自己定义这些风格或模板。
注意 Wren 语言是大小写敏感的,据 BNF 定义 Wren 程序中禁用大写字母。
对于一个含有语法错误的 Wren 源程序,必须至少指出一处语法错误的原因及其位置(错误产生的位置定位允许有偏差),除此之外无任何其他功能需求限制;是否支持其他功能取决于你的时间、精力与能力,譬如你可以尝试在错误中恢复并继续执行语法分析,也可以执行排版任务时中途停止。
- 10 - 李文军:《编译原理》课程实践环节你在生成 Wren 语言的语法分析器时,可以直接使用实验二由 JFlex 生成的 Wren 语言的词法分析器。
以你.
上一篇:
Java论文:基于Java报表检测系统研究
下一篇:
法律专业开题报告范文