编译原理习题集

第二章2 •构造产生下列语言的文法(2){a n b m c p|n/m,p^O}解：G(S) : S—aS|X,X—bX|Y,Y—cY| £(3){a n it b n|n^O}U {c n#dn|n 刁0}解：G(S)： S—X,S—Y z X->aXb |#, Y~>cYd |it}(5)任何不是以0打头的所有奇整数所组成的集合解：G(S)： S—J|IBJ,B—0B|IB| £ J—J|2|4|6|8」f 1|3|5|7|9}(6)(思考题)所有偶数个0和偶数个1所组成的符号串集合解：对应文法为S^OA|1B| £ , A->OS|1C B—0CI1S C^1A|OB3.描述语言特点(2) STS STAO ATAO A—£解：L(G)={l nl O nl l n2O n2…l nm0nm |nl,n2/—,nm^0：且nl’n乙—nm 不全为零}该语言特点是：产生的句子中，0、1个数相同，并且若干相接的1后必然紧接数量相同连续的0。

(5) S—aSS S—a解：L(G)={a(2")|n$l}可知：奇数个 a5.(1)解：由于此文法包含以下规则：AA->£ ,所以此文法是0型文法。

7 •解:(l)aacb是文法G⑸中的句子，相应语法树是:最右推导：S=>aAcB=>aAcb=>aacb最左推导：S=>aAcB=>aacB=>aacb(3)aacbccb 不是文法G ⑸中的句子aacbccb 不能从S 推导得到时，它仅是文法G ⑸的一个句型的一部分，而不是一个句子。

.解：最右推导：(1) S=>AB=>AaSb=>Aacb=>bAacb=>bbAacb=>bbaacb上面推导可下划褒部芬为当前砲的句麻对应的语法树为：第三章3假设M:人W:载狐狸过河，G:载山羊过河，C:载口菜过河人.犯.羊、白菜：{{M. G、C?, {”丧朮在方消仃{{}• {M.氐C. C"在右坤.将川舵存在的状态加爪安全农态• fl K：({M. T. G. C}. 0).⑴.<M.・ G. Q)・⑴、W. G》・(C}}. {{M, BL C> •⑹八{{ML G、Clr {V}} p UC}r恥叭G” ・{{G；U M 叭C}}, m f M G. C}}r{{M. G},他C}} , (IF, 0, (M. GD笛弧I：的标记符:<M>;氐斥人单独过河、<MC>；农示人和羊过河.5T九浪示人和狠过河、Q【C>；我示人和白菜过河KM.莎、G. C}r {}•・--------------- {測C}r {JL G}}7 职 Ch {G}}{{G}, M 叭C}}<MG> MG>心M叭G、c》6根据文法知其产生的语言是L={a m b n c i| m,n,iMl}可以构造如下的文法VN={S,A,B,C}/ VT={a,b,c}P={ S f aA, A-*aA, A—bB, B~^bB, B—cC, C-^cC, C—c}其状态转换图如下：7(1)其对应的右线性文法是：A f OD,B —OA,B —lC’C—l|OA,Ff O|OE|lAQf OB|lC,Ef 1C|OB ⑵最短输入串Oil⑶任意接受的四个审:011,0110,0011,000011 ⑷任意以1打头的串・9.对于矩阵(iii)⑵3型文法(正规文法)S-^aAla | bB A —bA| b|aC|aB —aB| bC| bC —aC|a | bC|b(3)用自然语言描述输入串的特征以a 打头，中间有任意个(包括0个)b,再跟°最后由一个a,b 所组成的任 意串结尾或者以b 打头，中间有任意个(包括0个)①再跟b,最后曲一个a,b 所组 成的任意吊结尾。

编译原理试题及答案一、选择题1. 编译器的主要功能是什么？A. 程序设计B. 程序翻译C. 程序调试D. 数据处理答案：B2. 下列哪一项不是编译器的前端处理过程？A. 词法分析B. 语法分析C. 语义分析D. 代码生成答案：D3. 在编译原理中，词法分析器的主要作用是什么？A. 识别程序中的关键字和标识符B. 将源代码转换为中间代码C. 检查程序的语法结构D. 确定程序的运行环境答案：A4. 语法分析通常采用哪种方法？A. 自顶向下分析B. 自底向上分析C. 正则表达式匹配D. 直接解释执行答案：B5. 语义分析的主要任务是什么？A. 检查程序的语法结构B. 检查程序的类型安全C. 识别程序中的变量和常量D. 将源代码转换为机器代码答案：B二、简答题1. 简述编译器的工作原理。

答案：编译器的工作原理主要包括以下几个步骤：词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成。

词法分析器将源代码分解成一系列的词素；语法分析器根据语法规则检查词素序列是否合法；语义分析器检查程序的语义正确性；中间代码生成器将源代码转换为中间代码；代码优化器对中间代码进行优化；最后，目标代码生成器将优化后的中间代码转换为目标机器代码。

2. 什么是词法分析器，它在编译过程中的作用是什么？答案：词法分析器是编译器前端的一个组成部分，负责将源代码分解成一个个的词素（tokens），如关键字、标识符、常量、运算符等。

它在编译过程中的作用是为语法分析器提供输入，是编译过程的基础。

三、论述题1. 论述编译器中的代码优化技术及其重要性。

答案：代码优化是编译过程中的一个重要环节，它旨在提高程序的执行效率，减少资源消耗。

常见的代码优化技术包括：常量折叠、死代码消除、公共子表达式消除、循环不变代码外提、数组边界检查消除等。

代码优化的重要性在于，它可以显著提高程序的运行速度和性能，同时降低程序对内存和处理器资源的需求。

四、计算题1. 给定一个简单的四则运算表达式，请写出其对应的逆波兰表达式。

第一章1、将编译程序分成若干个“遍”就是为了。

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

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

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

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

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

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

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

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

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

a．语义规则b．语法规则c．构词规则d．等价变换规则二、多项选择题1、编译程序各阶段得工作都涉及到。

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

a．词法分析b．语法分析c．中间代码生成d．语义检查e．目标代码生成三、填空题1、解释程序与编译程序得区别在于。

2、编译过程通常可分为5个阶段，分别就是、语法分析、代码优化与目标代码生成。

3、编译程序工作过程中，第一段输入就是，最后阶段得输出为程序。

4、编译程序就是指将程序翻译成程序得程序。

单选解答1、将编译程序分成若干个“遍”就是为了使编译程序得结构更加清晰，故选b。

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

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

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

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

编译原理练习题一、选择题（每题2分，共10分）1. 编译器的主要功能是将源代码转换为：A. 可执行文件B. 汇编代码C. 机器代码D. 中间代码2. 词法分析阶段的主要任务是：A. 将源代码分解成多个语句B. 将源代码分解成多个单词C. 将源代码分解成多个符号D. 将源代码分解成多个表达式3. 下列哪个是自顶向下的语法分析方法？A. LL(1)分析B. LR分析C. LALR分析D. GLR分析4. 语义分析的主要任务是：A. 检查语法正确性B. 检查类型正确性C. 检查代码风格D. 检查代码的可读性5. 编译过程中的优化主要发生在：A. 词法分析阶段B. 语法分析阶段C. 语义分析阶段D. 代码生成阶段二、填空题（每空1分，共10分）6. 编译器的前端主要包括词法分析、语法分析、________和________四个阶段。

7. 编译器的后端主要包括代码生成、________和________两个阶段。

8. 编译原理中的“三地址代码”是指每个指令最多有三个________。

9. 编译过程中的“死代码”是指________。

10. 编译器的优化技术可以分为________优化和________优化。

三、计算题（每题5分，共10分）11. 假设有一个简单的算术表达式：a * b + c * d。

请使用三地址代码表示这个表达式，并给出相应的指令序列。

四、简答题（每题5分，共10分）12. 简述编译原理中词法分析器的作用和实现方法。

五、论述题（每题15分，共15分）13. 论述编译原理中语法分析的两种主要方法：自顶向下分析和自底向上分析，并比较它们的优缺点。

第一章练习题（绪论）一、选择题1．编译程序是一种常用的B软件。

A) 应用B) 系统C) 实时系统D) 分布式系统2．编译程序生成的目标代码程序 B 是可执行程序。

A) 一定B) 不一定3．编译程序的大多数时间是花在 D 上。

A) 词法分析B) 语法分析C) 出错处理D) 表格管理4．将编译程序分成若干“遍”将 B 。

