编译原理试题整理
考试题型：简答（4道）、计算（4道）、综合（3道）
一、简答题：
1、什么是编译程序？其分为几个阶段？
编译程序：也称为编译器，能够直接将高级语言程序翻译为对应的低级语言程序。
编译程序通常分为：词法分析、语法分析、语义分析与中间代码生成、代码优化、目标代码生成5个阶段。
2、文法的形式定义是什么？ 文法的形式定义为G=（
N V ，T V ，P ，S ），其中N V 为非终结符集，T V 是终结符集， P 是
产生式集合，S 是开始符号
3、什么是上下文无关文法？
若在文法的定义中限定文法的产生式左部只有一个非终结符，则该文法称为上下文无关文法。
4、什么是文法的语言？
从文法G 的开始符号S 出发，所能推导出的句子的全体称为文法G 产生的语言。 5、文法的分类？
乔姆斯基把文法分为0型文法（短语文法）、1型文法（上下文有关文法）、2型文法（上下文无关文法）、3型文法（正规文法）四类。这几类的差别在于对产生式施加不同的限制。 6、词法分析的功能？
1）按规则识别单词，输出单词本身及其类别码；（主要任务） 2）滤掉程序中的无用成分；
3）调用出错处理程序，识别并定位错误；
4）调用符号管理程序，将识别出来的单词及其属性进行管理。 7、什么是符号表？有何作用？
符号表：是一种用于保存源程序中出现的标识符和常数的各种信息的数据结构。 作用：编译器在分析阶段收集信息放入符号表中，在综合阶段生成目标代码时使用符号表中的信息。
8、什么是正规文法？
若文法G=（N V ，T V ，P ，S ）中的每个产生式P 的形式都是A →aB 或A →a ，其中A 、B ∈N V ，a ∈*
T V ，则G 是正规文法。
9、语义分析的主要任务？
1）对语法分析所识别出的各类语法短语进行静态语义审查；
2）若无语义错误，再根据识别出的语法单位的类型进行处理，若是说明语句，则将变量的类型等属性填入符号表，若是可执行语句，则进行初步的翻译，将其翻译为中间代码。 10、什么是属性文法？ 属性文法：包含一个上下文无关文法和一系列的语义规则，为每个文法符号配备若干相关的“值”（属性）。
11、什么是语法制导翻译？
若遍历语法树的操作和建立语法树的操作同时进行，称为语法制导翻译。 12、什么是代码优化？
代码优化：指的是为了提高目标程序的质量而对源程序或中间代码进行的各种合理的等价变换，使得变换后的程序能生成更有效的目标代码。
13、代码优化要遵循哪些原则？
遵循如下原则：等价原则、有效原则、合算原则。
14、局部优化常用哪些技术？
包括：删除公共子表达式、删除无用赋值、合并已知量、对临时变量改名、对语句变换位置、代数变换等。
15、循环优化常用哪些技术？
包括：代码外提、强度削弱、删除归纳变量等。
*16、什么是短语文法？
若对文法中的产生式α→β的要求是：α至少含有一个非终结符，则称该文法为短语文法。
二、计算题：
1）推导、画语法树、二义性的证明：
5、已知表达式的文法G为：
<表达式>→<项>|<表达式>+<项>
<项>→<因子>|<项>*<因子>
<因子>→(<表达式>)| i
给出i+i+i和i+i*i的最左推导、最右推导和语法树。
解答：
用E表示<表达式>，T表示<项>，F表示<因子>，上述文法可以写为：
E → T | E+T
T → F | T*F
F → (E) | i
最左推导：
E=>E+T=>E+T+T=>T+T+T=>F+T+T=>i+T+T=>i+F+T=>i+i+T
=>i+i+F=>i+i+i
E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i
最右推导：
E=>E+T=>E+F=>E+i=>E+T+i=>E+F+i=>E+i+i=>T+i+i
=>F+i+i=>i+i+i
E=>E+T=>E+T*F=>E+T*i=>E+F*i=>E+i*i=>T+i*i=>F+i*i =>i+i*i
i+i+i和i+i*i的语法树如下图所示。
i+i+i 、i+i*i 的语法树
8、考虑文法G[S]： S →aSbS|bSaS|ε
(1)试用最左推导说明此文法的二义性。
(2)对于句子abab 构造两个相应的最右推导。 (3)对于句子abab 构造两棵相应的分析树。 (4)此文法所产生的语言是什么？ 解答：
(1) 句子abab 有如下两个不同的最左推导：
S => aSbS => abS =>abaSbS => ababS => abab S => aSbS => abSaSbS => abaSbS => ababS => abab 所以此文法是二义性的。
(2) 句子abab 的两个相应的最右推导：
S => aSbS => aSbaSbS => aSbaSb => aSbab => abab S => aSbS => aSb => abSaSb => abSab => abab (3) 句子abab 的两棵分析树：
(a) (b)
(4) 此文法产生的语言是：在{a ，b}上由相同个数的a 和b 组成的字符串。 2）给出短语写文法：
7、试构造生成下列语言的上下文无关文法： (1)1L ={i
n n c b a |n ≥1,i ≥0}。
(6)语言6L ={x|x ∈{a,b,c}*
,x 是重复对称排列的(aabcbaa ，aabbaa 等)}
解答：
(1) 把a n b n c i 分成a n b n 和c i 两部分，分别由两个非终结符号生成，因此，生成此文法的产生式为：
S → AB A → aAb|ab B → cB|ε
(6) G[S]：S →aSa | bSb | cSc | a | b | c |ε
3）短语、素短语、最左素短语、firstVT 、lastVT ： 例4.19（P92）、例4.20（P93） 12、已知文法G[E]：（拆成两道大题出） E →T|E+T T →F|T*F
F→(E)|i
(1)给出句型（T*F+i）的最右推导，并画出语法树；
(2)给出句型（T*F+i）的短语、素短语和最左素短语；
(3)证明E+T*F是文法的一个句型，指出这个句型的所有短语、直接短语和句柄。解答：
①最右推导：
E=>T=>F=>(E)=>(E＋T)=>(E＋F)=>(E＋i)=> (T＋i)=>(T*F＋i)
语法树：
图4.1句型(T*F＋i)的语法树
②短语：(T*F＋i)，T*F＋i，T*F，i
素短语：T*F，i
最左素短语：T*F
③由于E =>E+T =>E+T*F，故E+T*F为该文法的句型
短语：T*F、E+T*F
直接短语：T*F
句柄：T*F
13、给定文法G[S]，其产生式如下：
S→(T)|a
T→T,S|S
(1)给出输入串(a,(a,a))的最左和最右推导过程；
(2)计算该文法各非终结符的FirstVT集和LastVT集。
解答：
最左推导：
S=> (T)=> (T,S)=> (S,S)=> (a,S)=> (a,(T))=> (a,(T,S))
=> (a,(S,S)) => (a,(a,S))=> (a,(a,a))
最右推导：
S=> (T)=> (T,S)=> (T,(T))=> (T,(T,S))=> (T,(T,a))
=> (T,(T,a)) => (T,(a,a))=> (S,(a,a))=> (a,(a,a))
文法中S和T的FirstVT和LastVT集为：
FirstVT(S)={a,(} FirstVT(T)={,,a, (}
lastVT(S)={a, ）} lastVT(T)={,,a,)}
4）给语句写四元式序列（四选一）：
例5.12（P156）
11、将下面的语句翻译为四元式序列：
(1)if (A if A=1 then c :=c+1 else if A<=D then A :=A+2； (4)for i :=b*2 to 100 do x :=(a+b)*(c+d)-(a+b+c)； 解答： (1) 四元式序列为： 1．（j<,A,C,3）8.(:=,T,-,C) 2.(j,-,-,14) 9.(j,-,-,14) 3.(j<,B,D,5) 11.(j,-,-,14) 4.(j,-,-,14) 12.(+,A,2,T2) 5.(j=,A,1,7) 13.(:=, T2,-,A) 6.(j,-,-,10) 14. 7.(+,c,1,T1) (4) 四元式序列为： 0. (*,b,2,t0) 1. (:=, t0, ,i) 2. (:=,100, , t1 ) 3. (j, , , 6) 4. (+,i,1,t2 ) 5. (:=, t2, , i) 6. (j>, i,t1,15) 7. (+, a, b, t3 ) 8. (+, c, d, t4 ) 9. (*,t3, t4, t5) 10. (+, a, b, t6 ) 11. (+, t6 c, t7 ) 12. ( -, t5, t7, t8) 13. ( :=, t8, , x ) 14. (j, , , 4) 15. 三、综合题： 1）NFA→DFA： 例3.9（P44） 2）自上而下分析（四选一）： 例4.12（P79） 8、已知文法G[S]，其产生式如下： S→(L)|a L→L,S|S 从G[S]中消除左递归，并为之构造一个非递归预测分析器LL(1)分析表，并说明对输入符号串（a,(a,a)）的分析过程。 解答： 消除所给文法的左递归，得G'： S →(L)|a L → SL' L'→ ,SL' | 实现预测分析器的不含递归调用的一种有效方法是使用一张分析表和一个栈进行联合控制，下面构造预测分析表： 根据文法G'有： First(S) = { ( , a ) Follow(S) = { ) , , , #} First(L) = { ( , a ) Follow(L) = { ) } First(L') = { ,} Follow(L') = { ) } 按以上结果，构造预测分析表M如下： 文法G'是LL(1)的，因为它的LL(1)分析表不含多重定义入口。 9、求下述文法中各非终结符号的First集、Follow集，各候选式的First集。 (1)S→AB|bC (2)A→b|ε (3)B→aD|ε (4)C→AD|b (5)D→aS|c 解答： 各非终结符的First集： First(S)={First(A)\{ε}}∪{First(B)\{ε}}∪{ε}∪{b}={a,b, ε} First(A)={b}∪{ε}={b,ε} First(B)＝{ε}∪{a}={a,ε} First(C)={First(A) \{ε}}∪First(D)∪First(b) ={a,b,c} First(D)={a}∪{c}={a,c} 各个候选式的First 集为： First(AB)={a,b, ε} First(bC)={b} First(ε)＝{ε} First(b)＝{b} First(aD)={a} First(AD)={a,b,c} First(b)={b} First(aS)={a} First(c)={c} 各非终结符的Follow 集的计算： Follow(S)={#}∪Follow(D) ={#} Follow(A)=(First(B)\{ε})∪Follow(S)∪First(D) ={a,#,c} Follow(B)=Follow(S) ={#} Follow(C)=Follow(S) ={#} Follow(D)=Follow(B)∪Follow(C) ={#} 11、下述文法中哪个是LL(1)的，说明理由。 (1)S →Abc A →a|ε B →b|ε (2)S →Ab A →a|B|ε B →b|ε 解答： (1) a. 文法不含左递归； b. S,A,B 各候选式的First 集不相交； c. First(A)∩Follow(A)={a,ε}∩{b}=Φ First(B)∩Follow(B)={b,ε}∩Φ=Φ ∴该文法为LL(1)文法。 (2) a. 文法不含左递归； b. S,A,B 各候选式的First 集不相交； c. First(A)∩Follow(A)={a,b, ε}∩{b}={b }≠Φ ∴ 该文法不是LL(1)文法。 3）LR(0)项目集构造： 例4.29（P106） 附加问题：写出符号串#abc#的分析过程。 一、填空题|（每题4分，共20分） 1. 乔母斯基定义的3型文法（线性文法）产生式形式 A→Ba|a,或A→aB|a，A，B∈Vn, a,b∈Vt 。 2.语法分析程序的输入是单词符号，其输出是语法单位。 3 型为 B → .aB 的LR（0）项目被称为移进项目，型为 B → a.B 的LR（0） 项目被称为待约项目， 4.在属性文法中文法符号的两种属性分别为继承属性和综合属性。 5、运行时存贮管理方案有静态存储分配、动态存储分配和堆式存储分配和方案。 二.已知文法 G(S) (1) E → T | E+T (2) T → F | F*F (3) F →（E）| i （1）写出句型（T*F+i）的最右推到并画出语法树。（4分） （2）写出上述句型的短语，直接短语和句柄。（4分） 答：（1）最右推到（2分） E ==> T ==> F ==> (E) ==> (E+T) ==> (E+F) ==> (E+i) ==> (T+i) ==> (T*F+i) (2) 语法树（2分） （3）（4分） 短语：（T*F+i），T*F+i ，T*F ， i 直接短语：T*F ， i 句柄：T*F 三. 证明文法G(S) ：S → SaS |ε是二义的。（6分） 答：句子aaa对应的两颗语法树为： 因此，文法是二义文法 四.给定正规文法G（S）： (1) S → Sa | Ab |b (2) A → Sa 请构造与之等价的DFA。（6分） 答：对应的NFA为：（6分） 状态转换表： a b {F} Φ{S} {S} {S,A} Φ {S,A} {S,A} {S} 五. 构造识别正规语言b*a(bb*a)*b* 最小的DFA（要求写出求解过程）。（15分）答：（1）对应的NFA（5分） a b {0} {1，3} {0} {1,3} Φ{2，3} {2,3} {1,3} {2,3} （5分） 六. 已知文法G(S) : (1) S → ^ | a | (T) (2) T → T,S | S 试：（1）消除文法的左递归；（4分） （2）构造相应的first 和 follow 集合。（6分） 答：（1）消除文法的左递归后文法 G’（S）为： (1) S → ^ | a | (T) 编译原理的复习提纲 1.编译原理=形式语言+编译技术 2.汇编程序： 把汇编语言程序翻译成等价的机器语言程序 3.编译程序： 把高级语言程序翻译成等价的低级语言程序 4.解释执行方式： 解释程序，逐个语句地模拟执行 翻译执行方式： 翻译程序，把程序设计语言程序翻译成等价的目标程序 5.计算机程序的编译过程类似，一般分为五个阶段： 词法分析、语法分析、语义分析及中间代码生成、代码优化、目标代码生成 词法分析的任务： 扫描源程序的字符串，识别出的最小的语法单位（标识符或无正负号数等） 语法分析是： 在词法分析的基础上的，语法分析不考虑语义。语法分析读入词法分析程序识别出的符号，根据给定的语法规则，识别出各个语法结构。 语义分析的任务是检查程序语义的正确性，解释程序结构的含义，语义分析包括检查变量是否有定义，变量在使用前是否具有值，数值是否溢出等。 语法分析完成之后，编译程序通常就依据语言的语义规则，利用语法制导技术把源程序翻译成某种中间代码。所谓中间代码是一种定义明确、便于处理、独立于计算机硬件的记号系统，可以认为是一种抽象机的程序 代码优化的主要任务是对前一阶段产生的中间代码进行等价变换，以便产生速度快、空间小的目标代码 编译的最后一个阶段是目标代码生成，其主要任务是把中间代码翻译成特定的机器指令或汇编程序 编译程序结构包括五个基本功能模块和两个辅助模块 6.编译划分成前端和后端。 编译前端的工作包括词法分析、语法分析、语义分析。编译前端只依赖于源程序，独立于目标计算机。前端进行分析 编译后端的工作主要是目标代码的生成和优化后端进行综合。独立于源程序，完全依赖于目标机器和中间代码。 把编译程序分为前端和后端的优点是： 可以优化配置不同的编译程序组合，实现编译重用，保持语言与机器的独立性。 7.汇编器把汇编语言代码翻译成一个特定的机器指令序列 第二章 1.符号，字母表，符号串，符号串的长度计算P18，子符号串的含义，符号串的简单运算XY，Xn， 2.符号串集合的概念，符号串集合的乘积运算，方幂运算，闭包与正闭包的概念P19，P20A0 ={ε} 3.重写规则，简称规则。非xx（V 第一章： 1.编译程序的步骤和任务： 1）词法分析：从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个单词。 2）语法分析：是在词法分析基础上将单词序列分解成各类语法短语(比如程序、语句、表达式等），通过语法分析确定整个输入串是否构成一个语法上正确的程序。 3）语义分析：是审查源程序有无语义错误，为代码生成阶段收集类型信息。 4）中间代码产生：将源程序变成一种易于翻译成目标代码的内部表示形式。 5）代码优化：对前阶段生成的中间代码进行变换或改造，使生成的目标代码更为高效6）目标代码生成：把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。 2.前端和后端的概念，试问前端通常包括那些阶段，后端包括那些阶段？ 答：前端只依赖于源语言，与目标机无关。编译程序的前端通常包括词法分析程序、语法分析程序、语义分析程序、中间代码生成程序及相关的表格管理程序和出错处理程序。后端是指编译器中依赖于目标机器的部分,只与中间代码有关。通常包括目标代码生成程序、代码优化程序以及相关的表格管理程序和出错处理程序。 遍（PASS)：对输入文件（源程序或其等价的中间语言程序）从头到尾扫视，完成预定处理的过程。 一个多遍的编译程序较之一遍的编译程序可能少占内存，逻辑结构可能清晰些，但效率相对可能差点 3.程序的正确与否：结构上的语法规则，语义上的语义规则。 翻译程序：汇编，解释，编译。 4.解释程序及其与编译程序的比较 解释程序功能：源程序+初始数据=计算结果 解释与编译的区别： 工作模式：这是根本区别，编译把源程序翻译成目标代码，而解释直接得到计算结果，不生成目标代码。 存储区内容：编译方式翻译和执行分开，解释方式翻译和执行同时并允许修改源程序，因此二者存储组织不同。 效率：解释慢于编译，很多语言两种方式都有。 标识符：=表达式 第三章：文法和语言 1.文法的直观概念：一组判定规则。 在实践中，文法不包含多余产生式。 2.文法G定义为四元组（VT，VN ,S, P ），其中： VT是一个非空有穷终结符号集合； VN是一个非空有穷的非终结符号集合，且VT∩VN＝Φ； P是一个产生式的非空有穷集合（注意：产生式左部至少含有一个非终结符）； S VN ，称为开始符号，且S至少必须在某个产生式的左部出现一次。 通常用V表示VN∪ VT,V称为文法G的字母表或字汇表. 3.句型、句子：设文法G，如果符号串x是从识别符号推导出来的，即S→x,x∈V*，则称x 是一个句型。仅含终结符号的句型是一个句子。 4.语言：语言 L(G）是由文法G产生的所有句子所组成的集合。 5文法的类型：逐渐对产生式施加限制四种类型：0型，1型，2型，3型 编译原理期末复习 鉴于编译原理马上就要期末考试，我将手中集中的一些资料上的题目进行了整理归类，每种类型题目给出了所涉及到的基本知识，然后对每类题目中的第一道例题进行了做法进行了讲解，剩下的例题请给大家作为练习，答案也都给出，希望对大家复习有所帮助，最后由于时间很紧，整理的有些仓促，整理中难免有遗漏或错误，请大家见谅。 注：下面出现的字母中，若无特别说明，小写英文字母为终结符，大写英文字母为非终结符，希腊字母为终结符与非终结符的任意组合。 1、简答题（或者名词解释） 下面涉及到的概念中，加下划线的都是在以往一些试卷中出现的原题，务必掌握。 注：这类题目老师说答案不会超过一百个字，否则写的再多也不给分，有些点到即可，不要重复啰嗦。（1）简述编译程序的概念及其构成 答：1）编译程序：它特指把某种高级程序设计语言翻译成等价的低级程序设计语言的翻译程序。 2)构成： （2）简述词法分析阶段的主要任务（也有可能问语法分析阶段主要任务）答：词法分析的任务是输入源程序，对源程序进行扫描，识别其中的单词符号，把字符串形式的源程序转换成单词符号形式的源程序。 语法分析的主要任务是对输入的单词符号进行语法分析（根据语法规则进行推导或者归约），识别各类语法单位，判断输入是不是语法上正确的程序 (3) 简述编译程序的构造过程（这个大家看看，是对（1）和（2）的综合） 答：1）构造词法分析器：用于输入源程序进行词法分析，输出单词符号； 2）构造语法分析器：对输入的单词符号进行语法分析，识别各类语法单位，判断输入是不是语法上正确的程序 3）构造语义分析和中间代码产生器：按照语义规则对已归约出的语法单位进行语义分析并把它们翻译成中间代码。 4）构造优化器：对中间代码进行优化。 5) 构造目标代码生成器：把中间的代码翻译成目标程序。 6) 构造表格管理程序：登记源程序的各类信息和编译各阶段的进展情况。 7)构造错误处理程序：对出错进行处理。 (4) 说明编译和解释的区别： 1)编译要程序产生目标程序，解释程序是边解释边执行，不产生目标程序； 2)编译程序运行效率高而解释程序便于人机对话。 （5）文法：描述语言语法结构的形式规则，一般用一个四元式表示： G=(V T，V N，S，P)，其中V T：终结符集合(非空) V N：非终结符集合(非空)，且V T ?V N=? S：文法的开始符号，S?V N P：产生式集合(有限)。 《编译原理》期末复习 【题型】 一、填空题：每空1分，共10分； 二、单选题：每题2分，共20分； 三、应用题：每小题6分，共48分； 四、综合分析题：每小题11分，共22分。 【知识点】 1.编译程序的整个过程从逻辑上依次分为哪6个阶段，其中还涉及哪2个重要工作。 2.语法分析有哪两大类方法？ 3.编译程序和解释程序的概念，二者最主要的区别是？ 4.句柄的定义。 5.什么是规范推导？ 6.语言、句型、句子的定义。 7.LR分析法中的项目类型定义（待约项目、移入项目、归约项目）。 8.中间代码和目标代码区别。 9.文法与正则表达式所描述的语言及句子。 10.如何判断自动机（状态转换图）所能识别的字符串。 11.中间代码生成时主要依据什么规则？ 12.根据给定文法，通过推导，画出指定句子的语法树。 13.自底向上的语法分析过程中，构造LR分析表时可能会面临的两种冲突。 14.判断源程序中出现的某类错误可能在编译的哪个阶段被发现。 15.词法分析及语法分析的输入输出是什么？ 16.0、1、2、3型文法的定义、别名及描述能力强弱排名。 17.证明给定文法是二义性的（参考第二章课后练习）。 18.消除文法的左递归及提取公共左因子。 19.给定一个文法和该文法的句型，要求写出句型的最左推导、画出语法分析树、指出短语、简单短 语、句柄（参考第二章课后练习及课件中的例题）。 20.根据有限自动机的定义（五元组），给出其状态转换矩阵和状态转换图。 21.画出按照给定翻译模式分析某句子时所产生的分析树，分析其输出结果（参考第六章课后练习及 课件中的例题）。 22.针对给定的语言构造一个文法G，然后判断该文法类型（0、1、2、3型）（参考第二章课后练习）。 23.根据有限自动机M的定义（五元组），画出M的状态转换图，并说明它所识别或接受的语言是 什么（参考课件第三章例题）。 24.给出一个复合表达式，写出该表达式的三元式和四元式（如：-a*(b+c)/d）。 25.判断某语法制导定义在给定输入下的输出结果，分析文法产生的语言，指出语法制导定义功能。 26.已知文法及其LR分析表，给出对该文法某个句子的分析过程。（参考例题及习题） 27.给定一个文法，消除其左递归和提取左公因子，求所有非终结符的FIRST和FOLLOW集，构造 该文法的LL(1)分析表，根据分析表给出某句子的分析过程（参考第四章课后练习）。 一、填空题（每空2分，共20分） 1．编译程序首先要识别出源程序中每个单词，然后再分析每个句子并翻译其意义。 2．编译器常用的语法分析方法有自底向上和自顶向下两种。 3．通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的分析，中间代码生成、代码优化与目标代码的生成则是对源程序的综合。 4．程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即静态存储分配方案和动态存储分配方案。 5．对编译程序而言，输入数据是源程序，输出结果是目标程序。 1．计算机执行用高级语言编写的程序主要有两种途径：解释和编译。 2．扫描器是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。 3．自下而上分析法采用移进、归约、错误处理、接受等四种操作。 4．一个LL（1）分析程序需要用到一张分析表和符号栈。 5．后缀式abc-/所代表的表达式是a/(b-c)。 二、单项选择题（每小题2分，共20分） 1．词法分析器的输出结果是__C。 A．单词的种别编码B．单词在符号表中的位置 C．单词的种别编码和自身值D．单词自身值 2．正规式M 1 和M 2 等价是指__C_。 A．M1和M2的状态数相等 B．M1和M2的有向边条数相等 C．M1和M2所识别的语言集相等D．M1和M2状态数和有向边条数相等 3．文法G：S→xSx|y所识别的语言是_C____。 A．xyx B．(xyx)* C．xnyxn(n≥0) D．x*yx* 4．如果文法G是无二义的，则它的任何句子α_A____。 A．最左推导和最右推导对应的语法树必定相同B．最左推导和最右推导对应的语法树可能不同 C．最左推导和最右推导必定相同D．可能存在两个不同的最左推导，但它们对应的语法树相同5．构造编译程序应掌握____D__。 A．源程序B．目标语言C．编译方法D．以上三项都是 6．四元式之间的联系是通过__B___实现的。 A．指示器B．临时变量C．符号表D．程序变量 7．表达式(┐A∨B)∧(C∨D)的逆波兰表示为__B___。 A．┐AB∨∧CD∨B．A┐B∨CD∨∧ C．AB∨┐CD∨∧D．A┐B∨∧CD∨ 8. 优化可生成__D___的目标代码。 A．运行时间较短 B．占用存储空间较小 C．运行时间短但占用内存空间大D．运行时间短且占用存储空间小 9．下列___C___优化方法不是针对循环优化进行的。 A. 强度削弱B．删除归纳变量C．删除多余运算D．代码外提 10．编译程序使用_B_区别标识符的作用域。 A. 说明标识符的过程或函数名B．说明标识符的过程或函数的静态层次 C．说明标识符的过程或函数的动态层次 D. 标识符的行号 三、判断题（对的打√，错的打×，每小题1分，共10分） 2．一个有限状态自动机中，有且仅有一个唯一的终态。x 编译原理复习题 一、选择题 1、编译原理是对(C)。 A、机器语言的执行 B、汇编语言的翻译 C、高级语言的翻译 D、高级语言程序的解释执行 2、(A)是一种典型的解释型语言。 A．BASIC B．C C．FORTRAN D．PASCAL 3、把汇编语言程序翻译成机器可执行的目标程序的工作是由(B)完成的。 A. 编译器 B. 汇编器 C. 解释器 D. 预处理器 4、用高级语言编写的程序经编译后产生的程序叫(B) A．源程序 B．目标程序C．连接程序D．解释程序 5、(C)不是编译程序的组成部分。 A.词法分析程序 B.代码生成程序 C.设备管理程序 D.语法分析程序 6、通常一个编译程序中，不仅包含词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成等六个部分，还应包括(C)。 A．模拟执行器B．解释器 C．表格处理和出错处理D．符号执行器 7、编译程序绝大多数时间花在(D)上。 A．出错处理B．词法分析C．目标代码生成D．表格管理 8、源程序是句子的集合，(B)可以较好地反映句子的结构。 A. 线性表 B. 树 C. 完全图 D. 堆栈 9、词法分析器的输出结果是(D)。 A、单词自身值 B、单词在符号表中的位置 C、单词的种别编码 D、单词的种别编码和自身值 10、词法分析器不能(D) A. 识别出数值常量 B. 过滤源程序中的注释 C. 扫描源程序并识别记号 D. 发现括号不匹配 11、文法：G：S→xSx | y所识别的语言是(D)。 A、xyx B、(xyx)* C、x*yx* D、x n yx n (n≥0) 12、如果文法G是无二义的，则它的任何句子α(A) A．最左推导和最右推导对应的语法树必定相同 B．最左推导和最右推导对应的语法树可能不同 C．最左推导和最右推导必定相同 D．可能存在两个不同的最左推导，但它们对应的语法树相同 一． 填空题（每空2分，共20分） 1. 不同的编译程序关于数据空间的存储分配策略可能不同，但大部分编译中采用的方案有两种：静 态存储分配方案和动态存储分配方案，而后者又分为（1） 和 （2） 。 2. 规范规约是最（3）规约。 3. 编译程序的工作过程一般划分为5个阶段：词法分析、（4） 、语义分析与中间代码生成，代码优化及（5） 。另外还有（6）和出错处理。 4．表达式x+y*z/(a+b)的后缀式为 （7） 。 5．文法符号的属性有综合属性和 （8）。 6．假设二位数组按行存放，而且每个元素占用一个存储单元，则数组a[1..15,1..20]某个元素a[i ，j]的地址 计算公式为（9）。 7．局部优化是局限于一个（10）范围内的一种优化。 二． 选择题（1-6为单选题，7-8为多选题，每问2分，共20分） 1. 一个上下文无关文法G 包括四个组成部分：一组终结符，一组非终结符，一个（ ），以及一组 （ ）。 A ． 字符串 B ． 产生式 C ． 开始符号 D ． 文法 2.程序的基本块是指（ ）。 A ． 一个子程序 B ． 一个仅有一个入口和一个出口的语句 C ． 一个没有嵌套的程序段 D ． 一组顺序执行的程序段，仅有一个入口和一个出口 3. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于（ ）分析方法。 A ． 自左向右 B ． 自顶向下 C ． 自底向上 D ． 自右向左 4．在通常的语法分析方法中，（ ）特别适用于表达式的分析。 A ． 算符优先分析法 B ． LR 分析法 C ． 递归下降分析法 D ． LL （1）分析法 5．经过编译所得到的目标程序是（ ）。 A ． 四元式序列 B ． 间接三元式序列 C ． 二元式序列 D ． 机器语言程序或汇编语言程序 6． 一个文法所描述的语言是（ ）；描述一个语言的文法是（ ）。 A ． 唯一的 B ． 不唯一的 C ． 可能唯一，也可能不唯一 7． 如果在文法G 中存在一个句子，当其满足下列条件（ ）之一时，则称该文法是二义文法。 A ． 其最左推导和最右推导相同 B ． 该句子有两个不同的最左推导 C ． 该句子有两个不同的最右推导 D ． 该句子有两棵不同的语法树 第3章文法和语言 第1题 文法G＝({A,B,S},{a,b,c},P,S)其中P为： S→Ac|aB A→ab B→bc 写出L(G[S])的全部元素。 答案： L(G[S])={abc} 第 11题 令文法 G[E]为： E→T|E+T|E-T T→F|T*F|T/F F→(E)|i 证明 E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。答案： 此句型对应语法树如右，故为此文法一个句型。 或者：因为存在推导序列: E=>E+T=>E+T*F，所 以E+T*F句型 此句型相对于E的短语有:E+T*F；相对于 T的短语 有 T*F 直接短语为：T*F 句柄为：T*F 第 13题 一个上下文无关文法生成句子abbaa的推导树如下： (1)给出串abbaa最左推导、最右推导。 (2)该文法的产生式集合 P可能有哪些元素？ (3)找出该句子的所有短语、直接短语、句柄。 A S a S B B B A S a 《编译原理》课后习题答案第三章 答案： (1)串abbaa最左推导: S=>ABS=>aBS=>aSBBS=>aBBS=>abBS=>abbS=>abbAa=>abbaa 最右推导： S=>ABS=>ABAa=>ABaa=>ASBBaa=>ASBbaa=>ASbbaa=>Abbaa=>abbaa (2)产生式有：S→ABS |Aa|ε A→a B→SBB|b abbaa aaabbaa ? 可能元素有：ε aa ab (3)该句子的短语有： a是相对 A的短语 ε是相对 S的短语 b是相对 B的短语 εbb是相对 B的短语 aa是相对 S的短语 aεbbaa是相对 S的短语 直接短语有：a ε b 句柄是：a 第八节习题一、单项选择题 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 二、多项选择题 《编译原理》期末考试复习题 一、是非题（请在括号内，正确的划√，错误的划×）（每个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*} 。 一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分） ×1．对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。() ×2．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。() √3．递归下降分析法是自顶向上分析方法。() ×4．产生式是用于定义词法成分的一种书写规则。() √5．LR 法是自顶向下语法分析方法。() √6．在SLR （1 ）分析法的名称中，S的含义是简单的。() ×7．综合属性是用于“ 自上而下” 传递信息。() ×8．符号表中的信息栏中登记了每个名字的属性和特征等有关信息，如类型、种属、所占单元大小、地址等等。() ×9．程序语言的语言处理程序是一种应用软件。() ×10．解释程序适用于COBOL 和FORTRAN 语言。() 三、填空题(每空1分，共10分) 1．一个句型中的最左简单短语称为该句型的___句柄__。 南京工业大学继续教育学院编译原理期末考试试卷 (2012-2013学年) A卷 一、选择题（每题2分，共20分） 得分 1. 一个上下文无关文法G包括四个组成部分：一组终结符，一组非终结符，一个_____，以及一组产生式。 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．正规式M 1 和M 2 等价是指_____。 A．( ) M1和M2的状态数相等B．( ) M1和M2的有向边条数相等 C．( ) M1和M2所识别的语言集相等D．( ) M1和M2状态数和有向边条数相等 8．文法G：S→xSx|y所识别的语言是_____。 A．( ) xyx B．( ) (xyx)* C．( ) xnyxn(n≥0) D．( ) x*yx* 9．语言是_____。 A．句子的集合B．产生式的集合 C．符号串的集合D．句型的集合 10．编译程序前三个阶段完成的工作是 A．词法分析、语法分析和代码优化 B．代码生成、代码优化和词法分析 C．词法分析、语法分析、语义分析和中间代码生成 D．词法分析、语法分析和代码优化 二、名词解释（每题2分，共20分） 得分 1.最左推导： 2.语法： 3.文法： 4.基本块： 5.语法制导翻译： 6.短语： 7.规范句型： 1、给出下面语言的相应文法。L1={a n b n c i|n≥1,i≥0} 答案：S→AB|B A→a|aA B→bBc|bc 2．给出下面语言的相应文法 L1={a n b n c m d m| m,n≥1，n为奇数，m为偶数}。 答案：文法G(S):S→AC A→aaAbb/ab C→ccCcc/cc 3、构造一个DFA，它接受 ={a，b}上所有包含ab的字符串。 （要求：先将正规式转化为NFA，再将NFA确定化，最小化） (一)相应的正规式为(a|b)*ab(a|b)* (二)①与此正规式对应的NFA为 答案；在自己写的纸上 4、对下面的文法G: E→TE’E’→+E|εT→FT’T’→T|ε F→PF’F’→*F’|εP→(E)|a|b|∧ （1）证明这个文法是LL(1)的。 考虑下列产生式: 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)文法. 计算这个文法的每个非终结符的FIRST和FOLLOW。（8分） 答案：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,^,+,),#} （3）构造它的预测分析表。（6分） 答案；在手机上 写出表达式a+b*(c-d)对应的逆波兰式和三元式序列。 答案：逆波兰式：(abcd-*+) 三元式序列: OP ARG1 ARG2 (1) - c d (2) * b (1) (3) + a (2) 给出下面语言的相应文法 L1={a n b n a m b m|n,m≥0} 给出下面语言的相应文法 答案：S→AB|A|B|∑ A→aAb|ab B→aBb|ab 编译原理 一、单选题 1、将编译程序分为若干个“遍”是为了（）。B A.提高程序的执行效率 B.使程序的结构更加清晰 C.利用有限的机器内存并提高机器的执行效率 D.利用有限的机器内存但降低了机器的执行效率 2、构造编译程序应掌握（）。D A.源程序 B.目标语言 C.编译方法 D.以上三项都是 3、变量应当（）。C A.持有左值 B.持有右值 C.既持有左值又持有右值 D.既不持有左值也不持有右值 4、编译程序绝大多数时间花在（）上。D A.出错处理 B.词法分析 C.目标代码生成 D.管理表格 5、（）不可能是目标代码。D A.汇编指令代码 B.可重定位指令代码 C.绝对指令代码 D.中间代码 6、编译程序是对（）。D A.汇编程序的翻译 B.高级语言程序的解释执行 C.机器语言的执行 D.高级语言的翻译 7、正规式M1和M2等价是指（）。C A.M1和M2的状态数相等和M2的有象弧条数相等 和M2所识别的语言集相等和M2状态数和有象弧条数相等 8、如果文法G是无二义的，则它的任何句子（）。A A.最左推导和最右推导对应的语法树必定相同。 B.最左推导和最右推导对应的语法树可能相同。 C.最左推导和最右推导必定相同。 D.可能存在两个不同的最左推导，但它们对应的语法树相同。 9、文法G：S→S+T|T T→T*P|P P→(S)|i 句型P+T+i的短语有（）B A.i，P+T B. P，P+T，i，P+T +i +T + i D. P，P+T，i 10、产生正规语言的文法为（）。D 型型型型 11、文法G：S→b|?|(T) T→T?S|S 则FIRSTVT(T)=() C A.{b，?，(} B.{b，?，)} C.{b，?，(，?} D.{b，?，)，?} 12、给定文法：A→bA | cc，下面的符号串中，为该文法句子的是（）。A cc bcbc bcbcc ④bccbcc ⑤bbbcc 可选项有： A. B.④⑤ C.④ D.④⑤ 13、采用自上而下分析，必须（）。C A.消除左递归 B.消除右递归 C.消除回溯 D.提取公共左因子 14、由文法的开始符经0步或多步推导产生的文法符号序列是（）。C A.短语 B.句柄 C.句型 D.句子 15、后缀式ab+cd+/可用表达式（）来表示。B 第一章引论 1.编译过程的阶段 由词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成六个阶段 2.编译程序的概念 3.编译程序的结构 例：（B）不是编译程序的组成部分。 A. 词法分析器； B. 设备管理程序 C. 语法分析程序； D. 代码生成程序 4.遍的概念 对源程序(或其中间形式)从头至尾扫描一次并进行有关加工处理，生成新的中间形式或最终目标程序，称为一遍。 5.编译程序与解释程序的区别 例：解释程序和编译程序是两类程序语言处理程序，它们的主要区别在于（D）。 A. 单用户与多用户的差别 B. 对用户程序的差错能力 C. 机器执行效率 D. 是否生成目标代码 第三章文法和语言 文法的概念 字母表、符号串和集合的概念及运算 例：(ab|b)*c 与下面的那些串匹配？（ACD） A. ababbc； B. abab； C. c； D. babc； E. aaabc 例：ab*c*(a|b)c 与后面的那些串匹配？（BC） A.acbbc B.abbcac C.abc D.acc 例：(a|b)a+(ba)*与后面的那些串匹配? （ADE）A.ba B.bba C.ababa D.aa E.baa 文法的定义（四元组表示） 文法G定义为四元组（V N，V T，P，S） V N：非终结符集 V T：终结符集 P：产生式（规则）集合 S：开始符号（或识别符号） 例：给定文法，A::= bA | cc，下面哪些符号串可由其推导出（①② ⑤）。 ①cc ②b*cc ③b*cbcc ④bccbcc ⑤bbbcc 什么是推导 例：已知文法G： E->E+T|E-T|T T->T*F|T/F|F F->(E)|i 试给出下述表达式的推导：i*i+i 推导过程：E->E+T ->T+T ->T*F+T ->F*F+T ->i*F+T ->i*i+T ->i*i+F ->i*i+i ●句型、句子的概念 例：假设G一个文法，S是文法的开始符 号，如果S=>*x，则称x是句型。 例：对于文法G，仅含终结符号的句型称 为句子。 ●语言的形式定义 例：设r=(a|b|c)(x|y|z)，则L(r)中元素为 9个。 例：文法G产生式为S→AB，A→aAb|ε， B→cBd|cd，则B∈L(G)。 A. ababcd； B. ccdd； C. ab； D. aabb ●等价文法 例：如果两个文法描述了同一个语言，则这两个文法是等价文法。 ●文法的类型 0型：左边至少有一个非终结符 1型：右边长度>=左边长度 2型：左边有且仅有一个非终结符 3型：形如：A->aB,A->a 各类型文法都是逐级包含关系， 例：文法S→abC|c，bC→d是几型文法？0 型 例：文法S→abC，bC→ad是几型文法？1 型 例：文法G[A]：A→ε，A→aB，B→Ab，B→a 是几型文法？2型 例：文法S→a|bC，C→d是几型文法？ 3 选择： 1.编译程序绝大多数时间花在 D 上。 a．出错处理b．词法分析 c．目标代码生成d．管理表格 3.如果文法G是无二义的，则它的任何句子α A 。 a. 最左推导和最右推导对应的语法树必定相同 b. 最左推导和最右推导对应的语法树可能不同 c. 最左推导和最右推导必定相同 d. 可能存在两个不同的最左推导，但它们对应的语法树相同 4.在规范归约中，用 B 来刻画可归约串。 a. 直接短语 b. 句柄 c. 最左素短语 d. 素短语 5.若a为终结符，则A→α·aβ为 B 项目 a.归约 b.移进 c.接受 d.待约 6.间接三元式表示法的优点为（A） A.采用间接码表，便于优化处理 B.节省存储空间，不便于表的修改 C.便于优化处理，节省存储空间 D.节省存储空间，不便于优化处理 7.下列C优化方法不是针对循优化进行的。 a．强度削弱b．删除归纳变量c．删除多余运算d．代码外提 8.过程P1调用P2时，连接数据不包含 A 。 a. 嵌套层次显示表 b. 老SP c. 返回地址 d. 全局DISPLAY地址 9.如果活动记录中没有DISPLAY表，则说明b。 a. 程序中不允许有递归定义的过程 b. 程序中不允许有嵌套定义的过程 c. 程序中既不允许有嵌套定义的过程，也不允许有递归定义的过程 d. 程序中允许有递归定义的过程，也允许有嵌套定义的过程 10.关于必经结点的二元关系，下列叙述中不正确的是 D 。 a．满足自反性b．满足传递性c．满足反对称性d．满足对称性11.构造编译程序应掌握 D 。 a．源程序b．目标语言 c．编译方法d．以上三项都是 12.词法分析器的输出结果是__C___。 A．单词的种别编码B．单词在符号表中的位置 C．单词的种别编码和自身值D．单词自身值 13.文法G：S→xSx|y所识别的语言是 C 。 a. xyx b. (xyx)* c. x n yx n(n≥0) d. x*yx* 14.同心集的合并有可能产生新的归约/归约冲突 15.四元式之间的联系是通过 B 实现的。 a.指示器 b.临时变量 c.符号表 d.程序变量 16.优化可生成_____的目标代码。 A. 运行时间较短 B．占用存储空间较小 C．运行时间短但占用内存空间大D．运行时间短且占用存储空间小 2011～ 2012 学年第 1 学期期末考试试卷答案 《编译原理》（共 4 页） （考试时间： 2011 年 12 月 25 日） 一、选择题（每题 1 分，共 10 分） 1.B 2.D 3.A 4.D 5.D 6.C 7.B 8.C 9.D 10.B 二、简答题（每题 5 分，共 20 分） 1．何谓二义性文法？试举一例说明。 答：若文法G 的一个句子对应有两棵或两棵以上不同的推导树，则称该句子是 二义性的。产生二义性句子的文法称为二义性文法，否则该文法是无二义性的。 例子：给定文法G[ 一、简答题 1.什么是编译程序 答：编译程序是一种将高级语言程序(源程序)翻译成低级语言(目标程序)的程序。 将高级程序设计语言程序翻译成逻辑上等价的低级语言(汇编语言,机器语言)程序的翻译程序。 2.请写出文法的形式定义 答：一个文法G抽象地表示为四元组?G=（Vn,Vt,P,S）? –其中Vn表示非终结符号 –Vt表示终结符号，Vn∪Vt=Ｖ(字母表)，Vn∩Vt=φ –> –S是开始符号， –P是产生式，形如：α→β(α∈V+且至少含有一个非终结符号，β∈V*) 3.语法分析阶段的功能是什么 答：在词法分析的基础上，根据语言的语法规则，将单词符号串分解成各类语法短语(例：程序、语句、表达式)。确定整个输入串是否构成语法上正确的程序。 4.局部优化有哪些常用的技术 答：优化技术1—删除公共子表达式 优化技术2—复写传播 优化技术3—删除无用代码 " 优化技术4—对程序进行代数恒等变换（降低运算强度） 优化技术5—代码外提 优化技术6—强度削弱 优化技术7—删除归纳变量 优化技术简介——对程序进行代数恒等变换（代数简化） 优化技术简介——对程序进行代数恒等变换（合并已知量） 5．编译过程分哪几个阶段 答：逻辑上分五个阶段：词法分析、语法分析、语义分析与中间代码生成、代码优化、目标代码生成。每个阶段把源程序从一种表示变换成另一种表示。 、 6. 什么是文法 答：文法是描述语言的语法结构的形式规则。是一种工具，它可用于严格定义句子的结构； 用有穷的规则刻划无穷的集合；文法是被用来精确而无歧义地描述语言的句子的构成方式；文法描述语言的时候不考虑语言的含义。 7. 语义分析阶段的功能是什么 答：对语法分析所识别出的各类语法范畴分析其含义，进行初步的翻译(翻译成中间代码)； 并对静态语义进行审查。 8.代码优化须遵循哪些原则 答：等价原则：不改变运行结果 有效原则：优化后时间更短，占用空间更少 合算原则：应用较低的代价取得较好的优化效果 》 9.词法分析阶段的功能是什么 答： 编译原理期末整理 1.语言概念：语言是人类所特有的用来表达意思、交流思想的工具，是一种特殊的社会现象，由语 音、词汇、语法、语义构成一个系统。语言包括口语和书面形式。 课本P1：语言是人们交流思想的工具，人们通过语言来描述事物，表达自己思想。 2.语言的分类及各类特点 自然语言:人与人之间交流信息的一种语言。动物之间通过动物语言交流信息。 数理语言：以数理逻辑、集合论和统计数学来描述的一种语言。 例如，用计算机进行几何定理的证明就得以数理语言形式进行描述。 程序设计语言：是人和计算机进行信息交流的一种语言，它遵循一定的语法和语义的规则，而编 译程序的功能正是：○1讨论语法，检查程序正确性○2讨论语义，生成目标代码 程序设计语言的分类及特点： 1)机器语言(第一代语言)：由机器指令构成的语言称机器语言，即用二进制编码组成。（如 01110101） 特点：○1费时费事○2难懂容易错○3只能在一种型号计算机上运行○4可以直接在计算 机上运行 2)汇编语言(第二代语言:50年代初期出现)：用容易记忆的符号来代替机器指令中操作码和 地址码的一种语言.（如:ADD 代表“+” SUB代表“-” MOV代表“传递”） 特点：优点——(1)程序直观容易阅读；(2)编程工作量相对小； 缺点——(1)只能在一种型号机器上运行；(2)不能直接在计算机上运行。 3)高级程序设计语言(第三代语言:50年代中期提出)：高级程序设计语言是一种面向过程 或者面向对象的语言，不面向机器，用一些符号或者数字对求解的问题或者现实世界进行描述。 特点：a) 直观、易写、易读、工作量小 b) 不依赖于具体的机器 c) 便于程序交流 d) 不可直接在计算机上运行，经编译程序编译成机器语言后方可运行 4)超高级程序设计语言(第四代语言):只需指出所求问题、输入数据及输出形式，就能得到 输出结果，无需对算法和计算过程描述的语言。 特点:a) 语言功能强，效率高，使用方便； b) 开发应用系统修改方便、维护容易； c) 系统复杂，不但要编译还要生成程序。 3.三种翻译程序的定义 解释程序：将高级语言写的源程序作为输入数据，但并不产生目标程序，而是边解释边执行源程序 本身的一种程序。 编译程序：是将高级语言写的源程序翻译成目标语言（汇编语言、机器语言）的程序。这种翻译过程 称为编译。 编译系统：目标程序，再加上运行系统（如服务子程序、动态分配程序、装配程序等）就可获得计算 结果，整个系统称为编译系统。 汇编程序：把汇编语言写的源程序翻译成机器语言的目标程序，这个翻译过程称为汇编。 4.编译基本过程 编译过程基本包括以下几个步骤：1.词法分析 2.语法分析 3.语义分析 4.中间代码生成 5.修饰优 化 6.生成目标程序编译原理期末考试习题及答案
编译原理知识点汇总
全套编译原理复习与期末必考试题
编译原理期末复习
【新版】《编译原理》期末复习
编译原理期末考试题目及答案
编译原理复习题
期末考试编译原理试卷及答案
编译原理复习资料
(2020年整理)编译原理期末总复习题(含答案).doc
《编译原理》期末考试复习题
编译原理考试试卷
编译原理复习题--有答案版
编译原理期末复习
编译原理复习(有答案)
编译原理期末考试复习题
编译原理2011期末考试试卷答案
）是上下文无关文法，产生式集合P 中任意一个产生式应具有什么样的形式？若G 是正则文法呢？ 答：上下文无关文法的产生式形式为： A →α，其中， A ∈ V N，α∈（ V N∪V T）* 正则文法产生式形式为： N，a∈V T A→，或→ （右线性文法）其中，A,B ∈V aBA a A→Ba，或 A → a（左线性文法）其中， A,B ∈ V N， a∈V T 三、推导题（共70 分） 1．对于文法 G[S]：四川大学编译原理期末复习总结
编译原理 期末复习整理
相关主题
文本预览