第一章：编译系统概述第一章：编译系统概述一单选题 1编译程序前三个阶段完成的工作是（ C ） 。 A词法分析、语法分析和代码优化 B代码生成、代码优化和词法分析 C词法分析、语法分析、语义分析和中间代码生成 D词法分析、语法分析和代码优化 2编译程序绝大多数时间花在（ D ）上。A出错处理 B词法分析 C目标代码生成 D表格管理 3编译程序是对（ C ） 。A汇编程序的翻译 B高级语言程序的解释执行 C高级语言的翻译 D机器语言的执行 4在使用高级语言编程时，首先可通过编译程序发现源程序的全部（ A ）错误。A语法 B语义 C语用 D运行 二填空题1编译程序首先要识别出源程序中每个( 单词 )，然后再分析每个( 句子 )并翻译其意义。2通常把编译过程分为分析前端与后端两大阶段。词法、语法和语义分析是对源程序的( 分析 )，中间代码生成、代码优化与目标代码的生成则是对源程序的 (综合 )。 3对编译程序而言，输入数据是( 源程序 )，输出结果是( 目标程序 )。 4对下列错误信息，请指出可能是编译的哪个阶段（词法分析、语法分析、语义分析、 代码生成）报告的。 （1） else 没有匹配的 if （语法分析） （2） 数组下标越界 （语义分析） （3） 使用的函数没有定义 （语法分析） （4） 在数中出现非数字字符 （词法分析） 5如果编译程序生成的目标程序是机器代码程序，则源程序的执行分为两大阶段： （ 编译阶段 ） 和（ 运行阶段 ） 。如果编译程序生成的目标程序是汇编语言程序，则源 程序的执行方式分成三个阶段：（ 编译阶段 ） （ 汇编阶段 ）和（ 运行阶段 ） 。 6编译程序在其工作过程使用最多的数据结构是（ 表 ） ，它记录着源程序中各种信 息，以便查询或修改，在这些（ 表 ）中，尤以（ 符号表 ）最重要，它的生存 期最长，使用也最频繁。 三简述题：1编译程序的工作分为那几个阶段?答：词法分析、语法分析和语义分析是对源程序进行的分析(称为编译程序的前端)， 而中间代码生成、代码优化和代码生成三个阶段合称为对源程序进行综合(称为编译程序的 后端)，它们从源程序的中间表示建立起和源程序等价的目标程序。第二章第二章 词法分析词法分析一单选题： 1语言是（ A ） 。 A句子的集合 B产生式的集合 C符号串的集合 D句型的集合 2扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法 单位即（ B ） 。 A 字符 B单词 C句子 D句型 3词法分析的任务是（ A ） 。A识别单词 B分析句子的含义 C识别句子 D生成目标代码 4DFA（如图所示）接受的字集为（ D ） 。A以 0 开头的二进制数组成的集合 B以 0 结尾的二进制组成的集合C含奇数个 0 的二进制组成的集合 D含偶数个 0 的二进制组成的集合 5词法分析器的输出结果是（ C ） 。A单词的种别编码 B单词在符号表中的位置C单词的种别编码和自身的值 D单词自身值二填空题：1描述程序设计语言的词法的机制是（正则表达式） ，识别机制是（有穷状态自动机） 。2最小状态 DFA 的含义是（没有多余状态，没有两个状态等价） 。3确定有限自动机 DFA 是（ NFA ）的一个特例。4确定的有穷自动机是一个（ 五元组 ） ，通常表示为（ DFA = ( S，f , s0 Z ) ） 。三、简述题：1词法分析答：词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则从构成源 程序的字符串中识别出一个个具有独立意义的最小语法单位，并转换成统一的内部表示 (token)，送给语法分析程序。 四综合应用题： 1设有非确定的有自限动机 NFA M=(A，B，C，0，1，A，C)，其中： (A，0)=C (A，1)=A，B (B，1)=C (C，1)=C。请画出状态转换距 阵和状态转换图。 解： 状态转换距阵为：01010YXACA，BBCCC状态转换图为：2有一台自动售货机，接收 1 分和 2 分硬币，出售 3 分钱一块的硬糖。顾客每次向机器中 投放 3 分的硬币，便可得到一块糖（注意；只给一块并且不找钱） 。 （1）写出售货机售糖的正则表达式； （2）构造识别上述正则式的最简 DFA。解：（1）设 a = 1, b = 2,，则售货机售糖的正则表达式为：a (b | a (a | b) | b (a | b) 。（2）画出与正则表达式 a (b | a (a | b) | b (a | b)对应的 NFA，如图所示：X 1 2 3 Y a b a b a b b a 3设=0，1上的正规集 S 由倒数第二个字符为 1 的所有字符串组成，请给出该字集对 应的正规式，并构造一个识别该正规集的 DFA。 解：构造相应的正规式：(0|1)*1(0|1) NFA: 1 1 1 0 0 确定化：(3 分)I 0I1I0,1,21,21,2,3AB1 C11011012341,21,21,2,31,2,31,2,41,2,3,41,2,41,21,2,31,2,3,41,2,41,2,3,4010 1 0 00 11 14构造一个 DFA，使其接受 = 0， 1上 0 和 1 的个数都是偶数的字符串。 解： 5构造一个字母表0，1上的 DFA，其接受的串中所含 0 的数目能被 3 除尽。 解： 6写出在 = a , b上不是 a 开头的，以 aa 结尾的的字符串集合的正规表达式，并直 接构造与之等价的状态最少的 DFA。 解：7写一个文法使其语言为 L(G)=anbncm| m，n 1，n 为奇数，m 为偶数。解： 文法 G(S)：ccCcc | cc Cb aaAbb | a AACS 8构造一个 DFA，它接受=a，b上所有包含 ab 的字符串。解：解：构造相应的正规式：(a|b)*ab(a|b)*a a a b b b确定化：I0I1I0,1,21,2,31,21,2,31,2,31,2,4,5,61,21,2,31,20123401236451,2,4,5,61,2,3,5,61,2,5,61,2,3,5,61,2,3,5,61,2,4,5,61,2,5,61,2,3,5,61,2,5,6b bb aa a a aa b bb 最小化：0，1，2 3，4，5 0， 2，1， 3，4，5第三章第三章 程序设计语言的语法描述程序设计语言的语法描述一单选题：1如果文法 G 是无二义的，则它的任何句子 （ A ）。A最左推导和最右推导对应的语法树必定相同 B最左推导和最右推导对应的语法树可能不同 C最左推导和最右推导必定相同 D可能存在两个不同的最左推导，但它们对应的语法树相同 2正规式 M 1 和 M 2 等价是指（ C ）。 AM1 和 M2 的状态数相等 BM1 和 M2 的有向边条数相等CM1 和 M2 所识别的语言集相等 DM1 和 M2 状态数和有向边条数相等 3文法 G 所描述的语言是（ D ）的集合。A文法 G 的字符表 V 中所有符号组成的符号串。 B文法 G 的字符表 V 的闭包 V*中的所有符号串。C由文法的识别符号推出的所有符号串。D由文法的识别符号推出的所有4已知语言 L = anbbn | n 1 ，则下述文法， （ D ）可以产生语言 L。AZ aZb|aAb|b BA aAbA aAb | b A b012345baa01b3baCZ AbB DZ aAbA aA | a A aAb | bB bB | b 5正则表达式的运算符的优先顺序为（ C ） 。A| * B * | C* | D| *6. ab3 的另一种表示方法是（ ） 。A. abbb B. ababab C.abbaab D.aaabbb二填空题：1如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（ 二义性的 ） 。2最右推导亦称为（规范推导） ，由此得到的句型称为（规范）句型。3对于文法 G，仅含终结符号的句型称为 ( 句子 )。42 型文法又称为（上下文无关）文法；3 型文法又称为（正则 ）文法。5一个文法 G 是一个四元式( VT,VN,S,P )组成的。6文法 G 产生的 （ 句子 ）的全体是该文法描述的语言。7L+ 可以写成 （ LL* ） 。三简述题1一个文法是由哪几部分组成的，各部分的功能是什么？解：一个文法 G 是一个四元式（VT, VN ,S, P）其中：VT是一个终结符的非空有限集合，终结符通常用小写字母表示；VN是一个非终结符的非空有限集合，非终结符通常用大写字母表示； S 是一个特殊的非终结符（SVN） ，称为开始符号。 P 是一个产生式（规则）的有限集合，每个产生式的形式是 A ，其中AVN，(VTVN)*。第四章第四章 自上而下的语法分析自上而下的语法分析一单选题：1文法 GS: S xSx|y 所识别的语言是（ C ） 。A.xyx B.(xyx)* C.xnyxn (n 0) D.x*yx* 2 编译过程中，语法分析器的任务是（ ） 。A分析单词是怎样构成的 B分析单词串是如何构成语句和说明的 C分析语句和说明是如何构成程序的 D分析程序的结构3下列关于标识符和名字的叙述中，正确的为（ C ） 。A标识符有一定的含义 B名字是一个没有意义的字符序列C名字有确切的属性 D都不对 二填空题：1