形式语言简介课件.ppt

1、v语言的的定义可以从两个方面进行：语言的的定义可以从两个方面进行：）从）从产生产生语言的角度；语言的角度；）从）从接收接收(或或识别识别)语言的角度。语言的角度。v产生一个语言，目的就是根据语言中的产生一个语言，目的就是根据语言中的基本句子基本句子和句子的和句子的形成规则形成规则，得到，得到(产生产生)该语言所包含的该语言所包含的所有句子所有句子。v这是这是形式语言形式语言所研究的问题。所研究的问题。v接收一个语言，目的就是使用某种接收一个语言，目的就是使用某种自动自动机模型机模型来来接收接收句子，该模型所接收的所句子，该模型所接收的所有句子，也形成一个语言。有句子，也形成一个语言。v这是这是

2、自动机自动机所研究的问题。所研究的问题。1.6 常用术语v(1)用用 代表空串，代表空串，代表仅含有代表仅含有空串的集合。空串的集合。v(2)用用代表空集，表示一个元素代表空集，表示一个元素都不包含的集合。都不包含的集合。v(3)用用 代表字母表。代表字母表。常用术语（续）v(4)用用代表两个字符串代表两个字符串与与的连接的连接（并置）。（并置）。v若若=a1a2a3an,=b1b2b3bm;则则=a1a2a3anb1b2b3bm。v显然，显然，=v(5)用用AB代表集合代表集合A与与B的连接。的连接。A=a1,a2,a3,an,B=b1,b2,b3,bm；vAB=a1b1，a1b2，a1b3

3、，a1bm，a2b1，a2b2，a2b3，a2bm，a3b1，a3b2，a3b3，a3bm，anb1，anb2，anb3，anbm 注意：v A=A=。v6)An代表集合代表集合A的的n次连接：次连接：A的的n次次幂幂定义为：定义为：(1)A0=(2)An=An-1A n 1v7)A*代表集合代表集合A上所有字符串的集上所有字符串的集合。合。即表示集合即表示集合A中的所有字符串进行中的所有字符串进行任意次连接而形成的串的集合。任意次连接而形成的串的集合。A*称为集合称为集合A的闭包（克林闭包）。的闭包（克林闭包）。A*=A0 A1 A2 An 例1-11 A=0，1v A0=即即长度为长度为0

