第三编译原理模拟试卷

1、编译原理模拟试卷（三）一、 单项选择题%151、编译程序是对 。 a汇编程序的翻译b高级语言程序的解释执行 c机器语言的执行d高级语言的翻译2、语法分析应遵循 。 a语义规则b语法规则 c构词规则d等价变换规则 3、设文法为：SSA|AAa|b则对句子aba，下面 是规范推导。a. SSASAAAAAaAAabAabab. SSASAAAAAAAaAbaabac. SSASAASAaSbaAbaabad. SSASaSAaSbaAbaaba4、文法G：Sb|(T)TT,S|S则FIRSTVT(T) 。a. b,(b. b,)c.b,(,，d.b,),，5、产生正规语言的文法为 。6、一个 A

2、指明了在分析过程中的某时刻所能看到产生式多大一部分。 a.活前缀b.前缀c.项目d.项目集7、中间代码生成所依据的是 C。a.语法规则b.词法规则c.语义规则d.等价变换规则8、四元式之间的联系是通过 B 实现的。 a.指示器b.临时变量c.符号表d.程序变量9、后缀式ab+cd+/可用表达式 B 来表示。a.a+b/c+db.(a+b)/(c+d)c.a+b/(c+d)d.a+b+c/d10、表达式（AB）（CD）的逆波兰表示为 ERB 。 a. ABCDb. ABCDc. ABCDd. ABCD11、在编译时有传名功能的高级程序语言是 。 a. Fortranb. Basicc. Pasc

3、ald. ALGOL12、栈式动态分配与管理在过程返回时应做的工作有 。 a. 保护SPb. 恢复SPc.保护TOPd. 恢复TOP13、优化可生成DD的目标代码。a运行时间较短b占用存储空间较小c运行时间短但占用内存空间大d运行时间短且占用存储空间小14、下列A优化方法不是针对循优化进行的。a强度削弱b删除归纳变量c删除多余运算d代码外提15、基本块内的优化为B。a代码外提，删除归纳变量b删除多余运算，删除无用赋值c强度削弱，代码外提d循环展开，循环合并二、多项选择题%161、下面哪些说法是错误的 。a. 有向图是一个状态转换图b. 状态转换图是一个有向图c.有向图是一个DFAd.DFA可以

4、用状态转换图表示2、对无二义性文法来说，一棵语法树往往代表了 。a. 多种推导过程b. 多种最左推导过程c.一种最左推导过程d.仅一种推导过程e.一种最左推导过程3、如果文法G存在一个句子，满足下列条件 之一时，则称该文法是二义文法。a. 该句子的最左推导与最右推导相同b. 该句子有两个不同的最左推导c. 该句子有两棵不同的最右推导d. 该句子有两棵不同的语法树 e.该句子的语法树只有一个4、有一文法G：SAB AaAb| BcBd|它不产生下面 集合。a. anbmcndm|n,m0b. anbncmdm|n,m0c. anbmcmdn|n,m0d. anbncmdm|n,m0e. anbn

5、cndn|n05、自下而上的语法分析中，应从 开始分析。a. 句型b. 句子c. 以单词为单位的程序d. 文法的开始符e. 句柄6、对正规文法描述的语言，以下 有能力描述它。a.0型文法b.1型文法 c.上下文无关文法 d.右线性文法 e.左线性文法7、在词法分析中，能识别出 。a. 基本字b. 四元式c. 运算符d. 逆波兰式e. 常数8、令=a,b，则上所有以b开头，后跟若干个ab的字的全体对应的正规式为 。a. b(ab)*b. b(ab)+c.(ba)*bd. (ba)+be. b(a|b)9、一个LR分析器包括 。 a.一个总控程序b.一个项目集c.一个活前缀d.一张分析表e.一个分

6、析栈10、LR分析器核心部分是一张分析表，该表包括 等子表。 a.LL(1)分析b.优先关系c.GOTO d.LRe.ACTION11、每一项ACTIONS，a所规定的动作包括 。a.移进b.比较c.接受d.归约e.报错12、对LR分析表的构造，有可能存在 动作冲突。a.移进b.归约c.移进/归约d.移进/移进e.归约/归约13、中间代码主要有。a四元式b二元式c三元式d后缀式e间接三元式14、下面中间代码形式中，能正确表示算术表达式a+b+c的有。+a +b c+ ca baab+c+babc+c d ea+b+c15、在下面的语法制导翻译中，采用拉链-回填技术。a赋值语句bgoto语句 c

7、条件语句d循环语句16、下列中间代码形式有益于优化处理。a三元式b四元式c间接三元式d逆波兰表示法e树形表示法三、填空题 %24 1、FORTRAN语言采用了 静态 存储空间分配方案，其程序所需的存储空间在 编译 时确定。2、一个函数的活动记录体积在 时确定，数组内情向量表的体积在 时确定。3、目标程序运行的动态分配策略中，含有 和 分配策略4、在Pascal中，由于允许用户动态地申请与释放内存空间，所以必须采用 存储分配技术。5、如果两个临时变量名 不相交，则它们可分配在同一单元中。6、堆式动态分配策略允许用户动态的 和 存储空间。7、符号表中名字栏内容有两种填写方式，它们是 填写和 填写。

8、8、词法分析阶段的错误主要是 ，可通过 的办法纠正错误。9、符号表中名字的有关信息在 和 过程中陆续填入。10、在目标代码生成阶段，符号表是 的依据。11、中间代码有 等形式，生成中间代码主要是为了使 。12、语法制导翻译既可以用来产生 代码，也可以用来产生 指令，甚至可用来对输入串进行 。 13、当源程序中的标号出现“先引用后定义”时，中间代码的转移地址须持 时才能确定，因而要进行 。四、判断题%81、一个有限状态自动机中，有且仅有一个唯一终态。（ ）2、设r和s分别是正规式，则有L（r|s）=L(r)|L(s)。（ ）3、自动机M和M的状态数不同，则二者必不等价。（ ）4、确定的自动机以及

9、不确定的自动机都能正确地识别正规集。（ ）5、对任意一个右线性文法G，都存在一个NFA M，满足L(G)=L(M)。（ ）6、对任意一个右线性文法G，都存在一个DFA M，满足L(G)=L(M)。（ ）7、对任何正规表达式e，都存在一个NFA M，满足L(G)=L(e)。（ ）8、对任何正规表达式e，都存在一个DFA M，满足L(G)=L(e)。（ ）五、综合题%371、 下面文法GS是否为LL（1）文法？说明理由。%10S A B | P Q x A x y B b cP d P | Q a Q | 2、设有文法GS为：Sa|b|(A)ASdA|S （1）给出句型（SdSdS）的短语、简单短

10、语、句柄、素短语和最左素短语。（2）用自下而上分析法给出输入串（adb）#的分析过程。%103、请写出在=（a,b）上，不是a开头的，但以aa结尾的字符串集合的正规表达式，并构造与之等价状态最少的DFA。%104、 写出下面算术表达式E值的语义描述 %7EE1+E2E0 E1解答3根据题意，不以a开头就意味着以b开头，且以aa结尾的正规式为：b(a|b)* aa根将图2.30所示的NFA确定化，如图2.31所示。a b a ab图3-6-8 NFA将图2.30所示的NFA确定化，如图。X12Y从图2.31可知已为最简状态，由于开始状态0只能输入字符b而不能与状态1合并，而状态2和状态3面对输入符号的下一状态相同，但两者一为非