A)提高编译程序的执行效率；B)使编译程序的结构更加清晰，提高目标程序质量；C)充分利用内存空间，提高机器的执行效率。

5．编译程序各个阶段都涉及到的工作有 D 。

A) 词法分析B) 语法分析C) 语义分析D) 表格管理6．词法分析的主要功能是 C 。

A) 识别字符串B) 识别语句C) 识别单词D) 识别标识符7．若某程序设计语言允许标识符先使用后说明，则其编译程序就必须A 。

A) 多遍扫描B) 一遍扫描8．编译方式与解释方式的根本区别在于 B 。

A) 执行速度的快慢B) 是否生成目标代码C) 是否语义分析9．多遍编译与一遍编译的主要区别在于D。

A)多遍编译是编译的五大部分重复多遍执行，而一遍编译是五大部分只执行一遍；B)一遍编译是对源程序分析一遍就立即执行，而多遍编译是对源程序重复多遍分析再执行；C)多遍编译要生成目标代码才执行，而一遍编译不生成目标代码直接分析执行；D)多遍编译是五大部分依次独立完成，一遍编译是五大部分交叉调用执行完成。

10．编译程序分成“前端”和“后端”的好处是 DA)便于移植B)便于功能的扩充C)便于减少工作量D)以上均正确第二章练习题（文法与语言）1、直接推导、＋推导、＊推导2、句型和句子, 文法定义（搞清楚）G＝（VT，VN，S，P）3、语言的形式定义: L(G[S])＝｛x | S -> x 且x∈VT*｝若L是无穷的，则G一定是递归的4、最左推导、最右推导（规范推导）5、归约、规范归约6、递归：规则递归、文法递归(1) A->BA,B->CA,…(2) A->B,B->CA,…7、文法的等价性：G1＝G28.（1）每棵子树的叶子组成一个短语；（2）每棵简单子树的叶子组成一个直接短语；简单子树：只有单层分支的子树（3）最左边简单子树的叶子是句柄一个句型不一定只对应一棵唯一的语法树。

