1、图灵社区会员 leezom() 专享 尊重版权图灵社区的电子书没有采用专有客户端，您可以在任意设备上，用自己喜欢的浏览器和PDF阅读器进行阅读。但您购买的电子书仅供您个人使用，未经授权，不得进行传播。我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。数字版权声明图灵社区会员 leezom() 专享 尊重版权图灵社区会员 leezom() 专享 尊重版权图灵社区会员 leezom() 专享 尊重版权 图书在版编目 （CIP） 数据 两周自制脚本语言 / （日） 千叶滋著； 陈筱烟译-北京：
2、 人民邮电出版社， 2014.6 （2016.12重印） （图灵程序设计丛书） ISBN 978-7-115-35564-5 . 两 . 千 陈 . JAVA语言程序设计 . TP312 中国版本图书馆CIP数据核字 （2014） 第093603号内 容 提 要本书是一本优秀的编译原理入门读物。全书穿插了大量轻松风趣的对话，读者可以随书中的人物一起从最简单的语言解释器开始，逐步添加新功能，最终完成一个支持函数、数组、对象等高级功能的语言编译器。本书与众不同的实现方式不仅大幅简化了语言处理器的复杂度，还有助于拓展读者的视野。 本书适合对编译原理及语言处理器设计有兴趣的读者以及正在学习相关课程的大
3、中专院校学生。同时， 已经学习过相关知识， 有一定经验的开发者， 也一定能从本书新颖的实现方式中受益良多。 著日千叶 滋 译陈筱烟 责任编辑徐骞 责任印制焦志炜 人民邮电出版社出版发行北京市丰台区成寿寺路11号 邮编100164电子邮件 网址http:/ 北京印刷 开本： 80010001/16 印张： 18.75 字数： 429千字 2014年6月第 1 版 印数： 5 001 - 5 300册 2016年12月北京第 5 次印刷著作权合同登记号图字： 01-2013-6220号定价： 59.00元读者服务热线： (010)51095186转600印装质量热线： (010)81055316反
4、盗版热线： (010)81055315广告经营许可证： 京东工商广字第8052号图灵社区会员 leezom() 专享 尊重版权译者序在大学时代，编译原理就是我十分感兴趣的一门课程。无论是手工进行语法分析计算，还是尝试设计一些简单的语言处理器，都给我留下了深刻的印象。为某些特殊用途的软件设计专用的程序设计语言，也是我一度着迷的课题。当时，阿尔弗雷德所著的编译原理技术与工具是自己包中的常客，我常带着英文原版辗转于教室、图书馆与自己的房间。怀着对编译原理的这份兴趣与热忱，我一直都希望能做一些与之相关的工作。遇到这本两周自制脚本语言 ，算是一种缘分。初见书名，我还有些犹豫。国内以速成为卖点的计算机书籍
5、不少，真正值得一读的好书却不多。诱惑读者靠走捷径学到真知，常常最终使他们绕了弯路。不过在了解到作者是东京大学和东京工业大学计算机系的资深教授后，我又对这本书产生了好奇。一位仍活跃在科研与教学第一线的学者，会怎样在两周内教会读者设计一种脚本语言呢？读完本书，我颇为惊喜，原本的担心消失殆尽。这是一本有趣而实用的书，内容编排十分独特，作为一本编译原理的入门读物，本书的很多编写思路都围绕这点展开。作者没有为了增添噱头而加入大量初学者不易理解也无需急着掌握的知识与技术，而是始终以够用为本，逐步扩展语言的语法规则，帮助读者从最基础的概念到一些常用的进阶设计理念，逐步掌握语言处理器的运行原理，以及设计一门新
6、的语言的必要步骤。书中随处可见的老师与学生、学生与学生间的轻松对话是本书的一大特色，几位性格迥异的出场人物时而为读者解惑，时而提出一些更深层次的问题，引发读者的思考。尽管书名是自制脚本语言，但本书的内容却是自制脚本语言处理器。作者花了大量篇幅讲解语言处理器的功能增强与性能优化。与同类书相比，本书使用了一种较为新颖的实现方式，能够有效简化语言处理器的设计与维护成本。尽管它还无法完全胜任实际生活中更为复杂的系统，这种解决问题的思路却对开拓读者的眼界很有帮助。得益于作者丰富的教学科研经验，本书涉及了不少实践中可能遇到的问题。作者没有直接给出解答，而是引导读者思考，无论是初学者还是有一定基础知识的读者
7、，都能在阅读本书后有新的发现。在翻译本书时，我也有所收获。其中，为了深究一些细节问题，我曾专门致信向作者请教。作者立刻对我的疑问进行了解答，并附上了细致的说明，在他的帮助下，中译本的质量得到了进一步提升。在此谨对作者的支持表示衷心的感谢。此外，中译本已经参照原书的勘误及补遗表做了修改与调整，一些细节问题得到了修正。图灵社区会员 leezom() 专享 尊重版权iv译者序在翻译过程中，我得到了许多人的帮助与支持。家人为自己创造了能够安心翻译的环境，并始终给予理解与关心。好友陈洁也为我提供了莫大的支持，使我可以每天以最佳状态投入工作。这里还要感谢图灵的各位编辑提出大量极具价值的建议与意见，帮助本书
8、顺利完成并最终问世。最后，希望对编译原理有兴趣的读者都能从本书中获益。陈筱烟2014 年 4 月于上海图灵社区会员 leezom() 专享 尊重版权前言本书是一本编译原理的入门读物。过去，大家普遍认为编译器与解释器之间存在很大的差异，因此会分别编写针对编译器与解释器的图书。不过，最近编译器与解释器之间的界限越来越模糊，我们只要稍微了解一下常见的程序设计语言，就会发现两者已不再是对立的概念。因此，与其说本书是编译原理的入门书，不如说是语言处理器的入门读物更为恰当。语言处理器是用于执行程序设计语言的软件，它同时包含了编译器与解释器。本书看似用了大量篇幅讲解解释器的原理，其实是在讲解编译器与解释器通
9、用的理论。第 1 章将详细介绍各章节的具体内容。本书采用了 Java 语言来实现语言处理器。在设计语言处理器时，C 语言或 C+ 语言更为常见，加之本书没有借助 yacc 等常用的工具来生成语言处理器，因此读者也许会认为本书的实用性不足。本书在介绍语言处理器的设计方式时，尽可能采用了较新颖的手段。C 语言或 C+ 语言结合 yacc 的方式性能较差，且是上世纪 80 年代的实现方式。在那之后，程序设计语言飞速发展，已不可同日而语，其运行性能也大幅提升。入门读物也应该与时俱进，讲解与过去不同的设计方式，展现它们的实践价值。时至今日，软件领域的发展依然日新月异，并逐渐渗透至生活的方方面面，这一势头
10、无疑将持续下去。在此期间，各类技术必将不断发展，为了跟上技术更新的步伐，软件应当以略微领先于时代的设计思路开发。很久以前，笔者曾使用 C+ 语言开发过适用于工作站的语言处理器，当时，时钟频率仅有100 兆赫，内存也不过几百兆字节。那套软件幸运地在各种环境下运行了十年以上。有一天，我收到了一封邮件。我记得好像是一个德国的年轻人，他洋洋洒洒写了很多，批评那套软件的设计有不少问题。还说开发者应当合理使用模板，并灵活运用各种库，要学习使用设计模式，还要用XML 来表示抽象语法树，等等。他指出我太节省内存，只顾着提升性能，结果程序难以阅读。从当时的主流软硬件标准来看，这些批评确实合情合理，但那套系统毕竟
11、是十年前的产物。在当时软硬件性能孱弱的情况下，如果遵循他的建议，最终完成的语言处理器恐怕会被打上缺乏使用价值的标签 （顺便一提，提出批评的那位年轻人虽然说了很多，却没有写一行代码） 。然而，从这件事中我深刻体会到，软件有着惊人的生命力，即使在开发时采用了最佳设计，最终还是会随着时代的进步而被迅速淘汰。因此，前文说软件应当以略微领先于时代的设计思路图灵社区会员 leezom() 专享 尊重版权vi前言开发有其合理性。当然，我们也可以不关心他人的批评，尽可能缩短软件的生命周期，并积极抛弃过时的内容。具体采用哪种策略因人而异。希望读者能够在阅读本书时始终记住这些理念。读过本书之后，如果大家觉得收获良
12、多，我将深感荣幸与喜悦。2012 年 新春千叶滋图灵社区会员 leezom() 专享 尊重版权推荐序本书虽然是编译原理的入门读物，但除了编译器之外，还将介绍程序设计语言的各种功能及相应实现方法的基本设计思路。不过，与现有的很多编译原理入门书不同，本书的内容十分新颖。已有的同类书大多遵循一些固定套路，以正则表达式、自动机、LL 语法、LR 语法及相关的语法分析算法等基础知识为核心，设计简化的 C 语言风格编译器。本书不仅会仔细讲解这些知识点蕴含的基本思想，还会通过现成的库来实现语言处理的词法分析与语法分析逻辑。本书仅简单讲解词法分析与语法分析等编译器的基本知识，而将重点放在语言处理器的实现上。已
13、有的同类书很少涉及各类具体的语言功能与它们的具体实现方式，本书将由简入繁，逐步修改语言处理器，介绍这些功能与实现。语言处理器最初只支持无变量声明的简单表达式，之后陆续添加函数与闭包、数组、面向对象类型、类型推论等功能，将它从解释器修改为编译器。本书采用 Java 语言来实现语言处理器，不过在多次修改后，已有的程序通常需要重写，这并非我们希望看到的。本书使用了笔者开发的语言处理工具 GluonJ，因此在添加功能时无需修改已有的代码，只需另外编写必要的程序即可。因此可以轻松更改不同功能的配置。这是一种非常理想的程序开发方式。得益于这种方式，本书能通过若干较为简短的独立程序实现语言处理器的各种功能，
14、并将完整代码收录于书中。这正是 GluonJ 的长处，如果合理设计程序结构，这种优势能进一步得到发挥，程序的扩展将更加容易。希望读者能够通过本书体会这种编程思想。本书并非一味教授基础知识，而会尽可能简明地讲解这些基本概念背后的原理。此外，乍一看类与函数是完全不同的概念，其实类是函数概念的一种延伸，本书也会对此进行说明。正文中插入了大量学生与教师的对话，时而质疑时而反驳，提供了很多相关信息，引发读者深入思考。本书是一本优秀的编译原理入门读物，它尝试以一种现代的方式设计一种现代的语言，即使读者对编译器已有一定程度的了解，也一定能从中学到很多。中田育男图灵社区会员 leezom() 专享 尊重版权致
15、谢笔者在执笔期间得到了多方帮助。其中，我要特别要感谢五十岚淳、笹田耕一，以及以学生视角审读本书草稿的栗田昂裕。中田育男老师不仅审读了草稿，还特地为本书作序，在此谨深表谢意。此外，从本书策划阶段起，技术评论社的池本公平先生一直给予我诸多照顾，非常感谢。本书使用的软件与技术是笔者日常研究中积累的成果，我要感谢研究室的各位成员。最后，我要感谢爱妻典子与孩子们，正是有了他们的支持，本书才得以顺利完成。图灵社区会员 leezom() 专享 尊重版权本书的阅读方式对话形式的补充说明在本书中随处可见。这些对话有时用于补充正文内容，有时会引入一些更深入的主题。本书的对话中将出现以下 5 个角色。 出场角色C某
16、大学的老师。程序设计语言研究室的负责人。H最年长的学生。彬彬有礼的运动型男生。F好为人师的学生。S博学的学生。平时少言寡语，一开口反而会语惊四座。A留过级，所谓的差生。不过他究竟是不是真的差生还是一个谜。图灵社区会员 leezom() 专享 尊重版权x本书的阅读方式这些出场角色纯属虚构，与现实中存在的人物没有任何关系。希望读者能够结合对话与正文，更深入地理解本书的内容。 有效利用源代码在阅读本书时，强烈建议读者下载源代码并通过 Eclipse 等集成开发环境调试。如果不使用Eclipse 之类的开发环境，用面向对象语言写成的程序将变得难以理解。读者可以从以下地址下载源代码。http:/www.
17、csg.ci.i.u-tokyo.ac.jp/chiba/files/stone-2012feb21.zip需要注意的是，在不同的程序设计环境中，源代码中的反斜杠 可能会显示为 等字符。本书将统一使用 。图灵社区会员 leezom() 专享 尊重版权目录 第1部分 基础篇第1天 来，我们一起做些什么吧 11.1机器语言与汇编语言 .21.2解释器与编译器.31.3开发语言处理器.51.4语言处理器的结构与本书的框架.6第2天 设计程序设计语言 102.1麻雀虽小、五脏俱全的程序设计语言.112.2句尾的分号.122.3含糊不得的语言.14第3天 分割单词 173.1 Token对象 .183.
18、2通过正则表达式定义单词 .193.3借助java.util.regex设计词法分析器.223.4词法分析器试运行.27第4天 用于表示程序的对象 304.1抽象语法树的定义.314.2设计节点类.344.3BNF.384.4语法分析与抽象语法树.42第5天 设计语法分析器 445.1Stone语言的语法.45图灵社区会员 leezom() 专享 尊重版权xii目录5.2使用解析器与组合子 .465.3由语法分析器生成的抽象语法树.535.4测试语法分析器.59第6天 通过解释器执行程序 626.1 eval方法与环境对象.636.2各种类型的eval方法.656.3关于GluonJ.696.
19、4执行程序 .72第7天 添加函数功能 757.1扩充语法规则.767.2作用域与生存周期.817.3执行函数 .837.4计算斐波那契数.897.5为闭包提供支持.907.6实现闭包 .92第8天 关联Java语言 958.1原生函数 .968.2编写使用原生函数的程序.98第9天 设计面向对象语言 1019.1设计用于操作类与对象的语法 .1029.2实现类所需的语法规则.1039.3实现eval方法.1049.4通过闭包表示对象.1109.5运行包含类的程序.114第10天 无法割舍的数组 11510.1扩展语法分析器.11610.2仅通过修改器来实现数组 .119图灵社区会员 leez
20、om() 专享 尊重版权目录xiii 第2部分 性能优化篇第11天 优化变量读写性能 12311.1通过简单数组来实现环境 .12411.2用于记录全局变量的环境 .12711.3事先确定变量值的存放位置.13011.4修正eval方法并最终完成性能优化.134第12天 优化对象操作性能 13712.1减少内存占用 .13812.2能否通过事先查找变量的保存位置来优化性能 .14112.3定义lookup方法.14412.4整合所有修改并执行 .14712.5内联缓存 .152第13天 设计中间代码解释器 15613.1中间代码与机器语言.15713.2Stone虚拟机.15813.3通过栈实
21、现环境.16713.4寄存器的使用 .17013.5引用变量的值 .17313.6 if语句与while语句.17313.7函数的定义与调用.17513.8转换为虚拟机器语言 .17713.9通过虚拟机执行.184第14天 为Stone语言添加静态类型支持以优化性能 18714.1指定变量类型.18814.2通过数据类型检查发现错误.19314.3运行程序时执行类型检查 .20414.4对类型省略的变量进行类型推论.20814.5Java二进制代码转换.21414.6综合所有修改再次运行程序.226图灵社区会员 leezom() 专享 尊重版权xiv目录 第3部分 解说篇（自习时间）第15天
22、手工设计词法分析器 22915.1修改自动机.23015.2自动机程序.23315.3正则表达式的极限.235第16天 语法分析方式 23616.1正则表达式与BNF.23716.2语法分析算法.23816.3LL语法分析.23916.4算符优先分析法与自底向上语法分析.244第17天 Parser库的内部结构 25117.1组合子分析.25217.2解析器组合子的内部.252第18天 GluonJ的使用方法 26318.1设定类路径.26418.2启动设定 .26518.3GluonJ语言.26718.4功能总结 .268第19天 抽象语法树与设计模式 27119.1理想的设计.27219.
23、2Interpreter模式 .27319.3Visitor模式 .27619.4使用反射 .28219.5面向切面语言.284图灵社区会员 leezom() 专享 尊重版权来，我们一起做些什么吧第1部分1第基 础篇天图灵社区会员 leezom() 专享 尊重版权某大学研究室内C 话说，我现在正在写一本新书。H 老师，您这次写的是什么主题的书呢？C 是一本和编译相关的书。确切地说，是关于语言处理器的书。F 这样啊，这次是要写成一本教科书吗？C 不，出版社要求我这次写得通俗些，所以这本书的内容会比教材来得简单。H 那这次还会像前一本书A那样，通过对话形式进行解说吗？C 这个问题现在还没有确定。有
24、人赞成用对话的形式，但也有人反对。F 老师，那这次的新书中会出现哪些人物呢？肯定会有 H 吧，毕竟这里他最年长。H 哎呀，别这么说，就算没有我也没关系。F H 肯定会出现啦。至于还会有哪些人，真是很期待呀。此外，MB那样称职的角色也必不可少。这次选谁才好呢？设计程序时使用的语言称为程序设计语言。如 Java 语言、C 语言、Ruby 语言、C+ 语言、Python 语言等，都是程序设计语言。程序员必须使用与各程序设计语言相匹配的软件来执行由该语言写成的程序。这种软件通常称为语言处理器。本章将首先说明语言处理器的基本概念。1.1机器语言与汇编语言不久后A 该不会是要让我来扮演 M 的角色吧？真是
25、这样倒也没问题，M 一直也很关照我。C 不，所有出现的人物都是虚构的，不必在意。有些程序设计语言无需借助软件执行，也就是说，它们不需要语言处理器。这些语言称为机器语言。机器语言可以由硬件直接解释执行，理论上不必使用软件。A千叶滋面向方面程序设计入门技术评论社，2005 年。B这里指的是在注 1 提到的书中出现的角色 M。来，我们一起做些什么吧基础篇第天1第1部分图灵社区会员 leezom() 专享 尊重版权1.2解释器与编译器3然而，机器语言书写的程序只有载入内存后才能通过硬件执行。因此用户在实际使用时，必须先通过软件从磁盘文件中读取机器语言程序，再将它复制至内存。不过，这类程序称不上是语言处
26、理器，通常称为操作系统 （Operating System，OS） 。A 我先打个岔，如果说操作系统是用于复制的软件，机器语言就该是其中的程序了吧。F 你是想问，机器语言是不是需要通过某种软件来复制到内存吧？C 当然需要了。这叫做引导装载程序。A 老师，我想知道的是这个引导装载程序是怎样被复制到内存中的呢？F 小 A，引导装载程序会事先写在内存中，无需复制。计算机在启动时会首先执行这个程序。C 没错，即使切断电源，引导装载程序依然会留在内存中。A 那为什么不一开始就把操作系统写入内存呢？S 那样的话，升级操作系统将会变得很麻烦。F 而且也无法实现 Windows 和 Linux 双操作系统启动
27、。C 嗯。不过要是断电后数据也不会丢失的高速内存能得到普及，预先将操作系统写入内存的计算机系统也会出现吧。汇编语言与机器语言是很容易混淆的概念，但两者并不相同。机器语言写成的程序本质上是一个位数很长的二进制数字。由于它不易于阅读，人们常通过汇编语言程序来表述这个巨大的数字，使其更易于理解。因此，如果要执行汇编语言写成的程序，用户通常需要使用软件将其转换为机器语言。这种软件称为汇编程序 （assembler） 。汇编程序可以说是一种最基本的语言处理器。1.2解释器与编译器语言处理器可大致分为解释器与编译器两种。这两类语言处理器的执行原理有很大差异。 解释器解释器根据程序中的算法执行运算。简单来讲
28、，它是一种用于执行程序的软件。如果执行的程序由虚拟机器语言或类似于机器语言的程序设计语言写成，这种软件也能称为虚拟机。 编译器编译器能将某种语言写成的程序转换为另一种语言的程序。通常它会将原程序转换为机器语言程序。编译器转换程序的行为称为编译，转换前的程序称为源代码或源程序。如果编译器没有把源代码直接转换为机器语言，一般称为源代码转换器或源码转换器 （source code translator） 。程序设计语言提供了何种类型的语言处理器不一而论，一些具有解释器，另一些则会提供编译器。例如，尽管 C 语言也提供了解释器，但却很少使用。C 语言通常直接通过编译器转换为机器语言执行。转换后得到的机
29、器语言程序会暂时保存至某个文件，需要借助操作系统来执行。图灵社区会员 leezom() 专享 尊重版权4第 1 天来，我一做些什么吧来，我一做些什么吧另一方面，Common Lisp 或 Haskell 等语言一般会同时提供解释器与编译器，供用户根据需要选用。有些语言混用解释器与编译器。通常，Java 语言首先会通过编译器把源代码转换为 Java二进制代码，并将这种虚拟的机器语言保存在文件中。之后，Java 虚拟机的解释器将执行这段代码。传统的狭义的编译器将会以文件形式保存转换后的程序。因此，只要源程序没有变更，编译就仅需执行一次，执行时间也会缩短。然而，一些编译器并不保存转换后的程序文件。这
30、种编译器常见于解释器内部。大多数 Java 虚拟机为了提高性能，会在执行过程中通过编译器将一部分 Java 二进制代码直接转换为机器语言使用。执行过程中进行的机器语言转换称为动态编译或 JIT 编译 （Just-In-Time compile） 。转换后得到的机器语言程序将被载入内存，由硬件执行，无需使用解释器。编译器的用途多样。如上所述，它能够直接在解释器内部执行。此外，编译器的作用也不局限于将源程序转换为机器语言。例如，Ruby 语言的解释器内部会通过编译器来执行预处理工作，将源程序转换为类似于 Java 二进制代码的虚拟机器语言程序。解释器真正执行的是这种经过编译的语言。这种设计提高了执
31、行性能。C 最近在解释器内部编译的例子越来越多，解释器的定义也变得模糊了呢。F 是呀。不过前面提到的 Java 源代码将首先经过编译这一点，恐怕很多人并不知道吧。H 的确如此，如果使用 Eclipse 开发 Java 程序，开发者很难看到编译过程。F Eclipse 其实已经把编译器与编辑器整合了，编译器会在开发者书写代码的同时执行编译，就好像编译始终能即时完成。C 对，开发者要意识到代码已被编译反而是一件难事。过去人们提到编译器时，首先会联想到费时的编译过程。不过由于编译后实际执行的是机器语言，因此执行速度很快。而对于解释器，人们通常认为它会在程序输入的同时立即执行，执行速度较慢。这就是两者
32、的基本区别。现代的解释器内部常采用各种类型的编译器，已经越来越没有必要将解释器与编译器区分看待。C 另外，编译器是否将源代码转换成了机器语言，并不那么易于分辨呢。A 只要编译后的文件双击后能够运行，它就是机器语言了。S 咦，但是 Java 编译后的 .jar 文件大都能双击运行不是吗？H 嗯，如果我说 .jar 文件的内部其实是机器语言，大概也会有人相信吧。C 当然了，.jar 文件内保存的是 Java 二进制代码。操作系统将会在后台启动 Java 虚拟机，并通过它来运行 .jar 文件。F Android 系统也是这种机制，它采用了名为 Dalvik 的虚拟机。图灵社区会员 leezom()
33、 专享 尊重版权1.3开发语言处理器51.3开发语言处理器本书将为极为简单的脚本语言开发语言处理器。由于对象是脚本语言，所以如果按上一节的分类方式，本书开发的语言处理器属于解释器。不过，该解释器内部将采用编译器来提高性能，因此本书也将涉及开发编译器的一些基本知识。本书不包含代码优化之类的技巧，因此不会介绍诸如编译器在将程序转换为机器语言时，如何提高机器语言的执行效率等内容。F 脚本语言这个词的含义有些模糊不是吗？C 嗯，这的确是一个无法回避的问题。H 要回答脚本语言是怎样的程序设计语言，实在是不容易。C 总之，我并不是要设计 C 语言那样的语言。不过，这类主题的书常会选择 C 语言的某些简化版
34、本作为研究对象呢。F 本书会包含通过正则表达式实现模式匹配的语法功能吗？C 我不打算介绍这些。F 本书中出现的语言，会像 Perl 那样，同一种逻辑可以通过多种方式表达吗？H 熟悉之后，只需数行就能写出复杂的功能，这也是脚本语言的一个特点了。C 你当然可以增加语法的种类，不过这就留作课后作业吧。毕竟不同语法的本质是相同的。H 也就是说不会介绍这部分内容了吗？C 是的。这只会平白增加篇幅而已。F 那本书使用的语言还能称为脚本语言吗？C 想问的是这个啊？这种语言支持动态数据类型，无需事先声明变量，且通过解释器运行。其实本书的主题应该是以现代的手法来设计现代语言。A 这样一来，这本书会变成什么样子呢
35、？或许会有人说书的标题与内容不符了吧。本书将设计的语言命名为 Stone 语言。实现该语言的开发语言是 Java 语言。因此，Stone 语言也是一种运行于 Java 虚拟机的语言。H 老师，还是说明一下“实现”这个词的含义比较好吧？C 这里的实现 （implementation） 指的是通过程序来实现某种功能。把它理解为书写程序也可以。F 说来，Stone 语言的命名灵感是来自 Perl 语言和 Ruby 语言对吧？C 没错。它称不上是宝石，顶多算是小石子，因此取名为 Stone。Stone 语言运行于 Java 虚拟机，并不轻巧。之所以选择 Java 语言，是为了以面向对象的方式设计语言处
36、理器。语言处理器的复杂度适中，常用于实验或论证各种语言范型的性能。例如，Haskell 语言或 OCaml 语言之类的函数型语言，非常适合开发语言处理器。面向对象语言也是如此。本书在讲解时，默认读者十分了解面向对象语言，尤其是 Java 语言的基本编程方式。图灵社区会员 leezom() 专享 尊重版权6第 1 天来，我一做些什么吧来，我一做些什么吧A 如果是要使用面向对象语言，Ruby 语言或 Scala 语言这些不可以吗？C 这个嘛它可能会赶跑一部分读者，编辑或许会否决这个提议的吧。H 那用 C 语言和 yacc 来实现的话如何？老师您觉得这样可以吗？C 嗯，C 语言本身没什么不好，但要实
37、现稍微复杂些的语言处理器时，就不得不使用各种不同的编程技术。最终写出的 C 语言程序会具有面向对象风格，那还不如从最开始就使用面向对象语言。S 我倒是觉得以函数式语言风格来写 C 语言代码也挺好。H 如果要写一本设计 TinyC 编译器的书，C 语言会是个不错的选择吧。C 此外，这里不会使用 yacc 相关的外部工具。我打算用其他方法来设计。1.4语言处理器的结构与本书的框架无论是解释器还是编译器，语言处理器前半部分的程序结构都大同小异。如图 1.1 所示，源代码首先将进行词法分析，由一长串字符串细分为多个更小的字符串单元。分割后的字符串称为单词。之后处理器将执行语法分析处理，把单词的排列转换
38、为抽象语法树。至此为止，解释器与编译器的处理方式相同。之后，编译器将会把抽象语法树转换为其他语言，而解释器将会一边分析抽象语法树一边执行运算。F 首先需要把源代码转换为抽象语法树没错吧？C 程序的分析结果能由抽象语法树表现，因此无论是解释器还是编译器都需要用到抽象语法树。词法分析源代码（一长串整行相连的字符串）语法分析单词排列（简短字符串的排列）代码生成执行抽象语法树其他语言（如机器语言）的程序程序的执行结果【编译器】【解释器】 图1.1 语言处理器内部的处理流程图灵社区会员 leezom() 专享 尊重版权1.4语言处理器的结构与本书的框架7今后，本书将根据这一流程开发 Stone 语言的处
39、理器。各章内容如下所示。第 1 部分基础篇设计 Stone 语言的解释器。第 28 章将实现一个具有基本功能的解释器。第 910 章将介绍一些高级内容。 第 1 章 （第 1 天）本章。 第 2 章 （第 2 天）第 2 章将设计 Stone 语言，决定 Stone 语言需要具备哪些语法功能。 第 3 章 （第 3 天）第 3 章将设计词法分析器，介绍通过正则表达式实现词法分析的方法。 第 4 章 （第 4 天）第 4 章将讲解抽象语法树，并通过 BNF 表达 Stone 语言的语法。 第 5 章 （第 5 天）第 5 章将利用非常简单的解析器组合子库来创建语法解释器。解析器组合子库的内部结构
40、将在第 17 章进行说明。 第 6 章 （第 6 天）第 6 章将设计一种极为基本的解释器。在这一章结束后，解释器将能够实际执行 Stone 语言写成的程序。本书采用了 GluonJ 这一系统来设计解释器的程序，因此这一章还会简单介绍GluonJ 的使用方法。 第 7 章 （第 7 天）第 7 章将增强解释器的功能，使它能够执行程序中的函数，并且支持闭包语法。 第 8 章 （第 8 天）第 8 章将为解释器增加 static 方法的调用支持，使 Stone 语言能像 Java 语言那样调用静态方法。 第 9 章 （第 9 天）第 9 章将为 Stone 语言新增类与对象的语法。本章将使用闭包来
41、实现该功能。 第 10 章 （第 10 天）第 10 章将为 Stone 语言增加数组功能。图灵社区会员 leezom() 专享 尊重版权8第 1 天来，我一做些什么吧来，我一做些什么吧第 2 部分性能优化篇第 2 部分将对第 1 部分设计的 Stone 语言解释器进行性能优化。其中，第 13 章将介绍如何设计 Stone 语言的编译器，帮助提高性能。如果读者仅对编译器的设计方法感兴趣，只需阅读第11 章与第 13 章即可。 第 11 章 （第 11 天）程序不应在访问变量时每次都搜索变量名，而应首先搜索事先分配好的编号，提高访问性能。 第 12 章 （第 12 天）同样地，程序在调用对象的方
42、法或引用其中的字段时，也不应直接搜索其名称，而应搜索编号。此外，第 12 章还会为 Stone 语言的解释器增加内联缓存，进一步优化性能。 第 13 章 （第 13 天）Stone 语言的解释器也采用了中间代码解释 （或虚拟机）的机制。Stone 语言写成的程序将首先被转换为中间代码 （或二进制代码） ，解释器执行的其实是转换后的中间代码。Ruby 等语言也采用了这样的方式。第 13 章还将介绍如果要设计一个能把 Stone 语言转换为机器语言的编译器，需要做哪些准备。 第 14 章 （第 14 天）最后，为了提高性能，Stone 语言有必要支持静态数据类型，并根据数据类型的不同进一步优化性能
43、。在执行具有静态数据类型的 Stone 语言程序时，编译器可以先将其转换为 Java 二进制代码，再直接由 Java 虚拟机执行该程序。第 14 章还会为编译器增加类型检查功能，在执行程序前检查是否存在类型错误，并同时提供类型预判功能。这样一来，即使程序没有显式地声明数据类型，Stone 语言的解释器也能推测并指定合适的类型。Scala 等一些语言也采用了这一机制。第 3 部分解说篇 （自习时间）第 3 部分将介绍一些在开发 Stone 语言过程中没能涉及的进阶主题。第 15、16 章的内容是大多语言处理器相关教材中都会讲解的基础知识。A 咦，前 14 章就把书名所讲的内容都介绍完了呢。C 嗯
44、，的确如此。A 这么做是为了博人眼球吗？H 小 A，不能这么挑刺哦。F 不过其实这也不难理解，上课时也常会出现本课内容还没全部结束，就被要求去自学剩下的内容的情况呢。C 没错，这里也是一样。图灵社区会员 leezom() 专享 尊重版权1.4语言处理器的结构与本书的框架9 第 15 章 （第 15 天）Stone 语言的词法分析器由 Java 的正则表达式库实现。第 15 章将不使用这种方式，手工设计词法分析器。具体来讲，这一章将介绍基于正则表达式的字符串匹配程序设计。 第 16 章 （第 16 天）本书采用了解析器组合子库这一简单的库来实现语法分析器。第 16 章将介绍一些语法分析的基本算法
45、，并以 LL 语法分析为基础，手工设计一个简单的语法分析器。 第 17 章 （第 17 天）第 17 章将简单介绍本书使用的解析器组合子库的内部结构，并分析该库的源代码。 第 18 章 （第 18 天）Stone 语言的解释器采用了 GluonJ 系统来实现，该系统允许 Java 语言执行类似于 Ruby 语言中 open class 的功能。第 18 章将总结使用 GluonJ 时的一些琐碎的注意事项。 第 19 章 （第 19 天）抽象语法树是语言处理器的核心。在实现面向对象语言时，抽象语法树的节点对象的类会包含各种类型的方法。本书借助了 GluonJ 来增加这些方法，读者还可以通过其他设
46、计模式来实现相同的效果。第 19 章将介绍使用设计模式实现抽象语法树的优缺点，并与使用 GluonJ 的方式作比较。A 也就是说全书共有 19 章对吧？老师，那平时时间不多的读者应该优先阅读那些章节比较好呢？F 你是想问有哪些章节跳过不读也可以对吧？C 嗯，我建议先读完第 28 章，之后是第 15、16 章，如果还有时间，再读一下第 11 章和第13 章。F 第 9 章关于面向对象的内容不重要吗？S 要说最近比较流行的话题，第 14 章的内容才更重要吧。C 其实如果时间足够，我希望读者能够读完全书。真要选取部分来读的话，我建议按前面讲的顺序阅读。图灵社区会员 leezom() 专享 尊重版权设
47、计程序设计语言第1部分2第基础篇天图灵社区会员 leezom() 专享 尊重版权从本章开始，我们将逐步实现一种名为 Stone 语言的程序设计语言。在具体实现之前，我们必须设计 Stone 语言的语法。本章将讨论如何设计 Stone 语言。如果想要从零开始设计一种新颖实用的语言，结果往往是半途而废。即使设计成功，也可能由于过于复杂难以实现等原因而最终不了了之。因此，本书将首先设计一种极为简单的语言，并开发相应的语言处理器，确保程序能够正确运行。之后，再慢慢向其中添加诸如面向对象等一些复杂的语言功能。也就是说，先设计出一个简化的成品，再逐步改良。2.1麻雀虽小、五脏俱全的程序设计语言一种程序设计
48、语言至少需要具备哪些语法功能呢？整数四则运算之类的功能自然必不可少，最好还能支持字符串处理。同时，这种语言应该对变量提供支持，不然就和计算器没什么区别了。 if 语句及 while 语句等一些基本的控制语句也是必需的。Stone 语言姑且算是一种脚本语言，因此不需要指定静态数据类型，用户在使用时也不必事先声明变量，这样它的语法能较为简洁。像 Java 语言那样必须静态地指定数据类型的语言，用户在使用变量及参数前必须先进行声明，并指定数据类型。例如，以inti=0;的方式声明了变量 i 之后，它就成为了一个 int 类型的变量。虽然这种限制确实有用，但目前的 Stone 语言还不需要。Stone
49、 语言既不需要在使用变量前事先声明，也不需要指定变量的类型。用户可以将变量任意赋值为整数或字符串。只是这样一来，如果程序中出现字符串变量相减的语句，就会引起运行错误并终止。和 Java 语言一样，Stone 语言的句末需要使用分号 （ ;） 。不过如果正巧在句末换行，分号也可省略。例如，下面这样的代码也是合法的。sum=0i=1whilei10sum=sum+ii=i+1sum这段程序是计算 1 至 9 这 9 个数字的和，并输出结果。在执行这段程序时，最后一条语句设计程序设计语言基础篇第天2第1部分图灵社区会员 leezom() 专享 尊重版权12第 2 天设计程序设计语言设计程序设计语言将
50、显示计算结果，之后程序结束。Stone 语言不支持类似于 Java 语言中 return 语句的功能，最后一条语句的计算结果就是整个程序的运行结果。在上面的例子中，最后一行只写了一个 sum。Stone 语言会把变量 sum 也视为一条语句，该语句将读取变量 sum 的值。执行完这条语句后程序就会结束。于是，上面这段含有 while 语句的程序的运行结果是得到一个值为 45 的变量 sum。F 这段程序和 Ruby 语言很像呢。它和 Ruby 语言唯一的不同在于， while 语句体是通过 括来的，而 Ruby 语言则是使用 do 和 end。A 而且不同于 Java 语言，这段程序中 whi
个人主页
