编译原理--总复习

《编译原理--总复习》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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、把他化为最