《编译原理》复习题集1．名词解释短语句柄文法上下文无关文法LL（1）文法LR（1）文法语法分析无环路有向图(DAG)后缀式语法制导翻译遍局部优化词法分析语法分析语义分析源语言源程序目标语言中间语言（中间表示）2．简答题(1)编译程序和高级语言有什么区别?(2)编译程序的工作分为那几个阶段?(3)简述自下而上的分析方法。

(4)目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？(5)何谓优化？按所涉及的程序范围可分为哪几级优化？(6)简述代码优化的目的和意义。

3．叙述下面的正规式描述的语言，并画出接受该语言的最简DFA的状态转换图。

( 1 | 01 )* 0*4．Pascal语言无符号数的正规定义如下：num→digit+ (.digit+)? (E(+|-)? digit+)?其中digit表示数字，用状态转换图表示接受无符号数的确定有限自动机。

5．画出Pascal中实数(不带正负号，可带指数部分)的状态转换图。

6．用状态转换图表示接收(a|b)*aa的确定的有限自动机。

7．处于/* 和 */之间的串构成注解，注解中间没有*/。

画出接受这种注解的DFA的状态转换图。

8．某操作系统下合法的文件名为device:name.extension其中第一部分（device:）和第三部分（.extension）可缺省，device, name和extension都是字母串，长度不限，但至少为1，画出识别这种文件名的确定有限自动机。

9．构造一个DFA，它接受∑={0, 1}上0和1的个数都是偶数的字符串。

10．设有非确定的有自限动机 NFA M=({A，B，C}，{0，1}，δ，{A}，{C})，其中：δ(A，0)={C} δ (A，1)={A，B} δ (B，1)={C} δ (C，1)={C}。

请画出状态转换距阵和状态转换图。

11．设L⊆ {a,b,c}* 是满足下述条件的符号串构成的语言：(1)若出现a ，则其后至少紧跟两个c ；(2)若出现b ，其后至少紧跟一个c 。

第一章1、将编译程序分成若干个“遍”是为了。

