下载文档原格式
一、简答题（每题4分，共24分）1、构造一个文法G，使得：L(G)={(m )m|m>0}解答：G[S]: s-> ()|(S)2、构造一个正规式，它接受 ={0，1}上符合以下规则的字符串：串内有且只有2个1的0、1字符串全体。
解答：0*10*10*3、消除文法G[S]中的直接左递归和回溯S→(L) | aS | aL→L，S | S解答：S→(L) | aS'S'→S | εL→S L'L'→，S L' | ε4、文法G[S]是乔姆斯基几型文法？S → ABS | ABAB → BAA → 0B → 1解答：1型文法/上下文有关文法5、按Thmopson算法构造与正则表达式(1*|0) * 等价的NFA。
解答：略6、设计一个状态转换图，其描述的语言规则为：如果以a开头，则其后是由a、b组成的任意符号串；如果以b开头，则其后是至少包含一个a的由a、b组成的任意符号串。
解答：略二、（本题10分）对于文法G[E]：E→ET+|TT→TF* | FF→F^ | a(1) 给出句子FF^^*的最左推导和语法树；(2) 给出句子FF^^*的短语、直接短语和句柄。
解答： (1) 2分：句子FF^^*的最左推导 2分：句子FF^^*的语法树E=>T=>TF*=>FF*=>FF^*=>FF^^*(2) 3分:句子FF^^*的短语FF^^*、FF^^*、F、F^、F^^2分:句子FF^^*的直接短语F、F^1分:句子FF^^*的句柄F三、（本题15分）构造与下列NFA等价的最小化DFA。
解答：（1）10分：构造与NFA等价的DFA（2）5分：对DFA最小化首先，将所有的状态集合分成子集： k1={0,1,2,4} k2={3,5}四、（本题15分）对下列文法G[S]：s→ eT | RTT→ DR | εR→ dR | εD→ a | bd(1) 写出文法G[S]每个非终结符的FIRST集和FOLLOW集；(2) 判断文法G[S]是否LL(1)文法（注：必须给出判断过程，否则不得分）；(3) 写出文法文法G[S]的预测分析表。
编译原理复习题及答案一、选择题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．(A)是一种典型的解释型语言。
A．BASIC B．C C．FORTRAN D．PASCAL12．把汇编语言程序翻译成机器可执行的目标程序的工作是由(B)完成的。
A. 编译器B. 汇编器C. 解释器D. 预处理器13．用高级语言编写的程序经编译后产生的程序叫(B)A．源程序 B．目标程序C．连接程序D．解释程序14．(C)不是编译程序的组成部分。
A.词法分析程序B.代码生成程序C.设备管理程序D.语法分析程序15．通常一个编译程序中，不仅包含词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成等六个部分，还应包括(C)。
A．模拟执行器B．解释器 C．表格处理和出错处理D．符号执行器16．编译程序绝大多数时间花在(D)上。
编译原理试卷参考答案练习题1-01.编译程序的工作过程一般可以划分为_ __等几个基本阶段,同时还会伴有_ __和 .1-02.若源程序是用高级语言编写的,目标程序是__ __,则其翻译程序称为编译程序.1-03.编译方式与解释方式的根本区别在于_ _.1-04.翻译程序是这样一种程序,它能够将__ ___转换成与其等价的__ __.1-05.对编译程序而言,输入数据是__ __,输出结果是 __ __.1-06.如果编译程序生成的目标程序是机器代码程序,则源程序的执行分为两大阶段:_ __和__ __.如果编译程序生成的目标程序是汇编语言程序,则源程序的执行分为三个阶段: _ __,_ ___和_ __ .1-07.一个典型的编译程序中，不仅包括_ __等五个部分，还应包括_ __和_ __。
其中，词法分析器用于识别_ __。
1-08.如果编译程序生成的目标程序是汇编语言程序，则源程序的执行分为三个阶段: _ ，汇编阶段和运行阶段。
1-09.编译方式与解释方式的根本区别为是否 _ 。
2-01.所谓最右推导是指：。
2-02.一个上下文无关文法所含四个组成部分是。
2-03.产生式是用于定义的一种书写规则。
2-04.设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为：。
2-05.设G是一个给定的文法，S是文法的开始符号，如果S x（其中x∈V*），则称x是文法的一个。
2-06.设G是一个给定的文法，S 是文法的开始符号，如果S x(其中x∈V T*),则称x是文法的一个。
3-01.扫描器的任务是从源程序中识别出一个个。
4-01.语法分析最常用的两类方法是_ __和_ __分析法。
4-02.语法分析的任务是识别给定的终极符串是否为给定文法的_。
4-03.递归下降法不允许任一非终极符是直接 _递归的。
4-04.自顶向下的语法分析方法的关键是 _ 的问题。
4-05.递归下降分析法是自 _ 分析方法。
<编译原理>历年试题及答案一．（每项选择2分，共20分）选择题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．正规式MI和M2等价是指____。
a. MI和M2的状态数相等b.Ml和M2的有向弧条数相等。
C.M1和M2所识别的语言集相等 d. Ml和M2状态数和有向弧条数相等7．中间代码生成时所依据的是—。
a．语法规则 b．词法规则 c．语义规则 d．等价变换规则8．后缀式ab+cd+/可用表达式___来表示。
a．a+b/c+d b．(a+b)/(c+d) c．a+b/(c+d) d．a+b+c/d9．程序所需的数据空间在程序运行前就可确定，称为_____＿管理技术。
a.动态存储b.栈式存储c.静态存储d.堆式存储10.堆式动态分配申请和释放存储空间遵守_______＿原则。
a.先请先放b.先请后放c.后请先放d.任意二（每小题10分，共80分）简答题1.画出编译程序的总体结构图，简述各部分的主要功能。
2. 已知文法G[E]:E→ET+|T T→TF* | F F→F^ | a试证：FF^^*是文法的句型，指出该句型的短语、简单短语和句柄.3．为正规式(a|b) *a(a|b)构造一个确定的有限自动机。
4．设文法G(S)：S→(L)|a S|aL→L，S|S(1) 消除左递归和回溯；(2) 计算每个非终结符的FIRST和FOLLOW；(3) 构造预测分析表。
编译原理(第三版)答案《编译原理（第三版）》答案概念：1.编译器是一种程序，它把某种语言写的源程序翻译成另一种语言写的目标程序。
2.编译器的编写是一项复杂而耗时的任务，因为它必须处理语法和语义分析等复杂的编程语言概念。
3.编译器通常分为六个主要阶段：词法分析、语法分析、语义分析、中间代码生成、代码优化、代码生成。
4.词法分析是将源代码转换为令牌序列的过程，这些令牌构成了源代码的抽象语法树（AST）的节点。
5.语法分析是将令牌序列转换为抽象语法树的过程，这个抽象语法树表示了源代码的结构。
6.语义分析是检查源代码是否符合语言的规则，并收集类型信息的过程。
7.中间代码生成是将抽象语法树转换为中间代码的过程，这个中间代码可以在进行进一步优化和代码生成时更容易处理。
8.代码优化是优化中间代码以改进目标代码性能的过程。
9.代码生成是将中间代码转换为目标代码的过程。
10.编译器通常使用特定的数据结构和算法来处理编译的不同阶段，例如优先级队列用于语法分析，哈希表用于语义分析等。
习题答案：1.什么是编译器？它的主要功能是什么？编译器是一种程序，它把某种编程语言写的源程序翻译成另一种编程语言写的目标程序。
主要功能包括词法分析、语法分析、语义分析、中间代码生成、代码优化和代码生成。
2.编译器的基本组成部分是什么？编译器的基本组成部分包括词法分析器、语法分析器、语义分析器、中间代码生成器、优化器和代码生成器。
3.什么是编译器的中间表示？它有哪些形式？编译器的中间表示是编译器在源代码和目标代码之间的一个抽象级别，也被称作中间代码。
它可以是三地址码、抽象语法树或其他形式。
其中三地址码是最常见的中间表示形式之一，它是一种易于理解和处理的中间语言。
4.编译器的优化主要有哪些类型？编译器的优化主要可以分为两种类型：存储优化和执行效率优化。
存储优化主要关注如何减少目标代码的存储空间，而执行效率优化则关注如何提高目标代码的执行效率。
编译原理试题计算机学院2001级班学号姓名一选择题（12分）【】1．词法分析器的输入是。
A．符号串B．源程序C．语法单位D．目标程序【】2．两个有穷自动机等价是指它们的。
A．状态数相等B．有向弧数相等C．所识别的语言相等D．状态数和有向弧数相等【】3．文法G：S → xSx | y 所识别的语言是。
A．xy*x B．(xyx)* C．xx*yxx* D．x*yx*【】4．设a,b,c为文法的终结符，且有优先关系a≡b和b≡c，则。
A．必有a≡c B．必有c≡aC．必有b≡a D．选项A、B和C都不一定成立【】5．若状态k含有项目“A→α.”，且仅当输入符号a∈FOLLOW(A)时，才用规则“A →α”归约的语法分析方法是。
A．ALR分析法B．LR(0)分析法C．LR(1)分析法D．SLR(1)分析法【】6．生成中间代码时所依据的是。
A．语法规则B．词法规则C．语义规则D．等价变换规则【】7．表达式（┐a∨b）∧（c∨d）的逆波兰表示为。
A．┐ab∨∧cd∨B．a┐b∨cd∨∧C．ab∨┐cd∨∧D．a┐b∨∧cd∨【】8．基本块。
A．只有一个入口语句和一个出口语句B．有一个入口语句和多个出口语句C．有多个入口语句和一个出口语句D．有多个入口语句和多个出口语句二判断题（6分。
认为正确的填“T”，错的填“F”）【T】1．同心集的合并有可能产生“归约/归约”冲突。
【T】2．一个文法所有句子的集合构成该文法定义的语言。
【】3．非终结符可以有综合属性，但不能有继承属性。
【T】4．逆波兰表示法表示表达式时无需使用括号。
【】5．一个有穷自动机有且只有一个终态。
【】6．若过程p第k次被调用，则p的DISPLAY表中就有k+1个元素。
三填空题（8分）1．最常用的两类语法分析方法是自顶向下和自低向上分析法。
2．对于文法G[E]：E→T|E+T T→F|T*F F→P↑F|P P→(E)|i,句型T+T*F+i 的直接短语为，句柄为。
试卷（三）： 一、 选择 1.下面说法正确的是：A A 一个正规文法也一定是二型文法 B 一个二型文法也一定能有一个等价的正规文法
2.文法G[A]：A→b A→AB B→Ab B→a是( A )： A 二型文法 B 正规文法
3.下面说法正确的是( B )： A lex是一个词法分析器 B yacc是一个语法分析器的生成器
4.一个LR（1）文法合并同心集后,如果不是LALR(1)文法必定存在( B )： A 移进--归约冲突 B 归约--归约冲突
5 PL/0语言编译程序使用递归子程序法进行语法分析，他的文法必须满足(A )： A LL（1）文法 B SLR(1) 文法
二、 问答题 问答第1题 （6分）试对 repeat x:=b until b>a or (b令地址，并指出真假出口链和链头及回填的次序。 应回填的值 回填的次序 真链头 E.true= (1) x:= b 真出口链( ) (2) if b>a goto ( ) ( ) 真出口链( ) (3) goto ( ) ( ) (4) if b(5) goto ( ) ( ) 假出口链( ) (6) if b=d goto ( ) ( ) (7) goto ( ) ( ) (8) ... 解： 应回填的值 回填的次序 真链头 E.true= 6 (1) x:= b (2) if b>a goto ( 8 ) ( 6 ) 真出口链( 6,2 ) (3) goto ( 4 ) ( 1 ) (4) if b(5) goto ( 1 ) ( 4 ) 假出口链( 7,5 ) (6) if b=d goto ( 8 ) ( 5 ) (7) goto ( 1 ) ( 3 ) 问答第2题 (10分)某语言的拓广文法G′为： (0) S′→S (1) S → Db|B (2) D → d|ε (3) B → Ba|ε 证明G不是LR(0)文法而是SLR(1)文法，请给出SLR(1)分析表。 解： 拓广文法G'，增加产生式S'→S 在项目集I0中： 有移进项目D →·d 归约项目D →·和B →· 存在移进-归约和归约-归约冲突，所以G不是LR(0)文法。 若产生式排序为： (0) S'→S (1) S → Db (2) S → B (3) D → d (4) D →ε (5) B → Ba (6) B →ε
G′的LR(0)项目集族及识别活前缀的DFA如下图： 识别G′活前缀的DFA 由产生式知： Follow(S)={#} Follow(D)= {b} Follow(B)= {a ,#} 在I0中: Follow(D) ∩{d}={ b} ∩{d}= Follow(B) ∩{d}= { a ,#} ∩{d}= Follow(D) ∩ Follow(B)= {b}∩{a ,#} = 在I3中: Follow(S) ∩{a}={#}∩{a}= 所以在I0，I3中的移进-归约和归约-归约冲突可以由Follow集解决,所以G是SLR(1)文法, 构造的SLR(1)分析表如下表。 SLR(1)分析表
问答第3题 (5分)给出文法G[S]的LR(1)项目集规范族中I0项目集的全体项目。 G[S]为： S →S;V|V V →VaA|A A →b(S)| ε I0: 解：I0: 问答第4题 (5分)文法G[M]及其LR分析表如下，请给出对串dada#的分析过程。 G[M]: 1) S →VdB 2) V →e 3) V →ε 4) B →a 5) B →Bda 6) B →ε
解：对串dada#的分析过程如下表 对输入串dada#的分析过程
步骤 状态栈 文法符号栈 剩余输入符号 动作 1 2 3 4 5 6 0 02 024 0245 0246 02467 # #V #Vd #Vda #VdB #VdBd dada# dada# ada# da# da# a# 用V →ε归约 移进 移进 用B →a归约 移进 移进 7 8 9 024678 0246 01 #VdBda #VdB #S # # # 用B →Bda归约 用S →VdB归约 接受
问答第5题 (7分)(1) 给出下列PL/0示意程序中当程序执行到D过程调用A过程后（即执行A过程体时）的栈式存储分配布局和用Display显示表时A过程最新活动记录的内容。 (2) 说明Display表和全局Display的作用。 PL/0示意程序为： var x; procedure A; var d; begin (* A *) write(x); end (* A *); procedure B; const n=7; var e,g; procedure D; var j,k; begin (* D *) read(j,k); x:=x+j*n; call A; end ;(* D *) begin (* B *) call D; end ;(* B *) begin (* main *) read(x); call B; end. (* main *) 解：（1）PL/0示意程序中当程序执行到D过程调用A过程后（即执行A过程体时）的栈式存储分配布局和用Display显示表时栈中过程最新活动记录的内容如下图。 栈式存储分配布局和栈中过程最新活动记录的内容 （2）Display表和全局Display的作用是： ·Display表的作用是对嵌套过程语言实现对非局部变量的引用而设置的，它依次存放着包围它的外过程的最新活动记录的基地址SP值，由于，嵌套层次为i+1过程中的非局部变量可能在i，i-1，…，0层，所以，对非局部变量的引用是通过它的Display表元素d[i]，d[i-1]，…，d[0]而获得包围它的外过程的最新活动记录的基地址SP值，再加上变量在该过程（第i层）的偏移量。如若非局部变量a是在第i层，那么引用a时，首先从当前栈顶过程的Display表中元素d[i]中取出存放的第i层最新活动记录基地址sp值，然后加上a所在过程（第i层）的偏移量，就得到a的存放地址。 ·全局Display是存放本过程Display表的起始地址，其作用是把Display地址作为连接数据之一，如过程P1调用过程P2时，这时先从P1的全局Display找到P1的Display表起始地址，然后从P1的Display表中自底向上地抄录I2个单元（I2为P2的层数）再添上进入P2后新建立的P2的sp值，就构成了P2的Display表。
问答第6题 (5分)给出问答第5题PL/0示意程序编译到D过程体时TABLE表的内容。其中TABLE表的格式可为下表。 TABLE表的格式： name kind level val adr size
解：问答第5题PL/0示意程序编译到D过程体时TABLE表的内容如下表。 TABLE表的内容 由于A和B是并列过程，当编译到B过程时A过程体已经编译结束，A所定义的标识符不会再被使用，所以由B过程定义的标识符覆盖。
问答第7题 （6分）按指定类型给出下列语言的文法。 (1) L1={ candbm| n≥0,m>0 } 用正规文法。 (2) L2={ 0na 1nbmcm| n>0，m ≥0} 用二型文法
（1）解：描述L1语言的正规文法如下： S→cA A→aA|B B→dD D→bD|ε （2）解：描述L2语言的二型文法如下： S→AB A→0A1|0a1 B→bBc|ε
问答第8题 （5分）文法G[S]为： S→SdT | T T→TG→(S) | a 试给出句型(SdG)解：句型(SdG)短语：(SdG)简单(直接)短语：G 、a 句柄：G 最左素短语：SdG
问答第9题 （5分） 给出与正规式 R＝（aba）*（(ba)*|b）b等价的NFA。 问答第10题 (6分)将下图的NFA确定化为DFA。
解：用子集法确定化如下表 I Ia Ib 状态 {X,0,1,3} {0,1,3} {2,3,Y} {1,3} {2,Y} {Y} {0,1,3} {0,1,3} {1,3} {1,3} {2,3,Y} {2,3,Y} {Y} {2,Y} {Y} X 1 2 3 4 Y 确定化后如下图
问答第11题 (5分)将文法G[S] 改写为等价的G'[S]，使G'[S]不含左递归和左公共因子。 G[S]： S→[A A→B]|AS B→aB|a 解：文法G[S] 改写为等价的不含左递归和左公共因子的G'[S]为： S →[A A →B]A′ A′→SA′|ε B →aB′ B′→B|ε
问答第12题 (10分) 判断下面文法是否为LL(1)文法，若是，请构造相应的LL(1)分析表。 S→aD D→STe|ε T→bM M→bH
