第3 语言翻译问题 [学习目标]：学习和掌握语言的语法的基本概念和基本要素，理解翻译的步骤；学习和掌握BNF文法。 第3 语言翻译问题 [学习目标]：学习和掌握语言的语法的基本概念和基本要素，理解翻译的步骤；学习和掌握BNF文法。 了解通用语法的标准，学习语法的基本要素； 了解几种语言的特点； 学习和掌握源程序分析和目标程序综合的原理和方法； 掌握和使用BNF文法；

[重点和难点]： 本章的重点是：源程序的分析和目标程序综合的原理与方法；BNF文法； 本章的难点是：语法二义性，语义分析原理； [知识点]： 语法；语义；二义性；独立子程序定义；独立数据定义；嵌套子程序定义；独立接口定义；词法分析；语法分析；语义分析；优化；连接与载入；系统自举；语法树；BNF文法

本章概述 对于在虚拟计算机上实现的高级语言程序，必须经过翻译才能在实际的计算机上运行。 翻译一般要经“词法分析”—>“语法分析” —>“语义分析” —>“代码优化” —>“目标程序生成”等5个阶段。其中， “语法分析”阶段最为重要，它是描述程序结构的主要手段。 “遍”的概念？ “一遍”翻译？“二遍”翻译？ “三遍”翻译？

本章主要内容 3.1 编程语言语法 3.2 翻译步骤 3.3 BNF文法

3.1 编程语言语法 语法：以句子中词的排列来表明它们的彼此关系。如C语言中，x=y+z具有正确的语法，而x+-则语法错误。 语法是理解一个程序的重要手段，也为将源程序翻译成目标程序提供了必要的信息。 但，只有语法是不够的。如“张三踢足球”和“足球踢张三”，语法都正确，但语义？如 x = 2.54+3.67, 结果为5,6,6.21?

本节主要内容 通用语法标准 语言的语法要素 主程序-子程序结构

通用语法标准 可读性： 如果一个程序的算法和数据结构能够明显的从程序文本中观察出来，则这个程序是可读的。可读的程序称之为自引证的。 可读性成为如今程序编制的重要目标是一。 增加可读性的方法：用自然语句格式、结构化、自由使用关键字和噪声码、注释、不限标识符长度、助记符、自由域格式、完整的声明。

可写性： 可写性是指程序易于编写。语法结构简单的语言程序可写性好。 增加可写性的方法：设计简洁、整齐的语法结构。允许保留不明确声明和操作的隐含。 可写性与可读性是一对矛盾。简洁的结构可增强程序的可写性，但降低了程序的可读性。如C语言，可写性较好，但可读性差。允许保留不明确声明和操作的隐含可增强可写性，但会降低可读性，同时可检验性差。

易检验性： 证明程序的正确性。 这不仅涉及到语法，主要涉及到语义的正确性验证。 目前，主要通过一些测试方法，以及谓词演算方法来验证。

易翻译性： 源程序容易翻译成可执行的目标程序。易翻译性与翻译器密切关联。 易于翻译的关键是结构的规范化。 易翻译性与可读性和可写性之间存在矛盾。如LISP程序易于翻译，但可读性和可写性较差。COBOL语言程序的语义较为简单，可读性和可写性较好，但由于存在数量庞大的语句和声明，翻译极为困难。

每一条语句均清楚的解释了语义，不存在二义性。但将两个语句组合为： if (ConE1) if (ConE2) S1 else S2 无二义性： 所谓二义性是指：相同的语法结构存在两种或更多种理解。无二义性是每个程序语言设计的中心问题。二义性问题通常不是出现在单个的程序元素中，而是在不同结构的相互作用下表现出来的。 例1：C语言中存在两种不同的条件形式： if (ConE) S if (ConE) S1 else S2 每一条语句均清楚的解释了语义，不存在二义性。但将两个语句组合为： if (ConE1) if (ConE2) S1 else S2 此时，存在二义性。