4、的的0和和1组成的串的集合组成的串的集合vA1=A=0,1 v即即长度为长度为1的的0和和1组成的串的集合组成的串的集合vA2=AA=00,01,10,11 即即长度为长度为2的的0和和1组成的串集合组成的串集合v A3=A2A =000,001,010,011,100,101,110,111 即即长度为长度为3的的0和和1组成的串的集合组成的串的集合vv A*=A0 A1 A2 An =0和和1 组成的所有的串组成的所有的串 =w|w是是0和和1 组成的串组成的串v如果串如果串是集合是集合A的闭包中的串，的闭包中的串，也称也称是集合是集合A上的串上的串。v对于任何集合对于任何集合A 有有(A

5、*)*=A*。v8)A+代表一个集合，称为代表一个集合，称为A的正闭的正闭包，包，vA+=AA2A3An。A*与 A+vA*=A+A0 v即即vA*=A+语言的形式定义v设设 是一个是一个字母表字母表，L L *,L L称为称为字母表字母表 上上的一个的一个语言语言,w w L L,w,w称为语言称为语言L L的一个的一个句子句子。2.1 例子语言v括号匹配串的语言。括号匹配串的语言。该语言是指所有的左括号和右括号相该语言是指所有的左括号和右括号相匹配的串的集合；匹配的串的集合；()，()，()()等等都是该语言的句子等等都是该语言的句子 )(，()等等不是该语言的句子。等等不是该语言的句子。

6、v如何如何产生产生这个语言呢？这个语言呢？即如何即如何产生产生该语言所有句子呢？该语言所有句子呢？v实际上，就是需要给出语言中句子的实际上，就是需要给出语言中句子的构构造（形成）规则造（形成）规则。v递归定义递归定义提供了语言的良好的定义方式，提供了语言的良好的定义方式，使得语言中的句子的构造规律较明显。使得语言中的句子的构造规律较明显。v可以使用多种方法可以使用多种方法描述描述构造规则。构造规则。v自然语言自然语言的描述方式，采用如下的的描述方式，采用如下的 递归规则：递归规则：()是该语言的最基本的句子；是该语言的最基本的句子；若若S是句子是句子,则则(S)是句子；是句子；若若S是句子是句

7、子,则则SS是句子；是句子；v这些规则称为这些规则称为形成规则形成规则，根据这些规则，根据这些规则，可以可以 (1)产生该语言的任意的句子；产生该语言的任意的句子；(2)判断某个判断某个串串是否是该语言的句子。是否是该语言的句子。例如v可以产生句子可以产生句子（）（）而推断串而推断串 （）（）不是句子。不是句子。v规则规则(的个数的个数)是有限的，但可以产生无是有限的，但可以产生无限个句子和长度无限的句子；限个句子和长度无限的句子；v因为规则是因为规则是递归递归的。的。BNF的描述方式v巴科斯和诺尔采用的巴科斯和诺尔采用的巴科斯巴科斯-诺尔范式（诺尔范式（BNF-Backus-Naur For

8、m）描述规则描述规则：v:=()v:=v:=()vChomsky采用的符号化采用的符号化(形式化形式化)的描述的描述方式，运用如下的规则（这些规则被称方式，运用如下的规则（这些规则被称为为产生式产生式）：）：S()S(S)SSS v“”读作读作“定义为定义为”或者或者“是是”，v它的左边和右边分别称为该产生式的它的左边和右边分别称为该产生式的左左边边和和右边右边；v根据根据产生式产生式 可以生成任意句子；可以生成任意句子；可以判断一个串是否为句子可以判断一个串是否为句子(语法分析语法分析)。v产生句子的过程为：产生句子的过程为：从从S开始，反复利用产生式的右边开始，反复利用产生式的右边代替代替

9、产生式的左边（称之为推导过程），产生式的左边（称之为推导过程），最后，得到匹配的（）组成的句子。最后，得到匹配的（）组成的句子。例:句子()()()的产生过程S=S SS S=(=(S S)S)S=()=()S S=()(=()(S S)=()(=()(S SS)S)=()()=()()S S)=()()()=()()()v产生式的个数是有限的，规则是递归产生式的个数是有限的，规则是递归的，因而的，因而v所有的小括号匹配的句子（有无限个）所有的小括号匹配的句子（有无限个）均可以由它们产生，它们组成的集合均可以由它们产生，它们组成的集合就称为一个语言。就称为一个语言。vS称为非终结符，在推导过程

10、中，可以被称为非终结符，在推导过程中，可以被代替的符号。代替的符号。v(和和)称为终结符，在推导过程中，不可以称为终结符，在推导过程中，不可以被代替的符号。被代替的符号。v 是产生式系统的是产生式系统的元符号元符号，不属于非终，不属于非终结符，也不属于非终结符。结符，也不属于非终结符。v例例2-1 由偶数个由偶数个0组成的串的语言组成的串的语言 规则的自然语言描述方式：规则的自然语言描述方式：00是该语言的基本的句子；是该语言的基本的句子；若若S是句子是句子,则则SS是句子；是句子；v形式化的描述方式：形式化的描述方式：S00 SSS 问题：v将产生式将产生式SSS换成换成S0S0或者或者S0

11、0Sv是否还产生相同的语言？是否还产生相同的语言？结论：v同一个语言，可以使用不同的产生式组同一个语言，可以使用不同的产生式组合来产生。合来产生。考虑v由奇数个由奇数个1组成串的语言的产生规则。组成串的语言的产生规则。例2-2v高级程序设计语言中的包含有高级程序设计语言中的包含有+、*、/、()的算术表达式的算术表达式(的语言的语言)的产生。的产生。自然语言的描述方式单个变量是最基本的单个变量是最基本的句子句子；若若E是一个是一个句子句子，则，则EAE是一个是一个句子句子（其中（其中A代表运算符代表运算符+、-、*、/）若若E是一个是一个句子句子，则，则(E)是是句子句子；形式语言的描述方式

12、E i （i代表单个变量）代表单个变量）EEAE E(E)A+A-A*A/思考：v字母表为？字母表为？v若以若以A开始推导，则产生？开始推导，则产生？其中其中：A+，A-，A*，A/四个产生式四个产生式的左边是相同的符号，可以合并为的左边是相同的符号，可以合并为 A+|-|*|/+、-、*、/称为称为A的的侯选式侯选式。E i EEAE E(E)也可以记为：也可以记为：E i|EAE|(E)注意：v这组产生式没有表示出运算符的这组产生式没有表示出运算符的优优先级先级。v表示出运算符的优先级的产生式：表示出运算符的优先级的产生式：EE+T|E-T|T TT*F|T/F|F F(E)|iv其中：其

13、中：E E代表表达式，代表表达式，T T代表项，代表项，F F代表因子代表因子(E)(E)代表的是带小括号的表达式。代表的是带小括号的表达式。该组产生式表示出先算因子，再该组产生式表示出先算因子，再*、/，最，最后后+、-。例2-3v标识符标识符(以字母开头的字母、数字的串以字母开头的字母、数字的串)的产生的产生(仅考虑小写字母仅考虑小写字母)。ILIILIIDLa|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t u|v|w|x|y|zD0|1|2|3|4|5|6|7|8|9思考：上例是从标识符的上例是从标识符的形成角度形成角度思考问题。思考问题。从标识符的从标识符

14、的定义定义角度考虑，则？角度考虑，则？注意 D0|1|2|3|4|5|6|7|8|9不能简写为不能简写为 D0|9将I的定义加入到表达式中：EE+T|E-T|T TT*F|T/F|F F(E)|I IL|IL|ID L D 2.2 文法和语言的关系v介绍语言的定义。介绍语言的定义。v介绍文法的定义。介绍文法的定义。v介绍文法与语言的关系。介绍文法与语言的关系。再次强调：v语言就是字母表上的字符串组成语言就是字母表上的字符串组成的一个集合。的一个集合。v语言中的字符串称为语言中的字符串称为句子句子。v文法的作用就是产生一个语言。文法的作用就是产生一个语言。定义2-1 短语结构文法(文法)的定义文

15、法文法G是一个四元式，是一个四元式，G=(，V，S，P)v是一个有限字符的集合是一个有限字符的集合(字母表字母表)，它的，它的元素称为字母或者终结符；元素称为字母或者终结符；vV是一个有限字符的集合是一个有限字符的集合-非终结符集合，非终结符集合，它的元素称为变量或者非终结符；它的元素称为变量或者非终结符；vSV，称为文法的开始符号；，称为文法的开始符号；vP是有序偶对是有序偶对(，)的集合，其中的集合，其中是集是集合合(UV)上的字符串，但至少包含一个上的字符串，但至少包含一个非终结符；非终结符；是集合是集合(UV)*的元素。一的元素。一般，将有序偶对般，将有序偶对(，)记为记为，称为，称为

16、产生式；产生式；v如果有如果有，称之为空串产生式或者，称之为空串产生式或者产生式。产生式。v如果如果有有ABAB，称之为单产生式。，称之为单产生式。一个产生式的左边可能不只一个符号；一个产生式的左边可能不只一个符号；第一个产生式的左边只能有一个符号，就第一个产生式的左边只能有一个符号，就是是开始符号开始符号S。v文法文法的作用就是产生一个的作用就是产生一个语言语言。约定：如果没有特别说明,则 第一个产生式左边的符号，就是开始符第一个产生式左边的符号，就是开始符号，号，可以不为可以不为S；大写的英文字母代表非终结符；大写的英文字母代表非终结符；小写的英文字母小写的英文字母a，b，c，d，e和数字

17、和数字代表终结符；代表终结符；小写的英文字母小写的英文字母u，v，w，x，y，z代代表表 终结符串；终结符串；小写的希腊字母小写的希腊字母，代表非终结符和终代表非终结符和终结符串；结符串；推导（派生）的定义2-2v文法文法G，和和是集合是集合(UV)上的串，上的串，=pvr，=pur(p和和r可能同时为可能同时为)，v而而vu是文法是文法G的一个产生式的一个产生式,则称则称可以可以直接推导出直接推导出，记为记为=，既，既 pvr=pur。v推导的实质推导的实质 产生式的产生式的右边右边替换替换产生式的产生式的左边左边。v非终结符非终结符代表在推导的过程中可以被替代表在推导的过程中可以被替代的符

18、号，代的符号，v终结符终结符代表在推导的过程中不可以被替代表在推导的过程中不可以被替代的符号。代的符号。v推导推导的的逆逆过程称为过程称为归约归约。与与pvr=pur对应，称串对应，称串pur可以直接可以直接归约成串归约成串pvr。记为记为pvr+zv表示表示y可以经过可以经过多步多步推导出推导出z，即，即 存在串的序列存在串的序列 1，2，3，n；有有y=1，z=n，且且 i=i+1；对所有；对所有ni1。任意步推导(包括0步)vy=*z表示表示y可以经过可以经过任意步任意步推导出推导出z，即，即 y=z；或者；或者 y=+z。思考：v对于任意文法对于任意文法G：S=*S S=+S v一定都

19、成立吗一定都成立吗？最左推导和最右推导v如果在推导的过程中，如果在推导的过程中，每一步每一步都是将都是将推导产生的串的推导产生的串的最左边最左边的非终结符代的非终结符代替掉替掉-最左推导最左推导v如果每一步都是将推导产生的串的最如果每一步都是将推导产生的串的最右边的非终结符代替掉右边的非终结符代替掉-最右推导最右推导(规规范推导范推导)，v当然，还有其它方式的推导过程当然，还有其它方式的推导过程（例如混合）。（例如混合）。v而而最左推导最左推导和和最右推导最右推导是比较常用是比较常用的推导方式。的推导方式。v对于文法对于文法G，如果，如果S=*，则称，则称是是文法的一个文法的一个句型句型，v若

20、若 *,称为称为句子句子。定义2-3 语言的定义v给定文法给定文法G，有开始符号，有开始符号S，则把，则把S可以可以推导出所有句子的集合，称为由文法产推导出所有句子的集合，称为由文法产生的语言，记为生的语言，记为L(G)，即，即 L(G)=|S=*，且且*例v文法文法 G=(,),S,S,S(),S(S),SSS)产生语言产生语言 L(G)=w|w是括号匹配的串是括号匹配的串注意:v文法文法G产生语言产生语言L(G)，必须：，必须：该文法推导产生的所有该文法推导产生的所有串串都在该语都在该语言中；言中；语言中的任意一个语言中的任意一个句子句子都可以由该都可以由该文法产生。文法产生。v对于文法对

