编译原理复习题

编译原理复习题及答案一、选择题1．一个正规语言只能对应(B)A 一个正规文法B 一个最小有限状态自动机2．文法G[A]：A→εA→aB B→Ab B→a是(A)A 正规文法B 二型文法3．下面说法正确的是(A)A 一个SLR（1）文法一定也是LALR（1）文法B 一个LR（1）文法一定也是LALR（1）文法4．一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL（1）文法的(A)A 必要条件B 充分必要条件5．下面说法正确的是(B)A 一个正规式只能对应一个确定的有限状态自动机B 一个正规语言可能对应多个正规文法6．算符优先分析与规范归约相比的优点是(A)A 归约速度快B 对文法限制少7．一个LR（1）文法合并同心集后若不是LALR（1）文法(B)A 则可能存在移进/归约冲突B 则可能存在归约/归约冲突C 则可能存在移进/归约冲突和归约/归约冲突8．下面说法正确的是(A)A Lex是一个词法分析器的生成器B Yacc是一个语法分析器9．下面说法正确的是(A)A 一个正规文法也一定是二型文法B 一个二型文法也一定能有一个等价的正规文法10．编译原理是对(C)。

A、机器语言的执行B、汇编语言的翻译C、高级语言的翻译D、高级语言程序的解释执行11．用高级语言编写的程序经编译后产生的程序叫(B)A．源程序 B．目标程序C．连接程序D．解释程序12．(C)不是编译程序的组成部分。

A.词法分析程序B.代码生成程序C.设备管理程序D.语法分析程序13．通常一个编译程序中，不仅包含词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成等六个部分，还应包括(C)。

A．模拟执行器B．解释器 C．表格处理和出错处理D．符号执行器14．源程序是句子的集合，(B)可以较好地反映句子的结构。

A. 线性表B. 树C. 完全图D. 堆栈15．词法分析器的输出结果是(D)。

A、单词自身值B、单词在符号表中的位置C、单词的种别编码D、单词的种别编码和自身值16．词法分析器不能(D)A. 识别出数值常量B. 过滤源程序中的注释C. 扫描源程序并识别记号D. 发现括号不匹配17．文法：G：S→xSx | y所识别的语言是(D)。

编译原理（一）一、是非题1、算符优先关系表不一定存在对应的优先函。

………………………………………（）2、数组元素的地址计算与数组的存储方式有关。

……………………………（）3、仅考虑一个基本块，不能确定一个赋值是否真是无用的。

…………………………（）4、每个文法都能改写为LL(1)文法。

……………………………………………（）5、对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。

………………（）二、填空题1、从功能上说，程序语言的语句大体可分为（）语句和（）语句两大类。

2、扫描器的任务是从（）中识别出一个个（）。

3、所谓最右推导是指：（）。

4、语法分析最常用的两类方法是（）和（）分析法。

5、一个上下文无关文法所含四个组成部分是（）。

6、所谓语法制导翻译方法是（）。

7、符号表中的信息栏中登记了每个名字的有关的性质，如（）等等。

8、一个过程相应的DISPLA Y表的内容为（）。

9、常用的两种动态存贮分配办法是（）动态分配和（）动态分配。

10、产生式是用于定义（）的一种书写规则。

三、名词解释1、遍－－2、无环路有向图(DAG)－－3、语法分析－－4、短语－－5、后缀式－－四、简述题1、考虑下面程序…………V ar a：integer；Procedure S(X)；V ar X：integer；Begina：＝a＋1；X：＝a＋XEnd；Begina：＝5；S(a)；Print(a)End．试问：若参数传递方式分别采取传名和传值时，程序执行后输出a的值是什么？2、画出Pascal中实数(不带正负号，可带指数部分)的状态转换图。

3、写出表达式(a＋b*c)/(a＋b)－d的逆波兰表示及三元式序列。

4、已知文法G(S)S→a|∧|(T)T→T，S|S写出句子((a，a)，a)的规范归约过程及每一步的句柄。

5、何谓优化？按所涉及的程序范围可分为哪几级优化？6、目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？五、计算题1、写一个文法，使其语言是奇数集，且每个奇数不以0开头。

编译技术命题指导意见教学内容知识点及题型第一章编译器概述A （1）编译的阶段划分[选择题2分][1] 编译程序绝大多数时间花在( )上。

A. 出错处理B. 词法分析C. 目标代码生成D. 符号表管理答案：D[2] ( ) 和代码优化部分不是每个编译程序都必需的。

A. 语法分析B. 中间代码生成C. 词法分析D. 代码生成答案：B[3] 编译程序前三个阶段完成的工作是( )。

A. 词法分析、语法分析和代码优化B. 代码生成、代码优化和词法分析C. 词法分析、语法分析和语义分析D. 词法分析、语法分析和代码生成答案：C（2）遍的概念[填空题2分][1] 编译阶段的活动常用一遍扫描来实现，一遍扫描包括和。

答案：读一个输入文件写一个输出文件[2] 将编译程序分成若干个“遍”是为了________。

答案：使程序的结构更加清晰[3] 编译器从逻辑上可以分为7个阶段，其中，可以作为一个后端遍的是___________阶段。

答案：代码生成（3）前端和后端的划分[简答题5分][1] 什么是前端？[5分]答案：编译器分成分析和综合两大部分。

分析部分揭示源程序的基本元素和它们所形成的层次结构，决定它们的含义，建立起源程序的中间表示，分析部分经常被称为前端。