语句S2的执行控制存在不同的理解，是ConE1为假时执行，还是ConE1为假时执行？ 解决方法： 插入定界符，如 if (ConE1) if (ConE1) { if (ConE2) S1； 或 { if (ConE2) S1}； else S2；} else S2； 二者语义中强制的选择一种作为合法的解释，如就近匹配原则，即else与最近的 if 匹配。

例2：Fortran语言中，函数调用和数组引用语法是完全相同的。如语句 x = A(i,j) 存在二义性。此时A(i,j)是函数A的调用？还是数组A的引用？ 解决方法：若没有数组A的声明，就默认为是函数A的调用。Pasacl和C语言中的解决方案是：用[]表示数组，（）表示函数，如A[i,j]理解为数组引用， A(i,j)解释为函数调用。 返回本节

语言的语法要素 选用不同的基本语法要素就形成了一种语言的基本风格。下面，将简介一些语法要素。 字符集： 字符集的选择是语法设计的第一步。通常选择的字符集是ASCII字符集。 目前，通常使用8为（一个Byte）来表示一个字符，这足够表示52个大小写字母、10个数字、标点符号以及一些特殊字符。但如今，计算机工业越来越国际化，各个国家的文字、货币符号等已远远超过256。因此，考虑使用16位表示字符集。

标识符: 大多数语言都遵循以字母开始字母和数字组成的字符串作为标识符的原则。有的语言还允许包括“.”和“_”之类的特殊字符。如name_student是C中的合法标识符。这样，可以增强可读性和改善长度方面的限制。 标识符长度应该不受限制。

操作符： 大多数语言均使用 “+” 和 “-” 来表示基本的数学运算操作，除此之外，很少有相同的。 如Pascal使用 “：=”作为赋值操作，而C使用 “=”。 Pascal使用 “=” 作为比较操作，而C使用 “= =”，Fortran 使用字符串.EQ.。

关键字和保留字： 关键字是语句语法中固定部分使用的标识符。当关键字不能用作程序的标识符时，该关键字就是一个保留字。如C语言中的 if, for, while等。 使用保留字使翻译过程中的语法分析变得简单。作为反面例子，Fortran 中用户可以使用DO 和 IF作为标识符，因此以DO 和 IF 开始的语句实际上并不一定是循环或条件语句，所以Fortran 的语法分析较为困难。 使用保留字可增加程序的可读性。 但保留字也不能太多，否则难以记忆，编程不方便。如COBOL的保留字太多。 但当语言扩充而扩充新的保留字时，会引来麻烦。

噪声码： 插入在于语句中用来增加可读性的可选代码。 如Basic 语言中“GOTO”语句中的“GO”是必需的关键字，而“TO”是可选的噪声码。 如汇编语言中， return [n] 中的n是噪声码。

注释： 注释是程序文档中的重要组成部分。一种语言可以使用多种方法引入注释。如： Basic 中使用 REM 引导单独的注释行； C、Java语言中使用“ /*”和“*/”作为多行注释定界符。 Ada中的“--”，C++中的“//”，Fortran 语言中的“!”，Basic中的“ ’ ”都可以从语句行的人以位置开始标示注释。

空白符（空格） 各种语言使用空白符的规则不太相同。如C语言中，空白符在除字符串数据以外的任何地方没有重要的意义。？起分隔符号的作用。在词法分析中有重要的作用。多余的空白符被忽略。 在SNOBOL4语言中，空白符起基本连接操作作用。

定界符： 定界符一般用于简单的标示诸如语句或表达式这些语法单位的语法元素。 定界符有时仅用来增强可读性和使语法分析变得简单，更多的时候用于清楚的界定特定语法结构的边界以消除二义性。 如Pascal语言中的begin … end。C语言中的花括号{}。

自由或固定字段格式： 如果程序中的语句可以书写在一行的任意位置，则该语言的语法是自由字段格式的。目前绝大多数的高级语言均采用该语法。 若要求程序中的语句每一元素必须在一输入行的指定位置书写，则该语言的语法是固定字段格式的。固定字段格式语言的语法利用输入行的位置来传递信息。如Fortran77语言的一行80列分为四个区：1~5列为标号区；第6列为“续行标志区”；第7~72列为语句区；第73~80列为注释区。