21、于文法G=(，V，S，P)约定：约定：第一个产生式左边的符号，就是开始符第一个产生式左边的符号，就是开始符号（号（可以不是可以不是S）；大写的英文字母代表非终结符大写的英文字母代表非终结符。v对于文法（对于文法（G），只需给出该文法的所），只需给出该文法的所有产生式即可。上例文法可以写成有产生式即可。上例文法可以写成 S()S(S)SSS v还可以再简单写成还可以再简单写成 S()|(S)|SS 2.3Chomsky对文法的分类v本节介绍本节介绍ChomskyChomsky对文法的分类。对文法的分类。v语言是由文法产生的，对语言的分语言是由文法产生的，对语言的分类，是根据产生语言的文法的分类类

22、，是根据产生语言的文法的分类而进行的。而进行的。0型文法对于一般的短语结构文法对于一般的短语结构文法(PSG)，G=(，V，S，P)G称为称为0型文法，对应的型文法，对应的L(G)叫作叫作0型型语言或者短语结构语言语言或者短语结构语言(PSL)、递归递归可枚举集可枚举集。1型文法v如果对于任意如果对于任意P，均有，均有|成立，则称成立，则称G为为1型文法，或型文法，或上下文上下文相关文法相关文法(CSG)。v对应的对应的L(G)叫作叫作1型语言或者上下文型语言或者上下文相关语言相关语言(CSL)。1型文法v1型文法产生式的标准形式为：型文法产生式的标准形式为：yAzyz其中：其中：AV；y,z

