编译原理总复习认真复习，重点是掌握基本概念。基本概念掌握了，相当一部分试题的解就有了。习题与试题的目的区别：习题的目的是通过反复的练习理解、掌握所学知识，会有不少繁、难、大量步骤的题；试题的目的是考察对本课程综合掌握的情况，特点是短时间内覆盖大量内容。太繁琐步骤或太难等需要耗费大量时间的题是不可能出的，大部分应该是基本概念题，但也会有一些综合性的题目。自己要会辨别什么是主要的什么是次要的，抓什么丢什么。“基本概念要严谨（清楚），基本方法要灵活”。复习内容包括核心算法和重要概念（不再详细点出）：复习：什么是语言，什么是文法？掌握由文法求语言和由语言求文法，重点复习课本的几道例子和课后作业的几个习题请问“我是大学生”是否是该语言的句子？〈句子〉::=〈主语〉〈谓语〉〈主语〉::=〈代词〉|〈名词〉〈代词〉::=你|我|他〈名词〉::=王明|大学生|工人|英语〈谓语〉::=〈动词〉〈直接宾语〉〈动词〉::=是|学习〈直接宾语〉::=〈代词〉|〈名词〉〈句子〉〈主语〉〈谓语〉〈代词〉〈谓语〉我〈谓语〉我〈动词〉〈直接宾语〉我是〈直接宾语〉我是〈名词〉我是大学生请问下列是否是句子：我是大学生、王明是大学生、王明学习英语、他学习英语、你是工人复习：学会求闭包，正闭包：•符号串集合：若集合A中一切元素都是某字母表S上的符号串，则称A为字母表S上的符号串集合。•两个符号串集合A和B的乘积定义为AB={xy|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}，则Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}Σ+={a,b,aa,ab,ba,bb,aaa,aab,…}复习：弄清楚什么是正规式、什么是正规文法、什么是语言、什么是正规集正规式和正规文法的互换，请看课本例题（1）将正规式转换成正规文法•例求正规式a(a|d)*的正规文法解：分析过程如下：S-->aAA-->(a|d)*A-->(a|d)BA→εB-->(a|d)BB→ε所以最终的正规文法为：SaAA->(a|d)B|εB->(a|d)B|ε例子2：已知正规文法G1的产生式，求出它所定义的正规式。产生式为：S→aS|aBB→bB|bAA→cA|c解：（1）S=aS|aBB=bB|bAA=cA|c(2)根据定理2由S=aS|aB得S=a*aB=a+B同理由B=bB|bA得B=b+A由A=cA|c得A=c+代入得B=b+c+,S=a+b+c+。故正规式为S=a+b+c+。例3：考虑文法G[S]：S→aSbS|bSaS|ε(1)试用最左推导说明此文法的二义性。(2)对于句子abab构造两个相应的最右推导。(3)对于句子abab构造两棵相应的分析树。(4)此文法所产生的语言是什么？解答：(1)句子abab有如下两个不同的最左推导：S=>aSbS=>abS=>abaSbS=>ababS=>ababS=>aSbS=>abSaSbS=>abaSbS=>ababS=>abab所以此文法是二义性的。(2)句子abab的两个相应的最右推导：（推导过程请不要偷工减料）S=>aSbS=>aSbaSbS=>aSbaSb=>aSbab=>ababS=>aSbS=>aSb=>abSaSb=>abSab=>abab(3)句子abab的两棵分析树：(a)(b)(4)此文法产生的语言是：在{a，b}上由相同个数的a和b组成的字符串复习：识别二义文法，懂得转换二义文法为无二义文法判断一个语法是否为二义文法（重点）若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的。产生某上下文无关语言的每一个文法都是二义的，则称此语言是先天二义的。•判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的。但可以为无二义性寻找一组充分条件。•二义文法改造为无二义文法（重点）G[E]:E→iG[E]：E→T|E+TE→E+ET→F|T*FE→E*EF→（E）|iE