1、厦门大学软件学院毕业设计（论文）开题报告 学生姓名 班级 学号 指导教师姓 名 职称 所在单位 厦门大学软件学院 毕业设计（论文）题 目 基于 虚拟机和解释器的游戏脚本系统 解释器模块设计 与实现 一毕业设计目标： 1. 背景介绍： 随着游戏项目规模的不断扩大，游戏内容越来越丰富，需要编辑的东西越 来越多，对数据驱动的要求也越来越高，传统的编译型语言 C/C+已无法满足游戏开发者对于语言灵活性，易用性，动态编译的需求。游戏开发趋向于将脚本语言和 C/C+等语言结合起来 。作为底层的游戏引擎大部分使用汇编语言， C/C+等语言开发，而游戏本身却用动态脚本语言来编写 。 动态脚本语言在网络游戏开发
2、中的主要优势： 1) 语法简单，易懂。脚本语言中抽象符号和古怪的语法和缩写词相对较 少， 编写 和维护容易，其结果是测试，调试和修改也变得容易 2) 动态的数据类型。变量不需要预先定义其类型，系统会在运行时自动检 查变量的类型。 3) 自动垃圾收集和内存分配。据 CERT 报告称，软件中 80%的漏洞都是由缓 冲区溢出产生的 2。脚本语言没有指针，在运行时自动处理垃圾收集和内存分配，这样就使得缓冲区溢出难以发生 。 4) 可移植性强。脚本语言与处理器，操作系统的平台无关，当脚本语言编 写的程序移植到不同的平台时，只要改变它的解释器，其他任何事情都不需要做。 5) 扩展性强。脚本语言都、非常容易
3、地与 C/C+, Java 整合。脚本语言提 供了与外界联系的接口，其他语言的组件或库可以扩展脚本语言或被脚本语言整合到一起。 6) 模块化，可重用性高。脚本语言支持模块化设计，代码可以被制作成 容 易使用的小组件。它也可以很轻松地重用到未来的项目中去。 2. 研究现状： 目前的网络游戏编程过程中大量使用游戏脚本，例如著名的网络游戏魔兽世 界中就使用 Lua 脚本。由于游戏脚本语言在 GUI 控制，人工智能，数据管理等方面的强大能力，所以经常使用脚本语言来运行 AI，处理游戏中玩家的属性等数据。如此，编写游戏引擎的编码人员就可以专注于游戏引擎的代码上，从而实现游戏引擎和游戏本身进行严格分离。这
4、样非常有利于大型游戏的开发，管理，维护和升级。 游戏开发中常用脚本语言 Python 语言 Python 是一种面向对象的脚本语言。 Python 具有非常好的可移植性 ,几乎可以运行在任何平台和操作系统上。因此 ,游戏开发人员可以利用 python 语言创建具有自己特色的游戏。 Python 通过扩展和嵌入等方式与其它语言相结合来增强它的开发能力。在 Python 语言中 ,只有极少数内置的将它与其它语言结合起来的方法。为了利用其它语言 ,开发人员需要开发一个包装程序 ,这个包装程序将 Python 中的功能参数转化到另一个语言中 ,同时将返回的结果以一种 Python 能理解方式传给 Py
5、thon。 Python 语言的主要优点包括 : (1)与 Lua 等相比 ,它有更多的扩展模块。 (2)语法简单、易读在线学习资料、案例和相关书藉相对较多。 (3)与它相关的工具相对较多。 Python 语言的主要缺点包括 : (1)它的调试器比较古怪且速度慢 ,它的执行速度慢。 (2)很难将 Python 与其它语言捆绑。 (3)很多开发人员不太喜欢它对空格符敏感这一语言特点 Lua 语言 Lua 是一个小巧简单、功能强大的语言 ,这使得 Lua 非常容易学习 ,它的完全发布版可用一张软件装下来。 Lua 有很高的执行效率 ,统计表明在众多脚本语言中 ,Lua 是平均效率最高的脚本语言 。
6、 Lua 被设计为易于扩展的 ,Lua 很容易与 C/C+、 Java,以及其它语言接口 ,可用其它语言代码来扩展功能 ,实际上它的很多功能都是通过外部库来扩展的。鉴于它卓越的扩展 性 ,可以把它作为搭建领域语言的工具 (如 :游戏脚本 )。 Lua 不是通过使用条件编译来实现平台无关的 ,而是完全使用 ANSI(ISO)C,这样只要是有 ANSIC编译器的系统都可以使用 Lua。 Lua 也存在一些不足 ,例如学习材料和文档非常少 ,自带的功能模块较少等。 Lua 在复杂游戏用户界面控制、人工智能等方面的强大功能 ,使得它在游戏开发中得到重用。例如魔兽世界的自定义界面系统就采用了 Lua,网
7、易经典“西游系列”也使用了 Lua。在游戏的开发过程中 ,开发人员一般将游戏引擎交由 C/C+等语言完成。而在用户界 面、人工智能、游戏逻辑、动态行为等游戏中经常变动的部分交予 Lua 来完成。 其它语言 Ruby 是 一 种 用 于 迅 速 和 简 便 的 面 向 对 象 编 程 的 解 释 性 脚 本 语 言 。RGSS(RubyGameScriptingSystem) 是它的一个脚本性质的游戏编程系统。RPGMakerXP(RMXP)这款制作角色扮演类游戏开发软件所使用的脚本语言就是 Ruby。RGSS 的功能有限 ,并不能用它完成一个完整的游戏 ,但随着游戏行业对网页游戏的看好和 Ro
8、R,即一个用于编写网络应用程序的框架 ,它基于计算机脚本语言 Ruby)的流行 ,Ruby 越来越 受到重视。 Erlang 是用户相对很少 ,但它非常适合分布式的 MMOG 的开发。 3. 存在的问题： 虽然动态脚本语言有许多优势，但它也存在许多不足，主要表现在 : 1) 与编译型的静态语言相比，脚本语言边解释边执行，这样虽然减少了程 序人员的编码时间和调试难度， 但它的执行速度慢，所以它不适合开发系统的底层部分，例如游戏引擎。 2) 使用游戏脚本语言写的源代码解释后的字节码容易受到攻击。 3) 游戏脚本语言缺乏对底层资源的控制和管理。 4) 英文和中文文档极度缺乏，与其他语言相比，在游戏方
9、面所作的工作和 实例都比较少。 4. 设计 目标 系统整体 目 标： 1) 设计一个简单，高效，便于扩展的基于堆栈的虚拟机，实现基本逻辑， 堆栈，函数，对象装载，异常处理，并重点关注使用垃圾收集机制实现自动内存管理。 2) 实现解释器，它将动态语言翻译成能直接在虚拟机上运行的字节码，这 个解释器应该是高效的，能够识别程序中的语法错误，并且能够对源程序进行适当优化。 3) 定义一种运行于虚拟机和解释器的简洁的动态脚本语言，它针对游戏领 域领域的特殊应用需求，提供高效的数据类型，例如散列表，并提供必要的库函数，以支持游戏开发中 最常用的功能。 4) 使用动态脚本语言开发一个小游戏，例如贪吃蛇，五子
10、棋等。以演示系 统效果，包括系统稳定性，效率等各个方面。 解释器模块设计目标： 1) 解释器把源程序作为输入，输出虚拟机可以理解的字节码文件 。经历如 下阶段：词法分析，语法分析，语义分析，代码优化和字节码 代码生成。 2) 解释执行过程灵活，正确，可方便地插入修改和调试措施，并确保执 行效率。 二实现方法 1. 基本环境 开发工具： vim, gcc, gdb 开发语言： C/C+ 开发平台： Linux 2. 系统模块划分 系统的总体架构： 解释器 视其底层的虚拟机为目标机器，生成能够直接在虚拟机上运行的字节码文件 解释器 模块的设计主要包括以下几个部分： 源程序文 件 源程序 解 释 器
11、 过程字节码文件 字节码文件 虚 拟 机 数据栈 寄存器 内存管理 3. 主要实现 方法 1) 构建词法分析器有两种方法：自己编码实现语法分析器和向专门的词法 分析器生成工具描述出词素的模式，然后将这些模式编译为具有词法分析器功能的代码。我们将优先选择用 C 语言自己编码实现词法分析器，在需要的情况下，研究或使用词法分析生成工具 Flex，实现其词法分析接口 yylex()函数 6。 2) 语法分析是解释器的核 心部分，它的任务是在词法分析识别出的词法单元 的基础上，分析并判断程序的语法结构是否符合语法规则。 语法分析的结果应该是构建语法树。 此阶段根据词法分析模块产生的词法单元， 在移进，规
12、约的过程中形成抽象语法树 1。 3) 语义分析是审查源程序有无语义错误， 语法结构是否符合语法规则， 为代码生 成阶段收集类型信息。当不符合语言规范时，解释程序应该报告错误。 4) 为了进一步提高目标代码的质量，我们采用一种简单而有效的优化技术 窥 孔优化。 它通过考查一小段目标指令并把这些指令替换为更短更快的一段指令，从而提高目标代码的质量 3。而且窥孔优化的一个特点是，优化后所产生的结果可能会给后面的优化提供进一步的机会。我们将运用常用的窥优化技术，例如冗余存取，不可达代码，控制流优化，强度削弱，删除无用操作，并借鉴 GCC 编译器的优化模块。 5) 符号表的主要操作有插入，查找以及删除等
13、。考虑到符号表对插入删除的 性能以及解决冲突的方式，我们选择哈希函数来解决。分为全局符号表和函数的符号表，全局符号表用于存储全局变量，对于每一个函数单独建立一个符号表。 词 法 分 析 器 语 法 分 析 器 语 义 分 析 器 代 码 优 化 器 错误处理器 符号表 字节码文件 代 码 生 成 源程序 4. 测试方法 在编码的每一个阶段，我们都严格执行单元测试，确保程序每一部分功能的正确性。 在系统集成阶段，逐一测试个模块之间的接口，避免接口不一致而导致错误。 最后开发一个小型的游戏，考察其稳定性，运行效果，通过与其它编译型的静态语言的横向比较和当前主流的动态脚本语言的横向比较，得出系统的优
14、势和不足。 5. 开发前的准备 了解正则表达式，自动机，编译原理相关基础知识和算法。学习垃圾收集，哈希 函数相关算法，了解系统的性能测试。 GCC 编译器的系统构架，各个模块使用的主要算法。 Java 虚拟机的类装载技术，垃圾收集算法等。 时间进度安排 阶段 起讫时间 主要完成内容 1 2008 年 11 月 17 日 -2009年 1 月 15 日 理解毕业设计，收集，阅读相关资料，熟悉开发环境，完成开题报告 2 2009 年 1 月 16 日 -2009 年 1 月 15 日 学习相关资料，提出系统的总体是设计框架 3 2009 年 1 月 16 日 -2009 年 2 月 5 日 约定虚
15、拟机提供的指令集，并形成文档 4 2009 年 2 月 6 日 -2009 年 2 月 25 日 约定脚本语言的语法规则，并形成文档 5 2009 年 2 月 26 日 -2009 年 3 月 5 日 解释器的详细设计，形成文档 6 2009 年 3 月 6 日 -2009 年 3 月 25 日 完成词法 分析器 编码，测试 ， 并提交毕业设计中 期报告 7 2009 年 3 月 26 日 -2009 年 4 月 10 日 完成语法，语义分析器编码，测试 8 2009 年 4 月 11 日 -2009 年 4 月 25 日 进行解释器优化模块设计与编码，测试 9 2009 年 4 月 26 日
16、 -2009 年 5 月 5 日 完成解释器模块的集成测试 10 2009 年 5 月 6 日 -2009 年 5 月 25 日 完成系统的集成测试，并编写演示程序 11 2009 年 5 月 26 日 -2009 年 5 月 31 日 整理文档，形成论文，准备答辩 主 要 参 考 文 献 1Alfred V.Aho； Monica S.Lam； Ravi Sethi； Jeffrey D.Ullman. Compiler Principles, Techniques and Tools， Second Edition .机械工业出版社， 2009 2陶为民，陈特放 . Java 的虚拟机的垃圾收集 .中南大学， 2007 年 3张素琴，吕映芝，将维杜，戴桂兰著 .编译原理 第二版 .清华大学出版社， 2005 年 4高勇，吴建 .语言解释器的面向对象构造模式 .西北工业大学， 2003 年 5吴作顺，窦文华 .几个常用解释器的性能分析 .国防科技大学， 2002 年 6温敬和 . LR 分析法在词法分析器自动构造中的应用 上海第二工业大学， 2000 年 导教师审核意见： 校内指导教师签名： 年 月 日