23、(V)*，(V)+；2型文法v如果对于任意如果对于任意P，均有，均有|且且 V成立，则称成立，则称G为为2型文法，或型文法，或上下文无关文法上下文无关文法(CFG)。v对应的对应的L(G)叫作叫作2型语言或者上下文型语言或者上下文无关语言无关语言(CFL)。3型文法v如果对于任意如果对于任意P，具有形式，具有形式 Aw，AwB 其中，其中，A，BV，w+则称则称G为为3型文法，或右线性文法型文法，或右线性文法 RLG，也可称为也可称为正则文法正则文法RG。对应的对应的L(G)叫作叫作3型语言，型语言，或右线性语言或右线性语言RLL，或正则语言或正则语言RL。v四类文法和对应的四类四类文法和对应

24、的四类语言语言之间之间是是真包含真包含关系。关系。文法分类判断方法：文法文法G=(，V，S，P)，则，则 1)G是短语结构文法；是短语结构文法；2)如果文法如果文法G的所有产生式的左边的所有产生式的左边长度长度小于等于右边长度部分，那么小于等于右边长度部分，那么G是是上下文相关文法上下文相关文法；3)如果上下文相关文法如果上下文相关文法G的所有产生式的所有产生式的左边都是的左边都是一个非终结符一个非终结符，那么，那么G是是上上下文无关文法下文无关文法；4)如果如果上下文无关文法上下文无关文法G的所有产生式的所有产生式的右边最多只有一个非终结符，且该非的右边最多只有一个非终结符，且该非终结符号只