表达式： 表达式的作用是访问程序中的数据对象并返回值。表达式是语句的基本元素，有时甚至是程序的基本元素。如C中，表达式组成了改变机器状态的基本操作。在ML和LISP语言中，表达式形成了驱动程序执行的基本顺序控制。

语句： 语句是命令式语言中最重要的语法单元。语句的语法对整个语言的规则性、可读性和可写性有着决定性的作用。 侧重于规则性的语言使用一个基本的语句格式。如SNOBOL4语言只使用一种基本的语句语法，即模式匹配替代语句。 侧重于可读性的语言则对不同类型的语句是用不同的语法。大多数的语言采用该方式。 返回本节

主程序-子程序结构 主程序-子程序结构的语法组织的定义与其他语言语法一样千差万别。 独立子程序定义 C语言的语法组织结构将每个子程序定义看作独立的语法单元。 每个子程序能够独立的编译并在装入的时候通过连接形成一个完整的程序。 面向对象语言要求信息能够在独立编译的单元中传递。类定义的继承性要求编译器在程序装入运行之前处理所有独立子程序

int aa(x,y) void bb(x,y) int x,y; float x; {……} int y; {…… } main() { float a; int b,c; bb(a,b); aa(c,b); }

独立数据定义： 将所有对一个给定数据对象的操作组织在一起。一个子程序可能包括该程序中涉及一个特定数据类型的所有操作，如建立、打印、运算数据记录的操作。 Java、C++和Smalltalk语言中类机制通常采用这种方法。

嵌套子程序定义： 所有子程序的定义嵌套在主程序中。 嵌套子程序定义对于建立模块化程序起者重要的作用。 嵌套子程序定义为那些在编译时定义的、允许静态类型检查且允许为包含非局部引用的子程序编译高效的可执行代码的子程序提供了一种非局部的引用环境。 Pascal语言是嵌套子程序定义的典型。

program mainPro (input, output) …… procedure pro begin end function fun(x: integer): integer; begin (*main begin)

独立接口定义： 将若干个子程序相关的接口进行单独定义。 其好处是：1）编译器可方便的检测出相同数据在不同子程序中不同定义的错误；2）调试时只需重新编译修改过的模块，提高编译效率。 如C语言中，“.h”文件形成了形式说明部分，以解决两个独立编译组件之间传输信息的问题，而“.c”文件形成了实现部分。

从可执行语句中独立出来的数据描述 讲数据与程序进行分离; 好处是使得数据格式与程序分区中的运算逻辑独立。只修改数据分区就可以完成数据结构的细微变动而不需同时修改程序。

非独立子程序定义 主程序与子程序之间没有任何语法的区别。即程序组织结构无组织性。 一个函数调用即开始了一个新的子程序，Return 的执行则结束一个子程序。 程序的行为完全是动态的。 SNOBOL4是典型的实例。 返回本章

3.2 翻译的步骤 高级语言源程序必须经过翻译才能在虚拟计算机上运行。 3.2 翻译的步骤 高级语言源程序必须经过翻译才能在虚拟计算机上运行。 翻译一般是一个较为复杂的过程。通常经过“词法分析”—>“语法分析” —>“语义分析” —>“代码优化” —>“目标程序生成”等5个阶段。可归纳为源程序的分析和目标代码的生成。 翻译通常追求高效的编译速度或高效的可执行的优化代码。 “一遍”翻译？“二遍”翻译？ “三遍”翻译？ 由于编译技术的发展，编译速度与扫描次数之间的关系不明显了，而语言的复杂度显得突出

源程序的分析 具体过程包括： 词法分析 语法分析 语义分析

词法分析 将源程序中的字符串划分成基本要素单元：标识符、限定词、运算符、数字、关键字、噪声码、空格、注释等。划分的结果称为语法项。 该分析过程由词法分析器完成。 虽然词法分析的概念简单，但过程复杂，耗费的编译时间较长。必须对源程序进行逐字的阅读和分析。