b．使程序的结构更加清晰2、构造编译程序应掌握。

a．源程序b．目标语言c．编译方法3、变量应当。

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

d．管理表格5、不可能是目标代码。

d．中间代码6、使用可以定义一个程序的意义。

a．语义规则7、词法分析器的输入是。

b．源程序8、中间代码生成时所遵循的是- 。

c．语义规则9、编译程序是对。

d．高级语言的翻译10、语法分析应遵循。

c．构词规则二、多项选择题1、编译程序各阶段的工作都涉及到。

b．表格管理c．出错处理2、编译程序工作时，通常有阶段。

a．词法分析b．语法分析c．中间代码生成e．目标代码生成三、填空题1、解释程序和编译程序的区别在于是否生成目标程序。

2、编译过程通常可分为5个阶段，分别是词法分析、语法分析中间代码生成、代码优化和目标代码生成。

3、编译程序工作过程中，第一段输入是源程序，最后阶段的输出为标代码生成程序。

4、编译程序是指将源程序程序翻译成目标语言程序的程序。

一、单项选择题1、文法G：S→xSx|y所识别的语言是。

a. xyxb. (xyx)*c.x n yx n(n≥0) d. x*yx*2、文法G描述的语言L(G)是指。

a. L(G)={α|S+⇒α , α∈V T*}b. L(G)={α|S*⇒α, α∈V T*}c. L(G)={α|S*⇒α,α∈(V T∪V N*)} d. L(G)={α|S+⇒α, α∈(V T∪V N*)}3、有限状态自动机能识别。

a. 上下文无关文法b. 上下文有关文法c.正规文法d. 短语文法4、设G为算符优先文法，G 的任意终结符对a、b有以下关系成立。

a. 若f(a)>g(b)，则a>bb.若f(a)<g(b)，则a<bc. a~b都不一定成立d. a~b一定成立5、如果文法G是无二义的，则它的任何句子α。

a. 最左推导和最右推导对应的语法树必定相同b. 最左推导和最右推导对应的语法树可能不同c. 最左推导和最右推导必定相同d. 可能存在两个不同的最左推导，但它们对应的语法树相同6、由文法的开始符经0步或多步推导产生的文法符号序列是。

编译原理》习题（一）——词法分析一、 是非题（请在括号内，正确的划 V,错误的划X ） 1•编译程序是对高级语言程序的解释执行。

（X 2.一个有限状态自动机中，有且仅有一个唯一的终态。

（X ） 9.两个正规集相等的必要条件是他们对应的正规式等价。

（X ） 二、 选择题 1 .词法分析器的输出结果是 A . （ ） 记号 C . （ ） 记号和属性二元组 2. 正规式 A . （ ） M1 C . （ ） M13. 语言是A •句子的集合B .C .符号串的集合D . 4. 编译程序前三个阶段完成的工作是 A •词法分析、语法分析和代码优化 B •代码生成、代码优化和词法分析 C .词法分析、语法分析、语义分析和中间代码生成 D •词法分析、语法分析和代码优化 5．扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法 单位即 A ． 字符 6．构造编译程序应掌握 A ． （ ） 源程序 C ．（ ） 编译方法 7．词法分析的任务是 A ．识别单词C .识别句子 。

B ．（ ） 相应条目在符号表中的位置D ． （ ） 属性值 M 1 和 M 2 等价是指 __ 和 M2 的状态数相等 和 M2 所识别的语言集相等 B . （ ） M1和M2的有向边条数相等 D ．（ ） M1 和 M2 状态数和有向边条数相等 产生式的集合 句型的集合 B .单词 C .句子 D .句型 oB ． （ ） 目标语言 D ． （ ） 以上三项都是 B .分析句子的含义 D .生成目标代码 三、填空题 1 ．计算机执行用高级语言编写的程序主要有两种途径： ，（语法分析） ，（语义分析与中间代码生成 3.编译过程可分为 （ 词法分析） 和（目标代码生成 ）五个阶段。

解释__和__编译___。

），（优化） 6.扫描器的任务是从（ 源程序中 17. 一张转换图只包含有限个状态 （终 ）态。

1．编译程序首先要识别出源程序中每个 （单词），然后再分析每个 （句子）并翻译其意义。