25、能出现在最右边，那么终结符号只能出现在最右边，那么G是是正则文法正则文法。2.4文法产生语言v例例2-6 文法文法 S0S S0v该文法产生语言该文法产生语言L=0n|n0。分析 如果开始使用第如果开始使用第2个产生式个产生式S0，则，则S=0，就不能再往下进行推导了。，就不能再往下进行推导了。产生产生基本句子基本句子0；v若使用产生式若使用产生式S0S，n-1次后，则次后，则 S=0S=00S=000S=+0n-1S，使用使用S0，则，则S=+0n 这对于任何这对于任何n1都是成立的；都是成立的；v总之，该文法产生语言总之，该文法产生语言L=0n|n0。定义2-7 递归文法v一个一个上下文无

26、关文法上下文无关文法G，vAV，如果，如果 A=+A，则该文法称为，则该文法称为递归递归的文法；的文法；(A:递归递归非终结符非终结符)v递归分为递归分为直接直接和和间接间接递归。递归。v若若A=A 则称为则称为直接递归直接递归的非终结符。的非终结符。v直接递归直接递归可以从可以从产生式产生式判断。判断。v间接递归间接递归需要根据需要根据推导推导过程才能进行判过程才能进行判断。断。思考v是否可以将间接递归是否可以将间接递归转换转换为直接递为直接递归？归？v如何如何进行进行转换？转换？v基本思路：基本思路：将推导过程直接反映在产生式中将推导过程直接反映在产生式中v方法方法 代入法代入法v一个一个

27、上下文无关上下文无关文法的产生式的个文法的产生式的个数总是有限的。数总是有限的。v如果该文法是如果该文法是递归文法递归文法，则该文法，则该文法就能够产生一个就能够产生一个无穷语言无穷语言。v若一个若一个上下文无关上下文无关文法文法不是递归不是递归的的文法，则该文法产生文法，则该文法产生有穷语言有穷语言。注意 特殊形式的产生式特殊形式的产生式 AA 是递归的，可以反复利用任意多次，是递归的，可以反复利用任意多次，但对于无穷语言的产生，没有任何作用。但对于无穷语言的产生，没有任何作用。定义2-8 空串产生式的定义v形如形如A的产生式，称为的产生式，称为上下文无上下文无关关文法的空串产生式，或文法的