[2] 什么是后端？[5分]答案：编译器分成分析和综合两大部分。

综合部分从源程序的中间表示建立起和源程序等价的目标程序，它经常被称为后端。

[3] 什么是前端？什么是后端？[5分]答案：编译器分成分析和综合两大部分。

分析部分揭示源程序的基本元素和它们所形成的层次结构，决定它们的含义，建立起源程序的中间表示，分析部分经常被称为前端。

综合部分从源程序的中间表示建立起和源程序等价的目标程序，它经常被称为后端。

第二章2.1 2.2 词法记号的定义及描述B （1）词法分析器的功能[选择题2分][1] 词法分析程序的输出结果是（）。

A. 单词的种别编码B. 单词在符号表中的位置C. 单词的种别编码和单词属性值D. 单词的单词属性值答案：C[2] 词法分析器用于识别_____。

新建试卷20181220104955一、单选题（共65题，65分）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、词法分析的任务是B、分析句子的含义C、识别句子D、生成目标代码7、常用的中间代码形式不含A、三元式B、四元式C、逆波兰式D、语法树8、代码优化的目的是A、节省时间B、节省空间C、节省时间和空间D、把编译程序进行等价交换9、代码生成阶段的主要任务是A、把高级语言翻译成汇编语言B、把高级语言翻译成机器语言C、把中间代码变换成依赖具体机器的目标代码D、把汇编语言翻译成机器语言10、将编译程序分成若干个“遍”是为了( )A、 . 提高程序的执行效率B、使程序的结构更加清晰C、利用有限的机器内存并提高机器的执行效率D、利用有限的机器内存但降低了机器的执行效率11、11．正规式MI 和M等价是指（）。

A、 . MI 和M2 的状态数相等B、 Ml 和M2 的有向弧条数相等。

C、 .M1 和M2 所识别的语言集相等D、 Ml 和M2 状态数和有向弧条数相等12、中间代码生成时所依据的是（）。

A、语法规则C、语义规则D、等价变换规则13、后缀式ab+cd+/可用表达式（）来表示。

A、 a+b/c+dB、 (a+b)/(c+d)C、 a+b/(c+d)D、 a+b+c/d14、一个编译程序中，不仅包含词法分析，（），中间代码生成，代码优化，目标代码生成等五个部分。

1、（10分）下面的文法G[S]是否是LL（1）文法，说明理由，构造LL（1）分析表S→aBc|bAB A→aAb|Bb B→cB|2、（5分）消除下列文法的左递归，消除左递归后判断是否是LL（1）文法。

S→SaB|bB A→S|a B→Ac3、（5分）构造下面算符文法的优先矩阵，判断是否是算符优先文法S→A[] A→[ A→aA A→B] B→a4、（10分）将表达式A+B*(C-D)-E/F↑G分别表示为三元式、四元式、逆波兰式序列5、（10分）现有文法如下：S→aS|bS|a 判断该文法是哪一类LR文法，说明理由，并构造相应的分析表。

1、已知文法G A::=aABe|a B::=Bb|d（1）给出与上述文法等价的LL（1）文法G’。

（2）构造预测分析表并给出输入串aade#分析过程。

（10分）2、设已给文法G: E::=E+T E::=T T::=T*F T::=F F::=P↑F F::=P P::=(E)P::=i构造此文法的算符优先矩阵。

（10分）3、有正规式b*abb*(abb*)*（1）构造该正规式所对应的NFA（画出状态转换图）。

（2）将所求的NFA确定化。

（画出确定化的状态转换图）。

（3）将所求的NFA最小化。

（画出最小化后的状态转换图）。

（10分）4、若有文法G（S）的产生式如下：S::=L=R S::=R L::=*R L::=i R::=L,构造识别所有项目集规范族的DFA。

（15分）（1）判断该文法是否是LR（0）文法，说明理由。

（2）判断该文法是否是SLR（1）文法，说明理由。

（3）判断该文法是否是LR（1）文法，说明理由。

（4）判断该文法是否是LALR（1）文法，说明理由1、（10分）将表达式（（B*D+A）/E+D）*F+G分别表示为三元式、四元式、逆波兰式序列2、（10分）对基本块P画出DAG图B:=3D:=A+CE::=A*CF:=E+DG:=B*FH:=A+CI:=A*CJ:=H+IK:=B*5L:=K+JM:=L假定只有L在基本块出口之后活跃，写出优化后的四元式序列。

