《第3语言翻译问题》由会员分享，可在线阅读，更多相关《第3语言翻译问题（59页珍藏版）》请在金锄头文库上搜索。
1、艳墙菩匿造弟苔讶寥煌磺蹭极淋傣委绷饭赊夯叁烷狐惩审吓擞旧求浊豺娶第3语言翻译问题第3语言翻译问题第第3 3 语言翻译问题语言翻译问题 学习目标学习目标 ：学习和掌握语言的语法的基本概念学习和掌握语言的语法的基本概念和基本要素，理解翻译的步骤；学习和掌握和基本要素，理解翻译的步骤；学习和掌握BNFBNF文文法。法。-了解通用语法的标准，学习语法的基本要素；了解通用语法的标准，学习语法的基本要素；-了解几种语言的特点；了解几种语言的特点；-学习和掌握源程序分析和目标程序综合的原理和学习和掌握源程序分析和目标程序综合的原理和方法；方法；-掌握和使用掌握和使用BNF文法；文法；秉锹抑想二蛹私吕胞椎德滦
2、卒髓薯稿夸突垮颧除光师位肋廓优俞末开樱盗第3语言翻译问题第3语言翻译问题 重点和难点重点和难点 ：本章的重点是：源程序的分析和目标程序综合的本章的重点是：源程序的分析和目标程序综合的原理与方法；原理与方法；BNF文法；文法；本章的难点是：语法二义性，语义分析原理；本章的难点是：语法二义性，语义分析原理； 知识点知识点 ：语法；语义；二义性；独立子程序定义；独立数语法；语义；二义性；独立子程序定义；独立数据定义；嵌套子程序定义；独立接口定义；词法据定义；嵌套子程序定义；独立接口定义；词法分析；语法分析；语义分析；优化；连接与载入；分析；语法分析；语义分析；优化；连接与载入；系统自举；语法树；系统
3、自举；语法树；BNF文法文法袭喳潜旨决弹佃养捌浸垃隐绚位拘阀洋孕惦谭态望规歧故澄谁辙击涤肋振第3语言翻译问题第3语言翻译问题l对于在虚拟计算机上实现的高级语言程序，对于在虚拟计算机上实现的高级语言程序，必须经过翻译才能在实际的计算机上运行。必须经过翻译才能在实际的计算机上运行。l翻译一般要经翻译一般要经“词法分析词法分析”“”“语法分析语法分析” “” “语义分析语义分析” “” “代码优化代码优化” ” “目标程序生成目标程序生成”等等5 5个阶段。其中，个阶段。其中， “ “语法分析语法分析”阶段最为重要，它是描述程序结阶段最为重要，它是描述程序结构的主要手段。构的主要手段。l“遍遍”的概
4、念？的概念？l“一遍一遍”翻译？翻译？“二遍二遍”翻译？翻译？ “ “三遍三遍”翻译？翻译？ 本章概述录滞帐阴炊傣恿磨阴珊扫遏殊钡尧抽乞沿莉怪篆仔奸琉痞惨钝优郸懈哭报第3语言翻译问题第3语言翻译问题本章主要内容本章主要内容3.13.1 编程语言语法编程语言语法3.23.2 翻译步骤翻译步骤3.33.3 BNFBNF文法文法盗舰镊绳失幌耻酋撼薯终腮兹吕颤独歹奎廊杰困舀脚幌悯撞状粗颓报陆这第3语言翻译问题第3语言翻译问题3.1 编程语言语法编程语言语法l语法：以句子中词的排列来表明它们的彼此关系。语法：以句子中词的排列来表明它们的彼此关系。如如C语言中，语言中，x=y+z具有正确的语法，而具有正确
5、的语法，而x+-则语则语法错误。法错误。l语法是理解一个程序的重要手段，也为将源程序语法是理解一个程序的重要手段，也为将源程序翻译成目标程序提供了必要的信息。翻译成目标程序提供了必要的信息。l但，只有语法是不够的。如但，只有语法是不够的。如“张三踢足球张三踢足球”和和“足球踢张三足球踢张三”，语法都正确，但语义，语法都正确，但语义？如如 x = 2.54+3.67, 结果为结果为5,6,6.21?赠砍冠灭窑吏桃秦蝶野作锦晤耿扛藩蛋菲癌后喇晋蟹掖惺瘴妈跳俏燎客纶第3语言翻译问题第3语言翻译问题本节主要内容本节主要内容l通用语法标准通用语法标准l语言的语法要素语言的语法要素l主程序主程序- -子程
6、序结构子程序结构蜜跟龋必肾笺柑觅处竞酸崇势抚渠草戴渣辞嫡单祝远侦溪剔破入磐嫉悬拜第3语言翻译问题第3语言翻译问题通用语法标准通用语法标准l可读性：可读性：如果一个程序的算法和数据结构能够明显的如果一个程序的算法和数据结构能够明显的从程序文本中观察出来，则这个程序是可读从程序文本中观察出来，则这个程序是可读的。可读的程序称之为自引证的。的。可读的程序称之为自引证的。可读性成为如今程序编制的重要目标是一。可读性成为如今程序编制的重要目标是一。增加可读性的方法：用自然语句格式、结构增加可读性的方法：用自然语句格式、结构化、自由使用关键字和噪声码、注释、不限化、自由使用关键字和噪声码、注释、不限标识符
7、长度、助记符、自由域格式、完整的标识符长度、助记符、自由域格式、完整的声明。声明。医驮境钎厅宛膳秤郑幅坚赡赂醒署涅隋承每役洋衔榜即眶侣谎话拭唱咖狂第3语言翻译问题第3语言翻译问题l可写性：可写性：可写性是指程序易于编写。语法结构简单的可写性是指程序易于编写。语法结构简单的语言程序可写性好。语言程序可写性好。增加可写性的方法：设计简洁、整齐的语法增加可写性的方法：设计简洁、整齐的语法结构。允许保留不明确声明和操作的隐含。结构。允许保留不明确声明和操作的隐含。可写性与可读性是一对矛盾。简洁的结构可可写性与可读性是一对矛盾。简洁的结构可增强程序的可写性，但降低了程序的可读性。增强程序的可写性，但降低
8、了程序的可读性。如如C语言，可写性较好，但可读性差。允许语言，可写性较好，但可读性差。允许保留不明确声明和操作的隐含可增强可写性，保留不明确声明和操作的隐含可增强可写性，但会降低可读性，同时可检验性差。但会降低可读性，同时可检验性差。蚂鄂回避蹲呈园举肇搓慨拾柳熏圭龟镊按似造杨封鲤合拔鹅召驴怠侣枉咳第3语言翻译问题第3语言翻译问题l易检验性：易检验性：证明程序的正确性。证明程序的正确性。这不仅涉及到语法，主要涉及到语义的正确这不仅涉及到语法，主要涉及到语义的正确性验证。性验证。目前，主要通过一些测试方法，以及谓词演目前，主要通过一些测试方法，以及谓词演算方法来验证。算方法来验证。骄正懂栽示罩贮唾
9、柿寸巧氧锣测照谗灵惊曰今芹弟术景厚似休痒盲盼泊仟第3语言翻译问题第3语言翻译问题l易翻译性：易翻译性：源程序容易翻译成可执行的目标程序。易翻源程序容易翻译成可执行的目标程序。易翻译性与翻译器密切关联。译性与翻译器密切关联。易于翻译的关键是结构的规范化。易于翻译的关键是结构的规范化。易翻译性与可读性和可写性之间存在矛盾。易翻译性与可读性和可写性之间存在矛盾。如如LISP程序易于翻译，但可读性和可写性较程序易于翻译，但可读性和可写性较差。差。COBOL语言程序的语义较为简单，可语言程序的语义较为简单，可读性和可写性较好，但由于存在数量庞大的读性和可写性较好，但由于存在数量庞大的语句和声明，翻译极为
10、困难。语句和声明，翻译极为困难。孩党容伺肮饵怀乖荐俩疫措丈闰婉夏埃枯伟期毒吭埋杉宵栋窝关岳翰鳖砂第3语言翻译问题第3语言翻译问题l无二义性：无二义性：所谓二义性是指：相同的语法结构存在两种所谓二义性是指：相同的语法结构存在两种或更多种理解。无二义性是每个程序语言设或更多种理解。无二义性是每个程序语言设计的中心问题。二义性问题通常不是出现在计的中心问题。二义性问题通常不是出现在单个的程序元素中，而是在不同结构的相互单个的程序元素中，而是在不同结构的相互作用下表现出来的。作用下表现出来的。例例1：C语言中存在两种不同的条件形式：语言中存在两种不同的条件形式： if (ConE) S if (Con
11、E) S1 else S2每一条语句均清楚的解释了语义，不存在二每一条语句均清楚的解释了语义，不存在二义性。但将两个语句组合为：义性。但将两个语句组合为： if (ConE1) if (ConE2) S1 else S2 此时，存在二义性。此时，存在二义性。码止胸席卷哉徽绩暇查粟刃详褪悦橇说翅悦么发喧轻祭氨夸悟民肥陇蚜哈第3语言翻译问题第3语言翻译问题语句语句S2的执行控制存在不同的理解，是的执行控制存在不同的理解，是ConE1为假时执行，还是为假时执行，还是ConE1为假时执行为假时执行？解决方法：解决方法：l插入定界符，如插入定界符，如 if (ConE1) if (ConE1) if (
12、ConE2) S1； 或或 if (ConE2) S1； else S2； else S2；l二者语义中强制的选择一种作为合法的解二者语义中强制的选择一种作为合法的解释，如就近匹配原则，即释，如就近匹配原则，即else与最近的与最近的 if 匹配。匹配。怪缨幂飞疡青休垣虑铃烛琼偷锰允抉晤蹋蟹颐作郁混灿琶剖匝奥支焦典牌第3语言翻译问题第3语言翻译问题例例2：Fortran语言中，函数调用和数组引用语言中，函数调用和数组引用语法是完全相同的。如语句语法是完全相同的。如语句 x = A(i,j) 存在二义性。此时存在二义性。此时A(i,j)是函数是函数A的调用？还是的调用？还是数组数组A的引用？的引
13、用？解决方法：若没有数组解决方法：若没有数组A的声明，就默认为的声明，就默认为是函数是函数A的调用。的调用。Pasacl和和C语言中的解决方语言中的解决方案是：用案是：用表示数组，（）表示函数，如表示数组，（）表示函数，如Ai,j理解为数组引用，理解为数组引用， A(i,j)解释为函数调解释为函数调用用。返回本节返回本节娩渣怎级纽汀奏霹耳沼银崭厦插载够镣恐莹溶擦玉息竟排巢淆胖限氛阎贱第3语言翻译问题第3语言翻译问题语言的语法要素语言的语法要素l选用不同的基本语法要素就形成了一种语言的选用不同的基本语法要素就形成了一种语言的基本风格。下面，将简介一些语法要素。基本风格。下面，将简介一些语法要素。
14、l字符集：字符集：字符集的选择是语法设计的第一步。通常选字符集的选择是语法设计的第一步。通常选择的字符集是择的字符集是ASCII字符集。字符集。目前，通常使用目前，通常使用8为（一个为（一个Byte）来表示一）来表示一个字符，这足够表示个字符，这足够表示52个大小写字母、个大小写字母、10个个数字、标点符号以及一些特殊字符。但如今，数字、标点符号以及一些特殊字符。但如今，计算机工业越来越国际化，各个国家的文字、计算机工业越来越国际化，各个国家的文字、货币符号等已远远超过货币符号等已远远超过256。因此，考虑使。因此，考虑使用用16位表示字符集。位表示字符集。阉埔见暴浇靡报玛诅芬氓盟疹戏应衔兵崩
15、吗肿舰盐摹赔菲痞筷玛肢俏讽坊第3语言翻译问题第3语言翻译问题l标识符标识符: :大多数语言都遵循以字母开始字母和数字组大多数语言都遵循以字母开始字母和数字组成的字符串作为标识符的原则。有的语言还成的字符串作为标识符的原则。有的语言还允许包括允许包括“.”和和“_”之类的特殊字符。如之类的特殊字符。如name_student是是C中的合法标识符。这样，中的合法标识符。这样，可以增强可读性和改善长度方面的限制。可以增强可读性和改善长度方面的限制。标识符长度应该不受限制。标识符长度应该不受限制。宁毛箔集掩肺涪狰绩蚕缅锤路苛和酪颜盅娜丧城搁驱区掇珐吾详痈身吸用第3语言翻译问题第3语言翻译问题l操作符：
16、操作符：大多数语言均使用大多数语言均使用 “+” 和和 “-” 来表示基来表示基本的数学运算操作，除此之外，很少有相同本的数学运算操作，除此之外，很少有相同的。的。如如Pascal使用使用 “：=”作为赋值操作，而作为赋值操作，而C使使用用 “=”。 Pascal使用使用 “=” 作为比较操作，作为比较操作，而而C使用使用 “= =”，Fortran 使用字符串使用字符串.EQ.。 高瘦比荔痢括睦饰仕汾唤萎尾珊项华鸟气靳隅菇淑轰涸钳督匣初友玉袭驰第3语言翻译问题第3语言翻译问题l关键字和保留字：关键字和保留字：关键字是语句语法中固定部分使用的标识符。当关关键字是语句语法中固定部分使用的标识符。
17、当关键字不能用作程序的标识符时，该关键字就是一个键字不能用作程序的标识符时，该关键字就是一个保留字。如保留字。如C语言中的语言中的 if, for, while等。等。使用保留字使翻译过程中的语法分析变得简单。作使用保留字使翻译过程中的语法分析变得简单。作为反面例子，为反面例子，Fortran 中用户可以使用中用户可以使用DO 和和 IF作作为标识符，因此以为标识符，因此以DO 和和 IF 开始的语句实际上并不开始的语句实际上并不一定是循环或条件语句，所以一定是循环或条件语句，所以Fortran 的语法分析的语法分析较为困难。较为困难。使用保留字可增加程序的可读性。使用保留字可增加程序的可读性
18、。但保留字也不能太多，否则难以记忆，编程不方便。但保留字也不能太多，否则难以记忆，编程不方便。如如COBOL的保留字太多。的保留字太多。但当语言扩充而扩充新的保留字时，会引来麻烦。但当语言扩充而扩充新的保留字时，会引来麻烦。叹妻箱朵粕傀盛婴冤塑数挤限鳖玻蜘福柄囤悟兹吐冤贵绅这峦皱熬椰死室第3语言翻译问题第3语言翻译问题l噪声码：噪声码：插入在于语句中用来增加可读性的可选代码。插入在于语句中用来增加可读性的可选代码。如如Basic 语言中语言中“GOTO”语句中的语句中的“GO”是是必需的关键字，而必需的关键字，而“TO”是可选的噪声码。是可选的噪声码。如汇编语言中，如汇编语言中， return
19、 n 中的中的n是噪声码。是噪声码。眉羡左医检傻果解蜡反彻儒辰振洼愤系于慧糟棕哭彦氓装逃邓恋师胚注凄第3语言翻译问题第3语言翻译问题l注释：注释：注释是程序文档中的重要组成部分。一种语注释是程序文档中的重要组成部分。一种语言可以使用多种方法引入注释。如：言可以使用多种方法引入注释。如：Basic 中使用中使用 REM 引导单独的注释行；引导单独的注释行；C、Java语言中使用语言中使用“ /*”和和“*/”作为多作为多行注释定界符。行注释定界符。Ada中的中的“-”，C+中的中的“/”，Fortran 语言中的语言中的“!”，Basic中的中的“ ”都可以都可以从语句行的人以位置开始标示注释。
20、从语句行的人以位置开始标示注释。塞立冲筷刮雇欲恿絮又辙目限辗撤铁层斌晃指削贿跟解洞舀叠忘莲溉席獭第3语言翻译问题第3语言翻译问题l空白符（空格）空白符（空格）各种语言使用空白符的规则不太相同。各种语言使用空白符的规则不太相同。如如C语言中，空白符在除字符串数据以外的任何语言中，空白符在除字符串数据以外的任何地方没有重要的意义。？地方没有重要的意义。？起分隔符号的作用。起分隔符号的作用。在词法分析中有重要的作用。多余的空白符在词法分析中有重要的作用。多余的空白符被忽略。被忽略。在在SNOBOL4语言中，空白符起基本连接操语言中，空白符起基本连接操作作用。作作用。魏啦闸怖折息攫达几丑枯笑支辣河论富
21、扎暖袭狄笛镐荣芭骋筹色铝格求财第3语言翻译问题第3语言翻译问题l定界符：定界符：定界符一般用于简单的标示诸如语句或表达定界符一般用于简单的标示诸如语句或表达式这些语法单位的语法元素。式这些语法单位的语法元素。定界符有时仅用来增强可读性和使语法分析定界符有时仅用来增强可读性和使语法分析变得简单，更多的时候用于清楚的界定特定变得简单，更多的时候用于清楚的界定特定语法结构的边界以消除二义性。语法结构的边界以消除二义性。如如Pascal语言中的语言中的begin end。C语言中的语言中的花括号花括号。栋烯寨槐馒宛募腋骂厄六排伸贸睁坪骆茎匝署带帛搓劝名篱檀执惹镰施拐第3语言翻译问题第3语言翻译问题l自
22、由或固定字段格式：自由或固定字段格式：如果程序中的语句可以书写在一行的任意位如果程序中的语句可以书写在一行的任意位置，则该语言的语法是自由字段格式的。目置，则该语言的语法是自由字段格式的。目前绝大多数的高级语言均采用该语法。前绝大多数的高级语言均采用该语法。若要求程序中的语句每一元素必须在一输入若要求程序中的语句每一元素必须在一输入行的指定位置书写，则该语言的语法是固定行的指定位置书写，则该语言的语法是固定字段格式的。固定字段格式语言的语法利用字段格式的。固定字段格式语言的语法利用输入行的位置来传递信息。如输入行的位置来传递信息。如Fortran77语语言的一行言的一行80列分为四个区：列分为
23、四个区：15列为标号区；列为标号区；第第6列为列为“续行标志区续行标志区”；第；第772列为语句列为语句区；第区；第7380列为注释区。列为注释区。克块侦靳毒窝优获房她年聘委佬秤贰讼无款光商扰了挤底樟扛辟赢伴款役第3语言翻译问题第3语言翻译问题电信溶旅场茎侗锌巡肯蕊仁卤胃阉检恰贯慎认凑号轧零结粘撩敖得帐叶跑第3语言翻译问题第3语言翻译问题l表达式：表达式：表达式的作用是访问程序中的数据对象并返表达式的作用是访问程序中的数据对象并返回值。表达式是语句的基本元素，有时甚至回值。表达式是语句的基本元素，有时甚至是程序的基本元素。如是程序的基本元素。如C中，表达式组成了中，表达式组成了改变机器状态的基
24、本操作。在改变机器状态的基本操作。在ML和和LISP语语言中，表达式形成了驱动程序执行的基本顺言中，表达式形成了驱动程序执行的基本顺序控制。序控制。嗽炉宅索企郡堑潘挺援墨径柞藕装婶摆寺呕蔚阿芍坐眺形天计簇返洱魄掌第3语言翻译问题第3语言翻译问题l语句：语句：语句是命令式语言中最重要的语法单元。语语句是命令式语言中最重要的语法单元。语句的语法对整个语言的规则性、可读性和可句的语法对整个语言的规则性、可读性和可写性有着决定性的作用。写性有着决定性的作用。侧重于规则性的语言使用一个基本的语句格侧重于规则性的语言使用一个基本的语句格式。如式。如SNOBOL4语言只使用一种基本的语语言只使用一种基本的语
25、句语法，即模式匹配替代语句。句语法，即模式匹配替代语句。侧重于可读性的语言则对不同类型的语句是侧重于可读性的语言则对不同类型的语句是用不同的语法。大多数的语言采用该方式。用不同的语法。大多数的语言采用该方式。返回本节返回本节合包某允烩敌藐埂港料骂欺毛犊搓韶扯嘉昼儡呛嫩黑慈直晰质杖张虑弊叫第3语言翻译问题第3语言翻译问题主程序主程序- -子程序结构子程序结构l主程序主程序-子程序结构的语法组织的定义与其他子程序结构的语法组织的定义与其他语言语法一样千差万别。语言语法一样千差万别。独立子程序定义独立子程序定义lC语言的语法组织结构将每个子程序定义语言的语法组织结构将每个子程序定义看作独立的语法单元
26、。看作独立的语法单元。l每个子程序能够独立的编译并在装入的时每个子程序能够独立的编译并在装入的时候通过连接形成一个完整的程序。候通过连接形成一个完整的程序。l面向对象语言要求信息能够在独立编译的面向对象语言要求信息能够在独立编译的单元中传递。类定义的继承性要求编译器单元中传递。类定义的继承性要求编译器在程序装入运行之前处理所有独立子程序在程序装入运行之前处理所有独立子程序痹粮妈蓖疙员贱爵版均扳奢霍浦箕渠政柒否盏导彤拈袋白澜古寐躁种诽范第3语言翻译问题第3语言翻译问题int aa(x,y) void bb(x,y)int x,y; float x; int y; main() float a;
27、int b,c; bb(a,b); aa(c,b); 透竭桃器秘猪危钟消臭戴庄环卑桓步桐着紫未钠昌摇帜豹蝎帛另罕就闷煞第3语言翻译问题第3语言翻译问题l独立数据定义：独立数据定义：将所有对一个给定数据对象的操作组织在一将所有对一个给定数据对象的操作组织在一起。一个子程序可能包括该程序中涉及一个起。一个子程序可能包括该程序中涉及一个特定数据类型的所有操作，如建立、打印、特定数据类型的所有操作，如建立、打印、运算数据记录的操作。运算数据记录的操作。Java、C+和和Smalltalk语言中类机制通常采语言中类机制通常采用这种方法。用这种方法。棍箍窟摊袭袖治囱献赔腔卧牡掀幽斑聪再年锹庸末情可仕羡韵声
28、垛携咏呵第3语言翻译问题第3语言翻译问题l嵌套子程序定义：嵌套子程序定义：所有子程序的定义嵌套在主程序中。所有子程序的定义嵌套在主程序中。嵌套子程序定义对于建立模块化程序起者重嵌套子程序定义对于建立模块化程序起者重要的作用。要的作用。嵌套子程序定义为那些在编译时定义的、允嵌套子程序定义为那些在编译时定义的、允许静态类型检查且允许为包含非局部引用的许静态类型检查且允许为包含非局部引用的子程序编译高效的可执行代码的子程序提供子程序编译高效的可执行代码的子程序提供了一种非局部的引用环境。了一种非局部的引用环境。Pascal语言是嵌套子程序定义的典型。语言是嵌套子程序定义的典型。串韧且住撞欣梧皱蚜蜕瞧
29、哇邀令质轮转质饿耶玛射示肺通皆祁绣俐哨嘲庇第3语言翻译问题第3语言翻译问题 program mainPro (input, output) procedure pro begin end function fun(x: integer): integer; begin end begin (*main begin) end 培侧庇坪肤句摇蓟恨床历官时鹅导太雾虏占叫耪员箱崭药革惶凶撂榜跨傣第3语言翻译问题第3语言翻译问题l独立接口定义：独立接口定义：将若干个子程序相关的接口进行单独定义。将若干个子程序相关的接口进行单独定义。其好处是：其好处是：1）编译器可方便的检测出相同）编译器可方便的检测出相
30、同数据在不同子程序中不同定义的错误；数据在不同子程序中不同定义的错误；2）调试时只需重新编译修改过的模块，提高编调试时只需重新编译修改过的模块，提高编译效率。译效率。如如C语言中，语言中，“.h”文件形成了形式说明部文件形成了形式说明部分，以解决两个独立编译组件之间传输信息分，以解决两个独立编译组件之间传输信息的问题，而的问题，而“.c”文件形成了实现部分。文件形成了实现部分。豆芝努烬稼沈宝喧辊榨臭鸭罪臀幌措立把熙替味倪喧排搔任效屑拎策狂祟第3语言翻译问题第3语言翻译问题l从可执行语句中独立出来的数据描述从可执行语句中独立出来的数据描述讲数据与程序进行分离讲数据与程序进行分离; ;好处是使得数
31、据格式与程序分区中的运算逻好处是使得数据格式与程序分区中的运算逻辑独立。只修改数据分区就可以完成数据结辑独立。只修改数据分区就可以完成数据结构的细微变动而不需同时修改程序。构的细微变动而不需同时修改程序。灭立步防反或警楼铰讯臆桌蜂敞绚决赔伏囊搅一毁销院浮剑疤振舀牙斧冒第3语言翻译问题第3语言翻译问题l非独立子程序定义非独立子程序定义主程序与子程序之间没有任何语法的区别。主程序与子程序之间没有任何语法的区别。即程序组织结构无组织性。即程序组织结构无组织性。一个函数调用即开始了一个新的子程序，一个函数调用即开始了一个新的子程序，Return 的执行则结束一个子程序。的执行则结束一个子程序。程序的行
32、为完全是动态的。程序的行为完全是动态的。SNOBOL4是典型的实例。是典型的实例。返回本章返回本章雅洁滋彭拔矩灸品享语汤缨途词烃垫犀纹雀讳醚籽陈南呢牌惯卵暮者咯矗第3语言翻译问题第3语言翻译问题3.2 3.2 翻译的步骤翻译的步骤l高级语言源程序必须经过翻译才能在虚拟计算高级语言源程序必须经过翻译才能在虚拟计算机上运行。机上运行。l翻译一般是一个较为复杂的过程。通常经过翻译一般是一个较为复杂的过程。通常经过“词法分析词法分析”“”“语法分析语法分析” “” “语义分析语义分析” “” “代码优化代码优化” “” “目标程序生成目标程序生成”等等5 5个阶段。可归纳为源程序的分析和目标代码个阶段
33、。可归纳为源程序的分析和目标代码的生成。的生成。l翻译通常追求高效的编译速度或高效的可执行翻译通常追求高效的编译速度或高效的可执行的优化代码。的优化代码。l“一遍一遍”翻译？翻译？“二遍二遍”翻译？翻译？ “ “三遍三遍”翻翻译？译？l由于编译技术的发展，编译速度与扫描次数之由于编译技术的发展，编译速度与扫描次数之间的关系不明显了，而语言的复杂度显得突出间的关系不明显了，而语言的复杂度显得突出拒卸缺仍暖静搅峙汹斋骆默史勇价脚傈诽藕铱座舀己钒挥议二期滇婆桓辊第3语言翻译问题第3语言翻译问题源程序的分析源程序的分析l具体过程包括：具体过程包括：词法分析词法分析语法分析语法分析语义分析语义分析邀温缎
34、矣挖堤胰信叉碴沃谷雷金涛卞吸豪念瓣丝坝要毋也皆匪倒土肿丁压第3语言翻译问题第3语言翻译问题词法分析词法分析l将源程序中的字符串划分成基本要素单元：标将源程序中的字符串划分成基本要素单元：标识符、限定词、运算符、数字、关键字、噪声识符、限定词、运算符、数字、关键字、噪声码、空格、注释等。划分的结果称为语法项。码、空格、注释等。划分的结果称为语法项。l该分析过程由词法分析器完成。该分析过程由词法分析器完成。l虽然词法分析的概念简单，但过程复杂，耗费虽然词法分析的概念简单，但过程复杂，耗费的编译时间较长。必须对源程序进行逐字的阅的编译时间较长。必须对源程序进行逐字的阅读和分析。读和分析。魄条段拥突乘
35、赔萍熊孜缎沤瑶券疑柔描质狂牌极婿踞蹋限斡本揣移舶忆炯第3语言翻译问题第3语言翻译问题l词法分析实例：词法分析实例：l如下列如下列Fortran 语言中的语句如何分析？语言中的语句如何分析？ DO 10 K=1,10 ！循环语句！循环语句 DO 10 K=1.10 ！赋值语句！赋值语句l解决方法：假读：超前搜索（超前扫描）解决方法：假读：超前搜索（超前扫描）l超出边界怎么办？超出边界怎么办？返回本节返回本节嗜株同欲匙袱塑之蛔看栓拾术掐厦呢我锅网贿侮潦揣糠流蛹疆蓉坞殿捧跺第3语言翻译问题第3语言翻译问题语法分析语法分析l语法分析是翻译过程的核心部分。语法分析的语法分析是翻译过程的核心部分。语法分析
36、的任务是：按照语法，从源程序数据项中识别出任务是：按照语法，从源程序数据项中识别出各类语法成分，同时进行语法检查，为语义分各类语法成分，同时进行语法检查，为语义分析和代码生成做准备。析和代码生成做准备。l执行语法分析任务的程序是语法分析程序，也执行语法分析任务的程序是语法分析程序，也称之为语法分析器。称之为语法分析器。l一般采用的方法有自顶向下分析方法：递归子一般采用的方法有自顶向下分析方法：递归子程序法和程序法和LL(1)分析法；自低向上的分析方法：分析法；自低向上的分析方法：和和LR分析法。分析法。l高效的语法分析是基于形式语法的技术。高效的语法分析是基于形式语法的技术。返回本节返回本节糙
37、化竣缆汇卖傻沧目企梅观赞儿贤瘩茹啃隙胰挠败隋赵驮嫉郊诡具烘淹祈第3语言翻译问题第3语言翻译问题语义分析语义分析l语义分析的任务是：处理语法分析而识别出来语义分析的任务是：处理语法分析而识别出来的语法结构，生成中间代码。语义分析任务由的语法结构，生成中间代码。语义分析任务由语义分析器完成。语义分析器完成。l许多其它的辅助功能也在该过程进行，如符号许多其它的辅助功能也在该过程进行，如符号表的维护、隐含信息的插入、错误检测、宏的表的维护、隐含信息的插入、错误检测、宏的扩展等。扩展等。秦基颜霞颅均冠毡疼犯鄂木抡惮撰扦妆豹隆滩危痛战晴通钡唤殊锄霉肋悸第3语言翻译问题第3语言翻译问题目标程序的生成目标程序
38、的生成l语义分析器的输出结构是中间代码。中间代码语义分析器的输出结构是中间代码。中间代码一般是一种内部表达方式。代码生成器将根据一般是一种内部表达方式。代码生成器将根据这些中间代码生成目标代码。但在代码生成之这些中间代码生成目标代码。但在代码生成之前，可对中间代码进行一些优化处理。如果，前，可对中间代码进行一些优化处理。如果，子程序是单独翻译的或者需要使用子程序库，子程序是单独翻译的或者需要使用子程序库，则还需进行连接和装入。则还需进行连接和装入。l因此，目标代码的生成阶段通常包含的处理过因此，目标代码的生成阶段通常包含的处理过程有：程有：优化优化代码的生成代码的生成连接和装入连接和装入评证秋
39、题寓铆督刊帜旷趁梧爬跋潘惟膛守皆鄂玖脊幸砰瓶护呵徊羌姆卸端第3语言翻译问题第3语言翻译问题优化优化l考虑语句考虑语句: : A = B + C + D;l可能生成的中间代码是：可能生成的中间代码是： a) tmp1 = B + C; b) tmp2 = tmp1 + D; c) A = tmp2; 可见可见3 3、4 4、6 6、7 7指令指令是多余的是多余的 。优化后可。优化后可以获得较高的执行效以获得较高的执行效率。率。直接生成的执行代码是：直接生成的执行代码是：1）B传入寄存器传入寄存器2) 寄存器加寄存器加C3) 寄存器的值存寄存器的值存tmp1中中4）tmp1传入寄存器传入寄存器5)
40、 寄存器加寄存器加D6) 寄存器的值存寄存器的值存tmp2中中7) tmp2传入寄存器传入寄存器8) 寄存器的值存寄存器的值存A中中蛊篱呻腥肝沛蚕尧细粘跺薪赐哎兵超否叭酬店捏殃以旦料琳畸灰乾时翔竞第3语言翻译问题第3语言翻译问题代码的生成代码的生成l经过语义分析产生的中间代码经过优化后，必经过语义分析产生的中间代码经过优化后，必须转化成汇编语言、机器语言或其他可作为编须转化成汇编语言、机器语言或其他可作为编译输出的目标程序。该处理包括根据内部程序译输出的目标程序。该处理包括根据内部程序表达式所提供的信息对输出进行适当的格式化。表达式所提供的信息对输出进行适当的格式化。咳瞥檬寓弹思婴琳进日糜训葡
41、腰代扮谜克佐三巧怜箕稍霜佯淀像橇升腮颖第3语言翻译问题第3语言翻译问题连接与装入连接与装入l如果，子程序是单独翻译的或者需要使用子程如果，子程序是单独翻译的或者需要使用子程序库，则还需进行连接和装入，以便组成一个序库，则还需进行连接和装入，以便组成一个完整的目标程序。完整的目标程序。爹侠升桥架爪脆罩壹虎疮柔嫌逸价寇鸥袄讣糟潘叛唁亡捆唇鼠猖将篇爹斥第3语言翻译问题第3语言翻译问题系统自举系统自举l通常一种新语言的翻译器就是用该语言编写的。通常一种新语言的翻译器就是用该语言编写的。翻译器（翻译程序）本身是怎么被翻译的？即翻译器（翻译程序）本身是怎么被翻译的？即系统自举？系统自举？l解决方法：手工将
42、翻译器翻译成虚拟机上可执解决方法：手工将翻译器翻译成虚拟机上可执行的目标程序。该方法虽然繁琐，但并不困难。行的目标程序。该方法虽然繁琐，但并不困难。沽篷速局孔棉嫂薛嚣垢抹宗贰蔼晚秦撅合肤鬼苏渊壳痉合徊填钒倔蔬枪凶第3语言翻译问题第3语言翻译问题3.3 BNF文法文法l文法：即语法，对语言机构的定义与描述。文法：即语法，对语言机构的定义与描述。l我们首先考虑一个自然语言句子实例。如我们首先考虑一个自然语言句子实例。如 张三踢足球。l该语句是汉语句子？肯定！因为它符合汉语语该语句是汉语句子？肯定！因为它符合汉语语法，是一种主谓宾结构的语句。法，是一种主谓宾结构的语句。遵浑蚜姻倘迄遏洪砷逊呐佑瑟到刚
43、干土澄粗励膳录环巴弱表磷操扮靛刚水第3语言翻译问题第3语言翻译问题语法树语法树 根据汉语语法，上述句子的语法结构可用树的形式表根据汉语语法，上述句子的语法结构可用树的形式表示，称之为语法树。示，称之为语法树。任何一个语法正确的汉语句子任何一个语法正确的汉语句子读可以根据语法画出相应的语读可以根据语法画出相应的语法树，通过语法树，将一个句法树，通过语法树，将一个句子分解为各个组成部分。在语子分解为各个组成部分。在语法树中，带法树中，带的节点称为的节点称为“语语法成分法成分”，在形式语言中称为，在形式语言中称为“非终结符非终结符”，不带，不带的节点的节点称为称为“单词单词”，在形式语言中，在形式语
44、言中称为称为“终结符终结符”。番割虚扫觉痊载浩侈司徘桩何履泪抬丝朝辈蜀胡掠柱松面烧夷入揣趴己枢第3语言翻译问题第3语言翻译问题规则规则l我们也可以通过建立一组规则，来描述上述句我们也可以通过建立一组规则，来描述上述句子的语法结构，如用子的语法结构，如用“:=”“:=”表示表示“由由组组成成”，则上述句子可用下面的规则刻划：，则上述句子可用下面的规则刻划： := := := := := := := := := :=张三张三 := :=踢踢 := :=足球足球酚蕾毛况钻藏仗犊悉余帛肪叹丙闪讫魂绞末漳句匹剑堰拥殴奎嗓将颖城狠第3语言翻译问题第3语言翻译问题BNF范式范式l对于具有相同左部的规则，如对
45、于具有相同左部的规则，如 := :=张三，张三， := :=足球足球，可以缩写为，可以缩写为 := :=张三张三 | | 足球。足球。l这就是著名的这就是著名的BNFBNF表示法，或表示法，或“巴科斯范式巴科斯范式(Backus Normal Form)(Backus Normal Form)”。式中的。式中的“:=” “:=” 表示表示“定义为定义为”，“|”“|”表示表示“或或”。l如应用如应用BNFBNF范式，可以写出范式，可以写出 的语法的语法结构：结构：l := := :=:= | | :=0|1|2|9|:=0|1|2|9|户话存秀逞祭钳邹履踩屑瓤毒辞歌机柳胃瓦暖李厄始卤闯蹄今妖蔓
46、办善目第3语言翻译问题第3语言翻译问题语法树与二义性语法树与二义性l如果用某种语法定义的句子中，有某个句子存如果用某种语法定义的句子中，有某个句子存在两棵不同的语法树，则该语法是二义性的，在两棵不同的语法树，则该语法是二义性的，否则，该语法无二义性。否则，该语法无二义性。l如语法如语法GE E:=E+E|E-E| E*E| E/E|(E)|I I+I*I是该语法的一个句子，但存在两棵语是该语法的一个句子，但存在两棵语法树，故该语法存在二义性。法树，故该语法存在二义性。嘎虞垮朱仰褒寸蜀吟弧藏蓉搓祥涉拧拣山漓吓辊由佯忆及浙聪痕徒刨毡订第3语言翻译问题第3语言翻译问题l一般，为了是编译能够顺利的进行
47、，应该避免定一般，为了是编译能够顺利的进行，应该避免定义二义性的语法。然而，遗憾的是，已经证明，义二义性的语法。然而，遗憾的是，已经证明，二义性的性质是不可判定的，即不存在一种算法，二义性的性质是不可判定的，即不存在一种算法，它接收任一它接收任一BNF文法，能在有穷步骤内判定出该文法，能在有穷步骤内判定出该文法是否是二义性的。文法是否是二义性的。l解决方法：解决方法：根据提出的条件修改编译算法；根据提出的条件修改编译算法；l如如else 就近匹配原则。就近匹配原则。根据提出的条件直接修改文法；根据提出的条件直接修改文法；l如修改如修改 GE文法定义为：文法定义为：E:= T|E+T|E-TT:
48、=F|T*F|T/FF:=(E)|I骡厉调晨卵削光程逮讫淖鲸耐土右堵齿韦她淋嘎莱用记头阻享馏嚼肋峰柳第3语言翻译问题第3语言翻译问题BNF符号的扩充符号的扩充（1）lBNF的功能强大、外观优美、使用简单，但它的功能强大、外观优美、使用简单，但它往往对文法中一些常用的语法结构，如选择成往往对文法中一些常用的语法结构，如选择成分、交替成分及循环成分做出了相当不自然的分、交替成分及循环成分做出了相当不自然的表述。如表述。如 的的BNFBNF表示：表示： := := | | :=0|1|2|9|:=0|1|2|9| 其存在的缺点是：其存在的缺点是： 1) 包含了左递归，使文法具有复杂的递归性；包含了左
49、递归，使文法具有复杂的递归性； 2）由于递归，无符号整数的长度任意，不能由于递归，无符号整数的长度任意，不能表示出具体语言对该语法成分的最大长度限制。表示出具体语言对该语法成分的最大长度限制。俊驶绰娄吊伟瘫喂鸳挛蓄宇脾篇撼璃碗憋坟鳃挑谴瞳灾呕蓑踢恢达泰狭哮第3语言翻译问题第3语言翻译问题BNF符号的扩充符号的扩充（2）l在在BNF文法中，通常使用文法中，通常使用3个元符号：个元符号：“”，“:=”和和“|”。在扩充的。在扩充的BNFBNF中，新引入中，新引入了三个元符号：了三个元符号：“”，“”和和“（）（）”。下面作简单介绍：下面作简单介绍：l ：其中，：其中，t为符号串，表示为符号串，表示
50、t可重复出现可重复出现n n到到次，一般约定次，一般约定n=0。如如l好处：好处：方便的表示重复次数；方便的表示重复次数；消除了左递归；消除了左递归；救奄咋潍器袭动樊毒容帕苹蛤寺崎廖晕淹配箩买跪被滩岛尿措浚言咖厩烹第3语言翻译问题第3语言翻译问题BNF符号的扩充符号的扩充（3）l t: 其中，其中，t为符号串，表示为符号串，表示 t 是可选择项。是可选择项。如如 :=| else := if then 引入引入后，可表示为：后，可表示为： :=else 实际上，实际上， 与与的的n=0，m=1特例等价。特例等价。l好处：表达更为直观。好处：表达更为直观。眉贯藉壬养粪炽锅缎附褐粳挫三角鸡妓挎菠胰
51、失辈茹债凰则贩啮摘且窜成第3语言翻译问题第3语言翻译问题BNF符号的扩充符号的扩充（4）l（t）: 其中其中，t为符号串，可以提取因子。如为符号串，可以提取因子。如 U:=xy|xw|xz 可提取因子，表示为：可提取因子，表示为： U:=x（y|w|z）好处：使词法分析工作变的容易些。好处：使词法分析工作变的容易些。痊据佳蝇伸沙挪钠油梭盟舀瘴喧吕迹重莆交殃顷蛊强剧遣绍盏瞻汉田跳式第3语言翻译问题第3语言翻译问题本章小节本章小节l语法是以句子中词的排列来表明它们的彼此关语法是以句子中词的排列来表明它们的彼此关系。它描述了组成一个合法程序的符号的系列，系。它描述了组成一个合法程序的符号的系列，是理
52、解一个程序的重要手段，也为将源程序翻是理解一个程序的重要手段，也为将源程序翻译成目标程序提供了必要的信息。译成目标程序提供了必要的信息。l通用语法的标准是：好的可读性、可写性、容通用语法的标准是：好的可读性、可写性、容验证性、易翻译性和无二义性。验证性、易翻译性和无二义性。l二义性是指相同的语法形式允许存在两种或更二义性是指相同的语法形式允许存在两种或更多的语义解释。二义性的显著特点是存在两棵多的语义解释。二义性的显著特点是存在两棵或更多的语法树。无二义性是每个程序语言设或更多的语法树。无二义性是每个程序语言设计的中心问题。计的中心问题。艇几牙系双换眶惟芒宾棱裤展傅拾靴肤贡两增鼠现堰磺钉才桑粒
53、速甲粗埔第3语言翻译问题第3语言翻译问题l通常解决二义性的方法是：通常解决二义性的方法是：1）使用定界符；）使用定界符；2）选择多种语义中的一种作为唯一合理的解）选择多种语义中的一种作为唯一合理的解释。释。l主程序主程序-子程序的语法组织有六种：独立子程子程序的语法组织有六种：独立子程序定义、独数据定义、嵌套子程序定义、独立序定义、独数据定义、嵌套子程序定义、独立接口定义、非独立子程序定义、独立出来的数接口定义、非独立子程序定义、独立出来的数据描述。不同的语法结构对翻译具有不同的要据描述。不同的语法结构对翻译具有不同的要求和影响。求和影响。l翻译是指将一个程序从原来的语法形式转换成翻译是指将一
54、个程序从原来的语法形式转换成可执行的形式。可执行的形式。l翻译可分成两个主要的部分：源程序分析和目翻译可分成两个主要的部分：源程序分析和目标程序的综合。标程序的综合。桓澄手时船河灶液阻糙瓷腊麓蔑拙烯脊毁齐呜矿谎熙瘩庭蔷涅鲤养笔愁烽第3语言翻译问题第3语言翻译问题l编译的过程可经过一次或多次扫描完成。到底编译的过程可经过一次或多次扫描完成。到底采用几次与程序语言对编译速度和执行速度的采用几次与程序语言对编译速度和执行速度的追求目标的不同而密切相关。标准编译器一般追求目标的不同而密切相关。标准编译器一般采用两次扫描，如果追求编译速度，则采用一采用两次扫描，如果追求编译速度，则采用一次扫描，如果追求
55、执行速度，则可采用三次甚次扫描，如果追求执行速度，则可采用三次甚至更多次的扫描。至更多次的扫描。l源程序分析包括词法分析、语法分析和语义分源程序分析包括词法分析、语法分析和语义分析阶段。目标程序的综合包括优化、代码的生析阶段。目标程序的综合包括优化、代码的生成、连接和载入等阶段。成、连接和载入等阶段。lBNF文法是一种结构简单，功能较强的上下文文法是一种结构简单，功能较强的上下文无关文法。无关文法。BNF扩充文法进一步增强它的功能。扩充文法进一步增强它的功能。桨馆殴滩蔡狗吊吭齿殆臀敲焉屋尉恼诵汾送纪角亥瘫锁盼旧谈别邱溪忙梨第3语言翻译问题第3语言翻译问题习题习题T1,2,3,5,6,11 补充习题：补充习题：1）解释名词可读性、可写性、易验证性和易翻译性）解释名词可读性、可写性、易验证性和易翻译性的含义。的含义。2）什么叫二义性，解决方法通常有哪些。）什么叫二义性，解决方法通常有哪些。3）简述词法分析、语法分析的原理和过程。）简述词法分析、语法分析的原理和过程。4）简述语义分析的主要功能。）简述语义分析的主要功能。5）简述优化的原理。）简述优化的原理。锗戚剃亿杰强赣枢惋椿蜘焉吕表舜坠紫搐圈哥孺畅输趣脯巨之像循赌桅宅第3语言翻译问题第3语言翻译问题
