简答题
• 1．何谓扫描器？扫描器的功能是什么？ • 2．试简述有穷状态自动机与正则表达式的 等价性概念。 • 3．给出有限状态自动机的严格定义。
• • • •
• • • • • • • • • • •
解答 1．扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析，识别出一 个个的单词符号，其输出结果是单词符号，供语法分析器使用。 一般把词法分析器安排成一个子程序，每当语法分析器需要一个单词符号时就调用这 个子程序。每一次调用，词法分析器就从输入串中识别出一个单词符号，把它交给语 法分析器。 词法分析器工作的第一步是输入源程序文本。输入串中一般都包含一些没有意义的字 符，如：空白符、跳格符、回车符和换行符等编辑性字符除了出现在文字常数中之外， 在别处的任何出现都没有意义，而注解部分几乎允许出现在程序中的任何地方。它们 不是程序的必要组成部分，预处理时可以将其剔掉。词法分析器一般会构造一个预处 理子程序来处理上述任务。 2．∑上的非确定有限自动机M所能识别字的全体L（M）是∑上的一个正规集；同时， 对于∑上的每个正规集V，存在一个∑上的确定有限自动机M，使得V=L（M）。 3．有限状态自动机分为确定有限状态自动机和非确定有限状态自动机两类，确定有限 自动机是非确定有限自动机的特例，但它们具有相同的表示能力。给出有限状态自动 机的定义实际上只需要给出非确定有限状态自动机的定义就可以了： 一个有限状态自动机（NFA）M是一个五元式 M=(S, S, d, S0, F) 其中 1. S是一个有限集，它的每个元素称为一个状态； 2. S是一个有穷字母表，它的每个元素称为一个输入字符； 3. d是一个从S×S*到S的子集的映照，即 d：S×S*→2S 4. S0ÍS，是一个非空初态集； 5. FÍS，是一个终态集（可空）。
选择题
• 1．______不是NFA的成分。 • A.有穷字母表 B.初始状态集合 • C.终止状态集合 D.有限状态集合 • 2．______不是编译程序的组成部分。 • A.词法分析程序 B.代码生成程序 • C.设备管理程序 D.语法分析程序
• 1．分析NFA的5个组成部分：S是一个有限状态集合，S 是一个有穷字母表，d是一个从S×S*到S的子集的映照， 即d：S×S*→2S，S0ÍS是一个非空初态集，FÍS是一个终 态集（可空）。从字面上看，似乎A、B、C、D四个选项 都是NFA的组成部分，但仔细分析，就会发现B：初始状 态集合和NFA中定义的S0有区别，S0是非空初态集，而 初始状态集合却只是一个集合，可以是一个可空的集合。 另外三个选项都和NFA中的定义一致，因此本题的选择为 B。 • 2．查看编译程序的结构图，编译程序由以下7个部分组成： 词法分析器、语义分析器、语义分析及中间代码生成器、 优化段、目标代码生成器以及表格管理模块和出错处理模 块。由此可以看出A、B、D所描述的都是编译程序的一个 部分，但C设备管理程序，它所描述的是操作系统的一部 分，在操作系统中负责各种外设的管理，和编译程序没有 关系，因此本题的答案是C。
第一章例题
简答题 • 1．什么叫自展？什么叫交叉编译？ • 2．什么是标识符，什么是名字，他们的区 别是什么？ • 3.画出编译程序的总体结构图，简述个部分 的主要功能。
• 解答 • 1．采用“自编译方式”产生编译程序的方法叫自展。即 先对语言的核心部分构造一个小小的编译程序（可用低级 语言实现），再以它为工具构造一个能够编译更多语言成 分的较大编译程序。如此扩展下去，最后形成整个编译程 序。一般称运行编译程序的计算机为宿主机，运行编译程 序所产生目标代码的计算机称目标机。如果编译程序编译 时产生不同于其宿主机的机器代码，则称它为交叉编译， 即在A机上的编译程序对高级语言编译后所产生的目标代 码是B机的机器代码，而且A机和B机使用不同的机器代码。 • 2．标识符是由字母或数字以及某些特殊符号（因为不同 的高级语言而不同）组成的，但是以字母开头的一个字符 串。当给某标识符以确切的涵义时，这个标识符就叫做名 字。程序语言中各种名字都是用标识符表示的。名字和标 识符具有相同的形式，名字使用标识符来描述，但标识符 是没有意义的字符序列，而名字却有确切的意义和属性 （即类型和作用域）。
词法分析器，又称扫描器，它接受输入的源程序，对源程序进行词法分 析，识别出一个个的单词符号，其输出结果是单词符号。 • 语法分析器，对单词符号串进行语法分析（根据语法规则进行推导或 归约），识别出程序中的各类语法单位，最终判断输入串是否构成语 法上正确的“程序”。 • 语义分析及中间代码产生器，按照语义规则对语法分析器归约出（或 推导出）的语法单位进行语义分析并把它们翻译成一定形式的中间代 码。编译程序可以根据不同的需要选择不同的中间代码形式，有的编 译程序甚至没有中间代码形式，而直接生成目标代码。 • 优化器对中间代码进行优化处理。一般最初生成的中间代码执行效率 都比较低，因此要做中间代码的优化，其过程实际上是对中间代码进 行等价替换，使程序在执行时能更快，并占用更小的空间。 • 目标代码生成器把中间代码翻译成目标程序。中间代码一般是一种机 器无关的表示形式，只有把它再翻译成与机器硬件直接相关的机器能 识别的语言，即目标程序，才能在机器上运行。 • 表格管理模块保持一系列的表格，登记源程序的各类信息和编译各阶 段的进展状况。编译程序各个阶段所产生的中间结果都记录在表格中， 所需要的信息也大多从表格中获取，整个编译过程都在不断地和表格 打交道。 • 出错处理程序对出现在源程序中的错误进行处理。如果源程序有错误， 编译程序应设法发现错误，把有关错误信息报告给用户。编译程序的 各个阶段都有可能发现错误，出错处理程序要对发现的错误进行处理、 记录，并反映给用户。
第4章
• 例题4.1按照乔姆斯基(Chomsky)对文法的分类， 指出下述文法的所属类型，并给出所描述的语言。 • (a) S → Be (b) A → ε| aB • B → eC | Af B → Ab | a • A → Ae | e • C → Cf (c) S → abcA • D → fDA S → Aabc • A →ε • Aa → Sa • cA → cS
第3章
• 1．一张转换图只包含有限个状态，其中有一个被认为是初态，最多 只有一个终态。（ ） 2．对任何正则表达式e，都存在一个NFA M，满足L(M)=L(e) （ ） 3．对任何正则表达式e，都存在一个DFA M，满足L(M)=L(e) （ ）
• 分析 • 1．转换图是一张有限方向图。在状态转换图中，结点代表 状态，用圆圈表示。状态之间用箭弧连结。箭弧上的标记 （字符或字符串）代表在射出结点（即箭弧始结点）状态 下可能出现的输入字符或字符串。一张转换图只包含有限 个状态（即有限个结点），其中有一个被认为是初态，而 且实际上至少要有一个终态（用双圈表示）。由上述转换 图的定义知道，转换图只能有一个初态，但至少要有一个 终态，这说明转换图可以有多个终态，因此本题错。 • 2．正规式和有限自动机的等价性：：⑴ 对任何FA M，都 2 FA M 存在一个正规式r，使得L(r)=L(M)；⑵ 对任何正规式r，都 存在一个FA M，使得L(M)=L(r)。 • 因此对任何正则表达式e，都存在一个NFA M，满足 L(M)=L(e)。 • 所以本题正确。 • 3．根据上题以及确定有限自动机和非确定有限自动机之间 的等价性，可以知道本题正确。
第2章
• 是非题 • 1．因名字都是用标识符表示的，故名字与 标识符没有区别。（ ） • 2．正规文法产生的语言都可以用上下文无 关文法来描述。（ ） • 3．上下文无关文法比正规文法具有更强的 描述能力。（ ） •
ቤተ መጻሕፍቲ ባይዱ
• •
•
•
分析 1．标识符是高级语言中定义的字符串，一般是以英文字母开头（包括大小写 字母）的，由数字、字母和一些特殊字符（如下划线等）组成的一定长度 （不同的高级语言对标识符的长度的规定不同）的字符串，它只是一个标志， 没有其它含义。名字是用标识符表示的，但名字不仅仅是一个字符串，它还 具有属性和值，就象一个人的名字不仅仅是一个符号，对于认识这个人的人 来说，它还代表着这个人，因此本题错。 2．乔姆斯基把文法分成4种类型，从4种文法的形式化描述来看，它们的差别 主要在对规则形式的约束上。0型文法的规则形式是：每个产生式a→b都满足， aÎ（VN∪VT）*且至少含有一个非终结符，bÎ（VN∪VT）*，0型文法也叫短 语文法。1型文法的规则形式是：每个产生式a→b均满足|a|£|b|，仅仅S→e例 外，且S不得出现在任何产生式的右部，1型文法也称上下文有关文法，从两 种文法的规则形式来看，1型文法对规则形式的约束比0型文法强，1型文法能 描述的语言0型文法也能描述，而0型文法能描述的语言1型文法不一定能够描 述，1型文法是0型文法的特例。2型文法的规则形式是A→b，其中AÎVN，bÎ （VN∪VT）*，2型文法也称上下文无关文法，分析2型文法的规则形式不难 发现，2型文法是1型文法的特例，也是0型文法的特例。3型文法的规则形式 是A→aB或A→a，其中aÎ ，A、BÎVN，3型文法也称正规文法，可以看出3型 文法是前面3种文法的特例。从上面的分析可以，正规文法是上下文无关文法 的特例，可以用正规文法描述的语言，其正规文法描述的形式也是上下文无 关文法的描述形式，即可以用上下文无关文法描述，因此本题对。 3．上下文无关文法是2型文法，正则文法是3型文法，从上题的分析可以看出， 3型文法是2型文法的特例，3型文法可以描述的语言都可以用2型文法来描述， 而2型文法可以描述的语言则不一定能用3型文法来描述。即2型文法比3型文 法的描述能力强，因此本题对
填空题
• 1．词法分析器输出的单词符号常常表示成如下二元式： （ ）。 • 2．一张转换图只包含有限个状态，其中有一个被认为是 （ ）态，而且实际上至少要有一个（ ）态。 • 3．词法分析器的任务是（ 3 ）。 • 解答 • 1．词法分析器所输出的单词符号常常表示成如下的二元 式：（单词种别，单词符号的属性值） • 2．一张转换图只包含有限个状态（即有限个结点），其 中有一个被认为是（初）态，而且实际上至少要有一个 （终）态（用双圈表示） • 3．词法分析器的功能是（输入源程序，输出单词符号）。