28、空串产生式，或产生式；产生式；AV。v空串产生式的作用就是在推导的过空串产生式的作用就是在推导的过程中，对于某个句型，省略掉能够程中，对于某个句型，省略掉能够产生产生的非终结符号。的非终结符号。v若某个若某个上下文无关上下文无关文法有文法有S(SS(S为为文法的开始符号文法的开始符号)，则，则v该文法产生的语言一定包含空句子该文法产生的语言一定包含空句子。例2-7v文法文法 S0SS0S S Sv该文法产生语言该文法产生语言L=0L=0n n|n0|n0。v思考：思考：该文法是该文法是？型文法？型文法分析v如果开始使用第如果开始使用第2 2个产生式个产生式SS，则，则S=S=，就不能再往下进行

29、推导了，就不能再往下进行推导了，v产生空句子产生空句子；v如果开始使用产生式如果开始使用产生式S0SS0S，n n次后，次后，S=0S=00S=000S=S=0S=00S=000S=+0 0n nS S 最后，使用最后，使用SS，则，则S=S=+0 0n n 这对于任何这对于任何n1n1都是成立的；都是成立的；v总之，该文法产生语言总之，该文法产生语言L=0L=0n n|n0|n0。例2-8v文法文法 SaSb Sabv该文法产生语言该文法产生语言 L=anbn|n0。分析v如果开始使用第如果开始使用第2个产生式个产生式Sab，则，则S=ab，就不能再往下进行推导了，就不能再往下进行推导了，v

30、产生基本句子产生基本句子ab；v若 使 用若 使 用 S a S b，n-1 次，则次，则S=aSb=aaSbb=*an-1Sbn-1，最后，最后，使用使用Sab，则，则S=*anbn，这对于任何，这对于任何n1都是成立的；都是成立的；v总之，该文法产生语言总之，该文法产生语言L=anbn|n0。例2-9v文法文法SaSSbSSv该文法产生语言该文法产生语言 L=a，b*。例2-10v字母表字母表aa，bb上所有对称的上所有对称的非空串非空串组成组成的语言的语言(没有中心点没有中心点)。v构造文法产生该语言。构造文法产生该语言。分析vaaaa和和bbbb是最基本的句子。是最基本的句子。v如果如

31、果S S是句子，则是句子，则aSaaSa和和bSbbSb是句子；是句子；v得到文法：得到文法：SaaSaa Sbb Sbb SaSa SaSa SbSb SbSb思考v(1)(1)文法文法 SaSaSaSa SbSb SbSb Sa Sa Sb Sbv产生的语言是什么？产生的语言是什么？思考v(2)(2)文法文法 SaSaSaSa SbSb SbSb S Sv产生的语言是什么？产生的语言是什么？练习：构造文法，产生v(1)(1)字母表字母表aa，bb上所有对称的上所有对称的非空串非空串组成的语言。组成的语言。v(2)L=wdw(2)L=wdwT T|wa,b,c|wa,b,c+。v(3)L=a

32、(3)L=an nb bn n|n|n=0=0。一般v对任意的对任意的a a,b b+，可以使用，可以使用Aab|aAbAab|aAb来产生来产生 a an nb bn n|n|n00；v对 任 意 的对 任 意 的 a,ba,b +，可 以 使 用，可 以 使 用Aa|b|aS|bSAa|b|aS|bS来产生来产生aa，bb+；v对任意的对任意的aa+，可以使用，可以使用Aa|aAAa|aA来产来产生生aan n|n|n00；v对任意的对任意的a a，bb+，可以使用，可以使用 AaAa|bAbAaAa|bAb来产生来产生 w wA Aw wT T|w wa,ba,b+注意：v不能使用不能使

33、用 AaAa2 2v代表代表 AaaAaav不能使用不能使用 AaAan n(n1)(n1)或或 AaAa+v来代表来代表 A A可以产生任意多个可以产生任意多个a a。例2-13 文法SaSBCSaSBC SaBCSaBC CBBC CBBC aBabaBab bBbbbBbb bCbcbCbc cCcccCcc v产生的语言为产生的语言为 L(G)=aL(G)=an nb bn nc cn n|n|n00。2.5 推导树v对于上下文无关文法，对于上下文无关文法，利用推导树也可以表示句型的产生利用推导树也可以表示句型的产生过程。过程。例-16 vS0B|1AvA0|0S|1AAvB1|1S|

34、0BBv对于串对于串0011的产生过程：的产生过程：推导过程v最左推导：最左推导：S=0B=00BB=001B=0011 v最右推导：最右推导：S=0B=00BB=00B1=0011推导树表示推导 S S 0 B 0 B 0 B B 0 B B 1 1 1 12.7 消除左递归v在在某些情况某些情况下下,需要消除一个无关文法中需要消除一个无关文法中的的左递归左递归。v递归的作用是产生无穷的语言，消除左递归的作用是产生无穷的语言，消除左递归，只是将递归，只是将左递归左递归改造为改造为右递归右递归。v左递归包括左递归包括直接直接的和的和间接间接的左递归。的左递归。2.7.1 消除直接左递归v直接左

35、递归的产生式形式为直接左递归的产生式形式为 AAv 其中：其中：AV，v(UV)+。v递归的产生式可以产生串递归的产生式可以产生串v的任意次连的任意次连接。接。v假设文法假设文法G的产生式形式为：的产生式形式为：AAv|wv其中其中:v,w(UV)+，且且w不包含不包含Av对于对于A，有，有 A=*wv*v增加增加B V，构造无左递归文法：，构造无左递归文法：AwB|w BvB|v 右递归右递归则则 A=*wv*或（编译采用的文法）AwB BvB|实际上，消除了实际上，消除了产生式，就得产生式，就得 AwB|w BvB|vv一般地，产生式的形式为：一般地，产生式的形式为：AAv1|Av2|Avn|w1|w2|wmv对于对于A，有，有 A=*(w1|w2|wm)(v1|v2|vn)*v增加一个新的非终结符增加一个新的非终结符B，构造无，构造无左递归文法：左递归文法：Aw1B|w2B|wmB|w1|w2|wmBv1B|v2B|vnB|v2|v2|vnv某些文法可能没有直接左递归，某些文法可能没有直接左递归，但可能会有但可能会有间接左递归间接左递归。SAa ASb|b2.7.2 消除间接左递归（自学）