资源描述：
《编译原理复习大纲lk》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、1、理解编译器的概念，掌握编译器的功能，熟练掌握编译器的主要翻译步骤。了解与编译器相关的程序及其功能编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析，中间代码生成,代码优化等几个基本阶段,同时还会伴有表格处理和出错处理.@@2、扫描器功能,理论依据，它完成任务是什么？扫描器的任务是从源程序中识别出一个个单词符号，编译程序对源程序或中间代码程序从头到尾扫描一次，找到单词。@@5.符号表用法如、符号表中的信息栏中登记了每个名字的有关的性质，它有那些内容？名字、符号种类、类型、地址、扩展属性指针。@@6.能画出程序框图，了解其
2、功能，能叙述编译的基本结构@@2、文法的集中类型和主要特点.如文法有几种类型各自特点？一个文法组成部分？0型文法：短语结构文法，任何0型文法都是递归和可枚举的。1型文法：上下文有关文法，产生式左边至少有一个非终结符。2型文法：上下文无关文法，产生式左边只能有一个非终结符，右边无限制。3型文法：正则文法，右部可以有一个终结符和一个非终结符，或只有一个终结符。四元组（V[非终结符],T[终结符],P[产生式],S[开始符号]）；@@3.何为最左推导？最右推导？最左推导，在A的每次推导过程中，每一步都是对当前句型的最左变量进行替换，每一步
3、所得为左句型，相应的归约称为最右归约；最右推导，在A的每次推导过程中，每一步都是对当前句型的最右变量进行替换，每一步所得为右句型，相应的归约称为最左归约。@@4、掌握正则表达式及其生成语言的定义，熟练掌握正则表达式的三种基本运算，会根据语言写出正则表达式，或者反过来写出指定的正则表达式生成的语言的特征。1.从各选择对象中选择，用元字符｜表示。比如：a
4、b；2.连结，由并置表示。比如：ab；3.重复或“闭包”，由元字符*表示。比如：a*；@@例题：给出下面语言的相应文法:L1={anbn
5、n≥1}L2={anbm+nam
6、n≥1，m≥
7、0}G1：S→ABA→aAb
8、abB→bBa
9、εG1：A→aAb
10、ab5、掌握DFA及其可接受的语言的定义，会根据语言画DFA图，或者反过来写出指定的DFA图可接受的语言的特征。例子：为正规式（a
11、b）*a(a
12、b)构造一个等价的确定的有限自动机。a,baabÞ012解答：@@5、掌握用代码实现DFA的两种算法，熟练掌握基于转换表的算法。例子：给定下列自动机：其中：开始状态：0终止状态：2aaÞa0bbb12(1)把此自动机转换为确定自动机DFA。(2)给出此DFA的正则表达式。解答：（1）：有状态矩阵如图：abÞ001201012
13、－21212abÞ00,1212－212Þ从而可得DFA如图：-Þ02aaba101bbb极小化后：Þ02babb1a@@（2）此DFA的正则表达式为：(aa*b½b)(b½ab)*或a*b（b½ab）*。@@5、掌握正则表达式和DFA图，了解词法分析程序。例题：给定文法G[S]：S→aA
14、bQ；A→aA
15、bB
16、b；B→bD
17、aQ；Q→aQ
18、bD
19、b；D→bB
20、aA；E→aB
21、bFF→bD
22、aE
23、b构造相应的最小的DFA。解：先构造其NFA：用子集法将NFA确定化：abSAQAABZQQDZBZQDDZABDABBQD将S、A、Q、
24、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,2｝,｛3,4｝）再用a、b进行分割，仍不变。再令｛０｝为A，｛1，2｝为B，｛3，4｝为C，｛5，6｝为D。最小化为右上图。@@2、掌握文法的二义性概念，会识别和消除文法的二义性。例题：设有文法G[S]:S→S(S)S
25、ε，该文法
26、是否为二义文法？说明理由。答：是二义的，因为对于（）（）可以构造两棵不同的语法树。SSS(S)SS(S)SεεS(S)SS(S)Sεεεεεεεε@@消除下列文法G[E]的左递归。E→E-T∣TT→T/F∣FF→(E)∣i解答：消除文法G[E]的左递归后得到：E→TE’E’→-TE’∣εT→FT’T’→/FT’∣εF→(E)∣i@@说明下面文法G[S]是二义性文法：S→SaS
27、SbS
28、cSd
29、eS
30、f例子：fafbf是文法G[S]的一个句子，并且有两个不同的最右推导。（1）S=>SaS=>SaSbS=>SaSbf=>Safbf=>f
31、afbf（2）S=>SbS=>Sbf=>SaSbf=>Safbf=>fafbf因此说明此文法有二义性。@@考虑文法G[S]:S→(T)
32、a+S
33、aT→T,S
34、S消除左递归公式：A→Aa
35、bA→bA'A'→aA'
36、ε消除文法的左递归及提