如下列Fortran 语言中的语句如何分析？ 词法分析实例： 如下列Fortran 语言中的语句如何分析？ DO 10 K=1,10 ！循环语句 DO 10 K=1.10 ！赋值语句 解决方法：假读：超前搜索（超前扫描） 超出边界怎么办？ 返回本节

语法分析 语法分析是翻译过程的核心部分。语法分析的任务是：按照语法，从源程序数据项中识别出各类语法成分，同时进行语法检查，为语义分析和代码生成做准备。 执行语法分析任务的程序是语法分析程序，也称之为语法分析器。 一般采用的方法有自顶向下分析方法：递归子程序法和LL(1)分析法；自低向上的分析方法：和LR分析法。 高效的语法分析是基于形式语法的技术。 返回本节

语义分析 语义分析的任务是：处理语法分析而识别出来的语法结构，生成中间代码。语义分析任务由语义分析器完成。 许多其它的辅助功能也在该过程进行，如符号表的维护、隐含信息的插入、错误检测、宏的扩展等。

目标程序的生成 语义分析器的输出结构是中间代码。中间代码一般是一种内部表达方式。代码生成器将根据这些中间代码生成目标代码。但在代码生成之前，可对中间代码进行一些优化处理。如果，子程序是单独翻译的或者需要使用子程序库，则还需进行连接和装入。 因此，目标代码的生成阶段通常包含的处理过程有： 优化 代码的生成 连接和装入

优化 考虑语句: A = B + C + D; 可能生成的中间代码是： a) tmp1 = B + C; b) tmp2 = tmp1 + D; c) A = tmp2; 直接生成的执行代码是： 1）B传入寄存器 2) 寄存器加C 3) 寄存器的值存tmp1中 4）tmp1传入寄存器 5) 寄存器加D 6) 寄存器的值存tmp2中 7) tmp2传入寄存器 8) 寄存器的值存A中 可见3、4、6、7指令是多余的 。优化后可以获得较高的执行效率。

代码的生成 经过语义分析产生的中间代码经过优化后，必须转化成汇编语言、机器语言或其他可作为编译输出的目标程序。该处理包括根据内部程序表达式所提供的信息对输出进行适当的格式化。

连接与装入 如果，子程序是单独翻译的或者需要使用子程序库，则还需进行连接和装入，以便组成一个完整的目标程序。

系统自举 通常一种新语言的翻译器就是用该语言编写的。翻译器（翻译程序）本身是怎么被翻译的？即系统自举？ 解决方法：手工将翻译器翻译成虚拟机上可执行的目标程序。该方法虽然繁琐，但并不困难。

3.3 BNF文法 文法：即语法，对语言机构的定义与描述。 我们首先考虑一个自然语言句子实例。如 张三踢足球。 该语句是汉语句子？肯定！因为它符合汉语语法，是一种主谓宾结构的语句。

语法树 根据汉语语法，上述句子的语法结构可用树的形式表示，称之为语法树。 任何一个语法正确的汉语句子读可以根据语法画出相应的语法树，通过语法树，将一个句子分解为各个组成部分。在语法树中，带<>的节点称为“语法成分”，在形式语言中称为“非终结符”，不带<>的节点称为“单词”，在形式语言中称为“终结符”。

规则 我们也可以通过建立一组规则，来描述上述句子的语法结构，如用“::=”表示“由……组成”，则上述句子可用下面的规则刻划： <句子>::= <主语> <谓语> <宾语> <主语> ::= <名词> <谓语> ::= <动词> <宾语> ::= <名词> <名词> ::=张三 <动词> ::=踢 <名词> ::=足球

BNF范式 对于具有相同左部的规则，如<名词> ::=张三， <名词> ::=足球，可以缩写为 <名词> ::=张三 | 足球。 这就是著名的BNF表示法，或“巴科斯范式(Backus Normal Form)”。式中的“::=” 表示“定义为”，“|”表示“或”。 如应用BNF范式，可以写出<无符号整数>的语法结构： <无符号整数>::= <数字串> <数字串>::=<数字串> <数字> |<数字> <数字>::=0|1|2|…|9|

