《编译原理第03章文法和语言.ppt》由会员分享，可在线阅读，更多相关《编译原理第03章文法和语言.ppt（72页珍藏版）》请在金锄头文库上搜索。
1、1编译原理编译原理文法和语言文法和语言华东交通大学华东交通大学软件学院网络工程教研室软件学院网络工程教研室万仲保万仲保Tel:704682113907097766E-mail:2第三章 文法和语言v本章目的本章目的为语言的语法描述寻求工具为语言的语法描述寻求工具w工具要对程序设计语言给出精确无二义的语法描述。（严工具要对程序设计语言给出精确无二义的语法描述。（严谨、简洁、易读）谨、简洁、易读）v形式工具形式工具-形式语言抽象地定义为一个数学形式语言抽象地定义为一个数学系统。系统。“形式形式”是指这样的事实：语言的是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来所有规则只以什麽符号串能
2、出现的方式来陈述。陈述。3v3.1文法的直观概念v3.2符号和符号串v3.3文法和语言的形式定义v3.4文法的类型v3.5上下文无关文法及其语法树v3.6句型分析v3.7实用说明第三章第三章文法和语言文法和语言4文法的直观概念文法的直观概念v一个程序设计语言是一个记号系统，如同自然语言一样，它的完整的定义应包括语法和语义两个方面。所谓一个语言的语法是指一组规则，用它可以形成和产生一个合适的程序。目前广泛使用的手段是上下文无关文法，即用上下文无关文法作为程序设计语言语法的描述工具。语法只是定义什么样的符号序列是合法的，与这些符号的含义毫无关系v阐明语法的一个工具是文法，这是形式语言理论的基本概念
3、之一。v示例：汉语句子的描述v语言概述5汉语句子的描述汉语句子的描述v语法规则定义v字符串的判断6语法规则定义语法规则定义句子=主语谓语主语=代词名词代词=我你他名词=王明大学生工人英语谓语=动词直接宾语动词=是学习直接宾语=代词名词7字符串的判断字符串的判断v有了一组规则以后，按照如下方式用它们导出句子：开始去找=左端的带有句子的规则并把它由=右端的符号串代替，这个动作表示成：句子主语谓语，v然后在得到的串主语谓语中，选取主语或谓语，再用相应规则的=右端代替之。比如，选取了主语，并采用规则主语=代词，v那么得到：主语谓语代词谓语，重复做下去。v句子：“我是大学生”的全部动作过程是：句子主语谓
4、语代词谓语我谓语我动词直接宾语我是直接宾语我是名词我是大学生8字符串的判断字符串的判断v“我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据，换句话说，这些规则看成是一种元语言，用它描述汉语。这里仅仅涉及汉语句子的结构描述。其中一种描述元语言称为文法。9符号和符号串v定义：符号：可以相互区别的记号（元素）。字母表（）：符号（元素）的非空有穷集合。符号串：由字母表中的符号组成的任何有穷序列称为该字母表上的符号串。1.空符号串(没有符号的符号串)是上的符号串2.若x是上的符号串,a是的元素,则xa是上的符号串3.y是上的符号
5、串,当且仅当它可以由1和2导出。例如： =a,b,a,b,aa,ab,aabba都是上的符号串v符号串的运算10符号串的运算符号串的运算v既然将语言定义为一个集合，那么有关集合的运算也适合语言。即：设L是（上的）一个语言,M是（上的）一个语言，则语言L和M的并，交，差，补是一个语言。符号串的头、尾、子串符号串的长度符号串的连接符号串的方幂符号串的集合11符号串的头、尾、子串符号串的头、尾、子串v符号串s的头（前缀）：移走符号串s尾部的零个或多于零个符号得到的符号串。如：b是符号串banana的一个前缀.v符号串s的尾（后缀）：删去符号串s头部的零个或多于零个符号得到的符号串。如:nana是符号
6、串banana的一个后缀.v符号串s的子串：从s中删去一个前缀和一个后缀得到的符号串。如:ana是符号串banana的一个子串.v对于每个符号串s，s和两者都是符号串s的前缀，后缀和子串。v符号串s的真前缀，真后缀，真子串：任何非空符号串x,相应地，是s的前缀，后缀或子串，并且sx。12v符号串中符号的个数。符号串中符号的个数。v符号串符号串s的长度记为的长度记为|s|。v的长度为的长度为0符号串的长度符号串的长度13符号串的连接符号串的连接v设设x x、y y是符号串，则是符号串，则x x、y y的连接是把的连接是把y y的符的符号写在号写在x x的符号之后得到的符号串的符号之后得到的符号串
7、xyxy如如 x=ab,y=cd x=ab,y=cd 则则 xy=abcdxy=abcd有有a = aa = a14符号串的方幂符号串的方幂v方幂：设x是符号串，把x自身连接n次得到的符号串z，即z=aaaa称为符号串x的方幂。写作z=anv示例：a1=a, a2=aaa0=15符号串集合符号串集合v若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。v两个符号串集合A和B的乘积定义为：AB=xy|xA且yB若集合A=ab,cde B=0,1，则AB=ab1,ab0,cde0,cde1v使用*表示上的所有有穷长符号串（包括）组成的集合。*称为的闭包。v上的除外的所有符号串组
8、成的集合记为+。+称为的正闭包。* =012 n + =12 n * =+ + =* =*16文法和语言的形式定义v文法和语言的形式定义文法的定义推导的定义句型（子）的定义语言的定义文法等价的定义17语言概述语言概述v语言是由句子组成的集合，是由一组符号所构成的集合。语言是由句子组成的集合，是由一组符号所构成的集合。v汉语汉语-所有符合汉语语法的句子的全体所有符合汉语语法的句子的全体v英语英语-所有符合英语语法的句子的全体所有符合英语语法的句子的全体v每个句子构成的规律每个句子构成的规律v语言研究语言研究每个句子的含义每个句子的含义v每个句子和使用者的关系每个句子和使用者的关系每个程序构成的规
9、律每个程序构成的规律v研究程序设计语言研究程序设计语言每个程序的含义每个程序的含义每个程序和使用者的关系每个程序和使用者的关系语法语法Syntaxv语言研究的三个方面语言研究的三个方面语义语义Semantics语用语用Pragmatics18程序设计语言程序设计语言v研究程序设计语言研究程序设计语言每个程序构成的规律每个程序构成的规律每个程序的含义每个程序的含义每个程序和使用者的关系每个程序和使用者的关系v语言研究的三个方面语言研究的三个方面语法语法Syntax语义语义Semantics语用语用Pragmatics19语言研究的三个方面v语法-表示构成语言句子的各个记号之间的组合规律v语义-表
10、示各个记号的特定含义。（各个记号和记号所表示的对象之间的关系）v语用-表示在各个记号所出现的行为中，它们的来源、使用和影响。v每种语言具有两个可识别的特性，即语言的形式和该形式相关联的意义。v语言的实例若在语法上是正确的，其相关联的意义可以从两个观点来看，其一是该句子的创立者所想要表示的意义，另一是接收者所检验到的意义。这两个意义并非总是一样的，前者称为语言的语义，后者是其语用意义。幽默、双关语和谜语就是利用这两方面意义间的差异。20文法的定义文法的定义v文法G定义为四元组(VN，VT，P，S)其中VN为非终结符号(或语法实体，或变量)集；VT为终结符号集；P为产生式(也称规则)的集合；VN，
11、VT和P是非空有穷集。S称作识别符号或开始符号，它是一个非终结符，至少要在一条产生式中作为左部出现。vVN和VT不含公共的元素，即VNVT=v通常用V表示VNVT，称为文法G的字母表或字汇表。v规则规则，也称重写规则重写规则、产生式产生式或生成式生成式，是形如或=的(，)有序对，其中是字母表V的正闭包V+中的一个符号，是V*中的一个符号。称为规则的左部，称作规则的右部。v示例：例3.1例3.221例例3.1v文法G=（VN，VT，P，S），VN=S,VT=0,1，P=S0S1,S01。这里，非终结符集中只含一个元素S；终结符集由两个元素0和1组成；有两条产生式；开始符号是S。22例例3.2v文
12、法G=(VN，VT，P，S)v其中VN=标识符，字母，数字VT=a,b,c,，x,y,z,0,1,，9vP=标识符字母标识符标识符字母标识符标识符数字字母a字母b字母z数字0数字1数字9S=标识符这里，使用尖括号和括起非终结符。23推导的定义v直接推导“”：如是文法G=(Vn，VT，P，S)的规则(或说是P中的一产生式)，和是V*中的任意符号，若有符号串v，w满足：v=，w=则说v(应用规则)直接产生w，或者说，w是v的直接推导直接推导，也可以说，w直接归约直接归约到v，记作vw。v如果存在直接推导的序列：v示例：直接推导多步推导24直接推导的示例v对于例3.1的文法G，可以给出直接推导的一些
13、例子如下：v=0S1,w=0011，直接推导：0S10011，使用的规则：S01，这里=0，=1。v=S,w=0S1，直接推导：S0S1使用的规则：S0S1，这里=，=v=0S1,w=00S11，直接推导：0S100S11，使用的规则：S0S1，这里=0，=1。v对于例3.2的文法G，直接推导的例子有：vv=标识符，w=标识符字母，直接推导：标识符标识符字母，使用的规则：标识符标识符字母，这里=vv=标识符字母数字，w=字母字母数字，直接推导：标识符字母数字字母字母数字，使用的规则：标识符字母。这里=，字母数字。vv=abc数字，w=abc5，直接推导：abc数字abc5,使用的规则：数字5，
14、这里=abc,=。25多步推导的示例多步推导的示例v对例3.1的文法，存在直接推导序列v=0S100S11000S11100001111=w，即0S100001111，也可记作0S100001111v对例3.2的文法，存在直接推导序列v=标识符标识符数字字母数字x数字x1=w，即x1，也可记作x1。26句型(子)的定义v设GS是一文法，如果符号串x是从识别符号推导出来的，即有Sx，则称x是文法GS的句型句型。若x仅由终结符号组成，即Sx，xVT*，则称x为GS的句子句子。v例：S，0S1，000111都是例3.1的文法G的句型，其中000111是G的句子。标识符字母，字母数字，a1等都是例3.
15、2文法G的句型，其中a1是G的句子。27语言的定义v文法G所产生的语言定义为集合x|Sx，其中S为文法识别符号，且xVT*。可用L(G)表示该集合。v从定义可以看出两点：第一，符号串x可从识别符号推出，也即x是句型。第二，x仅由终结符号组成，即x是文法G的句子。也就是说，文法描述的语言是该文法一切句子的集合。v例：例3.1 G： S0S1，S01L(G)=0n1n|n1例3.328例例3.3v设G=(VN，VT，P，S)，VN=S,B,E，VT=a,b,e，P由下列产生式组成：(1)SaSBE(2)SaBE(3)EBBE(4)aBab(5)bBbb(6)bEbe(7)eEeev则L（G）=an
16、bnen|n129文法的等价v若L（G1）=L（G2），则称文法G1和G2是等价的。v示例：文法G1A：A0R A01 RA1与G2S：S0S1 S01等价。 30文法的类型v乔姆斯基分类v示例：例3.4例3.5v乔姆斯基分类文法之间关系v对应于乔姆斯基分类文法的语言v文法和语言之间的关系31乔姆斯基对文法的分类乔姆斯基对文法的分类v通过对产生式施加不同的限制，Chomsky（乔姆斯基）将文法分为四种类型：0型文法：对文法G=(VN，VT，P，S)的任一产生式，都有(VNVT)*且至少含有一个非终结符，(VNVT)*。1型文法（上下文有关文法）上下文有关文法） ：对文法G=(VN，VT，P，S
17、)的任一产生式，都有|， 仅仅 S除外。2型文法（上下文无关文法）上下文无关文法）：对文法G=(VN，VT，P，S)的任一产生式，都有VN ， (VNVT)* 。3型文法（正规文法正规文法）：设G=(VN，VT，P，S)，若P中的每一个产生式的形式都是AaB或Aa，其中A和B都是非终结符，a是终结符。3型文法G=(VN，VT，P，S)的P中的规则有两种形式：一种是前面定义的形式，即：AaB或Aa其中A，BVN ，aVT*，另一种形式是：ABa或Aa，前者称为右线性文法，后者称为左线性文法。正规文法所描述的是VT*上的正规集。32例例3.43.4vG=(S,A,B,a,b,P,S)，其中P由下列
18、产生式组成：SaB AbAA SbA BbAa BbS AaS BaBB或将P改写为：SaB|bA AbA|a Aa|AaS BbS|BaB|bv则G是正规文法或3型文法。33例例3.53.5v文法G=(S,A,B,0,1,P,S)，其中P由下列产生式组成：S0A A1B S1B B1BS0 B1 A0A B0 A0S或将P改写为：S0A|1B|0A0S|1B|0AB1B|1|0 v则G是正规文法或3型文法。34乔姆斯基分类文法之间关系乔姆斯基分类文法之间关系2型文法型文法1型文法型文法0型文法型文法四种四种文法文法之间之间的的逐级逐级“包含包含”关系关系3型文法型文法35对应乔姆斯基分类文法
19、的对应乔姆斯基分类文法的语言v0型文法产生的语言称为0型语言。v1型文法或上下文有关文法（ CSG ）产生的语言称为1型语言或上下文有关语言（CSL）。v2型文法或上下文无关文法（ CFG ）产生的语言称为2型语言或上下文无关语言（CFL）。 v3型文法或正则（正规）文法（ RG）产生的语言称为3型语言正则（正规）语言（RL）。 36文法和语言之间的关系文法和语言之间的关系v四种文法之间的关系是将产生式做进一步限制而定义的。v语言之间的关系依次：有不是上下文有关语言的0型语言，有不是上下文无关语言的1型语言，有不是正则语言的上下文无关语言。37上下文无关文法及其语法树v语法树句型能够构造关联语
20、法树的条件示例：例3.7v最左（右）推导v二义性文法判断依据示例：例3.8二义性文法与二义性语言的区别38句型能够构造关联语法树的条件句型能够构造关联语法树的条件v给定文法G=(VN，VT，P，S)，对于G的任何句型都能构造与之关联的语法树(推导树)。这棵树满足下列4个条件：每个结点都有一个标记，此标记是V的一个符号。根的标记是S。若一结点n至少有一个它自己除外的子孙（子结点），并且有标记A，则A肯定在VN中。如果结点n的直接子孙，从左到右的次序是结点n1，n2，nk，其标记分别为A1，A2，Ak，那么AA1A2Ak一定是P中的一个产生式。39例例3.7G=(S,A,a,b,P,S)，其中P为
21、：SaASASbAASSSaAba右图是G（aabbaa）的一棵推导树。40最左（右）推导最左（右）推导v如果在推导的任何一步，其中，是句型，都是对中的最左(最右)非终结符进行替换，则称这种推导为最左(最右)推导。v在形式语言中，最右推导常被称为规范推导。由规范推导所得的句型称为规范句型。v最左推导示例SaASaSbASaabASaabbaSaabbaav最右推导示例SaASaAaaSbAaaSbbaaaabbaa41二义文法的判断依据判断依据v若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的。v如果
22、产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。v判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的，即，不存在一个算法，它能在有限步骤内，确切判定任给的一个文法是否为二义的。我们所能做的事是为无二义性寻找一组充分条件(当然它们未必都是必要的)。42例例3.8v文法G=(E,+,*,i,(,),P,E)其中P=EiEE+EEE*EE(E)是二义性的，假若规定了运算符“+”与“*”的优先顺序和结合规则，即按惯例，让“*”的优先性高于“+”，且它们都服从左结合，那么就可以构造出一个无二义文法。v定义表达式的无二义文法GE：ET
23、|E+TTF|T*FF(E)|i它和上述文法产生的语言是相同的。即它们是等价的。43二义性文法与二义性语言的区别二义性文法与二义性语言的区别v文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法G和G，其中G是二义的，但是却有L(G)=L(G)，也就是说，这两个文法所产生的语言是相同的。44句型的分析v句型分析句型分析是识别一个输入符号串是否为语法上正确的程序的过程。在语言的编译实现中，把完成句型分析的程序称为分析程序分析程序或识别程序识别程序，分析算法又称识别算法。v从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号，直
24、到分析结束。v句型的分析算法分类v句型的分析算法反映语法树的构造过程v句型分析的有关定义v句型分析的有关问题45句型的分析算法分类v自上而下分析法：是从文法的开始符号出发，反复使用各种产生式，寻找“匹配”于输入符号串的推导。示例：例3.9v自下而上分析法：从输入符号串开始，逐步进行“归约”，直至归约到文法的开始符号。示例46两种方法反映语法树的构造过程v自上而下方法：自上而下方法是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的末端结点符号串正好是输入符号串。v自下而上方法：自下而上方法是从输入符号串开始，以它做为语法树的末端结点符号串，自底向上地构造语法树。47例例3.9：
25、自上而下分析：自上而下分析例：考虑文法GS；ScAdAabAa识别输入串w=cabd是否该文法的句子。推导过程：推导过程：ScAdcabd48示例：自下而上分析示例：自下而上分析例：例：考虑文法GS；ScAdAabAa识别输入串w=cabd是否该文法的句子。SAAcabdcabdcabd规约规约过程构造的推导：过程构造的推导：cAdcabdScAd49句型分析的有关定义句型分析的有关定义v令G是一文法，S是文法的开始符号，是文法G的一个句型。如果有：SA且A则称是句型相对于非终结符A的短语短语。特别，如有A则称是句型相对于规则A的直接短语直接短语(也称简单短语简单短语)。一个句型的最左直接短语
26、称为该句型的句柄句柄。v示例v从句型的推导树中查找方法50示例示例v文法GE的一个句型i*i+i。为了叙述方便，将句型改写为i1*i2+i3。因为有：EF*i2+i3且Fi1则称i1是句型i1*i2+i3的相对于非终结符F的短语，也是相对于规则Fi的直接短语。又有：Ei1*F+i3且Fi2则i2是句型i1*i2+i3的相对于F的短语，也是相对于规则Fi的直接短语，还有：Ei1*i2+F且Fi3则i3也是句型i1*i2+i3的相对于F的短语，也是相对于规则Fi的直接短语。ET*i2+i3，且Ti1则i1是句型i*i2+i3的相对于T的短语。Ei1*i2+T且Ti3则i3是句型i1*i2+i3的相
27、对于T的短语。EE+i3且Ei1*i2则i1*i2是句型i1*i2+i3的相对于E的短语。EE且Ei1*i2+i3则i1*i2+i3是句型i1*i2+i3相对于E的短语。即i1，i2，i3，i1*i2和i1*i2+i3都是句型i1*i2+i3的短语，而且i1，i2，i3均为直接短语，其中i1是最左直接短语，即句柄。v虽然i2+i3是句型i1*i2+i3的一部分，并不是它的短语，因为尽管有Ei2+i3，但不存在从文法开始符号E到i1*E的推导。51从句型的推导树中查找方法从句型的推导树中查找方法v从句型的推导树上很容易找出句型的短语和直接短语。v设A是句型的某一子树的根，其中是形成此子树的末端结
28、点的符号串，则其中是句型的相对于A的短语。若这个子树只有一层分支，则是句型的直接短语。v示例52示例：推导树中找短语示例：推导树中找短语53句型分析的有关问题v在自上而下的分析方法中如何选择使用哪个产生式进行推导？假定要被代换的最左非终结符号是B，且有n条规则：BA1|A2|An，那么如何确定用哪个右部去替代B？v在自下而上的分析方法中如何识别可归约的串？在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”。v存在确定和不确定分析。54实用说明实用说明v有关文法的实用限制有关文法的实用限制v上下文无关文法中的上下文无关文法中的规则规则v无用符号和
29、无用产生式的消除无用符号和无用产生式的消除v-产生式的消除产生式的消除v单产生式的消除单产生式的消除55有关文法的实用限制v在实用中，我们将限制文法中不得含有有害规则和多余规则：有害规则，是指形为UU的产生式。它对描述语言显然是没有必要的。说它有害，是说它只会引起文法的二义性。多余规则，是指文法中那些连一个句子的推导都用不到的规则，这类规则在文法中以两种形式出现。一种是文法中某些非终结符不在任何规则的右部出现，所以任何句子的推导中不可能用到它。v对文法G=(VN，VT，P，S)来说，为了保证其任一非终结符A在句子推导中出现，必须满足如下两个条件：A必须在某句型中出现。即有SA，其中，属于(VT
30、VN)*。必须能够从A推出终结符号串t来。即At，其中tVT。v若程序设计语言的文法包含有多余规则时，其中必定有错误存在，因此检查文法是否包含多余规则是很有必要的。56上下文无关文法中的规则v上下文无关文法中某些规则可具有形式A，称这种规则为规则。v规则会使得有关文法的一些讨论和证明变得复杂,有时会限制这种规则的出现。v上下文无关文法的相关定理定理3.1定理3.257定理3.1v若L是由文法G=(VN，VT，P，S)产生的语言，P中的每一个产生式的形式均为A，其中AVN，(VNVT)*(即可能为)，则L能由这样一种文法产生：每一个产生式或者为A形式，其中AVN，(VNVT)+(即)，或者 S且
31、 S不出现在任何产生式右边。58定理3.2v如果如果G=G=(VN，VT，P，S)是一个上下文有关文法，是一个上下文有关文法，则存在另一个上下文有关文法则存在另一个上下文有关文法G G1 1，它所产生，它所产生的语言与的语言与G G产生的相同，即产生的相同，即L(G)=L(GL(G)=L(G1 1) )，其中，其中G G1 1的开始符号不出现在的开始符号不出现在G G1 1的任何产生式的右的任何产生式的右边。边。v若若G G为上下文无关文法或正规文法，类似结为上下文无关文法或正规文法，类似结论成立。论成立。59无用符号和无用产生式的消除无用符号和无用产生式的消除v定义：设G=(VN，VT，P，
32、S)是一文法，我们说G中的一个符号x(VNVT)是有用的指x至少出现在一个句子的推导过程中。即x必须同时满足以下两个条件：存在、V*，有S*x存在wVT*,x*w否则就说x是无用的。如果一个产生式的左部或右部含有无用符号，则此产生式称之为无用产生式。v消除算法算法1算法2v示例60算法算法1v1、分别置VN(1)和P(1)为；v2、对于P中的每一产生式A，若VT*，则将A置于VN(1)中；v3、对于P中的每一产生式Ax1x2xm若每个xi都属于VN(1)或VT，则将A置于VN(1)；v4、重复步骤3，直到VN(1)不再增大为止；v5、对于P中的每一产生式By1y2yn，若B及每一个yi都属于V
33、N(1)VT，则将此产生式By1y2yn置于P(1)。61算法算法2v1、分别置VN、VT和P为；v2、将文法的开始符号S置入VN中；v3、对于G(1)中任何形如Ax1|x2|xm的产生式，若AVN，则将符号串x1，x2，xm中的全部非终结符号置于VN中，而将其中的全部终结符号置于VT中；v4、重复步骤3，直到VN和VT都不再增大为止；v5、将P中左右部仅含VNVT中符号的所有产生式置P。62示例示例v文法的定义已知文法G=（S,U,V,W，a,b,c，P，S），产生式P的组成如下：SaS SW SU UaVbV Vac WaWv执行算法1v执行算法263执行算法执行算法1v第一步，由于产生式
34、Ua、 Vac的右部均为终结符号串，故置VN(1)=U，V；v第二步，对于产生式SU ，由于UVN(1)，故将S置于中，所以VN(1)=S，U，V；v于是得到以下文法G1：vG1=（S,U,V,a,b,c,P(1),S），其中P(1)由如下产生式组成：SaS SU UaVbV Vac64执行算法执行算法2v第一步，置VN=S；v第二步，因为G1中含有产生式SU、Ua，故应将U、a分别置于，即VN=S，UVT=a;v因此得到等价的且不含无用符号和无用产生式的文法为G2=（S，U，a，P，S），其中，P由如下产生式组成：SaSSUUa65-产生式的消除v算法3v算法4（不属于文法所产生的语言）v算
35、法5（属于文法所产生的语言）v示例：不属于文法所产生的语言属于文法所产生的语言66算法算法3v1、作集合W1=A|产生式AP；v2、作集合序列WK+1=WKUB|BP,且WK+；K1并使WK+1收敛；v令W=WK+1,则对于每一个AW，有A*。v对于上述对于上述W，如果，如果G中不含有可能导出中不含有可能导出的符号，则的符号，则W= 。67算法算法4v1、利用算法3，可将分VN为两个不相交的子集：W和VN-W；v设AX1X2Xm是P中的任一产生式，则按以下规则将所有形如AY1Y2Ym的产生式置入P中：（1）若XiVNW，则取Yi=Xi；（2）若XiW，则Yi分别取Xi和，若所有的均Xi属于W，
36、则不将所有Yi的取。68不属于文法所产生的语言不属于文法所产生的语言v已知文法G=（S,A,B,C，a,b,c，P，S），产生式P的组成如下：SaAABCBbBCcCBCv执行算法3，得到W=A,B,Cv执行算法4，可得到P如下：对于SaA,将产生式SaA、Sa放入P；对于ABC,将产生式ABC、AB、AC放入P；对于BbB，将产生式BbB、Bb放入P；对于CcC，将产生式CcC、Cc放入P。v则消除-产生式之后的文法的产生式如下：SaASaABCABACBbBBbCcCCc69算法算法5v1、引入新的符号S（SVNUVT）作为G的开始符号，令=VNUS；v2、作产生式集vP=PUS|产生式S
37、Pv3、对文法G=（VN，VT，P，S）执行算法4消去P中全部-产生式。v4、将S加入到所得的产生式集中。70属于文法所产生的语言属于文法所产生的语言v已知文法G=（S,A,B，a,b,c，P，S），产生式P的组成如下：ScSSABAaAbBBbABv引入新的符号S；v作产生式集P=PUScS,SABv利用算法4消去P中的-产生式，并加入S，得到全部的产生式如下：ScSScSABSASBSScSScSABSASBAaAbAabBBbBb71单产生式的消除v算法：1、设A=A1,A2,An，对于每一个Ai，作集合序列W1(Ai)=AiWK+1(Ai)=WK(Ai)UD|CD,CWK(Ai),DVN，并使其收敛为Wi。构造产生式集P=Ai|产生式BP，BWi，VN，此时P中不含有单产生式。v示例72示例：示例：单产生式的消除v已知文法G=（S,A,B，a,b，P，S），产生式P的组成如下：SASBSABAaAbBBbAabBbv对于G，执行算法得到：W(S)=S,A,BW(A)=AW(B)=Bv由此可构造产生式集P如下：SABSaAbSabSBbSbAaAbAabBBbBb
