编译原理习题与解析（第2版）一— 标识符 字母门 标识符+ 数字 图1.2标识符的构成规则 (2)标识符的构成规则用BNF范式描述为： <标识符>：一<字母标识符><字母>标识符><数字> <字母>：=alb…y <数字>：=011…819 (3)标识符的构成规则用扩充的BNF范式可表示为 <标识符>：=<字母>(<字母><数字>》 <字母>=albl--lylz <数字>：=01…89 (4)可以用如下的自然语言来描述标识符的构成规则： 标识符是由字母后跟若干个（包括0个）字母或数字的符号申组成的 2.试以PASCAL语言的赋值语句为例，说明什么是一个语法成分的语法、语义和语用。 解答：PASCAL语言赋值语句语法的非形式化描述为：赋值语句由一个变量，后随 个符号“：”，再在后面跟一个表达式所构成：或形式化描述为： <赋值语句>：=<变量>：=<表达式> 赋值语句的语义为：先对该语句的右部表达式求值，然后把所得结果与语句左部的变 量相结合，并取代该变量原有的值。 赋值语句的语用为：赋值语句可用来计算和保行表达式的值。 Page
第2章 编译程序概述 2.1基本内容 2.1.1程序的翻译 1,程序设计语言与程序的翻译 程序设计语言有多种：不需翻译就可直接执行的机器语言，机器指令助记符形式的汽 编语言，以及接近自然语言的请多高级程序设计诗言（如FORTRAN,PASCAL,C等）。 除机器语言程序外，用其他语言书写的程序都必须经过翻译才能被计算机识别，这 过程由翻译程序来完成。所谓翻译程序是指这样一种程序，它能将用甲语言编写的程序翻 译成与之等价的乙语言的程序。甲语言称为该翻译程序的源语言，乙语言称为该翻译程序 的目标语言。用源语言书写的程序称为源程序，与源程序等价的目标语言程序称为目标程 序。 程序的翻译通常有两种方式：一种是“编译”方式，另一种是“解释”方式。 2.编译方式与编译程序 编译方式是一种分阶段进行的方式。一般说来，首先进行“翻译”，把用高级语言或 汇编语言编写的程序翻译成与之等价的机器语言程序，然后对翻译出来的程序进行运行计 算。前一阶段的翻译工作由翻译程序完成，后一阶段的运行计算需要由运行程序来配合完 成。 如果翻译程序是将用高级语言书写的源程序翻译成与之等价的某特定计算机系统的汀 编语言程序或机器语言程序，则这种翻译程序称为编译程序。 如果翻译程序是将汇编语言程序翻译成某特定计算机系统的机器语言程序，则这种翻 译程序特称为汇编程序。 用机器语言构成的目标程序又称为目标代码程序，或简称为代码程序，有时又称为目 标代码或结果代码。 所谓运行程序是指运行目标代码程序时必须配置的各种子程序全体，通常以库子程序 的形式存在，如一些连接装配程序及一些连接库等。 3.解释方式与解释程序 在解释方式下，源程序的执行贝有一个阶段 解释执行阶段。具体地说，完成解释 工作的解释程序将按源程序中语句的动态顺序逐句地进行分析解释，并立即予以执行。 在解释方式下，并不生成目标代码，而是直接执行源程序本身。这是编译方式与解释 方式的根本区别。 随着解释方式的不断发展，解释程序逐渐发展成3种类型：
编译原理习题与解析（第2版）一二了 (1)直接解释源程序。 (2)先把源程序转换成高级屮间代码（与源程序相当接近），然后解释执行该中间代 (3)先把源程序转换成低级中间代码（和机器语言十分接近），然后再解释执行该中 间代码.通常，高级语言的一条语句对应于低级中间代码的若干条语句。在PASCAL语言 的P代码实现方案中，PASCAL程序首先被翻译成P代码，然后由P代码解释程序解释执行这 样的P代码。 上述3种解释程序都不生成目标代码。 在解释方式下执行源程序，易于查错，并可以在程序执行中修改程序。但和编译方式 相比，执行效率太低。将编译方式和解释方式二者相结合，可得到快速、灵活的集成开发 环境。 2.1.2编译程序的组成 1.编译程序的组成 编译程序一般需要完成词法分析、语法分析、语义分析（和中间代码生成）、中间代 码优化、目标代码生成5个方面的任务，完成这5个方面任务的程序分别为：词法分析程序 语法分析程序、语义分析（和中间代码生成）程序、中间代码优化程序、目标代码生成程 序。 (1)词法分析程序（又称扫描器) 词法分析程序的任务：依据语言的词法规则，分析由字符组成的源程序，把它识别为 个一个具有独立意义的最小语法单位，即“单词”，并识别出与其相关的属性（如是标 识符，是界限符，还是数，等等)，再转换成长度统一的标准形式（这种统一的标准形式 既刻画了单词本身；也刻画了它所具有的属性，又称为属性字)，以供其他部分使用。 词法分析程序往往还完成那些在语法分析之前需做的工作：如删除注解之类非必要信 息，处理编译程序的控制指示，把标识符登录入符号表及加工宏功能等各项预处理。 (2)语法分析程序 语法分析程序的任务：依据语言的语法规如，逐一分析词法分析时得到的单词（属性 字)，以确定它们是怎样构成“说明”和“语句”的，以及这些“说明”和“语句”又是 怎样组成程序的。分析时如发现有不符合语法规则的地方，语法分析程序便把这些出错的 地方及出错性质打印输出给程序员；如无语法错误，则以另一种内部表示（如三元式等中 间表示)给出正确的语法结构，供下-阶段分析使用。 (3)语义分析（和中间代码生成）程序 语义分析（和中问代码生成）程序的任务：依据语言的语义规则对语法分析得到的语 法结构进行静态语义检查（如确定类型、类型和运算合法性检查、识别语法成分的含义与 相应的语义处理、及进行其他一些静态语义检查)，并用另一种内部形式表示出米，或者 直接用目标语言表示出来。 Page
卜第2章编译程序概述· (4)代码生成程序 代码生成程序的任务；如果语义分析时把源程序表示成内部形式而不是表示成目标指 令，则由本部分完成从内部形式到目标指令的生成工作。如果语义分析时己直接生成目标 指令，则无需再做代码生成工作。 (5)代码优化程序 代码优化程序的任务：依据程序的等价变换规则，尽量压缩目标程序运行所需的时间 和所占的存储空间，以提高目标程序的质壁。 2。编译程序的逻辑结构 (1)遍(pas) 所谓一趟或一遍，是指一个编译程序在编译时刻把源程序或源程序的等价物（中间程 序)从头到尾扫描一遍，并转换成另一紧邻等价物的全过程。 (2)单遍扫描与多遍扫描 根据编译程序在完成翻译任务过程中需要对源程序或其中间等价物扫描的遍数，可以 把编译程序分为单遍扫描的编译程序（只需扫描一遍）和多遍打描的编译程序（需扫描多 遍) 在单遍扫描的编译程序中，词法分析程序往往作为语法分析的一个子程序，当语法分 析需要一个新单词时，便调用词法分析程序。当语法分析程序分析得到一个完整的语法成 分时，便调用语义分析程序进行语义分析。 (3)典型的编译程序结构 典型的编译程序逻辑结构如图2.1所示。 表格 处 理 中国 原程序 了分 目标程序 出错处理 图2.1典型的编译程序结构
编译原理习题与解析（第2版） — 2.2基本题 2.2.1填空题 1.若源程序是用高级语言编写的，日标程序是 语言的程序，则相应的翻译 程序称为编译程序。 答案：机器语言或汇编 2.(华中科技大学1985)翻译程序是这样一种程序，它能够将(1)转换成与其 等价的(2) 答案：(1)用甲语言书写的程序 (2)用乙语言书写的程序 3.对编译程序而言，输入数据是()·输出结果是(2)一。 答案：(1)源程序 (2)目标程序 4.如果编译程序生成的月标程序是某特定计算机系统的机器代码程序，则源程序的执 行分为两大阶段：(1)和(2)·如果编译程序生成的目标程序是汇编语言程序， 则源程序的执行分成3个阶段：(3)、 (4)和(5)。 答案：(1)编译阶段(2)运行阶段 (3)编泽阶段(4)汇编阶段 (5)运行阶段 分析： 如果编译程序生成的日标程序是某特定计算机系统的机器代码程序，则源程序的执行 分为两大阶段：先由编译程序将源程序翻译成机器语言的目标代码程序，这是编译阶段： 然后在运行子程序的辅助下运行所生成的目标代码程序，得到运行结果，这是运行阶段。 如果编译程序生成的目标程序是汇编语言程序，则源程序的执行分为3人阶段：先由编 译程序将源程序翻译成汇编语言的目标代码程序，这是编译阶段：然后由汇编程序将汇编 语言目标代码程序翻译成机器语言的目标代码程序，这是乳编阶段：最后在运行子程序的 辅助下运行所生成的机器语言目标代码程序，得到运行结果，这是运行阶段。 2.2.2单项选择题 1.在使用高级语言编程时，首先可通过编译程序发现源程序的全部()错误和 部分(2)错误。 选项有： a.语法b.语义c.语用d.运行 答案：(1)a(2)b 分析：源程序中所有的语法错误都可以在编译阶段被发现，但有些语义错误是编译程 序不能发现的。如sqt(xy)在运行时，若输入数据使得xy将导致语义错误，类似于这样 的语义错误只有在运行阶段才能被发现，故也称为动态语义错误。 Page