语法树与二义性 如果用某种语法定义的句子中，有某个句子存在两棵不同的语法树，则该语法是二义性的，否则，该语法无二义性。 如语法G[E] E::=E+E|E-E| E*E| E/E|(E)|I I+I*I是该语法的一个句子，但存在两棵语法树，故该语法存在二义性。

一般，为了是编译能够顺利的进行，应该避免定义二义性的语法。然而，遗憾的是，已经证明，二义性的性质是不可判定的，即不存在一种算法，它接收任一BNF文法，能在有穷步骤内判定出该文法是否是二义性的。 解决方法： 根据提出的条件修改编译算法； 如else 就近匹配原则。 根据提出的条件直接修改文法； 如修改 G[E]文法定义为： E::= T|E+T|E-T T::=F|T*F|T/F F::=(E)|I

BNF符号的扩充（1） BNF的功能强大、外观优美、使用简单，但它往往对文法中一些常用的语法结构，如选择成分、交替成分及循环成分做出了相当不自然的表述。如<无符号整数>的BNF表示： <无符号整数>::= <数字>| <无符号整数> <数字> <数字>::=0|1|2|…|9| 其存在的缺点是： 1) 包含了左递归，使文法具有复杂的递归性； 2）由于递归，无符号整数的长度任意，不能表示出具体语言对该语法成分的最大长度限制。

BNF符号的扩充（2） 在BNF文法中，通常使用3个元符号：“<>”，“::=”和“|”。在扩充的BNF中，新引入了三个元符号：“{}”，“[]”和“（）”。下面作简单介绍： ：其中，t为符号串，表示t可重复出现n到次，一般约定n=0。如 好处： 方便的表示重复次数； 消除了左递归；

BNF符号的扩充（3） [t]: 其中，t为符号串，表示 t 是可选择项。如 <条件语句>::=<if 子句>| <if 子句> else <语句> <if 子句> ::= if <布尔表达式> then <语句> 引入[]后，可表示为： <条件语句>::=<if 子句>[else <语句>] 实际上， []与{}的n=0，m=1特例等价。 好处：表达更为直观。

BNF符号的扩充（4） （t）: 其中，t为符号串，可以提取因子。如 U::=xy|xw|…|xz 可提取因子，表示为： U::=x（y|w|…|z） 好处：使词法分析工作变的容易些。

本章小节 语法是以句子中词的排列来表明它们的彼此关系。它描述了组成一个合法程序的符号的系列，是理解一个程序的重要手段，也为将源程序翻译成目标程序提供了必要的信息。 通用语法的标准是：好的可读性、可写性、容验证性、易翻译性和无二义性。 二义性是指相同的语法形式允许存在两种或更多的语义解释。二义性的显著特点是存在两棵或更多的语法树。无二义性是每个程序语言设计的中心问题。

通常解决二义性的方法是：1）使用定界符；2）选择多种语义中的一种作为唯一合理的解释。 主程序-子程序的语法组织有六种：独立子程序定义、独数据定义、嵌套子程序定义、独立接口定义、非独立子程序定义、独立出来的数据描述。不同的语法结构对翻译具有不同的要求和影响。 翻译是指将一个程序从原来的语法形式转换成可执行的形式。 翻译可分成两个主要的部分：源程序分析和目标程序的综合。

编译的过程可经过一次或多次扫描完成。到底采用几次与程序语言对编译速度和执行速度的追求目标的不同而密切相关。标准编译器一般采用两次扫描，如果追求编译速度，则采用一次扫描，如果追求执行速度，则可采用三次甚至更多次的扫描。 源程序分析包括词法分析、语法分析和语义分析阶段。目标程序的综合包括优化、代码的生成、连接和载入等阶段。 BNF文法是一种结构简单，功能较强的上下文无关文法。BNF扩充文法进一步增强它的功能。

习题 T1,2,3,5,6,11 补充习题： 1）解释名词可读性、可写性、易验证性和易翻译性的含义。 2）什么叫二义性，解决方法通常有哪些。 3）简述词法分析、语法分析的原理和过程。 4）简述语义分析的主要功能。 5）简述优化的原理。