《编译原理复习大纲lk》由会员分享，可在线阅读，更多相关《编译原理复习大纲lk（9页珍藏版）》请在金锄头文库上搜索。
1、1、 理解编译器的概念，掌握编译器的功能，熟练掌握编译器的主要翻译步骤。了解与编译器相关的程序及其功能编译程序的工作过程一般可以划分为 词法分析,语法分析,语义分析，中间代码生成,代码优化 等几个基本阶段,同时还会伴有 表格处理 和 出错处理 .2、 扫描器功能,理论依据，它完成任务是什么？扫描器的任务是从源程序中识别出一个个 单词符号 ，编译程序对源程序或中间代码程序从头到尾扫描一次，找到单词。5. 符号表用法如、符号表中的信息栏中登记了每个名字的有关的性质，它有那些内容？名字、符号种类、类型、地址、扩展属性指针。6.能画出程序框图，了解其功能，能叙述编译的基本结构2、 文法的集中类型和主要
2、特点.如文法有几种类型 各自特点？一个文法组成部分？0型文法：短语结构文法，任何0型文法都是递归和可枚举的。1型文法：上下文有关文法，产生式左边至少有一个非终结符。2型文法：上下文无关文法，产生式左边只能有一个非终结符，右边无限制。3型文法：正则文法，右部可以有一个终结符和一个非终结符，或只有一个终结符。四元组（V非终结符,T终结符,P产生式,S开始符号）；3. 何为最左推导？最右推导？最左推导，在A的每次推导过程中，每一步都是对当前句型的最左变量进行替换，每一步所得为左句型，相应的归约称为最右归约；最右推导，在A的每次推导过程中，每一步都是对当前句型的最右变量进行替换，每一步所得为右句型，相
3、应的归约称为最左归约。4、 掌握正则表达式及其生成语言的定义，熟练掌握正则表达式的三种基本运算，会根据语言写出正则表达式，或者反过来写出指定的正则表达式生成的语言的特征。1. 从各选择对象中选择，用元字符表示。比如： a|b；2. 连结，由并置表示。比如： ab；3. 重复或“闭包”，由元字符*表示。比如： a*；例题：给出下面语言的相应文法:L1=an bn | n1 L2=anbm+nam | n1，m0 G1： SAB AaAb | ab BbBa | G1： AaAb |ab 5、 掌握DFA及其可接受的语言的定义，会根据语言画DFA图，或者反过来写出指定的DFA图可接受的语言的特征。
4、例子：为正规式（a|b）*a(a|b) 构造一个等价的确定的有限自动机。a,baab012解答：5、 掌握用代码实现DFA的两种算法，熟练掌握基于转换表的算法。 例子：给定下列自动机：其中：开始状态：0 终止状态：2aaa0bbb12(1)把此自动机转换为确定自动机DFA。 (2)给出此DFA的正则表达式。解答：（1）： 有状态矩阵如图： a b0 01 201 01 22 1 2 1 2a b 0 0,1 2 1 2 2 1 2从而可得DFA如图：-02aaba101bbb极小化后：02babb1a（2）此DFA的正则表达式为： (aa*bb)(bab)* 或 a*b（bab）*。6、 掌握
5、正则表达式和DFA图，了解词法分析程序。例题：给定文法GS： SaA|bQ； AaA|bB|b；BbD|aQ ；QaQ|bD|b；DbB|aA ；EaB|bF FbD|aE|b构造相应的最小的DFA 。 解：先构造其NFA： 用子集法将NFA确定化： abSAQAABZQQDZBZQDDZABDABBQD 将S、A、Q、BZ、DZ、D、B重新命名，分别用0、1、2、3、4、5、6表示。因为3、4中含有z，所以它们为终态。ab012113224325416516625 令P0（0,1,2,5,6,3,4）用b进行分割： P1（0,5, 6,1,2,3,4）再用b进行分割： P2（0,5, 6,1
6、,2,3,4）再用a、b 进行分割，仍不变。 再令为A，1，2为B，3，4为C，5，6为D。 最小化为右上图。2、 掌握文法的二义性概念，会识别和消除文法的二义性。例题：设有文法GS: SS(S)S|，该文法是否为二义文法？说明理由。 答：是二义的，因为对于（）（）可以构造两棵不同的语法树。 S S S ( S ) S S ( S ) S S ( S ) S S ( S ) S 消除下列文法GE的左递归。EE-TTTT/FFF( E )i解答：消除文法GE的左递归后得到：ETEE -TETFTT/FTF( E )i说明下面文法GS是二义性文法：SSaS|SbS|cSd|eS|f例子：fafbf
7、是文法GS的一个句子，并且有两个不同的最右推导。（1）S = SaS = SaSbS = SaSbf= Safbf= fafbf （2）S = SbS = Sbf= SaSbf = Safbf= fafbf因此说明此文法有二义性。考虑文法 GS: S (T) | a+S | a T T,S | S 消除左递归公式：AAa|bAbAAaA| 消除文法的左递归及提取公共左因子。解：消除文法GS的左递归： S(T) | a+S | a TST T,ST| 提取公共左因子： S(T) | aS S+S | TST T,ST| b) 计算First集合和Follow集合的算法；例题：对文法G(S)：S
8、a | | (T)；T T，S | SS-#S#;)lastvt(T)(=,#=(2) 是算符优先文法，因为任何两个终结符之间至多只有一种优先关系。(3) 给出输入串(a,a)#的算符优先分析过程。步骤 栈当前输入字符剩余输入串动作1#(a,a#( 移进2#(a,a)#(, 归约4#(T,a)#T, 移进5#(T,a)#,) 归约7#(T,T）#,) 归约8#(T)#(=) 移进9#(T)#)# 归约10#T#接受d)LL(1)分析算法；例子：设有文法G（S）：SaBc|bABAaAb|bBb| 求各产生式的FIRST集，FOLLOW(A)和FOLLOW(B),以及各产生式的SELECT集。
9、构造LL(1)分析表，并分析符号串baabbb是否是。解：（1）FIRST(aBc)=a, FIRST(bAB)=b FIRST(aAb)=a, Ab: FIRST(Ab)=b, Bb: FIRST(b) = b, FIRST()= FOLLOW(A)=b,#, FOOLOW(B)=c,#SELECT(SaBc)=a, SELECT(SbAB) =b, SELECT(AaAb)=a, SELECT(Ab)=b, SELECT(Bb)=b, SELECT(B)=c, #因此，所得的LL(1)分析表如表A-4所示。表A-4 LL(1)分析表输入VN输入符号abc#SSaBcSbABAAaAbAbB
10、BbBB（2）分析符号串baabbb成功，baabbb是该文法的句子，如图A-16所示。图A-16 识别串baabbb的过程1、 掌握判断一个上下文无关文法是否为LL(1)文法的充分必要条件，并会对指定的文法进行判断。例题：设将文法G改写成等价的LL(1)文法，并构造预测分析表。 G：SS*aT|aT|*aT； T+aT|+a 解：消除左递归后的文法G: SaTS|*aTSS*aTS|T+aT|+a 提取左公因子得文法G:SaTS|*aTSS*aTS|T+aTTT| Select(SaTS)=aSelect(S*aTS)=*Select(SaTS)Select(S*aTS)=Select(S*aTS)=*Select(S)=Follow(s)=#Select(S*aTS)Select(S)= Select(T+aT)=+Select(TT)=First(T) =+Select(T )=Follow(T)=*,#Select(TT)Select(T)= 所以该文法是LL(1)文法。预测分析表： *+a#S*aTSaTSS*aTST+aTT T （五）语义分析理解三元式，四元式，逆波兰式等中间代码表示
