（计算机软件与理论专业论文）异种程序设计语言间的翻译模型设计及方法研究.pdf

异种程序设计语言间的翻译模型设计及方法研究 摘要 随着计算机科学技术的飞速发展，计算机技术应用在了越来越多的领域，实 现各种功能的软件被大量的开发出来，应用在我们的生活、学习、工作当中。相 应地，也产生了许多用以编写计算机程序的程序设计语言。软件开发人员使用这 些程序设计语言，编写了大量的程序源代码。在这些程序代码中，有很多在执行 的功能上都十分近似，有的甚至完全一致。但是，由于这些程序代码采用了不同 的程序设计语言来编写，所以很难直接实现对这些程序代码的移植和重用。 为了提高程序代码的可移植性和重用性，提高软件开发的效率，降低软件的 开发成本以及便于对软件进行二次开发，软件开发者们都希望能够实现异种程序 设计语言所编写的程序代码之间的翻译转换。本论文所阐述的就是对这一课题的 相关研究。 在本论文中描述了对一个模型系统的设计和实现。整个模型系统的实现是以 形式语言和自动机理论为理论基础，借鉴了编译系统的功能实现方法。通过该模 型系统中各个部分功能程序相应地分析和处理，逐步地对源程序的词法、语法和 语义这几方面的语言特性加以分析，逐步将源程序代码解构为可直接进行翻译转 换的语言单词符号，并对它们进行相应地翻译转换，最终将该源程序代码翻泽转 换为用另一种程序设计语言描述的源代码。 本论文所阐述的内容为实现异种程序设计语言的程序代码翻译转换，提高程 序代码的可移植性和重用性提供了有意义的思路和实现方法。 关键词：记号，记号词典，翻译转换，语法树，语义分析 墨翌墨至堡生量量塑塑墅堡堡型堡盐墨查堡塑窒 a b s t r a c t w it ht h ed e v e l o p m e n to fc o m p u t e rs c i e n c e t h ec o m p u t e r l e c h n o l o g i e s a r ea p p l i e dt om o r ea n dm o r ef i e l d v a r o u ss o f t w a r ea r em a d eo u tt os e r v e o u rl i v i n g ，l e a r n i n ga n dw o r k i n g a l s o ，s om a n yp r o g r a m m i n gl a n g u a g e sa r e c r e a t e da n du s e dt om a d eo u ts o f t w a r e s o f t w a r ee n g i n e e r sh a v ew r i t t e n m a n ys o u r c ec o d e sb yt h e s ep r o g r a m m i n gl a n g u a g e s 。m a n ys o u r c ec o d e sa r e c l o s e dt oo t h e r si nf u n c t i o n ，s o m em e a nt h es a m ef u n c t i o i li n d e e d t h e s e c o d e sa r ew r i t t e nb yd i f f e r e n tp r o g r a m m i n gl a n g u a g e s ，s oi ti sh a r dt o t r a n s p l a n ta n dr e u s et h e s es o u r c ec o d ed i r e c t l y i no r d e rt oi m p r o v et h e s ec o d e sc a p a b i l i t i e so ft r a n s p l a n ta n dr e u s e ， i m p r o v et h ee f f i c i e n c yo fs o f t w a r ed e v e l o p i n g ，r e d u c et h ed e v e o p i n gc o s t a n db ee a s yt or e d e v e l o p i n g ，a l1s o f t w a r ee n g i n e e r sw a n tt oc a r r yo u tt h e t r a n s f a t i o na n dc o n f o r m a t i o nb e t w e e nt h ep r o g r a mc o d et h a ta r ew r it t e n b yt h ed i f f e r e n tp r o g r a n u n i n gl a n g u a g e s w h a tt h i sp a p e re x p a t i a t ei sj u s t a b o u tt h er e s e a r c h i n go ft h i st h e s i s i nt h i sp a p e r ，w ed e s c r i b e dt h ed e s i g n i n ga n da c h i e v e m e n to fam o d e l s y s t e m t h ew h o l ea c h i e v e m e n t so ft h i sm o d e ls y s t e mb a s eo nt h ef o r m a i l a n g u a g ea n da u t o m a t o nt h e o r i e sa n dt h ew h o l em o d e ls y s t e md r a w s1e s s o n s f r o mc o m p il e rs y s t e m e a c hp a r t so ft h em o d e ls y s t e md o e ss o m ea n a l y s i sa n dp r o c e s s i n g ， a n a l y z i n gl e x i c a l 、s y n t a xa n ds e m a n t i co fs o u r c ep r o g r a ms t e pb ys t e p ， d i v i d i n gs o u r c ep r o g r a mt ow o r dc rs y m b o lw h i c hc a nb e t r a n s l a t e da n d t r a n s f o r m e dd i r e c t l y a tt h ee n d ，w ec a nt r a n s l a t ea n dt r a n s f o r mt h i s s o u r c ep r o g r a mt oa n o t h e rp r o g r a r a m i n g1a n g u a g e s t h ec o n t e n t so ft h i sp a p e re x p a t i a t es o m ec o n s i d e r a t i o na n de f f e c t iv e m e t h o d so fc a r r y i n go u tt h et r a n s l a t i n ga n dt r a n s f o r m i n gb e t w e e nt h e d i f f e r e n tp r o g r a m m i n gl a n g u a g e s s o u r c ec o d e s k e o r d ：t o k e n ，t o k e n d i c t i o n a r y ，t r a n s l a t i o n t r a n s f o r m ，s y n t a x t r e e ， s e m a n t i ca r i a y s i s i l 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明 确的说明并表示谢意。 签名： 夕碜一 日期：z 卯f 年i - 月日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：之整鱼 导师签名： 夏癌磊双 。 b 觏：弘眄年fr b 异种程序设计语言间的翻译模型设计及方法研究 1 1 课曩的背景和意义 第一章引言 随着计算机科学技术的飞速发展，计算机技术应用在了越来越多的领域，实 现各种功能的计算机程序被大量的创造出来，应用在我们的生活、学习、工作当 中。相应地，也产生了许多用以编写计算机程序的程序设计语言。 通过这些程序设计语言，人们创造出了大量的程序，应用在了不同的软件项 目中。由于在客观条件、外部环境、计算机科技水平、项目要求等诸多因素上的 不同，对这些软件项目的开发大相径庭，即使是对同一功能事务的程序开发，其 所采用的程序设计语言也不尽相同。例如，国外在建筑工程领域大量地使用 f o r t r a n 这种程序设计语言开发建筑工程类软件，而在国内则大量地使用c c r + 程序设计语言来进行相应地开发。 伴随着计算机科学技术的发展，软件开发者们开发了数量庞大的程序代码， 而这些程序代码所实现的功能、所描述的对象有很多实际上是相似甚至是一致 的。但遗憾的是，由于这些软件项目采用了不同的程序设计语言来开发，所以即 使是完成同一功能的程序代码，也很难将其直接移植应用于其他的软件项目中。 为了提高程序代码的可移植性和重用性，提高软件开发的效率，降低软件的 开发成本以及便于对软件进行二次开发，软件工程师们希望能够应用一些方法或 工具，从而能够较容易地实现异种程序设计语言所编写的程序代码之间的翻译转 换。这正是本论文课题的理论背景。对本论文课题的研究，能够有效地提高程序 代码的可移植性和重用性，能够有效地实现异种程序设计语言的程序代码间的翻 译转换，这正是本论文课题的意义所在。 本课题是以中铁二局研究所的一个软件项目为前身，该项目的目的是将一套 建筑工程软件的源程序代码( 由f o r t r a n 程序设计语言编写) 翻译转换为由c c + + 语言编写的程序代码，从而可以移植到该所的另一套建筑工程软件平台上。这是 本论文课题的实际应用背景。 异种程序设计语言间的翻译模型设计及方法研究 1 2 与课题相关的国内外动态 本课题具有较高的实用价值和意义，所以国内外一些大学的科研人员也在做 这方面的一些方法探索和项目实践。他们大多是以具体的软件项目为背景，进行 与本课题相关或类似的研究分析，它们的研究工作大多是基于某两种特定的程序 设计语言程序代码间的转换翻译。例如加州大学的一个研究小组，根据软件项目 需求，开发出了一个软件工具，该软件工具能将简单的f o r t r a n 语言源程序翻译 转换为用j a v a 语言描述的程序代码。 国内外现阶段对于本课题的相关研究，基本上都是着眼于具体的两种程序设 计语言，而本课题将研究和分析的重点主要集中于设计一个能够普遍适用的翻译 转换模型以及相应实现方法的研究，这在国内外有关方面的研究和分析中还较为 少见。 本课题研究的目标是希望通过对程序设计语言一些共性的研究和分析，能够 建立一个程序模型系统。该程序模型系统能够在分析方式和实现方法这两个方面 为实现异种程序设计语言源程序间的翻译转换提供一定的指导。 本课题所希望实现的结果是能够设计出合理有效的模型系统，应用较为合适 的分析、处理方法，定义出有效的数据结构，能够对程序代码进行相应的解构和 重新组织，编写出实现模型系统相应功能要求的程序，从而达到实现异种程序设 计语言源程序间翻译转换的目的。 1 4 作者的主要工作 ( 1 ) 设计模型系统的整体架构； ( 2 ) 研究实现模型系统功能的方法； ( 3 ) 设计模型系统各个部分所采用的数据结构 ( 4 ) 编写程序，实现模型系统的部分功能； 2 异种程序设计语言问的翻译模型设计及方法研究 1 5 论文的组织结构 本论文共分九章。 第一章介绍了本课题的研究背景和意义，阐述了课题研究所要达到的目标。 第二章介绍了展开课题研究工作所需要的基础知识。 第三章描述了一个为实现本课题目标而设计的模型系统的整体架构，阐述 了构建该模型系统的基本思路，并简单介绍了模型系统的各个组成 部分。 第四章阐述了模型系统中的预处理部分所具有的分析处理功能，对实现这 部分功能的方式、方法进行了探讨研究。 第五章阐述了模型系统中的词法判定部分所具有的分析处理功能。介绍了 词法分析的相关理论知识，阐述了如何构建词法分析程序。详细阐 述了记号词典和记号词典程序。 第六章阐述了模型系统中的语法判定部分所具有的分析处理功能。介绍了 如何用y a c c 自动生成语法分析程序，介绍了对语法分析程序加以改 进的思路和方法。介绍了模型系统如何通过语法分析程序产生相应 的语法树。 第七章阐述了模型系统中的语义分析部分所具有的分析处理功能。简单介 绍了语言的属性文法。阐述了模型系统如何进行语义分析，如何表 示分析对象的语义流程、逻辑结构。 第八章阐述了模型系统中的翻译转换部分所具有的分析处理功能。阐述了 语义流程判定程序如何对记号标签进行赋值，翻译转换程序如何实 现翻译转换。阐述了一个翻译转换的实例。 第九章对本论文进行总结，分析了课题研究的不足之处，阐述了下一步要 进行的工作。 3 异种程序设计语言间的翻译模型设计及方法研究 第二章课题研究工作的基础 2 1 基于编译系统的程序设计语言 一个程序设计语言的编译系统，就是针对该语言的编译器，它是将某程序设 计语言翻译成另一种程序设计语言的计算机程序。编译器将该程序设计语言编写 的源程序作为输入，而产生用目标程序设计语言编写的等价程序。通常，源程序 为高级语言程序，如c 或c + + ，而目标程序则是目标机器的目标代码，也就是写 在计算机机器指令中的用于运行的代码。编译器的这作用如图2 - 1 所示： 源程_ 葶目标程净 图2 - 1 编译器的作用 2 1 1 1 编译系统的产生 本世纪四十年代，由于冯诺依曼在存储一程序计算机方面的先锋作用，使得 编写一串代码或程序已成为可能和必要，这样计算机就可以执行所需的计算。开 始时，这些程序都是用机器语言编写，编写这样的代码十分枯燥乏味，很快就被 汇编语言代替了。汇编语言大大提高了程序编写速度和准确度，但它也有许多缺 点。于是发展编程技术的下个重要步骤就是以个更加类似于数学定义或自然 语言的简洁形式来编写程序的功能操作，它应与任何机器都无关，而且也可由一 个程序翻译为可执行的代码。 随着对形式语言和自动机的研究，人们对程序设计语言的认识也越来越深， 发现编译器的结构非常简单，甚至还可以带有一些自动化。人们通过对形式语言 文法规则的研究，相当完善地解决了分析问题( d a r s in gp r o b l e m ，用于限定上下 文无关语言的识别的有效算法) 。当分析问题好懂起来时，人们就在开发程序上 花费了很大的工夫来研究这一部分的编译器的自动构造，这些程序就是分析程序 生成器( p a r s e rg e n e r a t o r ) 最初的雏形。类似地，对有穷自动机的研究也促进了 4 异种程序设计语言闻的翻译模型设计及方法研究 一种称为扫描程序生成器( s c a n n fg e n e r a t o r ) 工具的发展。接着，人们又深化 了生成有效目标代码的方法，这些就构成了最初的编译器，它们被一直使用至今。 2 1 1 2 编译过程概述 编译器内部包括了许多步骤或称为阶段，它们执行不同的逻辑操作，如图 2 2 所示： 源程序 目标代码 图2 - 2 编译器的阶段示意图 ( 1 )扫描程序( s c a n n e r ) 在这个阶段编译器阅读源程序( 通常以字符流的形式表示) 。扫描程序执行词 法分析( 1 e x i c a la n a l y s i s ) ：它将字符序列收集到称为记号( t o k e n ) 的意义单元 中。实际上，一个扫描程序所做的工作同对单词的拼写是十分类似的。扫描程序 e 异种程序设计语言问的翻译模型设计及方法研究 还可完成与识别记号一起执行的其他操作。例如，可将相应的记号输入到对应的 符号表中。 ( 2 )语法分析程序( p a r s e r ) 语法分析程序从扫描程序中获取记号形式的代码，并完成定义程序结构的语 法分析( s y n t a xa n a l y s i s ) ，这与自然语言中旬子的语法分析类似。语法分析定 义了程序的结构元素及其关系。通常将语法分析的结果表示为分析树或语法树。 ( 3 ) 语义分析程序( s e m a n t i ca n a l y z e r ) 程序的语义就是它的“意思”，程序如何运行由它的语义来决定。大多数程 序设计语言具有在执行之前被确定的特征，这些特征不容易被语法结构表示出 来，也无法用词法分析程序进行分析，这些特征被称为静态语义。语义分析程序 就是分析这样的语义。般程序设计语言的典型静态语义有声明和类型检查。在 程序执行阶段才能确定的程序特性称为动态语义，语义分析程序无法对这类特性 做出分析。语义分析程序还要计算被称为属性( a t t r i b u t e ) 的程序固有信息，如 数据类型、值等。语义分析程序通常将计算后的属性值添加到语法树中( 还可将 属性添加到符号表中) 。 ( 4 ) 源代码优化程序( s o u r c ec o d eo p t i m i z e r ) 编译器通常包括许多代码改进和优化步骤。这些优化和改进一般是在语义分 析之后完成的。优化程序将源代码以中间代码( i n t e r m e d i a t ec o d e ) 的形式输出， 进而完成对源代码的相应优化处理。 ( 5 )代码生成器 代码生成器得到中间代码，并生成目标机器代码。在编译的这个阶段中，目 标机器的特性成为了主要因素。它必须使用存在于目标机器中的指令，而且所采 用的数据表示形式也十分重要。 ( 6 )目标代码优化程序 在这个阶段中，编译器尝试着改进由代码生成器生成的目标代码。这种改进 包括对编址模式的选择、提高性能、将速度慢的指令更换成速度快的以及删除多 余的操作。 6 异种程序设计语言间的翻译模型设计及方法研究 2 1 2 基于编译系统的程序设计语言 现在计算机科学领域中所应用的程序设计语言，大部分是基于编译系统的语 言，该语言的源程序需要经过编译系统的编译后，生成可执行的目标代码，才能 被计算机执行和处理。而编译系统的本质，实际上就是将源程序代码从一种语言 ( 所使用的某种程序设计语言) 翻译成用另一种程序设计语言描述的程序代码( 目 标代码) 。并且，大部分程序设计语言所编写的源程序经过编译系统编译后，所 产生的目标代码，基本上都是汇编语言代码或机器代码。也就是说，虽然这些程 序设计语言不尽相同，但是编译的结果却基本上是一致的，如图2 - 3 所示： 艘辫苦一懈器x 卜。景鬈隅一编译嚣y 卜魄辫言 图2 - 3 不同程序设计语言在编译结果、过程上一致 无论目标代码是汇编语言代码或机器代码，反映到计算机内部，最终都是以 0 、l 所组成的串。对于计算机硬件而言，它们并没有任何的差别。当计算机对 这些0 、1 串进行处理时，即用指令系统对这些串进行相应解释执行时，它们所 对应的各种微指令是一致的。所以我们说源程序编译结果的一致性不仅仅是指其 在目标代码形式上的一致，更为重要的是，这些目标代码所蕴涵的针对计算机硬 件的操作，从根本上来讲也是一致的。 现在所应用的基于编译系统的程序设计语言，其编译过程基本上都要经历词 法分析、语法分析、语义分析、目标代码生成这几个阶段。虽然不同的程序设计 语言在其编译过程中会有一定差别，但这种差别并不是逻辑意义上的，这就为我 们从翻译形式、转换过程和数据结构应用这几个角度来分析、设计和实现异种程 序设计语言问的翻译模型提供了一个基础，并且也为研究本论文课题提供了一些 思路和方法。 2 2 采用形式语言与自动机的描述 语言是用作信息交流的工具，它是由语言元符号按照一系列的生成规则和语 义规则组织、定义出的语言符号、符号串集合。对于语言的这些规则而言，用文 字性的描述，是不够精确的，需要将语言抽象地定义成一个数学系统，其形式性 7 异种程序设计语言间的l 译模型设计及方法研究 的数学定义可以给出语言的严格描述。这种通过抽象，对语言结构、生成与识别、 性质的表示，就是形式语言的内容。 从形式化的角度，语言可以定义为：语言是由一个字母表中的字母组成的串 的集合。即对任何语言l ，有一个字母表，使得l 耋。 从语言识别角度，可以给出语言的另一种描述：按照一定的生成规则构造的 一个自动机( a u t o m a t o n ) ，能够被该自动机所识别的所有句子的集合，就构成了 该自动机所定义的语言。 形式化的文法规则是语言定义的一个数学模型，而自动机则可看作是语言的 识别系统。乔姆斯基证明了文法与自动机的等价性，从而完整地建立了形式语言 与自动机理论的体系架构。 程序设计语言就是我们同计算机进行信息交流的语言，它同样符合语言的形 式化描述规则，能够用文法规则对该程序设计语言进行定义，并且可以构造自动 机来对该语言进行识别。 2 2 1 文法概述 在字母表上按照一定的规则定义一个文法( g r a m m a r ) ，该文法产生的所有句 子的集合就是该文法产生的语言。这些文法就是对该语言的形式化描述。 2 。2 1 1 文法的形式定义 文法e 是一个四元组：g = ( v ，t ，p ，s ) ，其中 v 变量的非空有穷集。v a v ，a 叫做一个语法变量，简称变量，也可叫 做非终结符。 t 一终结符的非空有穷集。v a t ，a 叫做终结符。v n t = a 。 p 一产生式的非空有穷集。p 中的元素均具有形式a 一1 3 ，称为产生式。其 中a ( v u t ) + ，且d 中至少有v 中的一个元素出现。b ( v u t ) + 。 s s v ，文法g 的开始符号。 2 2 1 。2 推导、归约以及语言的形式定义 设g = ( v ，t ，p ，s ) 是一个文法，如果一p ，y ，6 ( v u t ) 。，则称 8 异种程序设计语言间的翻译模型设计及方法研究 ya 6 在g 中直接推导出了yb6 ，记作ya 6j yb6 ，直接推导可简称为 推导( d e r i v a t i o n ) ，有时也称推导为派生。 与推导相对应，称yb6 在g 中直接归约成了ya6 ，直接归约可简称为归 约( r e d u c t i o n ) 。 设文法g 一( v ，t ，p ，s ) ，则称l ( g ) = ( i ) iu t 且s j ( i ) 为文法g 产生 的语言( 1 a n g u a g e ) 。v l ( g ) ，称( i ) 为g 产生的一个句子( s e n t e n c e ) 。 2 2 1 3 文法的乔姆斯基体系 乔姆斯基根据产生式的形式将文法分成4 类，通常称之为乔姆斯基体系。 设文法6 - - - - ( v ，t ，p ，s ) ，则 ( 1 ) g 叫做0 型文法，或短语结构文法( p s g ) 。对应地，l ( g ) 叫做0 型语言 或者短语结构语言( p s l ) 、递归可枚举集。 ( 2 )如果对于va 一1 3 p ，均有lbi lni 成立，则称g 为】型文法，或 上下文有关文法( c s g ) 。对应地，l ( g ) 叫做1 型语言或者上下文有关语 言( c s l ) 。 ( 3 )如果对于v 一b p ，均有ibl iai 成立，并且n v 成立，则称 g 为2 型文法，或上下文无关文法( c f g ) 。对应地，l ( g ) 叫做2 型语言 或者上下文无关语言( c f l ) 。 ( 4 ) 如果对于vq b p ，q 旦均具有形式a 一a 一b ，其中a 、b v ，t + ，则称g 为3 型文法，或正则文法( r g ) 。对应地，l ( ( ；) 叫做3 型语言或者正则语言( r l ) 。 从上述对文法的定义可以看出，在乔姆斯基体系中，4 类文法所产生的语言+ 具有包含关系，r l c c f l c s l p s l 。 按照一定的规则，识别按照某种语言规则所产生的句子，这样的识别系统就 是自动机。当自动机能够识别出某种语言中的所有句子时，我们就称该自动机为 识别该语言的自动机。自动机是从语言识别的角度，来对语言进行相应地阐述。 自动机这样的识别系统，可以归纳为以下几个方面： 9 异种程序设计语言间的翻译模型设计及方法研究 ( 1 ) 系统具有有限个状态，不同的状态代表不同的意义。 ( 2 ) 将输入字符串中出现的字符汇集在一起构成一个字母表。系统处理的 所有字符串都是这个字母表上的字符串。 ( 3 )系统在任何状态下从输入串中读入一个字符，根据当前状态和读入 的字符这两个条件来决定转移到哪一个新的状态。当前状态和新的状 态可以相同，也可以不同。系统从输入串中读入一个字符后，它下 次再读时，会读入下一个字符。 ( 4 )系统中具有一个开始状态，系统从这个状态开始，进行对某个给定句 子的处理。 ( 5 )系统中还有一些状态，它们表示到目前为止，系统所读入的字符构成 的字符串是语言的一个句子，这些状态称为终止状态。能从开始状态 引导到终止状态的所有字符串句子的集合，就是该自动机所能识别的 语言。 语言的生成规则不同，那么识别该语言的自动机系统也就不同。主要有三种 形式的自动机，它们分别对应了乔姆斯基文法体系结构中不同的文法所生成的语 言。 ( 1 )有穷状态自动机( f i n i t ea u t o m a t o n ，f a ) ，它所能识别的语言是3 型 文法所生成的语言，即有穷状态自动机是正则语言的识别器。 ( 2 )下推自动机( p u s h d o w na u t o m a t o n ，p d a ) ，它所能识别的语言是2 型文 法所生成的语言，即下推自动机是上下文无关语言的识别器。 ( 3 )图灵机( t u r i n gm a c h i n e ，t m ) ，它所能识别的是0 型文法所生成的语言， 即图灵机是短语结构语言的识别器。 2 2 3 以形式语言与自动机理论为基础 计算机的程序设计语言，同样符合乔姆斯基对于语言的形式化定义。并且通 过对形式语言的相关研究，对程序设计语言的抽象、归纳，人们发现乔姆斯基文 法体系中的上下文无关文法，是对计算机程序设计语言的最佳近似描述。例如 2 0 世纪5 0 年代，人们就使用巴克斯范式( b n f ，上下文无关文法的一种表示形式) ， 对a l g o l - 6 0 语言进行了描述。 异种程序设计语言间的翻译模型设计及方法研究 从语言识别的角度，可以应用自动机的相关理论，用相应的自动机模型，来 对程序设计语言进行分析、识别，还能够对程序设计语言的算法进行有效的形式 化描述和推导，并且这种推导带有一定的共通性和自动化。 现代计算机大部分都是基于冯诺依曼体系发展起来的，符合冯诺依曼体 系的两个特点。用程序设计语言编写的源程序，最终反映到计算机内部，就是由 0 、1 构成的代码串。所以无论多么复杂的程序设计语言，最终都是可描述的， 并且这种描述的最终目标具有高度的一致性。 能够用形式化的文法规则描述出程序设计语言的定义，能够构造出自动机完 成对程序设计语言的句子的自动识别，这两点是程序设计语言在形式语言与自动 机理论方面的共性表述。正是这两点的共性表述，为我们分析、构建异种程序设 计语言源程序间的翻译模型提供了理论基础，同时，也为研究翻译转换的方法提 供了有效的借鉴。 形式语言与自动机理论是分析程序设计语言的理论基础，在本论文的很多章 节中都是以它作为指导，并且借鉴它的一些方法，来完成对整个模型系统的设计、 构建，完成对模型系统各部分功能的程序实现。 异种程序设计语言间的翻译模型设计及方法研究 第三章模型系统的总体榘构 3 1 模塑系统的设计要求 3 1 1 要求面向多种程序设计语言 本论文所阐述的是如何构建一个异种程序设计语言问的翻译转换模型系统， 相应地，就要求这个翻译转换模型系统不仅仅是针对某两种具体的程序设计语 言，而是希望它能够适用于多种程序设计语言，为实现这些程序设计语言源程序 之间的转换提供相应的指导。 程序设计语言数量众多，这就要求模型系统在分析语言源程序时，需要弱化 不同的程序设计语言各自不同的个性，从语言本质的特性出发，来进行相应地分 析和方法的研究。 3 1 2 借鉴编译系统的构造及分析方法 虽然程序设计语言数量众多、差异很大，但是这些语言的编译系统都是从形 式语言与自动机理论等语言共性的角度来进行构建的。从这一点而言，与模型系 统的设计要求是一致的。所以模型系统的功能组成、对源程序的分析方法，都可 以借鉴编译系统、编译原理中的相应部分。借鉴编译系统的构造及一些分析方法， 也提高了整个模型系统的构建效率和易实现性。 3 1 3 模型系统的输入要求 模型系统的输入，既是要进行翻译转换的源程序代码。如果源程序代码本身 是错误的，那么就很难实现对它的正确翻译转换，实现翻译转换后的目标程序代 码也难以正确执行。所以这就要求模型系统的输入，其本身必须是正确的，能够 通过源程序设计语言编译器的编译，并且编译后的程序能正确执行。既是说作为 模型系统输入的源程序，在词法、语法和语义这三个方面必须是正确的。 1 2 异种程序设计语言间的翻译模型设计及方法研究 3 2 对构建模型系统的一些考虑 如何构建模型系统、采用什么样的分析方法，从而能够实现将一种程序设计 语言编写的程序用另一种程序设计语言来描述，这牵涉到与程序设计语言相关的 多方面的问题。 模型系统该如何来弱化源程序设计语言与目标程序设计语言间的个性化差 异，如何寻求两者之间可供翻译转换的共性基础，这是构建整个模型系统的基本 出发点。对于模型系统所要进行的翻译转换工作而言，以下几个方面的闯题是必 须考虑的： ( 1 )用源程序设计语言编写的程序代码中的单词符号在目标程序设计语言 中是如何描述、定义的，如何分析这些单词符号并进行相应的翻译转 换。 ( 2 )在翻译转换的过程中，如何保持源程序的各种信息( 如属性值，控制流 信息) 能较完整地反映到目标程序中去。 ( 3 )如何保持翻译转换前后的程序代码在执行流程( 语义流程、逻辑结构) 上的一致性。 对上述的几个问题加以解决的过程实际上就是构建整个模型系统的过程。 3 3 构建模型系统的基本思路 构建的模型系统，实际上是为实现异种程序设计语言源程序问的翻译转换提 供一个指导性架构，并且以这一架构为基础，探索一些分析、转换的方法，应用 一些合适的数据结构，进而实现具体的异种程序设计语言间的翻译转换功能。 借鉴产生程序设计语言编译系统的一些思路和方法，构建整个模型系统的基 本思路为：首先，分析、提取出源程序中的单词符号( 记号) ，对它们进行一定的 判定，按照各自的类别分别存储入相应的数据结构中。根据源程序设计语言的定 义，辨识出这些单词符号的性质、意义，进而找出同这些性质、意义相匹配的， 用目标程序设计语言描述的单词符号。然后，对源程序的整体结构进行分析，从 程序语法的角度出发，获得源程序的语法组织结构( 语法树) ，继而再以源程序的 语法结构为基础，分析语法结构中各个单词符号的语义信息。通过对源程序整体 1 1 异种程序设计语言间的翻译模型设计及方法研究 的语义分析，从而获知源程序的语义结构( 程序执行流程) 。将语义结构分解到单 词符号的级别，判定各个单词符号间的关系并加以描述，从而能够用单词符号间 的相互关系表示皑程序的语义结构。最终，对单词符号进行相应的翻译，对一些 逻辑关系加以转换，从而得到用目标程序设计语言描述的程序代码。 需要注意和强调的是，作为一个指导性的、方法性盼模型系统，在按照上述 的思路进行构建的过程中，在对源程序进行分析的过程中，会以一些理论假设、 理论性的设定为基础，这样才能够有效地进行设计模型系统以及分析方法的研究 应用，才能较好地完成模型系统方法性的指导意义。 3 4 模型系统构架示意图 按照上述的基本思路，可以看出对源程序段的分析过程是一个从词法到语法 再到语义，最后进行相应翻译转换的逐步处理的过程，所以模型系统就是依照这 样的一个过程层层递进地构建起来的。模型系统的整体架构表示，如图3 1 所示： 异种程序设计语言间的翻译模型设计及方法研究 灏程序 l 一一一一一一_ 一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一。 图3 - 1 模型系统的整体架构 3 5 模型系统各部分简介 从功能角度而言，模型系统各个部分相互关联，层层递进地完成模型系统的 功能要求，达到从记号表示的角度判定出整个源程序的执行流程并加以翻译转换 的目的；从定义的数据结构和存储信息的角度而言，模型系统各部分相互依赖， 前面部分所定义和输出的数据信息，是其后部分进行分析处理的信息基础。 这里我们从模型系统各个部分所完成的功能这一角度对各个部分加以简单 异种程序设计语言问的翻译模型设计及方法研究 说明j 而模型系统所定义、使用的数据结构以及产生的数据信息等内容，将在后 面具体的各章节中进行描述。 ( 1 ) 预处理 模型系统的预处理部分，主要完成对源程序进行逻辑分段和对源程序中的函 数进行转换、分解这两项工作。预处理部分的功能是将源程序分解为逻辑功能较 为独立、代码基较小的源程序代码段，并对各个代码段中的函数做一定的处理， 使得模型系统其后的部分能有效地进行分析和处理。 ( 2 )扫描处理程序 词法判定部分的扫描处理程序，其功能是遵照源程序设计语言的词法规则定 义，识别出源程序段中的单词符号( 记号) ，并进行一些记号属性的分析，同时将 这些记号信息存储入相应类别的记号词典数据文件中。还要依照对源程序段中记 号的识别顺序定义出该源程序段的记号链表。 ( 3 )记号词典程序 记号词典程序的操作对象是已经具有源程序段记号数据的记号词典文件，通 过记号词典程序所提供的一些功能，给出源程序段中记号的目标程序设计语言描 述，并将这些数据对应地存储入记号词典文件中，以供模型系统的翻译转换程序 使用。 ( 4 ) 语法分析程序 语法判定部分的语法分析程序，其功能是遵照源程序设计语言的语法规则定 义，对源程序段进行语法分析，识别出源程序段所具有的语法结构，并将该语法 结构信息用语法树的形式描述出来，存储为语法树文件，为模型系统下一阶段的 属性计算程序和抽象语法树生成程序提供进行分析处理的基本信息。 ( 5 )属性计算程序 语义分析阶段的属性计算程序，其功能是遵照源程序设计语言的属性文法定 义，以语法树作为分析的基础，通过语法制导翻译的方式对源程序段中的记号进 行属性计算，并将计算出的各个记号的属性存储入记号词典的对应项中。 ( 6 )抽象语法树生成程序 语义分析阶段的抽象语法树生成程序，其功能是对语法树进行分析、处理， 去掉语法树中的冗余信息，将源程序段的语法结构信息更加有效地描述出来，存 异种程序设计语言间的翻译模型设计及方法研究 储为的抽象语法树文件，为下一步的四元式生成程序提供可供分析的基本信息。 ( 7 )四元式生成程序 语义分析阶段的四元式生成程序，其功能是对源程序段的抽象语法树进行分 析，从而生成该源程序段语法结构的线性表示，既四元式表示，并将其存储为四 元式文件，为模型系统下一阶段的记号标签赋值程序提供可供分析的基本信息。 ( 8 )记号标签赋值程序 翻译转换阶段的记号标签赋值程序，其功能是结合源程序段的记号链表，对 源程序段的四元式表示进行分析和判定，完成对记号记录的记号标签信息域的相 应赋值，为下一步的语义流程判定程序提供必要的记号标签信息。 ( 9 ) 语义流程判定程序 翻译转换阶段的语义流程判定程序，其功能是对完成记号标签赋值后的记号 链表进行分析，从而获得由记号间逻辑关系表示的语义流程。为最后的翻译转换 程序提供必要的逻辑结构信息。 ( 1 0 ) 翻译转换程序 翻译转换程序，其功能是依照模型系统前面部分所获得的源程序段逻辑结 构，对源程序段的记号进行相应地分析和辨识，进而从记号词典文件中找到该记 号对应的目标程序设计语言描述，按照一定的算法迸行代码的组织和处理，最终 获得用目标程序设计语言描述的程序代码段。 7 异种程序设计语言间的翻译模型设计及方法研究 第四章硬处理 对源程序设计语言程序进行定的预处理，是模型系统进行其后的分析处理 工作的基础。对源程序设计语言程序的预处理主要是完成对源程序的逻辑分段和 对源程序中函数的替换、分解这两项工作。 4 1 对源程序进行逻辑分段 4 1 1 逻辑分段的原因 要进行翻译转换的源程序设计语言程序，其代码量可能十分巨大，如果要让 模型系统能够对其整体进行翻译转换，那么可想而知，其工作量和工作难度将会 十分庞大。并且由于各个程序设计语言具有不同的特性，要实现源程序的整体翻 译转换也是十分困难的。 设计模型系统的目的是实现对源程序设计语言程序的翻译转换，并不需要判 定源程序的正确性以及执行源程序代码。所以对源程序进行适当地逻辑分段，不 仅符合模型系统的功能设计要求，不会破坏源程序整体的逻辑结构，还为实现模 型系统的功能提供了更好的基础条件。 所以需要对源程序进行相应的预处理，将代码量较大的源程序分解为多个逻 辑上较为独立、代码量较小的程序代码段。这样，模型系统其后功能部分，都是 以逻辑分段后的每个独立程序代码段( 源程序段) 作为分析主体来进行相应分祈 处理的。 4 1 2 逻辑分段的原捌 要对代码量庞大的源程序进行逻辑分段，需要遵循如下的几个原则： ( 1 )分解出来的源程序代码段，在逻辑上应该较为独立，能够完成一个部 分性的逻辑功能。在进行逻辑分段时应尽量参考源程序的注释文档和 功能说明文档。 ( 2 )局部变量应该尽可能少地出现在多个源程序代码段中。最佳的情况是 】8 异种程序设计语言间的翻译模型设计及方法研究 分解出的各个源程序代码段只包含应用于该段程序的局部变量。 ( 3 )代码段的代码量不应该太大，应尽量控制在五百行之内。 ( 4 )去除源程序中的各种解释说明代码，只保留功能程序代码。 4 1 3 逻辑分段的方法 到目前为止，还没有一个有效的算法或方法能够对程序源代码进行有效的逻 辑功能划分，所以预处理部分中的逻辑分段工作大多是以手工的方式进行的。要 对源程序进行逻辑分段，最主要的工作就是判定源程序中实现某一逻辑功能的代 码段，那么下述的几种原则性方法不失为有效的逻辑分段方法。 ( 1 )参考源程序的功能说明文档和注释文档，确定源程序所完成的各项逻 辑功能以及实现这些功能的代码段。 ( 2 )源程序是由多个文件组成时，每个文件可视为一个独立的逻辑功能代 码段。 ( 3 )可以根据某局部变量的作用域范围来判定一个逻辑功能代码段。 4 2 对函数进行预处理 4 2 1 函数预处理的原因 在源程序中，不可避免地会出现大量的函数，这些函数可能是源程序设计语 言提供的标准( 库) 函数，也可能是为实现程序功能而自行编写的函数。这些函数 在源程序段中往往是以函数调用的形式出现，对于模型系统而言，要直接对它们 进行翻译转换是相当困难的。 为了能够减少源程序中函数的多样性、复杂性，降低模型系统实现翻译转换 功能的难度，模型系统的预处理部分会对源程序段中的函数进行相应的预处理。 4 2 2 函数预处理的原列 要对源程序段中的函数进行预处理，需要遵循如下的几个原则： ( 1 )不能破坏函数的功能，要注意存储、保护函数的参数以及函数的返回 1 9 异种程序设计语言间的翻译模型设计及方法研究 值。 ( 2 ) 需要一定的措施对函数及代表该函数的函数名进行辨识、存储，从而 方便模型系统其后部分的分析处理。 ( 3 ) 在不影响源程序段逻辑功能的前提下，尽量预先独立出函数体，并对 函数体进行一定的替换和分解，既是将函数尽量替换为目标程序设计 语言的函数，或者尽量用确定的简单程序代码对函数加以替换。 4 2 3 函数预处理的方法 到目前为止，还没有什么有效的方法能够对函数直接进行翻译转换。不过进 行预处理的意义就在于能够使得模型系统有效地完成对源程序段的翻译转换，这 种翻译转换的根本要求是要保留相同的程序功能。所以在这样的一个原则下，可 以按以下的步骤来对函数进行相应的替换、翻译预处理。 ( 1 )标识出各个源程序段中的函数，并用表的数据结构记录下该源程序段 包含的函数，以及这些函数的形式和参数。 ( 2 )将函数从源程序段中剥离出来，用等效或近似等效的筒单程序语句对 其进行替换。例如，含有求平方函数的源程序段代码y = s q u ( x ) 可以 直接替换为y = x 木x ；含有返回值为布尔类型函数的源程序段代码z = c o m p ( x ，y ) 可以直接替换为z = t r u e 。 ( 3 )一些与前后程序相关的参数，可能并不出现在替换后的语句中，这就 需要在函数轰中加以标识和注明。 4 。3 源程序预处理后的结果 源程序在经过预处理后的结果应该是形成若干个代码量较小、逻辑功能较独 立的源程序段，并且在这些源程序段中没有或只含有很少量的函数。 源程序在经过预处理后，会形成多个表文件，这些表中记录了各个源程序段 原来所包含的函数以及相关的参数。同时，在这些表中还会给出指向对应的替换 翻译语句的地址指针。 异种程序设计语言间的翻译模型设计及方法研究 4 4 源程序预处理示倒 c 语言是种使用广泛，具有大多数程序设计语言特点的语言，所以本论文 以一个c 语言的源程序段