编译原理期末复习
1、简答题（或者名词解释）
下面涉及到的概念中，加下划线的都是在以往一些试卷中出现的原题，务必掌握。 注：这类题目老师说答案不会超过一百个字，否则写的再多也不给分，有些点到即可，不要重复啰嗦。
（1）简述编译程序的概念及其构成
答：1）编译程序：它特指把某种高级程序设计语言翻译成等价的低级程序设计语言的翻译程序。
2)构成：
（2）简述词法分析阶段的主要任务（也有可能问语法分析阶段主要任务）
答：词法分析的任务是输入源程序，对源程序进行扫描，识别其中的单词符号，把字符串形式的源程序转换成单词符号形式的源程序。
语法分析的主要任务是对输入的单词符号进行语法分析（根据语法规则进行推导或者归约），识别各类语法单位，判断输入是不是语法上正确的程序
(3) 简述编译程序的构造过程（这个大家看看，是对（1）和（2）的综合） 答：1）构造词法分析器：用于输入源程序进行词法分析，输出单词符号；
2）构造语法分析器：对输入的单词符号进行语法分析，识别各类语法单位，判断输入是不是语法上正确的程序
3）构造语义分析和中间代码产生器：按照语义规则对已归约出的语法单位进行语义分析并把它们翻译成中间代码。
4）构造优化器：对中间代码进行优化。
5) 构造目标代码生成器：把中间的代码翻译成目标程序。
6) 构造表格管理程序：登记源程序的各类信息和编译各阶段的进展情况。 7)构造错误处理程序：对出错进行处理。 (4) 说明编译和解释的区别：
1)编译要程序产生目标程序，解释程序是边解释边执行，不产生目标程序； 2)编译程序运行效率高而解释程序便于人机对话。
（5） 文法：描述语言语法结构的形式规则，一般用一个四元式表示： G=(VT，VN，S，P)，其中VT：终结符集合(非空) VN：非终结符集合(非空)，且VT ? VN=? S：文法的开始符
1
号，S?VN P：产生式集合(有限)。
（6）二义性文法：一个文法中存在某个句子，它有两个不同的最左（或者最右推导），则称该文法是二义性的。
例子如文法G：S→if expr then S |other
S→if expr then S else S 句子if e1 then if e2 then s1 else s2
是二义性的。
（7）文法的形式（注：文法的形式一定要牢记，特别是2型和3型文法一定要牢记，不仅在概念题中有用，在下面的根据语言写文法题中也有重要作用，如果所写的文法形式不对，一切都是无用功……）
*
1）0型文法(短语文法，图灵机)：产生式形式为：? ? ? ，其中：?? (VT ? VN)且至少含
*
有一个非终结符；?? (VT ? VN)
2）1型(上下文有关文法，线性界限自动机)：产生式形式为:? ? ? 其中：|?| ? |?|，仅 S?? 例外，但是S不得出现在任何产生式右部。
3）2型文法（上下文无关文法，非确定下推自动机)：产生式形式为：P??， P?VN， ? ?
*
(VT ? VN) 。
4）3型文法(正规文法，有限自动机)：右线性文法：产生式形如：A ? ?B 或 A ? ?其
**
中：?? VT；A，B?VN 左线性文法：产生式形如：A ? B? 或 A ? ? 其中：?? VT；A，B?VN
例题：设G=(VT，VN，S，P)是一个上下文无关文法，产生集合P中的任一个产生式应具有什么样的形式？若G是1型文法呢？若G是正则文法呢？
*
上下文无关文法， 产生式形式为：P??， P?VN， ? ? (VT ? VN) 。
1型文法：产生式形式为:? ? ? 其中：|?| ? |?|，仅 S?? 例外，但是S不得出现在任何产生式右部。
*
正则文法：右线性文法：产生式形如：A ? ?B 或 A ? ?其中：?? VT；A，B?VN
*
左线性文法：产生式形如：A ? B? 或 A ? ? 其中：?? VT；A，B?VN
(8)什么是PDA(下推自动机)?
答：PDA是下推自动机，PDA M用一个七元组表示(K,Σ,f,H,h0,S,Z) K: 有穷状态集 ?：输入字母表(有穷) H:下推栈符号的有穷字母表
h0 :H中的初始符号 f: K ?（Σ?{?}) ? H –> K ? H* S：属于K是初始状态。 Z:包含于K，是终结状态集合。
(9) 什么是DFA（有穷状态自动机）?
自动机M是一个五元式M=(S, ?, f, S0, F),其中： 1）S: 有穷状态集， 2） ?：输入字母表(有穷)，
3） f: 状态转换函数，为S???S的单值部分映射，f(s，a)=s’表示：当现行状态为
s，输入字符为a时，将状态转换到下一状态s’。我们把s’称为s的一个后继状态。
4） S0?S是唯一的一个初态； 5） F?S ：终态集(可空)。
（10）推导：所谓推导就是对于一个含非终结符A的符号串，利用规则A→α，把A替换成α得到新符号串的过程。
2
最左推导：在推导的每一步，选择符号串最左边的非终结符进行替换。 最右推导：在推导的每一步，选择符号串最右边的非终结符进行替换。 (11)归约：归约是推倒的逆过程，即用产生式的左部非终结符替换右部符号串。 (12)什么是句型？什么称为句子？什么是语言？
句型：从文法的起始符号出发，经过有限步的推导能够推导出来的符号称为句型。 句子：只由终结符构成的句型称为句子。
语言：所有句子的集合构成该文法描述的语言。
(13)什么是短语？什么是直接短语（也称为简单短语）？什么是句柄？什么是素短语？什么是最左素短语？（以下几个概念一定要理解，考试中肯定会考哪些是短语，直接短语，句柄等，具体方法请参见后面的）
短语：如果存在某个文法非终结符P,满足S ?βPγ,并且P?α则称α为句型βαγ相对于非终结符P的短语。
直接短语：如果P?α,即从P出发一步推出α，则α称为直接短语。 句柄：一个句型的最左直接短语称为该句型的句柄。
素短语：至少含有一个终结符的短语，并且除了自身外，不包含更小的素短语。 最左素短语：句型中最左边的素短语。
（14）自顶向下的语法分析方法中需要解决的主要问题什么？如何表示？ 答：1）主要需要解决回溯和左递归问题。
2）表示方式，回溯：文法中存在形如A→α1|α2|…|αn ,即产生式右部存在多个候选，导致推导时不能确定到底应该选择哪个候选式。
左递归：文法中存在形如P→Pα的形式，推导时会导致推导过程无休止的进行下去。
注：解决方法，对回溯采取的是提取左公因子，对左递归使消除左递归（包括直接左递归和间接左递归）。
(15)内情向量：一般编译程序对数组说明的处理是把数组的有关信息汇集在一个叫做“内情向量”或“信息向量”的表格中，以便以后计算数组元素的地址时引用这些信息。每个数组有一个内情向量。其中的信息包括，数组的类型，维数，各维的上、下界，以及数组的首地址。
*?TOP（16） C语言的活动记录：
SP 临时单元 内情向量 局部变量 形式单元 参数个数 返回地址 Old SP 2、最左最右推导，画语法树，找短语、直接短语、句柄等。 这种题目很简单，送分题，一定不能丢分！
考题：1）文法G[S]为：S→SdT | T T→T 3 （2）根据所画出的语法树，可以很快的找出短语，直接短语，句柄和最左素短语等，先讲一个简单子树的概念，所谓简单子树是指仅具有单层分支的子树。 具体方法如下： 短语：任一子树的树叶全体(具有共同祖先的叶节点符号串)皆为短语； 直接短语：任一简单子树的树叶全体(具有共同父亲的叶节点符号串)皆为简单短语； 句柄：最左边的直接短语； 素短语：至少含有一个终结符的短语，并且除了自身外，不包含更小的素短语。 最左素短语：最左边的素短语。 答：（1）S?T? T 语法树： （2）短语：G，SdG, (SdG), a, (SdG) 注:还有一份试卷将句型改为adT<(S)，与这个类似，大家自己做做，答案是 短语：a,(S),T<(S),adT<(S) 直接短语：a,(S) 句柄：a 最左素短语：a 下面两道例题大家看看，一定要会找短语，直接短语，句柄等. ※短语、简单短语和句柄示例【例2.12】图2.3为一个算术表达式(型)的语法树： E E - T E + T T * F F T / F i 图2.3 E+F-T/F*i 的语法树※ 一类典型的综合例题：【例2.13】G(S): S->aAcBe ; A->Ab|b ; B->d ※ 给定符号串： aAbcde ⑴ 证明 = aAbcde 是一个句型； ⑵ 画出句型 的语法树； ⑶ 指出中的短语、简单短语和句柄。【题解】⑴ S=>aAcBe=>aAbcBe=> aAbcde⑵ 语法树如右图：⑶ 短语、简单短语和句柄:? 短语: aAbcde ,Ab , d? 简单短语: Ab , d? 句柄：Ab S a A c B e A b d ????句型： E+F-T/F*i短语: E+F-T/F*i，E+F，F，T/F*i，T/F，i 简单短语: F，T/F，i 句柄: F 考题：2)文法G[E]的产生式为E→E+T|T T→T*F|F F→i|(E) ①对于句型(i+i)*i，给出最左最右推导及相应的推导树 ②列出句型的所有短语、简单短语。（还有一份试卷上是出句型F+T*F的所有短语、简单短语和句柄，大家自己做做） 答：（1）最左推导：E?T?T*F?F*F?(E)*F?(E+T)*F?(T+T)*F?(F+T)*F?(i+T)*F 4 ?(i+F)*F?(i+i)*F?(i+i)*i 最右推导E?T?T*F?T*i?F*i?(E)*i?(E+T)*i?(E+F)*i?(E+i)*i?(T+i)*i ?(F+i)*i?(i+i)*i 推导树如下： （2）短语;i,i+i,(i+i),(i+i)*i 直接短语：i 句柄：i 3、根据语言推文法 这类题目首先要看清题目，指定的是什么文法，一般都是2型（上下无关文法）或者3型（正规文法），这两类文法形式一定要记住，具体请参见第2页的文法分类。 n 掌握几个基本形式{a | n>0}对应文法S→aS| a 如果是n>=0则为S→aS|ε(ε是空字) nn {ab| n>0}对应文法S→aSb| ab 下面这四道题目老是在试卷中重复出现，所以大家好好看看。 考题 1、按指定类型给出下列语言的文法,并指出语言的类型。（10 分） (1)L1={anbmcn| n≥0,m>0 } 二型文法：S→aSc|B B→bB|b (2) L2={ 0na1nbmcm| n>0，m ≥0} 二型文法：S→AB A→0A1|0a1 B→bBc|ε 2、按指定类型给出下列语言的文法。（10 分） (1)L1={ candbm| n≥0,m>0 } 用正规文法。 S→cA A→aA|B B→dC C→bC|b (2)L2={ 0na 1nbmcm| n>0,m ≥0}用二型文法。 S→AB A→0A1|0a1 B→bBc|ε 3、按指定的类型给出下列语言的文法（10 4、按指定的类型给出下列语言的文法（10 分） 分） (1)L1={ canbm| n≥0,m>0 } 用正规文法。 (1) L1={anbmc|n>=0,m>0}用正规文法 S→cA A→aA|B B→bB|b (2)L2={ 0na 1nbm| n>0，m ≥0} 用二型文法。 5 S→aS|A A→bA|bB B→c (2) L2={a0n1nbdm|n>0,m>0}用二型文法