编译原理第2阶段测试题
- 格式:doc
- 大小:127.50 KB
- 文档页数:2
《编译原理》期末试题(二)一、是非题:1.一个上下文无关文法的开始符,可以是终结符或非终结符。
( )2.一个句型的直接短语是唯一的。
()3.已经证明文法的二义性是可判定的。
()4.每个基本块可用一个DAG表示。
()5.每个过程的活动记录的体积在编译时可静态确定。
()6.2型文法一定是3型文法。
()7.一个句型一定句子。
( )8.算符优先分析法每次都是对句柄进行归约。
X ( )9.采用三元式实现三地址代码时,不利于对中间代码进行优化。
()10.编译过程中,语法分析器的任务是分析单词是怎样构成的。
( )11.一个优先表一定存在相应的优先函数。
X ( )12.目标代码生成时,应考虑如何充分利用计算机的寄存器的问题。
( )13.递归下降分析法是一种自下而上分析法。
( )14.并不是每个文法都能改写成LL(1)文法。
( )15.每个基本块只有一个入口和一个出口。
( )16.一个LL(1)文法一定是无二义的。
( )17.逆波兰法表示的表达试亦称前缀式。
( )18.目标代码生成时,应考虑如何充分利用计算机的寄存器的问题。
( )19.正规文法产生的语言都可以用上下文无关文法来描述。
( )20.一个优先表一定存在相应的优先函数。
( )21.3型文法一定是2型文法。
( )22.如果一个文法存在某个句子对应两棵不同的语法树,则文法是二义性的。
( )答案:1.× 2.× 3.× 4.√ 5.√ 6.×7.×8.× 9.√10.×11.×12.√ 13.× 14.√ 15.√ 16.√ 17.× 18.√19.√ 20.×21.√22.√二、填空题:2.编译过程可分为(词法分析),(语法分析),(语义分析与中间代码生成),(优化)和(目标代码生成)五个阶段。
3.如果一个文法存在某个句子对应两棵不同的语法树,则称这个文法是(二义性的)。
《编译原理》考试试题及答案(汇总)一、是非题(请在括号内,正确的划√,错误的划×)(每个2分,共20分)1.编译程序是对高级语言程序的解释执行。
(× )2.一个有限状态自动机中,有且仅有一个唯一的终态。
(×)3.一个算符优先文法可能不存在算符优先函数与之对应。
(√ )4.语法分析时必须先消除文法中的左递归。
(×)5.分析法在自左至右扫描输入串时就能发现错误,但不能准确地指出出错地点。
(√)6.逆波兰表示法表示表达式时无须使用括号。
(√ )7.静态数组的存储空间可以在编译时确定。
(×)8.进行代码优化时应着重考虑循环的代码优化,这对提高目标代码的效率将起更大作用。
(×)9.两个正规集相等的必要条件是他们对应的正规式等价。
(× )10.一个语义子程序描述了一个文法所对应的翻译工作。
(×)二、选择题(请在前括号内选择最确切的一项作为答案划一个勾,多划按错论)(每个4分,共40分)1.词法分析器的输出结果是。
A.( ) 单词的种别编码B.( ) 单词在符号表中的位置C.( ) 单词的种别编码和自身值D.( ) 单词自身值2.正规式 M 1 和 M 2 等价是指。
A.( ) M1和M2的状态数相等 B.( ) M1和M2的有向边条数相等C.( ) M1和M2所识别的语言集相等D.( ) M1和M2状态数和有向边条数相等3.文法G:S→所识别的语言是。
A.( ) B.( ) ()* C.( ) (n≥0) D.( ) x**4.如果文法G是无二义的,则它的任何句子α。
A.( )最左推导和最右推导对应的语法树必定相同B.( ) 最左推导和最右推导对应的语法树可能不同C.( ) 最左推导和最右推导必定相同D.( )可能存在两个不同的最左推导,但它们对应的语法树相同5.构造编译程序应掌握。
A.( )源程序B.( ) 目标语言C.( ) 编译方法 D.( ) 以上三项都是6.四元式之间的联系是通过实现的。
编译原理2014—2015学年第二学期第二单元测试试卷(闭卷考试)时间:45分钟满分:100分姓名班级出题人刘兵班级 02一、选择题(5*2分)(每题1分,共10分)1.文法分为四种类型,即0型、1型、2型、3型。
其中3型文法是_____。
A. 短语文法B.正则文法C.上下文有关文法D.上下文无关文法2.文法G[N]=({b},{N,B},N,{N→b│bB,B→bN}),该文法所描述的语言是_____A. L(G[N])={bi│i≥0}B. L(G[N])={b2i│i≥0}C. L(G[N])={b2i+1│i≥0}D. L(G[N])={b2i+1│i≥1}3.一个上下文无关文法G包括四个组成部分,它们是:一组非终结符号,一组终结符号,一个开始符号,以及一组_______A. 句子B. 句型C. 单词D. 产生式4.一个句型中的最左______称为该句型的句柄。
可选项有:A. 短语B. 简单短语C. 素短语D. 终结符号5.文法G[E]:E→T∣E+T T→F∣T﹡F F→a∣(E)该文法句型E+F﹡(E+T)的简单短语是下列符号串中的______ 。
①(E+T)②E+T ③F ④F﹡(E+T)可选项有:A) ①和③B) ②和③C) ③和④D) ③二、简答题(2*10分)(每题10分,共20分)1.解释语言、语法和语义的概念。
2. 文法 S→S(S)S|ε(1) 生成的语言是什么?(2) 该文法是二义的吗?说明理由。
三、分析题(4题共70分)1.文法 G[S]为:S→Ac|aBA→abB→bc该文法是否为二义的?为什么?2.考虑下面上下文无关文法:S→SS*|SS+|a(1)表明通过此文法如何生成串 aa+a*(2)G[S]的语言是什么?3.令文法 G[E]为:E→T|E+T|E-TT→F|T*F|T/FF→(E)|i证明 E+T*F 是它的一个句型,指出这个句型的所有短语、直接短语和句柄。
编译原理答案(前三章)第 1 章引论第 1 题解释下列术语:答案:(1)编译程序:如果源语言为高级语言,目标语言为某台计算机上的汇编语言或机器语言,则此翻译程序称为编译程序。
(2)源程序:源语言编写的程序称为源程序。
(3)目标程序:目标语言书写的程序称为目标程序。
(4)编译程序的前端:它由这样一些阶段组成:这些阶段的工作主要依赖于源语言而与目标机无关。
通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶段,某些优化工作也可在前端做,也包括与前端每个阶段相关的出错处理工作和符号表管理等工作。
(5)后端:指那些依赖于目标机而一般不依赖源语言,只与中间代码有关的那些阶段,即目标代码生成,以及相关出错处理和符号表操作。
(6)遍:是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。
第 2 题一个典型的编译程序通常由哪些部分组成?各部分的主要功能是什么?并画出编译程序的总体结构图。
答案:一个典型的编译程序通常包含 8 个组成部分,它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。
其各部分的主要功能简述如下。
词法分析程序:输人源程序,拼单词、检查单词和分析单词,输出单词的机内表达形式。
语法分析程序:检查源程序中存在的形式语法错误,输出错误处理信息。
语义分析程序:进行语义检查和分析语义信息,并把分析的结果保存到各类语义信息表中。
中间代码生成程序:按照语义规则,将语法分析程序分析出的语法单位转换成一定形式的中间语言代码,如三元式或四元式。
中间代码优化程序:为了产生高质量的目标代码,对中间代码进行等价变换处理。
目标代码生成程序:将优化后的中间代码程序转换成目标代码程序。
表格管理程序:负责建立、填写和查找等一系列表格工作。
表格的作用是记录源程序的各类信息和编译各阶段的进展情况,编译的每个阶段所需信息多数都从表格中读取,产生的中间结果都记录在相应的表格中。
编译原理 第一、二章单元测验(答案)姓名 学号 班级一.填空(40分)1. 编译系统一般可以分为① 词法分析 ② 语法分析 ③语义分析及中间代码生成 ④ 优化处理 ⑤ 目标代码生成 等5大部分组成,其中① 词法分析 ② 语法分析 ⑤ 目标代码生成 是每个编译程序必不可少的,而③语义分析及中间代码生成 ④ 优化处理 则是可有可无的。
这5个部分在工作过程中都会涉及到⑥ 表格处理 ⑦ 出错处理2. 中间代码生成所依据的是语言的 语义 规则3. 在使用高级语言编程时,首先可以通过编译程序发现源程序的全部 语法 错误和 语义 错误。
4. 由于受到具体机器主存容量限制,编译程序几个阶段的工作往往被组合成 遍 。
5. 编译程序绝大多数时间花在 管理表格/扫描 上。
6. 语法分析的依据是 语法/语义 规则。
7. 高级语言源程序执行有两种方式:即 编译 和 解释 。
8. 编译程序各阶段的工作往往是 穿插 进行的。
9. 文法G 产生的 句子 的全体构成该文法所描述的语言。
10. 乔姆斯基定义的4种形式的文法中,0型又称 短语结构文法 可由 图灵机 识别, 1型又称 前后文(或上下文)有关文法 可由 线性限界自动机 识别,2型又称 前后文(或上下文)无关文法 可由 非确定下推自动机 识别,3型包括 左线性文法 和 右线性文法 ,可由 有限自动机 识别。
11. 最左推导是指 对于一个推导序列中的每个直接推导,被替换的总是当前符号串中的最左非终结符号。
12. 产生式是用于定义 语法范畴 的一种书写规则。
13. 高级语言经过编译生成的语言一般是 机器语言 和 汇编语言 。
14. 句柄是指当前句型的 最左直接短语 。
15. 简单地说,文法中无用符号和无用产生式的删除必须满足:1.是否被用到过 2. 可否推出终结符号 。
16. 规范推导是指 最右推导 ,规范归约是指 最左归约 ,二者互为逆过程。
二.写一个语言,使其语言是奇数集,且每个奇数不以0开头。
第一章练习题(绪论)一、选择题1.编译程序是一种常用的软件。
A) 应用B) 系统C) 实时系统D) 分布式系统2.编译程序生成的目标代码程序是可执行程序。
A) 一定B) 不一定3.编译程序的大多数时间是花在上。
A) 词法分析B) 语法分析C) 出错处理D) 表格管理4.将编译程序分成若干“遍”将。
A)提高编译程序的执行效率;B)使编译程序的结构更加清晰,提高目标程序质量;C)充分利用内存空间,提高机器的执行效率。
5.编译程序各个阶段都涉及到的工作有。
A) 词法分析B) 语法分析C) 语义分析D) 表格管理6.词法分析的主要功能是。
A) 识别字符串B) 识别语句C) 识别单词D) 识别标识符7.若某程序设计语言允许标识符先使用后说明,则其编译程序就必须。
A) 多遍扫描B) 一遍扫描8.编译方式与解释方式的根本区别在于。
A) 执行速度的快慢B) 是否生成目标代码C) 是否语义分析9.多遍编译与一遍编译的主要区别在于。
A)多遍编译是编译的五大部分重复多遍执行,而一遍编译是五大部分只执行一遍;B)一遍编译是对源程序分析一遍就立即执行,而多遍编译是对源程序重复多遍分析再执行;C)多遍编译要生成目标代码才执行,而一遍编译不生成目标代码直接分析执行;D)多遍编译是五大部分依次独立完成,一遍编译是五大部分交叉调用执行完成。
10.编译程序分成“前端”和“后端”的好处是A)便于移植B)便于功能的扩充C)便于减少工作量D)以上均正确第二章练习题(文法与语言)一、选择题1.文法 G 产生的 (1) 的全体是该文法描述的语言。
A.句型B. 终结符集C. 非终结符集D. 句子2.若文法 G 定义的语言是无限集,则文法必然是 (2) A递归的 B 上下文无关的 C 二义性的 D 无二义性的3. Chomsky 定义的四种形式语言文法中, 0 型文法又称为(A)文法;1 型文法又称为(C)文法;2 型语言可由(G) 识别。
A 短语结构文法B 上下文无关文法C 上下文有关文法D 正规文法E 图灵机F 有限自动机G 下推自动机4.一个文法所描述的语言是(A);描述一个语言的文法是(B)。
《编译原理》考试试题及答案(汇总)一、是非题(请在括号内,正确的划√,错误的划×)(每个2分,共20分)1.编译程序是对高级语言程序的解释执行。
(× )2.一个有限状态自动机中,有且仅有一个唯一的终态。
(×)3.一个算符优先文法可能不存在算符优先函数与之对应。
(√ )4.语法分析时必须先消除文法中的左递归。
(×)5.LR分析法在自左至右扫描输入串时就能发现错误,但不能准确地指出出错地点。
(√)6.逆波兰表示法表示表达式时无须使用括号。
(√ )7.静态数组的存储空间可以在编译时确定。
(×)8.进行代码优化时应着重考虑循环的代码优化,这对提高目标代码的效率将起更大作用。
(×) 9.两个正规集相等的必要条件是他们对应的正规式等价。
(× )10.一个语义子程序描述了一个文法所对应的翻译工作。
(×)二、选择题(请在前括号内选择最确切的一项作为答案划一个勾,多划按错论)(每个4分,共40分) 1.词法分析器的输出结果是_____。
A.( ) 单词的种别编码B.( ) 单词在符号表中的位置C.( ) 单词的种别编码和自身值D.( ) 单词自身值2.正规式M 1 和M 2 等价是指_____。
A.( ) M1和M2的状态数相等B.( ) M1和M2的有向边条数相等C.( ) M1和M2所识别的语言集相等D.( ) M1和M2状态数和有向边条数相等3.文法G:S→xSx|y所识别的语言是_____。
A.( ) xyx B.( ) (xyx)* C.( ) xnyxn(n≥0) D.( ) x*yx*4.如果文法G是无二义的,则它的任何句子α_____。
A.( )最左推导和最右推导对应的语法树必定相同B.( ) 最左推导和最右推导对应的语法树可能不同C.( ) 最左推导和最右推导必定相同D.( )可能存在两个不同的最左推导,但它们对应的语法树相同5.构造编译程序应掌握______。
参考答案一、单项选择题(共10小题,每小题2分,共20分)1.语言是A .句子的集合B .产生式的集合C .符号串的集合D .句型的集合 2.编译程序前三个阶段完成的工作是 A .词法分析、语法分析和代码优化 B .代码生成、代码优化和词法分析C .词法分析、语法分析、语义分析和中间代码生成D .词法分析、语法分析和代码优化3.一个句型中称为句柄的是该句型的最左 A .非终结符号 B .短语 C .句子 D .直接短语4.下推自动机识别的语言是A .0型语言B .1型语言C .2型语言D .3型语言5.扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即 A . 字符B .单词C .句子D .句型6.对应Chomsky 四种文法的四种语言之间的关系是 A .L 0⊂L 1⊂L 2⊂L 3B .L 3⊂L 2⊂L 1⊂L 0C .L 3=L 2⊂L 1⊂L 0D .L 0⊂L 1⊂L 2=L 3 7.词法分析的任务是 A .识别单词B .分析句子的含义C .识别句子D .生成目标代码 8.常用的中间代码形式不含A .三元式B .四元式C .逆波兰式D .语法树 9. 代码优化的目的是A .节省时间B .节省空间C .节省时间和空间D .把编译程序进行等价交换10.代码生成阶段的主要任务是 A .把高级语言翻译成汇编语言 B .把高级语言翻译成机器语言C .把中间代码变换成依赖具体机器的目标代码装 订 线D.把汇编语言翻译成机器语言二、填空题(本大题共5小题,每小题2分,共10分)1.编译程序首先要识别出源程序中每个(单词),然后再分析每个(句子)并翻译其意义。
2.编译器常用的语法分析方法有(自底向上)和(自顶向下)两种。
3.通常把编译过程分为分析前端与综合后端两大阶段。
词法、语法和语义分析是对源程序的(分析),中间代码生成、代码优化与目标代码的生成则是对源程序的(综合)。
江南大学现代远程教育第二阶段练习题考试科目:《编译原理》第4章至第7章(总分100分)学习中心(教学点)批次:层次:专业:学号:身份证号:姓名:得分:一、选择与填充(30)1. 语法分析最常用的两类方法是______________和______________分析法。
2.若a为终结符,则A->α·a β为()项目。
A. 移进B. 归约C. 接受D. 待约3.最右推导是____________________________________________________。
4.文法分为四种类型,即0型、1型、2型、3型。
其中0型文法是( )。
A. 正则文法 B.短语文法 C.上下文有关文法 D.上下文无关文法5.自顶向下的语法分析方法的基本思想是:从文法的_____________开始,根据给定的输入串并按照文法的产生式一步一步的向下进行直接推导,试图推导出文法的___________,使之与给定的输入串_____________。
6. 在LR分析法中,分析栈中存放的状态是识别规范句型( )的DFA 状态。
A. 句柄B. 前缀C. 活前缀D. LR(0) 项目二、将文法G[S] 改写为等价的G'[S],使G'[S]不含左递归和左公共因子。
(15)G[S]:S→SAe|AeA→dAbA|dA|d三、写出下列程序的四元式。
(18)While a>0 ∨ b<0 doBeginX:=X+1;if a>0 then a:=a-1else b:=b+1End;四、说明带语义栈的LL驱动器中的四个语义栈指针的意义?(15)五、设文法G(S):S→(L)|a S|a L→L,S|S(1) 消除左递归和公共前缀;(2) 计算每个非终结符的FIRST集和FOLLOW集。
(22)附:参考答案:一、选择与填充(30)1. 语法分析最常用的两类方法是____自顶向下_____和_____自底向上____分析法。
《编译原理》考试试题及答案(汇总)一、是非题(请在括号内,正确的划√,错误的划×)(每个2分,共20分)1.编译程序是对高级语言程序的解释执行。
(× )2.一个有限状态自动机中,有且仅有一个唯一的终态。
(×)3.一个算符优先文法可能不存在算符优先函数与之对应。
(√ )4.语法分析时必须先消除文法中的左递归。
(×)5.LR分析法在自左至右扫描输入串时就能发现错误,但不能准确地指出出错地点。
(√)6.逆波兰表示法表示表达式时无须使用括号。
(√ )7.静态数组的存储空间可以在编译时确定。
(×)8.进行代码优化时应着重考虑循环的代码优化,这对提高目标代码的效率将起更大作用。
(×) 9.两个正规集相等的必要条件是他们对应的正规式等价。
(× )10.一个语义子程序描述了一个文法所对应的翻译工作。
(×)二、选择题(请在前括号内选择最确切的一项作为答案划一个勾,多划按错论)(每个4分,共40分) 1.词法分析器的输出结果是_____。
A.( ) 单词的种别编码B.( ) 单词在符号表中的位置C.( ) 单词的种别编码和自身值D.( ) 单词自身值2.正规式M 1 和M 2 等价是指_____。
A.( ) M1和M2的状态数相等B.( ) M1和M2的有向边条数相等C.( ) M1和M2所识别的语言集相等D.( ) M1和M2状态数和有向边条数相等3.文法G:S→xSx|y所识别的语言是_____。
A.( ) xyx B.( ) (xyx)* C.( ) xnyxn(n≥0) D.( ) x*yx*4.如果文法G是无二义的,则它的任何句子α_____。
A.( )最左推导和最右推导对应的语法树必定相同B.( ) 最左推导和最右推导对应的语法树可能不同C.( ) 最左推导和最右推导必定相同D.( )可能存在两个不同的最左推导,但它们对应的语法树相同5.构造编译程序应掌握______。
2-1 设有字母表A1 ={a,b,c,…,z},A2 ={0,1,…,9},试回答下列问题:(1) 字母表A1上长度为2的符号串有多少个?(2) 集合A1A2含有多少个元素?(3) 列出集合A1(A1∪A2)*中的全部长度不大于3的符号串。
2-2 试分别构造产生下列语言的文法:(1){a n b n|n≥0};(2){a n b m c p|n,m,p≥0};(3){a n#b n|n≥0}∪{c n#d n|n≥0};(4){w#w r# | w∈{0,1}*,w r是w的逆序排列 };(5)任何不是以0打头的所有奇整数所组成的集合;(6)所有由偶数个0和偶数个1所组成的符号串的集合。
2-3 试描述由下列文法所产生的语言的特点:(1)S→10S0S→aA A→bA A→a(2)S→SS S→1A0A→1A0A→ε(3)S→1A S→B0A→1A A→CB→B0B→C C→1C0C→ε(4)S→aSS S→a2-4 试证明文法S→AB|DC A→aA|a B→bBc|bc C→cC|c D→aDb|ab为二义性文法。
2-5 对于下列的文法S→AB|c A→bA|a B→aSb|c试给出句子bbaacb的最右推导,并指出各步直接推导所得句型的句柄;指出句子的全部短语。
2-6 化简下列各个文法(1) S→aABS|bCACd A→bAB|cSA|cCC B→bAB|cSB C→cS|c(2) S→aAB|E A→dDA|e B→bE|fC→c AB|dSD|a D→eA E→fA|g(3) S→ac|bA A→c BC B→SA C→bC|d2-7 消除下列文法中的ε-产生式(1) S→aAS|b A→cS|ε(2) S→aAA A→bAc|dAe|ε2-8 消除下列文法中的无用产生式和单产生式(1) S→aB|BC A→aA|c|aDb B→DB|C C→b D→B(2) S→SA|SB|A A→B|(S)|( ) B→[S]|[ ](3) E→E+T|T T→T*F|F F→P↑F|P P→(E)|i第2章习题答案2-1 答:(1) 26*26=676(2) 26*10=260(3) {a,b,c,...,z, a0,a1,...,a9, aa,...,az,...,zz, a00,a01,...,zzz},共有26+26*36+26*36*36=34658个2-2 解:(1) 对应文法为G(S)=({S},{a,b},{ S→ε| aSb },S)(2) 对应文法为G(S)=({S,X,Y},{a,b,c},{S→aS|X,X→bX|Y,Y→cY|ε },S)(3)对应文法为G(S)=({S,X,Y},{a,b,c,d,#}, {S→X,S→Y,X→aXb|#, Y→cYd|# },S)(4) G(S)=({S,W,R},{0,1,#}, {S→W#, W→0W0|1W1|# },S)(5) G(S)=({S,A,B,I,J},{0,1,2,3,4,5,6,7,8,9},{S→J|IBJ,B→0B|IB|ε, I→J|2|4|6|8, J→1|3|5|7|9},S)(6)对应文法为S→0A|1B|ε,A→0S|1C,B→0C|1S,C→1A|0B2-3 解:(1) 本文法构成的语言集为:L(G)={(10)n ab m a0n|n,m≥0}。
试卷(二):一、选择1.下面说法正确的是:BA 一个正规式只能对应一个确定的有限状态自动机;B 一个正规语言可能对应多个正规文法;2.算符优先分析与规范归约相比的优点是:AA 归约速度快B 对文法限制少3.一个LR(1)文法合并同心集后若不是LALR(1)文法:BA 则可能存在移进/归约冲突B 则可能存在归约/归约冲突C 则可能存在移进/归约冲突和归约/归约冲突4.下面说法正确的是:AA Lex是一个词法分析器的生成器B Yacc是一个语法分析器二、问答题问答第1题(5分) 将文法G[S] 改写为等价的G'[S],使G'[S]不含左递归和左公共因子。
G[S]:S→SAe|AeA→dAbA|dA|d解:文法G[S] 改写为等价的不含左递归和左公共因子的G'[S]为:S →AeS'S' →AeS'|εA →dA'A' →AB|εB →bA |ε问答第2题(10分) 判断下面文法是否为LL(1)文法,若是,请构造相应的LL(1)分析表。
S→aDD→STe|εT→bH|HH→d|ε首先计算文法的FIRST集和FOLLOW集如下表。
文法的FIRST集和FOLLOW集非终结符FIRST集FOLLOW集S {a}{#,b,d,e}D {a,ε}{#,b,d,e }T {b,d,ε} {e}H {d,ε}{e}由于select(D→STe)∩select(D→ε)={a}∩{# ,b ,d ,e }=select(T→bH)∩select(T→H)={b}∩{e }=select(H→d)∩select(H→ε)={ d }∩{ e }=所以该文法是LL(1)文法,LL(1)分析表如下表。
LL(1)分析表a eb d #S →aDD →STe →ε →ε →ε →εT →H→bH →HH →ε →d问答第3题(5分) 给出与正规式R=((ab)*|b)*(a|(ba)*)a 等价的NFA。
编译原理》考试试题及答案(汇总)一、是非题(请在括号内,正确的划",错误的划X)(每个2分,共20分)1 .编译程序是对高级语言程序的解释执行。
(x )2. —个有限状态自动机中,有且仅有一个唯一的终态。
(X)3. —个算符优先文法可能不存在算符优先函数与之对应。
(V )4. 语法分析时必须先消除文法中的左递归。
(x)5. 分析法在自左至右扫描输入串时就能发现错误,但不能准确地指出出错地点。
( V)6. 逆波兰表示法表示表达式时无须使用括号。
(V )7. 静态数组的存储空间可以在编译时确定。
(x)8. 进行代码优化时应着重考虑循环的代码优化,这对提高目标代码的效率将起更大作用。
( x)9. 两个正规集相等的必要条件是他们对应的正规式等价。
(x)(x )10. 一个语义子程序描述了一个文法所对应的翻译工作、选择题 ( 请在前括号内选择最确切的一项作为答案划一个勾, 多划按错4.如果文法G 是无二义的,则它的任何句子aA. ( ) 最左推导和最右推导对应的语法树必定相同B. ( ) 最左推导和最右推导对应的语法树可能不同C. ( ) 最左推导和最右推导必定相同论)( 每个 4 分,共 40分) 1.词法分析器的输出结果是。
A .( ) 单词的种别编码C .( ) 单词的种别编码和自身值 2. 正规式 M 1 和 M 2 等价是指。
A. ( ) M1和M2的状态数相等 的有向边条数相等C. ( ) M1和M2所识别的语言集相等 向边条数相等3. 文法G S f 所识别的语言是。
A. ( )B . ( ) ()*C . ( ) (nB. ( ) 单词在符号表中的位置 D . ( ) 单词自身值B . ( ) M1 和 M2D. ( ) M1 和M2状态数和有> 0) D . ( ) x**D. ( ) 可能存在两个不同的最左推导,但它们对应的语法树相同5.构造编译程序应掌握6.四元式之间的联系是通过实现的。
《编译原理》期末试题(二)一、是非题:1.一个上下文无关文法的开始符,可以是终结符或非终结符。
( )2.一个句型的直接短语是唯一的。
()3.已经证明文法的二义性是可判定的。
()4.每个基本块可用一个DAG表示。
()5.每个过程的活动记录的体积在编译时可静态确定。
()6.2型文法一定是3型文法。
()7.一个句型一定句子。
( )8.算符优先分析法每次都是对句柄进行归约。
X ( )9.采用三元式实现三地址代码时,不利于对中间代码进行优化。
()10.编译过程中,语法分析器的任务是分析单词是怎样构成的。
( )11.一个优先表一定存在相应的优先函数。
X ( )12.目标代码生成时,应考虑如何充分利用计算机的寄存器的问题。
( )13.递归下降分析法是一种自下而上分析法。
( )14.并不是每个文法都能改写成LL(1)文法。
( )15.每个基本块只有一个入口和一个出口。
( )16.一个LL(1)文法一定是无二义的。
( )17.逆波兰法表示的表达试亦称前缀式。
( )18.目标代码生成时,应考虑如何充分利用计算机的寄存器的问题。
( )19.正规文法产生的语言都可以用上下文无关文法来描述。
( )20.一个优先表一定存在相应的优先函数。
( )21.3型文法一定是2型文法。
( )22.如果一个文法存在某个句子对应两棵不同的语法树,则文法是二义性的。
( )答案:1.× 2.× 3.× 4.√ 5.√ 6.× 7.× 8.× 9.√ 10.×11.×12.√ 13.× 14.√ 15.√ 16.√ 17.× 18.√ 19.√ 20.× 21.√ 22.√二、填空题:2.编译过程可分为(词法分析),(语法分析),(语义分析与中间代码生成),(优化)和(目标代码生成)五个阶段。
3.如果一个文法存在某个句子对应两棵不同的语法树,则称这个文法是(二义性的)。
编译原理自测一一、是非题(下列各题,你认为正确的,请在题干的括号内打“√”,错的打“×”。
每题1分,共5分)1、算符优先关系表不一定存在对应的优先函数。
正确2、数组元素的地址计算与数组的存储方式有关。
.正确3、仅考虑一个基本块,不能确定一个赋值是否真是无用的。
正确4、每个文法都能改写为LL(1)文法。
不正确5、对于数据空间的存贮分配,FORTRAN采用动态贮存分配策略。
不正确二、填空题1、从功能上说,程序语言的语句大体可分为(执行性)语句和(说明性)语句两大类。
2、扫描器的任务是从(源程序)中识别出一个个(单词符号)。
3、所谓最右推导是指:(任何一步αβ都是对α中最右非终结符进行替换的)。
4、语法分析最常用的两类方法是(自上而下)和(自下而上)分析法。
5、一个上下文无关文法所含四个组成部分是(一组终结符号,一组非终结符号、一个开始符号、一组产生式)。
6、所谓语法制导翻译方法是(为每个产生式配上一个翻译子程序,并在语法分析的同时执行这些子程序)。
7、符号表中的信息栏中登记了每个名字的有关的性质,如(类型、种属、?)等等。
8、一个过程相应的DISPLAY表的内容为(现行活动记录)。
9、常用的两种动态存贮分配办法是(栈式)动态分配和(堆式)动态分配。
10、产生式是用于定义(语法范畴)的一种书写规则。
三、名词解释1.遍--指编译程序对源程序或中间代码程序从头到尾扫描一次。
2.无环路有向图(DAG)--如果有向图中任一通路都不是环路,则称庐有向图为无环路有向图,简称DAG。
3.语法分析--按文法的产生式识别输入的符号串是否为一个句子的分析过程。
4.短语--令G是一个文法。
S划文法的开始符号,假定αβδ是文法G的一个句型,如果有SαAδ且AB,则称β是句型αβ相对非终结符A的短语。
5.后缀式--一种把运算量写在前面,把算符写在后面的表示表达式的方法。
编译原理自测二一、是非题(下列各题,你认为正确的,请在题干的括号内打“√”,错的打“×”。
考试科目:《编译原理》第4章至第7章(总分100分)时间:90分钟
一、选择与填充(30)
1. 语法分析最常用的两类方法是___自顶向下_____和____自底向上____分析法。
2.若a为终结符,则A->α·a β为( A )项目。
A. 移进
B. 归约
C. 接受
D. 待约
3.最右推导是____在每步推导时总是替换句型中的最右的非终结符______。
4.文法分为四种类型,即0型、1型、2型、3型。
其中0型文法是( B )。
A. 正则文法 B.短语文法 C.上下文有关文法 D.上下文无关文法
5.自顶向下的语法分析方法的基本思想是:从文法的____开始符号___开始,根据给定的输入串并按照文法的产生式一步一步的向下进行直接推导,试图推导出文法的___句子__,使之与给定的输入串___匹配___。
6. 在LR分析法中,分析栈中存放的状态是识别规范句型( C )的DFA 状态。
A. 句柄
B. 前缀
C. 活前缀
D. LR(0) 项目
二、将文法G[S] 改写为等价的G'[S],使G'[S]不含左递归和左公共因子。
(15)
G[S]:S→SAe|Ae
A→dAbA|dA|d
三、写出下列程序的四元式。
(18)
While a>0 ∨ b<0 do
Begin
X:=X+1;
if a>0 then a:=a-1
else b:=b+1
End;
四、说明带语义栈的LL驱动器中的四个语义栈指针的意义?(15)
五、设文法G(S):S→(L)|a S|a L→L,S|S
(1) 消除左递归和公共前缀;(2) 计算每个非终结符的FIRST集和FOLLOW集。
(22)。