资源描述:
《编译原理--总复习》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、编译原理总复习认真复习,重点是掌握基本概念。基本概念掌握了,相当一部分试题的解就有了。习题与试题的目的区别:习题的目的是通过反复的练习理解、掌握所学知识,会有不少繁、难、大量步骤的题;试题的目的是考察对本课程综合掌握的情况,特点是短时间内覆盖大量内容。太繁琐步骤或太难等需要耗费大量时间的题是不可能出的,大部分应该是基本概念题,但也会有一些综合性的题目。自己要会辨别什么是主要的什么是次要的,抓什么丢什么。“基本概念要严谨(清楚),基本方法要灵活”。复习内容包括核心算法和重要概念(不再详细点出):复习:什么是语言,什么是文法?掌握由文法求语言和由语言求文法,重点复习课
2、本的几道例子和课后作业的几个习题请问“我是大学生”是否是该语言的句子?〈句子〉::=〈主语〉〈谓语〉〈主语〉::=〈代词〉
3、〈名词〉〈代词〉::=你
4、我
5、他〈名词〉::=王明
6、大学生
7、工人
8、英语〈谓语〉::=〈动词〉〈直接宾语〉〈动词〉::=是
9、学习〈直接宾语〉::=〈代词〉
10、〈名词〉〈句子〉〈主语〉〈谓语〉〈代词〉〈谓语〉我〈谓语〉我〈动词〉〈直接宾语〉我是〈直接宾语〉我是〈名词〉我是大学生请问下列是否是句子:我是大学生、王明是大学生、王明学习英语、他学习英语、你是工人复习:学会求闭包,正闭包:•符号串集合:若集合A中一切元素都是某字母表S上的符号串,则称A为字
11、母表S上的符号串集合。•两个符号串集合A和B的乘积定义为AB={xy
12、x属于A且y属于B}若集合A={a,b}B={c,d}则AB={ac,ad,bc,bd}{ε}A=A{ε}=A(∵εx=xε=x)•使用S*表示S上的所有有穷长的串(包括ε)的集合。Σ*称为Σ的闭包。•从S*中除去ε得到的集合记为S+。Σ+称为Σ的正闭包。Σ*=Σ0∪Σ1∪Σ2…∪Σn…Σ+=Σ1∪Σ2…∪Σn…Σ*=Σ0∪Σ+Σ+=ΣΣ*=Σ*ΣΣ+=Σ*-{ε}例:设Σ={0,1},则Σ*={ε,0,1,00,01,10,11,000,001,010,…}例:设Σ={a,b},则Σ*={ε,
13、a,b,aa,ab,ba,bb,aaa,aab,…}Σ+={a,b,aa,ab,ba,bb,aaa,aab,…}复习:弄清楚什么是正规式、什么是正规文法、什么是语言、什么是正规集正规式和正规文法的互换,请看课本例题(1)将正规式转换成正规文法•例求正规式a(a
14、d)*的正规文法解:分析过程如下:S-->>aAA-->>(a
15、d)*A-->>(a
16、d)BA→εB-->(a
17、d)BB→ε所以最终的正规文法为:SàaAA->(a
18、d)B
19、εB->(a
20、d)B
21、ε例子2:已知正规文法G1的产生式,求出它所定义的正规式。产生式为:S→aS
22、aBB→bB
23、bAA→cA
24、c解:
25、(1)S=aS
26、aBB=bB
27、bAA=cA
28、c(2)根据定理2由S=aS
29、aB得S=a*aB=a+B同理由B=bB
30、bA得B=b+A由A=cA
31、c得A=c+代入得B=b+c+,S=a+b+c+。故正规式为S=a+b+c+。例3:考虑文法G[S]:S→aSbS
32、bSaS
33、ε(1)试用最左推导说明此文法的二义性。(2)对于句子abab构造两个相应的最右推导。(3)对于句子abab构造两棵相应的分析树。(4)此文法所产生的语言是什么?解答:(1)句子abab有如下两个不同的最左推导:S=>aSbS=>abS=>abaSbS=>ababS=>abab S=>aSbS=>
34、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组成的字符串复习:识别二义文法,懂得转换二义文法为无二义文法判断一个语法是否为二义文法(重点)Ø若一个文法存在某个句子对应两棵不同的语法树,则称这个文法是二义的。或者,若一
35、个文法存在某个句子有两个不同的最左(右)推导,则称这个文法是二义的。Ø产生某上下文无关语言的每一个文法都是二义的,则称此语言是先天二义的。•判定任给的一个上下文无关文法是否二义,或它是否产生一个先天二义的上下文无关语言,这两个问题是递归不可解的。但可以为无二义性寻找一组充分条件。•二义文法改造为无二义文法(重点)G[E]:E→iG[E]:E→T
36、E+TE→E+ET→F
37、T*FE→E*EF→(E)
38、iE→(E)注意:必须规定优先顺序和结合律复习:大家要理解DFA和NFA的含义,两者之间的区别和联系,以及两者怎样转化;最后应该理解描述一个词法的DFA是否是唯一的,怎样
39、把他化为最