第二章P36-6(1)L G ()1是0~9组成的数字串(2)最左推导:N ND NDD NDDD DDDD DDD DD D N ND DD D N ND NDD DDD DD D ⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒0010120127334556568最右推导:N ND N ND N ND N D N ND N D N ND N ND N D ⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒77272712712701274434886868568P36-7G(S)O N O D N S O AO A AD N→→→→→1357924680|||||||||||P36-8文法：E T E T E T TF T F T F F E i→+-→→|||*|/()| 最左推导:E E T T TF T i T i T F i F F i i F i i i E T T F F F i F i E i E T i T T i F T i i T i i F i i i ⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒⇒⇒⇒⇒⇒+⇒+⇒+⇒+⇒+⇒+********()*()*()*()*()*()*()最右推导:E E T E TF E T i E F i E i i T i i F i i i i i E T F T F F F E F E T F E F F E i F T i F F i F i i i i i ⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒⇒⇒⇒⇒+⇒+⇒+⇒+⇒+⇒+⇒+**********()*()*()*()*()*()*()*()语法树：/********************************EE FTE +T F F T +iiiEEFTE-T F F T -iiiEEFT+T F FTiii*i+i+ii-i-ii+i*i*****************/P36-9句子iiiei 有两个语法树：S iSeS iSei iiSei iiiei S iS iiSeS iiSei iiiei ⇒⇒⇒⇒⇒⇒⇒⇒P36-10/**************)(|)(|S T TTS S →→***************/P36-11/*************** L1:ε||cC C ab aAb A AC S →→→ L2:bcbBc B aA A AB S ||→→→εL3:εε||aBb B aAb A AB S →→→ L4:AB B A A B A S |01|10|→→→ε ***************/第三章习题参考答案P64–7(1)确定化：最小化：{,,,,,},{}{,,,,,}{,,}{,,,,,}{,,,}{,,,,},{},{}{,,,,}{,,}{,,,},{},{},{}{,,,}{,012345601234513501234512460123456012341350123456012310100==== 3012312401234560110112233234012345610101}{,,,}{,,}{,},{,}{},{},{}{,}{}{,}{,}{,}{}{,}{}{},{},{,},{},{},{}=====P64–8(1)01)0|1(*(2))5|0(|)5|0()9|8|7|6|5|4|3|2|1|0)(9|8|7|6|5|4|3|2|1(*(3)******)110|0(01|)110|0(10P64–12(a)确定化：给状态编号：最小化：{,},{,}{,}{}{,}{}{,}{,}{,}{}{,},{},{}012301101223032330123a ba b ====(b)已经确定化了,进行最小化最小化：{{,}, {,,,}}012345011012423451305234523452410243535353524012435011012424{,}{}{,}{,}{,,,}{,,,}{,,,}{,,,}{,}{,}{,}{,}{,}{,}{,}{,}{{,},{,},{,}}{,}{}{,}{,}{,}a b a b a b a b a b a =============={,}{,}{,}{,}{,}{,}{,}10243535353524 b a baP64–14(2):给状态编号：最小化：{,},{,}{,}{}{,}{}{,}{,}{,}{}{,},{},{}0123011012231323301230101====第四章P81–1(1) 按照T,S 的顺序消除左递归ε|,)(||^)(T S T TS T T a S S G '→''→→' 递归子程序： procedure S; beginif sym='a' or sym='^' then abvance else if sym='('then beginadvance;T;if sym=')' then advance;else error;endelse errorend;procedure T;beginS;'Tend;procedure 'T;beginif sym=','then beginadvance;S;'Tendend;其中:sym:是输入串指针IP所指的符号advance:是把IP调至下一个输入符号error:是出错诊察程序(2)FIRST(S)={a,^,(}FIRST(T)={a,^,(}FIRST('T)={,,ε}FOLLOW(S)={),,,#}FOLLOW(T)={)}FOLLOW('T)={)}预测分析表是LL(1)文法P81–2文法：|^||)(|*||b a E P F F F P F T T T F T E E E T E →'→''→→''→+→''→εεε(1)FIRST(E)={(,a,b,^} FIRST(E')={+,ε} FIRST(T)={(,a,b,^} FIRST(T')={(,a,b,^,ε} FIRST(F)={(,a,b,^} FIRST(F')={*,ε} FIRST(P)={(,a,b,^} FOLLOW(E)={#,)} FOLLOW(E')={#,)} FOLLOW(T)={+,),#} FOLLOW(T')={+,),#}FOLLOW(F)={(,a,b,^,+,),#} FOLLOW(F')={(,a,b,^,+,),#} FOLLOW(P)={*,(,a,b,^,+,),#} (2)考虑下列产生式:'→+'→'→'→E E T T F F P E a b ||*|()|^||εεεFIRST(+E)∩FIRST(ε)={+}∩{ε}=φ FIRST(+E)∩FOLLOW(E')={+}∩{#,)}=φ FIRST(T)∩FIRST(ε)={(,a,b,^}∩{ε}=φ FIRST(T)∩FOLLOW(T')={(,a,b,^}∩{+,),#}=φ FIRST(*F')∩FIRST(ε)={*}∩{ε}=φFIRST(*F')∩FOLLOW(F')={*}∩{(,a,b,^,+,),#}=φ FIRST((E))∩FIRST(a) ∩FIRST(b) ∩FIRST(^)=φ 所以,该文法式LL(1)文法.(4)procedure E;beginif sym='(' or sym='a' or sym='b' or sym='^' then begin T; E' endelse errorendprocedure E';beginif sym='+'then begin advance; E endelse if sym<>')' and sym<>'#' then error endprocedure T;beginif sym='(' or sym='a' or sym='b' or sym='^' then begin F; T' endelse errorendprocedure T';beginif sym='(' or sym='a' or sym='b' or sym='^' then Telse if sym='*' then errorendprocedure F;beginif sym='(' or sym='a' or sym='b' or sym='^' then begin P; F' endelse errorendprocedure F';beginif sym='*'then begin advance; F' endendprocedure P;beginif sym='a' or sym='b' or sym='^'then advanceelse if sym='(' thenbeginadvance; E;if sym=')' then advance else error endelse errorend;P81–3/***************(1) 是，满足三个条件。

一、单项选择题概述部分1．构造编译程序应掌握 。

DA. 源程序B. 目标语言C. 编译方法D. 以上三项都是2．编译程序绝大多数时间花在 上。

DA. 出错处理B. 词法分析C. 目标代码生成D. 表格管理3．编译程序是对 。

DA. 汇编程序的翻译B. 高级语言程序的解释执行C. 机器语言的执行D. 高级语言的翻译4. 将编译程序分成若干“遍”，是为了 。

BA. 提高程序的执行效率B. 使程序的结构更为清晰C 利用有限的机器内存并提高机器的执行效率D. 利用有限的机器内存但降低了机器的执行效率词法分析部分1．DFA M(见图1-1)接受的字集为 。

DA. 以0开头的二进制数组成的集合B. 以0结尾的二进制数组成的集合C. 含奇数个0的二进制数组成的集合D. 含偶数个0的二进制数组成的集合 2．词法分析器的输出结果是 。

C A. 单词的种别编码 B. 单词在符号表中的位置C. 单词的种别编码和自身值D. 单词自身值3．正规式M1和M2等价是指 。

CA. M1和M2的状态数相等B. M1和M2的有向边条数相等C. M1和M2所识别的语言集相等D. M1和M2状态数和有向边条数相等4．词法分析器的加工对象是 。

CA ．中间代码B ．单词C ．源程序D ．元程序5．同正规式（a|b ）*等价的正规式为 。

DA ．(a|b)+B ．a*|b*C ．(ab)*D ．(a*|b*)+6. 两个DFA 等价是指： 。

DA. 这两个DFA 的状态数相同B. 这两个DFA 的状态数和有向弧条数都相等C. 这两个DFA 的有向弧条数相等D. 这两个DFA 接受的语言相同7. 下列符号串不可以由符号集S ＝{a,b}上的正闭包运算产生的是：（A ）A. εB. aC. aaD. ab8．称有限自动机A1和A2等价是指________。

DA ．A1和A2都是定义在一个字母表上的有限自动机B ．A1和A2状态数和有向边数相等C ．A1和A2状态数或有向边数相等图1-11D．A1和A2所能识别的字符串集合相等9．同正规式（a|b）+等价的正规式是_______。

第八节习题一、单项选择题1、将编译程序分成若干个“遍”是为了 b 。

a．提高程序的执行效率b．使程序的结构更加清晰c．利用有限的机器存并提高机器的执行效率d．利用有限的机器存但降低了机器的执行效率2、构造编译程序应掌握 d 。

a．源程序b．目标语言c．编译方法d．以上三项都是3、变量应当 c 。

a．持有左值b．持有右值c．既持有左值又持有右值d．既不持有左值也不持有右值4、编译程序绝大多数时间花在 b 上。

a．出错处理b．词法分析c．目标代码生成d．管理表格5、 d 不可能是目标代码。

a．汇编指令代码b．可重定位指令代码c．绝对指令代码d．中间代码6、使用 a 可以定义一个程序的意义。

a．语义规则b．词法规则c．产生规则d．词法规则7、词法分析器的输入是 a 。

a．单词符号串b．源程序c．语法单位d．目标程序8、中间代码生成时所遵循的是- d 。

a．语法规则b．词法规则c．语义规则d．等价变换规则9、编译程序是对 d 。

a．汇编程序的翻译b．高级语言程序的解释执行c．机器语言的执行d．高级语言的翻译10、语法分析应遵循 b 。

a．语义规则b．语法规则c．构词规则d．等价变换规则解答1、将编译程序分成若干个“遍”是为了使编译程序的结构更加清晰，故选b。

2、构造编译程序应掌握源程序、目标语言及编译方法等三方面的知识，故选d。

3、对编译而言，变量既持有左值又持有右值，故选c。

4、编译程序打交道最多的就是各种表格，因此选d。

5、目标代码包括汇编指令代码、可重定位指令代码和绝对指令代码3种，因此不是目标代码的只能选d。

6、词法分析遵循的是构词规则，语法分析遵循的是语法规则，中间代码生成遵循的是语义规则，并且语义规则可以定义一个程序的意义。

因此选a。

7、b 8、c 9、d 10、c二、多项选择题1、编译程序各阶段的工作都涉及到bc 。

a．语法分析b．表格管理c．出错处理d．语义分析e．词法分析2、编译程序工作时，通常有abce 阶段。

一、选择1、构造编译程序应掌握（）A.源程序B.目标文件C.编译方法D.以上三项2、编译程序绝大多数时间花在（）上A.出错处理B.词法分析C.目标代码生成D.表格管理3、编译程序是对（）A.汇编程序的翻译B.高级语言程序的解释执行C.机器语言的执行D.高级语言的翻译4、词法分析器的输出结果是（）A.单词的种别编码B.单词在符号表中的位置C.单词的种别编码和自身值D.单词自身值5、正规式M1和M2等价是指（）A. M1和M2的状态数相等B. M1和M22的有向变条数相等C. M1和M2所识别的语言集相等D. M1和M2状态数和有向边条数6、DFA M接受的字集为（）A.以0开头的二进制数组成的集合B.以0结尾的二进制数组成的集合C.含奇数个0的二进制数组成的集合D.含偶数个0的二进制数组成的集合7、文法G[S]:S→xSx|y所识别的语言是（）A.xyxB.（xyx）*C.x n yx n（n≥0）D.x n yx n8、如果文法G[S]是无二义的，则它的任何句子α（）A.最左推导和最右推导对应的语法树必定相同B.最左推导和最右推导对应的语法树可能不同C.最左推导和最右推导必定相同D.可能存在两个不同的最左推导，但它们对应的语法树相同9、采用自顶向下分析，必须（）A.消除左递归B.消除右递归C.消除回溯D.提取公共左因子10、设a、b、c是文法的终结符，且满足有限关系a〓b和b〓c，则（）A.必有a〓cB.必有c〓aC.必有b〓aD.a~c都不一定成立11、在规范规约中，用（）开刻画可归约串A.直接短语B.句柄C.最左素短语D.素短语12、若a为终结符，则A→α·aβ为（）项目A.规约B.移近C.接受D.待约13、若项目集合Ik含有A→α·，则在状态k时，仅当面临的输入符号a∈FOLLOW(A)时，才采取“A→α·”动作的一定是（）LR文法B.LR(0)文法C.LR(1)文法D.SLR(1)文法14、同心集合并有可能产生新的（）冲突A.归约B.“移进”/“移进”C.“移进”/“归约”D.“归约”/“归约”15、四元式之间的联系时通过（）实现的A.指示器B.临时变量C.符号表D.程序变量16、间接三元式表示法的优点为（）A.采用间接码表，便于优化处理B.节省存储空间，不便于表的修改C.便于优化处理，节省存储空间D.节省存储空间，不便于优化处理17、表达式（┐A∨B）∧（C∨D）的逆波兰表示为（）A. ┐AB∨∧CD ∨B. A┐B∨CD∨∧C.AB∨┐CD∨∧D.A┐B∨∧CD∨18、过程的DISPLAY表中记录了（）A.过程的连接数据B.过程的嵌套层次C.过程的返回地址D.过程的入口地址19、过程P1调用P2是，连接数据不包含（）A.嵌套层次显示表B.老SP值C.返回地址D.全局DISPLAY表地址20、堆式动态分配申请和释放存储空间遵守（）原则A.先请先放B.先请后放C.后请先放D.任意21、.栈式动态分配与管理在过程返回时应做的工作有（）A.保护SPB.恢复SPC.保护TOPD.恢复TOP22、如果活动记录中没有DISPLAY表，则说明（）A.程序中不允许有递归定义的过程B.程序中不允许有嵌套定义的过程C.程序中不允许有嵌套定义的过程，也不允许有递归定义的过程D.程序中允许有递归定义的过程，也允许有嵌套定义的过程23、优化可生成（）的目标代码A.运行时间较短B.占用存储空间较小C.运行时间短但占用内存空间大D.运行时间短且占用存储空间小24、下列（）优化方法不是针对循环优化进行的A.强度削弱B.删除归纳变量C.删除多余运算D.代码外提25、基本块内的优化为（）A.代码外提，删除归纳变量B.删除多余运算，删除无用赋值C.强度削弱，代码外提D.循环展开，循环合并26、在程序流图中，我们称具有下述性质（）的节点序列为一个循环A.它们是非连通的且只有一个入口结点B.它们是强连通的但有多个入口结点C.它们是非连通的但有多个入口结点D.它们是强联通的且只有一个入口结点27、关于必经结点的二元关系，下列叙述中不正确的是（）A.满足自反性B.满足传递性C.满足反对称性D.满足对称性28、有一语法制导翻译如下：S→bAb {print“1”} A→(B {print“2”}A→a {print“3”} B→Aa) {print“4”}若输入序列为b(((aa)a)a)b,且采用自底向上的分析方法，则输出序列为（）A.32224441B.34242421C.12424243D.3444221229、错误的局部化是（）A．把错误理解成局部的错误B. 对错误在局部范围内进行纠结C．当发现错误时，跳过错误所在的语法单位继续分析下去D．当发现错误时立即停止编译，待用户改正错误后再继续编译二、填空1、编译程序划分的类型_________2、编译程序是对__ 高级语言的翻译_3、若文法是无二义的，则规范推导与规范归纳的关系_________4、词法分析程序输出的单词符号通常表示成二元式的形式5、语言的目标是_______，是一个特殊的非终结符6、描述语言L={ab|n≥m ≥1}的文法为__________7、程序语言的生成系统是_________，而识别系统则是___________8、语法分析器的功能是输入_____________输出_____________9、两个自动机等价是指DFA和NFA10、文法四元组G[S]={V T V T S ξ}______________11、词法分析器的输出结果是__________________12、语法分析的方法种类_________________13、文法符号的属性种类____________________14、文法G所描述的语言是__________的集合15、为使编译程序能正确翻译，对程序设计语言必须使用___________的定义方法16、LR语法分析法是指_____________扫描输入串和________进行规范归纳17、首节点是指从它开始到控制流程图中任何一个结点都有一条通路的结点。

《编译原理》期末考试复习题一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分）×1．计算机高级语言翻译成低级语言只有解释一种方式。

()×2．在编译中进行语法检查的目的是为了发现程序中所有错误。

()√3．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。

()×4．正则文法其产生式为 A->a ， A->Bb, A,B∈VN ， a 、b∈VT 。

()√5．每个文法都能改写为 LL(1) 文法。

()√6．递归下降法允许任一非终极符是直接左递归的。

()×7．算符优先关系表不一定存在对应的优先函数。

()×8．自底而上语法分析方法的主要问题是候选式的选择。

()×9．LR 法是自顶向下语法分析方法。

()×10．简单优先文法允许任意两个产生式具有相同右部。

()三、填空题(每空1分，共10分)1．编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析,中间代码生成,代码优化等几个基本阶段,同时还会伴有__ ___和 ___ _。

表格管理出错处理_2．若源程序是用高级语言编写的,__ __是机器语言程序或汇编程序,则其翻译程序称为 __ __ 。

_目标程序_编译程序3．编译方式与解释方式的根本区别在于__ __。

是否生成目标代码_4．对编译程序而言,输入数据是__ __, 输出结果是__ ___。

_源程序目标程序5．产生式是用于定义__ __的一种书写规则。

_语法成分6．语法分析最常用的两类方法是___ __和__ __分析法。

自上而下_自下而上四、简答题（20分）1. 什么是句子什么是语言答：(1)设G是一个给定的文法，S是文法的开始符号，如果S x(其中x∈VT*),则称x是文法的一个句子。

(2)设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为： L(G)＝{x│S x,x∈VT*} 。

《编译原理》课程复习五、计算题：1、考虑下面程序…………V ar a：integer；Procedure S(X)；V ar X：integer；Begina：＝a＋1；X：＝a＋XEnd；Begina：＝5；S(a)；Print(a)End．试问：若参数传递方式分别采取传名和传值时，程序执行后输出a的值是什么？答：传名：a＝12传值：a＝62、写出表达式(a＋b*c)/(a＋b)－d的逆波兰表示及三元式序列。

逆波兰表示：abc*＋ab＋/d－三元式序列：①(*，b，c)②(＋，a，①)③(＋，a，b)④(/，②，③)⑤(－，④，d)3、已知文法G(S)S→a|∧|(T)T→T，S|S写出句子((a，a)，a)的规范归约过程及每一步的句柄。

句型归约规则句柄((a，a)，a)S→a a((S，a)，a)T→S S((T，a)，a)S→a a((T，S)，a)T→T，S T，S((S)，a)T→S S((T)，a)S→S(T)(T)(S，a)T→S S(T，a)S→a a(T，S)T→T，S T，S(T)S→(T)(T)S4、写一个文法，使其语言是奇数集，且每个奇数不以0开头。

解：文法G(N)：N→AB|BA→AC|DB→1|3|5|7|9D→B|2|4|6|8C→0|D5、设文法G(S)：S→(L)|a S|aL→L，S|S(1) 消除左递归和回溯；(2) 计算每个非终结符的FIRST和FOLLOW；(3) 构造预测分析表。

解：S→(L)|aS’S’→S|εL→SL’L’→SL’|εFIRST)S)＝{(，a}FOLLOW(S)＝{#，，，)}FIRST(S’)＝{，a,ε}FOLLOW(S’)＝{#，，，)}FIRST(L)＝{(，a}FOLLOW(L)＝{ )}FIRST(L’)＝{，，ε}FOLLOW(L’)＝{ }}6、While a＞0 ∨b＜0doBeginX：＝X＋1；if a＞0 then a：＝a－1else b：＝b＋1End；翻译成四元式序列。

编译原理复习《编译原理》复习README来源⽹络&书本&PPT整理截取了⽼师课上讲解or布置的题⽬⼀些题⽬懒得贴答案了，写了些注意事项第1 章引论运⾏编译程序的计算机：宿主机运⾏编译程序所产⽣的⽬标代码的计算机：⽬标机第1 题解释下列术语：（1）编译程序：如果源语⾔为⾼级语⾔，⽬标语⾔为某台计算机上的汇编语⾔或机器语⾔，则此翻译程序称为编译程序。

（2）源程序：源语⾔编写的程序称为源程序。

（3）⽬标程序：⽬标语⾔书写的程序称为⽬标程序。

（4）编译程序的前端：它由这样⼀些阶段组成：这些阶段的⼯作主要依赖于源语⾔⽽与⽬标机⽆关。

通常前端包括词法分析、语法分析、语义分析和中间代码⽣成这些阶段，某些优化⼯作也可在前端做，也包括与前端每个阶段相关的出错处理⼯作和符号表管理等⼯作。

（5）后端：指那些依赖于⽬标机⽽⼀般不依赖源语⾔，只与中间代码有关的那些阶段，即⽬标代码⽣成，以及相关出错处理和符号表操作。

（6）遍：是对源程序或其等价的中间语⾔程序从头到尾扫视并完成规定任务的过程。

第2 题⼀个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。

(区别编译程序的六个阶段)答案：⼀个典型的编译程序通常包含8 个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码⽣成程序、中间代码优化程序、⽬标代码⽣成程序、表格管理程序和错误处理程序。

其各部分的主要功能简述如下。

词法分析程序：输⼈源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。

语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。

语义分析程序：进⾏语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。

中间代码⽣成程序：按照语义规则，将语法分析程序分析出的语法单位转换成⼀定形式的中间语⾔代码，如三元式或四元式。

中间代码优化程序：为了产⽣⾼质量的⽬标代码，对中间代码进⾏等价变换处理。

一、单项选择题1．将编译程序分成若干个“遍”是为了( B )A．提高程序的执行效率B. 使程序的结构更加清晰C．利用有限的机器内存并提高机器的执行效率D．利用有限的机器内存但降低了机器的执行效率2．不可能是目标代码的是( D )A．汇编指令代码 B．可重定位指令代码C．绝对指令代码 D．中间代码3．词法分析器的输入是( B )A．单词符号串 B．源程序C．语法单位 D．目标程序4．中间代码生成时所遵循的是( C )A．语法规则 B．词法规则C．语义规则 D．等价变换规则5．编译程序是对( D )A．汇编程序的翻译 B．高级语言程序的解释执行C．机器语言的执行 D．高级语言的翻译6．词法分析应遵循( C )A．语义规则 B．语法规则C．构词规则 D．等价变换规则7．词法分析器的输出结果是( C )A．单词的种别编码 B．单词在符号表中的位置C．单词的种别编码和属性值 D．单词属性值8．正规式M1和M2等价是指( C )A．M1和M2的状态数相等 B．M1和M2的有向弧条数相等C．M1和M2所识别的语言集相等 D．M1和M2状态数和有向弧条数相等9．词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确，因此，( B ) A．词法分析器应作为独立的一遍B．词法分析器作为子程序较好C．词法分析器分解为多个过程，由语法分析器选择使用．D．词法分析器并不作为一个独立的阶段10．如果L(M1)=L(M2)，则M1与M2( A )A．等价 B．都是二义的C．都是无二义的 D．它们的状态数相等11．文法G：S→xSx|y所识别的语言是( C )A．xyx B．(xyx)* c．x n yx n(n≥0) d．x*yx*12．文法G 描述的语言L(G)是指( A )A ．⎭⎬⎫⎩⎨⎧∈⇒=+*,|)(T V S G L αααB ．⎭⎬⎫⎩⎨⎧⋃∈⇒=+*)(,|)(N T V V S G L ααα C ．⎭⎬⎫⎩⎨⎧∈⇒=**,|)(T V S G L ααα D ．⎭⎬⎫⎩⎨⎧⋃∈⇒=**)(,|)(N T V V S G L ααα 13．有限状态自动机能识别( C )A ．上下文无关文法B ．上下文有关文法C ．正规文法D ．短语文法14．如果文法G 是无二义的，则它的任何句子( A ) A ．最左推导和最右推导对应的语法树必定相同 B ．最左推导和最右推导对应的语法树可能不同 C ．最左推导和最右推导必定相同D ．可能存在两个不同的最左推导，但它们对应的语法树相同 15．由文法的开始符经0步或多步推导产生的文法符号序列是( C ) A ．短语 B ．句柄 C ．句型 D ．句子 16．文法G ：E →E+T|T T →T*P|P P →(E)|i则句型P+T+i 的句柄为( B )A ．P+TB ．PC ．P+T+iD ．i 17．文法G ：S →b|∧|(T) T →T ∨S|S 则FIRSTVT(T)=( C )A ．{ b ，∧，( }B ．{ b ，∧，) }C ．{ b ，∧，(，∨ }D ．{ b ，∧，），∨ } 18．产生正规语言的文法为( D )A ．0型B ．1型C ．2型D ．3型 19．任何算符优先文法( D )优先函数。

编译原理复习资料一、填空题.1.编译程序是一种程序，能够将某一种高级语言编写的源程序改造成另一种低级语言编写的目标程序，它们在逻辑上等价，完成相同的工作。

2.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是_二义性的__。

3.词法分析程序的功能是从左到右扫描源程序字符串，根据语言的词法规则识别出各类单词符号，并以__单词符号或单词符号表示的源程序_的形式输出。

4.编译程序一般划分为词法分析、语法分析、语义分析、中间代码生成、和代码优化目标代码生成六个阶段；除此以外,还有两个重要的基本工作,它们是表格管理和出错处理。

5.目前，语法分析方法有两大类，分别为自上向下的分析方法和__自下而上_分析方法。

自上而下的分析方法是从___文法的开始符号__出发，根据文法规则正向推导出给定句子的方法。

6.属性文法是编译技术中用来说明程序设计语言的___语义__的工具。

7.若源程序是用高级语言编写的,___目标程序__是机器语言程序或汇编程序,则其翻译程序称为 ____编译程序___。

8.扫描器（程序）的任务是从_字符串__中识别出一个个_单词符号_。

9.一个LR分析器包括三部分：总控程序、_分析表_和分析栈。

10.自顶向下的语法分析方法的基本思想是：从文法的_开始符号_出发，根据给定的输入串并按照文法的产生式一步一步的向下进行__正向推导_，试图推导出文法的给力句子__，使之与给定的输入串匹配。

11.按Chomsky分类法，文法被分成___4（0~3型文法）__类。

12.局部优化是在__基本块___范围内进行的一种优化。

13.编译程序是一种＿翻译＿程序，它将某一种高级语言编写的源程序改造成另一种低级语言编写的目标程序，源程序和目标程序在逻辑上等价，完成相同的工作。

14.编译程序与解释程序的根本区别为__解释程序在执行中不产生目标程序_。

15.语法分析的任务是识别给定的终结符号串是否为给定文法的___句子__。

编译原理学习指导与习题解析第一章：1-1选择、填空题(1)构造一个编译程序的三要素是，，。

答案：源语言、目标语言和编译方法、技术及工具(2)被编译的语言为A语言，编译的最终结果为B语言代码，编写编译程序的语言为C语言。

那么，语言是源语言，语言是宿主语言，语言是目标语言。

答案：A、C、B(3)下面对编译原理的有关概念描述正确的是。

A．目标语言只能是机器语言B．编译程序处理的对象是源语言C．Lex是语法分析自动生成器D．解释程序属于编译程序答案：c(4) 是编译程序的组成部分。

A．词法分析程序B．代码生成程序c．设备管理程序D．语法分析程序答案：C(5)下面对编译程序分为“遍”描述正确的是A．分“遍”可以使编译程序结构清晰B．可以提高程序的执行效率C．可以提高机器的执行效率D．可以增加对内存容量的要求答案：A(6)编译程序各阶段的工作都涉及到，。

A．表格管理B．语法分析C．出错处理D．代码优化答案：A、C(7)编译程序的生成方式可以是，，。

A．自编译B．高级程序设计语言编写C．完全自动生成D．汇编语言缩写答案：ABD(8)设有表达式a*b—c，将其中a*b识别为表达式的编译阶段是。

A．词法分析B．语法分析C．语义分析D．代码生成答案：B(9)设一个编译器接收的源语言A，目标语言为B，宿主语言为C，则该编译器的符号表示是。

答案：(10)下面对编译程序分“遍”应考虑的因素描述不正确的是。

A．源语言的特征和约束B．代码优化的因素C．编译程序的功能D．目标代码的选择答案：CI-2判断题(I)解释执行与编译执行的根本区别在于解释程序对源程序没有真正进行翻译。

( )答案：错(2)宿主语言是目标机的目标语言。

( )答案：错(3)具有优化功能的编译器可以组织为一遍扫描的编译器。

( )答案：错(4)编译程序是将用某一种程序设计语言编写的源程序翻译成等价的另一种语言程序(目标程序。

( )答案：错(5)编译程序是应用软件。

《编译原理》总复习-07级第一章编译程序的概述（一）内容本章介绍编译程序在计算机科学中的地位和作用，介绍编译技术的发展历史，讲解编译程序、解释程序的基本概念，概述编译过程，介绍编译程序的逻辑结构和编译程序的组织形式等。

（二）本章重点编译（程序），解释（程序），编译程序的逻辑结构。

（三）本章难点编译程序的生成。

（四）本章考点全部基本概念。

编译程序的逻辑结构。

（五）学习指导引论部分主要是解释什么是编译程序以及编译的总体过程。

因此学习时要对以下几个点进行重点学习：翻译、编译、目标语言和源语言这几个概念的理解；编译的总体过程：词法分析，语法分析、语义分析与中间代码的生成、代码优化、目标代码的生成，以及伴随着整个过程的表格管理与出错处理。

第三章文法和语言课外训练（一）内容本章是编译原理课程的理论基础，主要介绍与课程相关的形式语言的基本概念，包括符号串的基本概念和术语、文法和语言的形式定义、推导与归约、句子和句型、语法分析树和二义性文法等定义、文法和语言的Chomsky分类。

（二）本章重点上下文无关文法，推导，句子和句型，文法生成的语言，语法分析树和二义性文法。

（三）本章难点上下文无关文法，语法分析树，文法的分类。

（四）本章考点上下文无关文法的定义。

符号串的推导。

语法分析树的构造。

（五）学习指导要构造编译程序，就要把源语言用某种方式进行定义和描述。

学习高级语言的语法描述是学习编译原理的基础。

上下文无关文法及语法树是本章学习的重点。

语法与语义的概念；程序的在逻辑上的层次结构；文法的定义，文法是一个四元组：终结符号集，非终结符号集，开始符号、产生式集；与文法相关的概念，字符，正则闭包，积（连接），或，空集，产生式，推导，直接推导，句子，句型，语言，最左推导，最右推导（规范推导）；学会用文法来描述语言及通过文法能分析该文法所描述的语言；语法树及二义性的概念、能通过画语法树来分析一个文法描述的语言是否具有二义性；上下文无关文法的定义和正规文法的定义，能判断一个语言的文法是哪一类文法。

编译原理复习例题(有些内容没有覆盖，比如优化、SLR（1）、LR（1）、LALR（1）等。

但要求至少要按照作业题的范围复习。

)一选择题1．编译的各阶段工作都涉及。

[A]词法分析[B]表格管理 [C]语法分析 [D]语义分析2．型文法也称为正规文法。

[A] 0 [B] 1 [C] 2 [D] 33．文法不是LL(1)的。

[A]递归 [B]右递归 [C]2型 [D]含有公共左因子的4．文法E→E+E|E*E|i的句子i*i+i*i有棵不同的语法树。

[A] 1 [B] 3 [C] 5 [D] 75．文法 S→aaS|abc 定义的语言是。

[A]{a2k bc|k>0} [B]{a k bc|k>0}[C]{a2k-1bc|k>0} [D]{a k a k bc|k>0}6．若B为非终结符，则 A→α.Bβ为。

[A]移进项目 [B]归约项目 [C]接受项目 [D]待约项目7．同心集合并可能会产生新的冲突。

[A]二义 [B]移进/移进 [C]移进/归约 [D]归约/归约8．代码优化时所依据的是。

[A]语法规则 [B]词法规则[C]等价变换规则 [D]语义规则9．表达式a-(-b)*c的逆波兰表示（@为单目减）为。

[A]a-b@c* [B]ab@c*- [C]ab@- [D]ab@c-*10．过程的DISPLAY表是用于存取过程的。

[A]非局部变量[B]嵌套层次 [C]返回地址 [D]入口地址二填空题1．词法分析阶段的任务式从左到右扫描字符流，从而逐个识别一个个的单词。

2．对于文法G[E]：E→T|E+T T→F|T*F F→P^F|P P→(E)|i，句型T+T*F+i的句柄是。

3．最右推导的逆过程称为规范归约，也称为最左归约。

4．符号表的每一项是由名字栏和两个栏目组成。

在目标代码生成阶段，符号表是的依据。

三判断题（认为正确的填“T”，错的填“F”）【】1．同心集的合并有可能产生“归约/归约”冲突。