（计算机应用技术专业论文）基于net平台的lisp编译系统的研究与实现.pdf

摘要 随着硬件性能的不断提高，虚拟机得到了越来越多的应用和发展，基于虚 拟机的计算平台成为了主流的企业计算平台；与此同时，为了利用虚拟机提供 的各种服务和类库，拓广编程语言的应用范围，越来越多的编程语言需要被移 植到虚拟机平台上面。本文从编译器的设计原理入手，结合m t 平台的实际情 况，探讨了程序语言在n e t 平台的实现技术，提出了u s p 语言在n e t 平台的 实现方法，在此基础上文现了面向微软的n e t 平台的l i s p 编译系统。本文的研 究工作密切结合了实际编程操作，详细探讨了u s p 编译器四个主要部分即：词 法分析、语法分析、语义分析、代码生成部分的实现方法，并对编程语言的集 成开发环境的开发进行了探讨，最后我们对微软n l 玎平台下的调试器的实现方 法进行了详细分析。 关键字：编译器，词法分析，语法分析，语义分析，代码生成，n e t ，i j s p a bs t i a c t a b s t r a c t a l o n gw i t hs t e a d yi m p r o v e m e n to fm eh a r d w a r ec a p a b i l j t y ，v i r t u a lm a c h i n e s w e r ca p p l i e de x t e n s v e l ya n dg r e wf 酗t ；l h ev i n u a lm a c h i n ep l a t f o 咖b e c a m et h e p r i m a r ye n t e r p r i s ec a l c u l a t i o np l a f f 0 肋a tt h es a m et i n l e ，m o r ea n dm o r ci a n g u a g e s w e r ct r a i l s p l a n t e dt ot t l ev i n u a lm a c h i n ep l a t f o m l ，f o rm a k i n gu o fv a r i o u ss e r v i c e s a n dl i b m r yt h a tv i r t u a lm a d h i n e sp r 0 v i d e d 肺i sp a p e rc o m m e n c e df r o mt h ep 面c i p l e o ft h cc o m p i l e r ，c o m b i n e da c t u a lc i r c l j m s t d n c co ft l l em s n e tp l a t f o 咖，a n a l ) ，z e d t h et e c l l i l j q u eo fi l l l p l e m e n to fp r o g r 蛳m i n gi a n g i l a g 鼹_ i nt t l c n e tp l a t f o 加；p u t f b n a r dak i n do fn c wm e t h o do fl i s pi m p l e m e mi nt h em s n e 汀p l a t f o 衄f i n a l l y w eb r i n gt h ec o m p i l e rs y s t e mo fl i s pi n l p l e m e n ti i lt h em s n e i tp l a t f o 肋t os u c c e s s o u rr e s e a r c hc o m b i n e da c t u a lo p e r a t i o n ；w ea n a l y z e df o u rm a i np a n so ft h el i s p c o m p i l e r ：l e x i c a la n a l y s i s ，s y n t a xa n a l y s i s ，s e m a n t i c 卸a l y s i s ，c o d cg e n e m t i o n w e a i s od i s o u 锚i d ee n v i r o n m e n to ft i 忙l i s p 呻簪锄m i n gl 孤g i l a g e w ja l s oc a 玎i e do n a ni n v e s t i g a t i o ni nt h ed e b u gt e c i l i l o l o g yo ft h em s n l 强p i a t f b 蛐 k e yw o r d s ：c o m p i l e r l e x i c a i 姐a l y s i s ，s y n t a 】【a 1 1 a l y s i s ，s 锄粕t i ca i l a l y s i s ，d e g e n e m n o n ，m 巩l i s p i i 第一章语言理论及l i s p 语言 第一章语言理论及l i s p 语言 本文涉及的l i s p 语言的实现方法和实现的意义与程序设计语言的理论有 着密切的联系，作为全文的理论基础，有必要了解程序设计语言的基本理论和 l i s p 语言的理论基础，因此本章介绍了相关的程序语言理论基础和研究背景， 也详细介绍了u s p 的相关知识。 1 1 1 计算模型 第一节计算模型及程序语言 计算模型是描述如何在计算机中完成计算的一种概念性方法，不涉及硬件 和软件细节。它给出了完成计算所必须遵循的基本规则。计算机系统结构是有 关计算模型的一个具体体现。 数理逻辑学家们提出了四种计算模型，它们是递归函数、l a m b d a ( ) 演 算、图灵机和波斯特( p o s t ) 系统。这种种模型各不相同，区别很大，它们完 全是从不同的角度探究计算过程或证明过程的。但事实上，这几种模型却是等 价的，即它们完全具有一样的计算能力在这一事实基础上，最终形成了如今 著名的丘奇一图灵论点；凡是可计算的函数都是一般递归函数( 或都是图灵机可 计算的，或都是l a m b d a 演算可计算的，或都是波斯特系统可计算的) 。这就确 立了计算与可计算性的数学含义。直观的说计算就是从已知符号串开始，一步 一步地改变符号串，经过有限步骤，最后得到一个满足预先规定的符号串的变 换过程。现已证明：凡是可以从某些初始符号串开始而在有限步骤内计算的函 数与一般递归函数是等价的。这就是说，所有可计算的函数都是通过符号串的 变换来实现其计算过程的，即计算就是符号串的变换。 i a m b d a 演算【1 l 【2 l 是一套用于研究函数定义、函数应用和递归的形式系统。 它包括一条变换规则( 变量替换) 和一条函数定义方式，h m b d a 演算之通用在 于，任何一个可计算函数都能用这种形式来表达和求值。因而，它是等价于图 灵机的。尽管如此，h m b d a 演算强调的是变换规则的运用，而非实现它们的 第一章语言理论及“s p 语言 具体机器，可以认为这是一种更接近软件而非硬件的方式。 1 1 2 程序语言 一般来说，编程语言可以分为三类：命令式( i m p e r a t i v e ) 、函数式 ( f u n c t i o n a l ) 、逻辑式( i o g i c ) ( 也有把逻辑式和函数式语言合起来叫做说明式 的语言) 【3 】。命令式语言的理论基础是图灵机，图灵机通过不断修改存储带子 上的值，以命令式的方式做计算，就像命令式语言中通过改变变量的值来进行 计算。命令式的语言使用的最广泛，常用的编程语言如c ，c + + ，j a v a ，b 嬲i c ， p a s c a l ，饼等都是命令式语言。函数式语言基于丘奇( 舢o n z oc h u r c h ) 的计算 模型l a m b d a 演算，函数式语言主要有i j s p ，m l ，h 8 s k c n 等。逻辑式语言的理 论基础是谓词演算。逻辑式语言主要是p m l o g 。面向对象的语言不是把计算看 作处理器在存储器上的操作，而是看作一些的对象之间的相互作用，每个对象 有自己的状态和管理自己状态的函数。面向对象的语言一般与很强的命令式语 言非常接近，一般也归类到命令式语言里面。语言的分类并不是绝对的，大部 分函数式语言和逻辑式语言都有一些命令式语言的特征( 比如s i d e c 彘c t ，即副 作用) ，命令式语言也可以编写出函数式或逻辑式风格的程序来。 由于函数式语言在传统的冯诺依曼计算机中运行效率并不高，因此人们 构造了一种新的计算机，即规约机。规约机是一种需求驱动的数据流机器，依 靠表达式的规约束驱动机器，它是一种以函数式语言为机器语言的非冯诺依 曼体系结构的机器。归约机是面向函数程序设计语言的计算机，指令的执行顺 序取决于这些指令产生结果数据的需求，而这种需求又源于函数式程序设计语 言对表达式的归约。归约机和数据流机一样，都是基于数据流的计算模型，但 其驱动方式是采用需求驱动。在这种模型中，某条指令的执行，仅当其他指令 需要用它时才会进行。归约机按其归约模型可分为串归约机和图归约机两类。 两者的主要区分是对函数表达式所使用的存储方式不同，前者以字符串形式存 储而后者以图的形式存储。虽然规约机是面向函数程序设计语言的计算机，但 只是风行一时，并没有大规模的应用开发，现实中的函数式语言还是运行在 冯诺依曼体系结构的机器上。 2 第一章语言理论及l i s p 语言 第二节研究背景与意义 随着虚拟机技术( 这里所指的虚拟机和v m w a r e 、r t u a lp c 等硬件仿真器 的虚拟技术，x e nv m m 的半虚拟技术，以及m m 的a d v 锄c e dp o w e r 虚拟 技术所指的虚拟机是不同的，这里指的是用软件实现的虚拟机计算平台) 的不 断进步和效率的不断提高，加上硬件性能的不断提高，于是越来越多的虚拟机 被开发出来，越来越多的应用转到了虚拟机上面。现在最重要的企业计算平台 如s u n 公司的j 2 e e 和微软的t 都是基于虚拟机的平台，j 2 e e 的基础是j a v a 虚拟机j v m ，而微软的n e t 的基础是n e t 虚拟机c l r ；开放源代码社区也开 发了一些虚拟机，例如可以用来运行多种脚本程序的p 踟t 【4 j 虚拟机，可以运行 在w i n d o w s 和u n u x 下面的n e t 虚拟机m o n o 【5 1 。随着桌面p c 计算能力的提 高，虚拟机技术也越来越多的应用在桌面p c 上面，在微软最新的操作系统的 s t a l 6 l 中，玎将是操作系统的基础构件。现在的虚拟机本身就支持多种语言， 目前j v m 官方支持的语言是j a v a 和g m o v y ，而n l tc l r 官方支持的语言是 c 聋，v b m 玎，c + + 肥u ，j a v a s 硎p t 。为了紧跟这个趋势，利用虚拟机提供的 各种便利的服务和丰富的类库，越束越多的语言被移植到了虚拟机平台上面， 比如p h p m 、p y t h o n 【8 】，p e r l i 引，r u b y i i o 】，l u a l l ”，m e r c l l r y 【1 刁等语言。 虽然函数式语言出现很早，但是最初的函数式语言的实现一般都是解释型 的，效率不高，而且类库较少，影响了函数式语言的应用和普及。但是近年来 函数式语言的理论和实践都取得了巨大的进步，实用的编译器也已经开发出来， 函数式语言的类库也在不断扩充，函数式语言已经可以胜任实际中的各种应用 开发。现在影响函数式语言推广使用的主要障碍是社会的和商业的因素，而不 是技术的；函数式语言不是只能用于人工智能领域的语言，而是和其他通用语 言一样有着广泛的用途；函数式语言具有比命令式语言更高的数学抽象力，因 此在拙述某些算法的时候比命令式语言更佳1 3 】oc + + 的s t l ( s t a n d a r d t e m p l a t e l i b r a r y ) 使用起来非常方便，很好的实现了数掘结构和算法的分离，其中仿函 数( f u n c t o r ) j 分演了一个非常重要的角色；仿函数就是对函数的面向对象的封装， 用来实现一些类似函数式语言的功能。最近设计的命令式语言很多都加入了函 数式语言的东西，比如c # 2 o 中加入了对匿名函数的支持【”】，p y t h o n 和 j a v a s c r i p t 直接支持函数式编程，j a v a 中也加入了f u n c t o r 以支持函数式风格的 编程，最近s u nm i c m s v s t e m s 公司也宣布向j c p 提交了j s r2 9 2 ，用于支持j a v a 3 第一章语言理论及l i s p 语言 平台上的动态语苦( d y n a m i c a l l y ，i 卯e dl a n g u a g c s ) 1 1 4 j 。现在人们发现，在命 令式语言中引入局部的函数式编程思想，能将两种编程范式的好处合二为一； 在将来的v b 9 和c 躬中都将不同程度地引入函数式编程风格的特性【1 5 1 。 n l 玎平台是一个很好的通用计算平台，它对不同编程语言间交互提供了很 好的支持，可以方便的实现跨语言的集成，使代码复用变得非常简单，消除了 c o m 、e j b 、c o r b a 等组件模型的复杂性；它有着丰富的类库，免去了程序 语言开发人员开发类库的麻烦；它同时还提供了内存管理、线程管理、代码验 证、线程执行、j r r 编译、异常管理、远程处理等有用的服务。n l 玎平台的优 点导致了越来越多的编程语言把它作为一个实现平台。把i j s p 这种函数式语 言n l t 平台实现，既可以发挥函数式语言的优点，又可以利用n e t 平台的各 种优势，而且m 强平台的丰富的类库也解决了函数式语言类库不足的问题【1 6 1 。 因此作者设计并实现了一个基于微软的m t 平台的u s p 语言的编译系统。 第三节l i s p 概述 u s p 【1 _ 7 l 【1 8 l ，全名是u s tp r o c e s s o r ，意思就是表处理；u s p 最初是作为书 写字符与表的递归函数的形式系统出现的，1 9 5 8 年由美国麻省理工学院( m r d 的a i 小组提出( 要为问答系统设计一种语言) ，1 9 6 0 年由m r r 的j o i l l l m c c a r t h y 教授( 麦卡西教授，图灵奖获得者) 整理成统称为u s p l o 的形式发表，然后开始 流行于人工智能界。以后陆续出现了u s p l 5 ( 1 9 6 2 年) ，l i s p l 6 ，m a c u s p ， i n t e r l i s p ，c o m m o n l i s p ，g c u s p ，c c u s p 等等变种。l i s p 语言的现代 最流行的版本是c o m m o nu s p ，c o m m o ni j s p 也有着很多的不同实现。 u s p 语言具有下列特点1 1 9 l ： 主要数据结构是表( 符号表达式) ，而不是作为算术运算对象的数。u s p 的数据类型和句法结构简单，甚至简单到具有唯一性和一致性：其数 据和程序的表现形式是一样的，都是用s 表达式( 即用空格分隔的、 并且用圆括号包括的一系列记号) 表示，基本的数据结构是表f 表是s 表达式的特例1 。 l i s p 一切功能由函数来实现，程序的运行就是求值；u s p 程序的通常 形式是一串函数定义，其后跟着一串带有参数的函数调用，函数之间 的关系只是在调用执行时才体现出来。u s p 使用函数来产生更复杂的 4 第一章语言理论及“s p 语言 函数从而构成程序。 、 u s p 语言中最主要的控制结构为递归，适于过程描述和问题求解。大 多数语苦使用的控制结构是以循环为主的，有的程序语言允许递归， u s p 中递归形式运用的很广泛，当然现在u s p 也有循环结构和迭代。 大多数u s p 系统可以以交互方式运行，使用解释性开发环境，便于开 发各类程序。 l i s p 语言的实现都支持垃圾收集机制，自动垃圾收集的思想和实现都 来自于i j s p 。 u s p 的数据结构： 在基本l i s p 中，仅有一种数据类型，即表结构。大多数u s p 程序设计中， 数据是以表或者原子为专门形式。 原子；原子是l i s p 中最小的符号单位。原子有标识符，诸如a b c ，1 0 ，x y z ， n i l 等。各种性质或属性可附加到单个原子上。一个原子最重要的属性除其名 字外是值，这与变量有值同义一些原子有标准值：原子m l 的值是n i l ，t 的值是t 。任何数字原子，其相应的整数或浮点数是它的值。这里要注意，原 予不是“类型”，任何原子，除常数外，可以给予任意值。 表：一个表递归地定义为括号内零个或n 个元素的序列： ( 元素l 元素n ) 其中每一个元素是一个原子或是一个表。不包含任何原子的列表形如“o ”， 也可以写作“n i l ”，被称为“空表”。空表既可以被看作是一个原子，也可以被 看作是一个列表。表的固有递归结构非常灵活，便于表示各种信号。 例如： ( 12 3456 7 89 ) ( a bc de d u s p 表的内部表示是由称为c o n s 单元的基本单元构成。每个c o n s 单 元是一个地址，它包括一对指针，每个指针指到一个原子，或者指到另一个 c o n s 单元。 u s p 的控制结构；u s p 是函数式程序语言，u s p 的控制结构主要是应用 函数指导控制流，其中变元又可以是应用函数。这点与大多数程序设计语言的 顺序控制结构不同，在那里分离的句子是一句接一句地执行。在l i s p 中，语 句与表达式没有区别，过程与函数也没有区别。每个函数，不管是否是一个语 5 第一章语言理论及“叩语言 言原语，或是由用户定义的，都以指向一个表结构的形式返回一个单值。但是 u s p 中也有命令式语言中常用的控制语句，如i f 语句，c o n d ( 类似s w i t c h ) 语 句，d o ( 类似f o r 循环) 语句等。 i j s p 中的变量约束到值上，变量本身并无什么含义，它只是一个符号。通 过这个符号可以得到这个值。变量本身只不过是具有当前值的原子名称而已。 当我们引用到变量名时，u s p 返回原子的当前值。这个名称与原子当前具有的 值之间的联系称为约束，例如可把x 约束到5 。每当您在程序中引用x 时，u s p 都理解为5 。当个值约束一个变量时，约束直有效，直到程序员改变它为 止。如果在整个程序执行过程中始终保持变量的约束，那么变量被认为是全局 变量。如果变量的约束是建立在单个函数的内部，那么当函数结束时，约束就 消失，那么变量是该函数内的局部变量。 6 第二章n e t 平台 第二章n e t 平台 。微软的n e t f r a m e w o r k 是一个集中于快速应用程序开发( 1 认d ) 、平台无 关和网络透明的软件开发平台。n l 玎是微软战略上为下一个十年对服务器和桌 面软件工程的第一步。n e tf r a m c w o r k 是以一种类似于j a v a 系统的虚拟机方 式运行和管理的编程平台，通过以公共语言运行环境为基础，支持多种语言( c 弗、 v b n e t 、c + + 、j a v a s 嘶p t 等) 的歼发。我们实现的l i s p 语言是运行在微软的n e t 平台下面，编译器的实现中也涉及到了n e t 平台的一些底层的技术，特别是代 码生成部分更是与n e t 平台的底层的技术息息相关，因此需要对相关的技术进 行介绍和说明。 第一节平台概述 微软的n e t 平台( 见下图2 1 ) 是微软倡导的下一代企业级计算平台，也是 微软下一代操作系统( s t a ) 的基础。微软的n e tf r a m e w o r k 是m 玎的一个具体 实现( 另一个常用的t 实现是开放源码的m o n o ) ，它包括以下主要部分【刎： 公共语言运行环境( c l r ，c 0 m m o nl a n g l l a g cr u n t i n l e ) ：提供可靠、安 全的运行时环境，并且支持多种编程语言。 n l 玎f m m e w d r k 类库( f c l ) ：提供了一系列功能强大地、可扩充的类， 这些类适用于所有与h n 玎兼容的编程语言。 c l s ( c o m m o nl a n g i l a g cs p c c i f i c a t i o n ) 通过定义一组开发人员可以确 信在多种语言中都可用的功能来增强和确保语言互用性。c l s 还建立 了c l s 遵从性要求，这帮助您确定您的托管代码是否符合c l s 规范 的要求。 语言和开发人员工具：常用的语言如c + + 、v b n l 玎及j a v a s 面p t n e t 等在n e t 中都进行彻底地革新，其功能大大增强。n e t 提供了全新 的编程语言c 带，大幅度简化开发并且更适应发展潮流。第三方也可以 开发新的语言运行在n e t 平台上，比如我们的i j s p 。 7 第一章n e t 平台 c + +c 撑v b n e tu s p 2 1 1 公共语言运行环境 图2 1 n e t 平台 公共语言运行环境( 公共语言运行时，c u t ) 是n e tf 埘n e w o r k 的基础和 核心，它是n e t 应用程序的执行环境；它处于n i 玎框架的最低层，是将底层 操作系统平台差异进行抽象的运行时基础设施；它在n e t 应用程序和操作系统 之间提供了一个中间层，它类似于j a v a 虚拟机。公共语言运行环境是整个n e t f r a m e w o r k 构建的基础，是实现m 玎跨平台、跨语言、代码安全等核心特性的 关键。公共语言运行环境为多种开发语言提供了一种统一的运行环境，它是n e t 代码执行的一种平台，中间语言代码几运行在它上面，各种语言代码在编译后 都生成m 代码，公共语言运行环境包含执行i l 代码的各种机制。公共语言运 行环境实际上是驻留在内存里的一段代理代码，公共语言运行环境提供内存管 理、线程管理、代码验证、线程执行、j r r 编译、调试、异常管理、远程处理等 核心服务，并且还强制实施严格的类型安全检查，这些服务有助于简化代码开 发和应用程序的开发，同时也将提高应用程序的可靠性1 2 ”除此之外，它还在 具有如生命周期管理，强类型命名，跨语言异常处理以及动态绑定之类的功能， 8 第二章n e t 平台 从而可以减少开发人员将事务逻辑转成可重用组件时必须写的代码数量。公共 语言运行环境自动处理对象布局并管理对对象的目l 用，在不再使用它们时将它 们释放。这种自动内存管理解决了两个最常见的应用程序错误：内存泄漏和无 效内存引用；同时也解决了本地代码编程中最常见的安全漏洞：缓冲区溢出。 运行库还提高了开发人员的工作效率。程序员可以用他们选择的开发语言 编写应用程序，却仍能充分利用其他开发人员用其他语言编写的运行库、类库 和组件。尽管m 玎f r a m e w o f k 类库是为未来的软件设计的，但是它也支持现在 和以前的软件。托管和非托管代码之间的互操作性使开发人员能够继续使用所 需的c o m 组件和d l l 。尽管公共语言运行环境提供许多标准运行库服务，但 是它从不解释托管代码，一种称为即时编译( j i t ) 的机制使所有托管代码被即 时编译成本机代码后运行。 2 1 2 中间代码 以公共语言运行环境为目标的代码称为托管代码，而不以公共语言运行环 境为目标的代码称为非托管代码。托管代码由公共语言运行环境“托管”。托管 代码表示为一种抽象的中间形式，即m s i l 代码( 也叫c i l 代码) ，它独立于编 程语言，也独立于c p u 和操作系统，j 下是由于采用了这种表示形式，使不同语 言编写的n e t 应用程序可以进行相互操作，不仅可以相互调用函数，还可以彼 此进行类继承田j m i c r o s o f t 中间代码o 讧s i l ) ，可以有效地转换为本机代码且独立于c p u 的 指令。m s i l 包括用于加载、存储和初始化对象以及对对象调用方法的指令，还 包括用于算术和逻辑运算、控制流、直接内存访问、异常处理和其他操作的指 令。要使代码可运行，必须先将m s i l 转换为特定于c p u 的代码，这通常是 通过实时( j r r ) 编译器束完成的。由于公共语言运行环境为它支持的每种计算 机系统都提供了一种或多种j i t 编译器，因此同一组m s i l 可以在所支持的任 何系统经过j i t 实时编译和运行( 目前微软的j r r 只支持w i n d o w s 平台，但是 m o n o 支持w i d o w s 和l i n u x 平台) 。 2 1 3 公共语言规范 + 由于不同的编程语言之间必然存在一些差异，n e t 应用程序必须遵守一些 9 第二章n e t 平台 规则才可以进行相互操作。保证n l t 应用程序互操作的规则集合成为公共语言 规范( c l s ) ，该规范为编译器供应商详细描述了针对c l r 的编译器必须支持 的最少特性集c l s 通过定义一组开发人员可以确信在多种语言中都可用的功 能来增强和确保语言互用性。它限制了命名规则；数据类型、函数类型以及其 他的一些元素，为不同的语言提供了一个公共的语言规则。 公共语言规范即c l s ( c o m m o nl a n g u a g es p e c i f i c a t i o n ) ，它是许多应用程 序所需的一套基本语言功能。c l s 通过定义一组开发人员可以确信在多种语言 中都可用的功能来增强和确保语言互用性。c l s 规则定义了通用类型系统的子 集，即所有适用于公共类型系统的规则都适用于c l s 。如果您的组件在对其他 代码公开的a p i 中只使用了c l s 功能，那么可以保证在任何支持c l s 的编 程语言中都可以访问该组件。c l s 在设计上足够大，可以包括开发人员经常需 要的语言构造；同时也足够小，大多数语言都可以支持它。 有了公共语言规范，就可以很容易地设计出能够跨语言交互的组件和应用 程序。也就是说，用不同语言编写的对象可以互相通信。并且它们的行为可以 紧密集成。例如，可以定义一个类，然后使用不同的语言从原始类派生出另一 个类或调用原始类的方法。还可以将一个类的实例传递到用不同的语言编写的 另一个类的方法。这种跨语言集成之所以成为可能，是因为基于公共语言运行 环境的语言编译器和工具遵守公共语言规范，遵循关于定义新类型以及创建、 使用、保持和绑定到类型的规则。 2 1 4 元数据 元数据是由m e t a d a l a 翻译来的，可以理解为t y p eo f t y p e ，实际上就是描述 类型信息的类型信息。从最原始的头文件，到初始的语言层面支持的r 1 1 1 ( 如 c + + ，d e l p h i ) ，到后来二进制级别的c o m 的i d l 和类型库( 类型库是d l 编译 后的二进制形式) ，到现在的n e t 中的m e t a d a t a 和j a v a 的触t a t i o n ( 注释、 注解) ，到w e bs e i c e 的s o a p ，w s d l 其实是遵循着相同的发展思路。只是出 于不同的需求，设计、实现，有着各自的优点缺点但随着语言的发展，更多 的需求将集中到灵活性方面，因而语言发展的趋势是元数据和s o a p ，w s d l 的 使用越来越多，支持越束越强。 若要使公共语言运行环境能够向托管代码提供服务，语言编译器必须生成 l o 第二章n e t 平台 一些元数据来描述代码中的类型、成员和引用。元数据与代码一起存储：每个 加载的托管可移植执行( p e ) 文件都包含元数据。因此当编译器产生m s i l 时， 它必须也产生元数掘。m s i l 和元数掘包含在一个托管p e 文件中，托管p e 文 件基于并扩展了过去用于本地代码可执行文件的p e 格式和公共对象文件格式 ( c o f f ) 。这种文件格式包含m s i l 或本机代码以及元数据，操作系统能够识别 这种可执行文件。 元数据是一种二进制信息，用以对存储在托管p e 文件或存储在内存中的程 序进行描述。在模块或程序集中定义和引用的每个类型和成员都在元数据中进 行说明。元数掘描述代码中的类型，包括每种类型的定义、每种类型的成员的 签名、代码引用的成员和公共语言运行环境在执行时使用的其他数据。当执行 代码时，运行库将元数掘加载到内存中，并引用它来发现有关代码的类、成员、 继承等信息。公共语言运行环境使用元数据来完成以下任务：查找和加载类， 在内存中安排实例，解析方法调用，生成本机代码，强制安全性，以及设置运 行时上下文边界从使用的角度讲，元数据和c o m 领域中的类型库所扮演的 角色很相近，但是n i 玎中的元数据远比c o m 中提供的信息要丰富，而且元数 据是内嵌在托管模块中的，它和i l 代码是放在一起的。从结构上讲，元数据是 一个j 下规的关系数掘库，元数据是交叉引用关系的表的集合，元数据不会包含 任何的重复的数掘【矧 对于实现一种更简单方便的编程模型来说，元数据是关键，该模型不再需 要接口定义语言( m l ) 文件、头文件( 比如h 文件) 或任何外部组件引用方法。 元数据允许n l t 语言自动以非特定语言的方式对其自身进行描述，而这是开 发人员和用户都无法看见的。此外，程序员通过使用自定义的属性( c u s t o m a n 曲u t e ) ，可以对元数据进行扩展。 2 1 5j l t 弓i 擎 要运行m i c r 0 f t 中间语言( m s i l ) ，必须先用n e tf m m e w o r k 实时( j n ) 编译器将其转换为本机代码，因为c l r 虽然是虚拟机，但并不是以解释的方式 运行代码的。本机代码是运行于j r r 编译器所在的同一计算机结构上特定于 c p u 的代码。由于公共语言运行环境为所支持的每种c p u 结构都提供了j r r 编译器，开发人员可以编写一组可在具有不同结构的计算机上进行j i t 编译和 第二章n e t 平台 运行的m s i l 。但是，如果托管代码调用特定于平台的本机a p i ( 通过p l a t f o m i n v o k c ) 或特定于平台的类库( 例如m 0 n o p 0 s i x ) ，则将只能在特定的操作系统 上运行。 j r r 实时编译器考虑了在执行过程中某些代码可能永远不会被调用的情况， 它不是耗费时间和内存将可移植可执行( p e ) 文件中的所有m s i l 转换为本机 代码，而是在执行期间根据需要编译m s i l 并存储生成的本机代码以供后继的 调用使用1 2 4 i 。当加载类型时，加载器创建存根( s t u b ) 并将其附加到类型的每个 方法。当对方法进行初始调用时，存根将控制传递给j r r 编译器，而编译器将 该方法的m s l l 转换为本机代码并修改存根以直接执行到本机代码的位置。后 面对j r r 编译的方法的调用将直接进行到以前生成的本机代码，从而减少了进 行j r r 编译和运行代码所需的时间( 共享类库的本机代码存放在w i n d o w s 目录 的髂s 锄b l y 子目录下面) 。j 盯编译通常与代码验证操作相结合，在j r r 编译过 程中要检查i l 的类型是否合法，同时对象只执行合法的操作。 2 1 6 通用类型系统 通用类型系统( c t s ，c o m m o nt y p es y s t 锄) 定义了如何在公共语言运行环 境中声明、使用和管理类型，同时也是运行环境支持跨语言集成的一个重要组 成部分通用类型系统执行以下功能：建立一个支持跨语言集成、类型安全和 高性能代码执行的框架；提供一个支持完整实现多种编程语言的面向对象的模 型；定义各语言必须遵守的规则，有助于确保用不同语言编写的对象能够交互 作用。公共语言运行环境使用通用类型系统的严格类型验证和代码验证基础结 构来加强代码可靠性。c t s 确保所有托管代码都是可以自我描述的。各种 m i c r o s o f t 和第三方语言的编译器生成符合c r s 的托管代码。这意味着托管代 码可在严格保证类型安全的同时使用其他托管类型和实例 通用类型系统中所有类型都派生自s y s t e m 0 b j e c t 基本类型。通用类型系统 支持两种一般类型：值类型和引用类型。值类型直接包含它们的数据，值类型 的实例要么在栈上，要么内联在结构中，值类型不能派生出其他类型。引用类 型存储对值的内存地址的引用，位于托管堆上引用类型可以是自描述类型、 指针类型或接口类型。引用类型的类型可以由自描述类型的值来确定。自描述 类型进一步细分成数组和类类型。类类型是用户定义的类、装箱的值类型和委 第二章n e t 平台 托。作为值类型的变量，每个都有自己的数据副本，因此对一个变量的操作不 会影响其他变量。作为引用类型的变量可以引用同一对象；因此对一个变量的 操作会影响另一个变量所引用的同一对象。 对值类型装箱将把该值类型打包到o b j e c t 引用类型的一个实例中。这使得 值类型可以存储于堆中。对值类型装箱会在堆中分配一个对象实例，并将该值 复制到新的对象中。取消装箱将从对象中提取值类型。 2 1 7 n e t 。f r a m e 们r k 类库 n i 玎f r a m e w o r k 类库是一个综合性的面向对象的可重用类型集合，并且对 w i n d o w s a p i 提供了很好的封装( 微软的下一代w i n d o w s a p i 本省就是基于n e t 的) ，可以很方便使用它开发多种应用程序。它们按照单一有序的分级组织提供 了一个庞大的功能集，包括从文件系统到对x m l 功能的网络访问的每一样功 能，n e tf r 啪e w o r k 类库提供了几乎所有应用程序都需要的公共代码瞄j 。类库 主要的好处是它们将核心w i n d o w sa p i 的最常用的功能和外挂软件开发包s d k 的功能封装到了一个统一的包中，采用清晰而有条理的方式对类库进行了分组 和描述。这样开发者能更容易地找到他们的应用程序所需的大多数功能，这也 使得开发者能将精力集中于编写他们的应用程序所独有的代码，而不必一再重 复编写类似读写文件这样经常使用的功能代码，从而大大方便了应用程序开发 人员，减少了他们需要编写的代码 2 1 8 托管可执行文件 托管可执行文件就是在公共语言运行环境中执行的可执行文件。托管可执 行文件格式基于标准的微软w i n d a w s 可执行文件格式( p e c o f f ) ，并且对这种 格式进行了扩展；它利用p e 结构的可扩展性，将c l r 所需的信息扩展到p e 映 像中。n e t 利用了p e 结构中的数据且录表中的一项，即利用 i m a g e o p l r i o n a i ，h e a d e r d a t a d i r e c t o r y 【i m a g e _ d t e c i o r y e n t r yc o md e s c r i m 刚来存储i m a g ec 0 r 2 0h 队d e r 结构，其它的p e 结构 基本不变【6 1 1 2 7 l 。操作系统装载器根据p e 文件中的可执行文件头跳转到程序的入 口点，当然操作系统也不能执行中间语言代码，这个入口点也被设计为跳转到 m s c o r e e d l l ( n e t 平台的执行引擎即m i c r o s 咂n e t r u n t i n l e e x 咖t i o e n 西n c ) 一 兰= 童：型坚! 鱼 的一c b r e x e m a i n o 函数入口c o r e x e m a i n o 函数开始执行p e 文件中的中间语言 代码这里的执行的意思是通用语言运行环境按照调用的对象方法为单位，用 即时编译器将i l 代码编译成本地c p u 机器代码然后执行。这一即时编译过程只 在第一次执行的时候进行，因为编译后的代码会保存起来供下次使用。 1 4 第三章系统总体设计 第三章系统总体设计 第一节总体设计 本文主要是探讨函数式语言u s p 在面向对象的虚拟机上实现的相关技术， 在n e t 平台实现l i s p 的编译系统，即实现一个以微软的n e t 平台为目标机器 的l i s p 编译系统。系统主要由三部分组成：i i s p 语言编译器( 针对微软的m 玎 平台) ，l i s p 源代码编辑器( 运行于微软的n e t 平台) ，l i s p 调试器( 针对微软 的n e t 平台) 。 编译器完成从源程序代码到目标程序的翻译，是一个复杂的过程。一个编 译器的工作是分阶段进行的，每个阶段将源程序从一种表示形式转换成另一种 表示形式，各个阶段的工作从逻辑上说是紧密联系在一起的。一般来说编译过 程大致分为词法分析、语法分析、语义分析、中间代码生成、代码优化、目标 代码生成六个阶段。 在编译器的架构设计上有多种选择，我们要根据自己的需要选择适合的结 构。我们把对源程序或中日j 代码程序，从头至尾扫描一次并完成所规定的工作 称为一遍。编译器的具体实现时可以采用多遍扫描分析也可以只进行一遍扫描 分析1 2 8 】。多遍功能独立，相互联系简单，逻辑结构清晰，但增加了编译程序的 长度和编译时间。遍数少则逻辑结构比较复杂，占用系统的内存较多，但减少 了中间过程读取文件的开销。 在普通的一遍编译器中，编译器对源代码只进行一遍分析，如下图3 1 所示。 1 5 第三章系统总体设计 圈嘞囤 钽囤 图3 1 传统一遍编译器的流程 磅圈 国 粤 钽叵圈 实际中的编译器很多都采用多遍的分析扫描，但是为了实现的简单方便期 l 日j ，我们实现的l i s p 语言编译器是一遍编译器。它的流程大致分为词法分析、 语法分析、语义分析，代码生成、四个阶段；没有中间代码生成阶段和代码优 化阶段，因为i l 代码本身就是一种类似中间代码的代码，代码优化我们留给了 j r r 编译器去处理。流程如下图3 2 所示。 圈哟圈两圈 扫园 图3 2 本文实现的编译器的流程 编译器首先读取源代码文件，然后根掘语言的定义进行词法分析，扫描出 单词，接着根据语言的语法进行语法分析，随后进行语义分析，语义分析无误 后进行代码生成工作，最后生成可执行文件。 编译器的各个主要部分如下： 1 6 第二章系统总体设计 编译器主模块：c l a s su s p g o m p i l e r 词法分析器：c l a s s “s p k x c r 语法分析器：d 勰si j s p p a 巧e r 类型检查器：c i 髂s “s p t y p e c h e c k e f 代码生成器：d 鹤si l c o d e g c n u s p 语义类：d a s sl i s p s ”c a x 运行时类库：c l a s sl i s p r t l j b 各个模块的调用关系如下图3 3 。 围 囤 ( + e l ) 整数或浮点数的加法，返回 + ，如果 的类 型是字符串时对它们进行连接操作，类似c 语言中的s t r c a t o 函数。 ( ) 整数或浮点数的减法，返回 一 。 ( ， e 2 ) ，) 整数或浮点数的除法，返回 e l 冰e 参。 ( = ) 比较运算，如果 小于等于 则返回t m e 。 ( = ) 比较运算，如果 等于 则返回1 1 m e 。当e 1 ) 比较运算，如果 大于 则返回1 h e 。 ( =