编译原理 文法

第三章文法和语言本章的目的是为语言的语法描述寻求工具通过这个工具，可以达到以下目的：工具要对源语言（程序 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 语言）给出精确无二义的语法描述,要求严谨、简洁、易读根据语言文法的特点来指导语法分析的过程。从描述语言的文法可以自动构造出可用的语法分析程序。制导语义翻译文法的直观概念和语言概述 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，对于含有无穷句子的语言，存在着如何给出它的有穷表示的问题。自然语言无法列出全部句子，但可以给出一些规则，用这些规则来说明(或者定义)句子的组成结构，用EBNF来表示这种句子的构成规则：EBNF表示句子的构成规则〈句子〉∷=〈主语〉〈谓语〉〈主语〉∷=〈代词〉｜〈名词〉〈代词〉∷=我｜你｜他〈名词〉∷=王明｜大学生｜工人｜英语〈谓语〉∷=〈动词〉〈直接宾语〉〈动词〉∷=是｜学习〈直接宾语〉∷=〈代词〉｜〈名词〉导出句子首先去找∷=左端的带有〈句子〉的规则并把它由∷=右端的符号串代替，这个动作表示成：〈句子〉〈主语〉〈谓语〉然后在得到的串〈主语〉〈谓语〉中，选取〈主语〉或〈谓语〉，再用相应规则的∷=右端代替之。比如，选取了〈主语〉，并采用规则〈主语〉∷=〈代词〉，那么得到：〈主语〉〈谓语〉〈代词〉〈谓语〉，重复做下去，即可得到一个句子。【例】句子：“我是大学生”的全部动作过程是：〈句子〉〈主语〉〈谓语〉〈代词〉〈谓语〉我〈谓语〉我〈动词〉〈直接宾语〉我是〈直接宾语〉我是〈名词〉我是大学生句子构成规则“我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则。这些规则成为判别句子结构合法与否的依据，这些规则是一种元语言，用它描述汉语。这里仅仅涉及汉语句子的结构描述。其中一种起描述作用的元语言称为文法。语言概述语言是由句子组成的集合，是由一组符号所构成的集合。汉语－所有符合汉语语法的句子的全体英语－所有符合英语语法的句子的全体程序设计语言－所有该语言的程序的全体每个句子构成的规律研究语言每个句子的含义每个句子和使用者的关系语言概述研究程序设计语言每个程序构成的规律每个程序的含义每个程序和使用者的关系语言研究的三个方面语法（Syntax）：表示构成语言句子的各个记号之间的组合规律语义（Semantics）：表示各个记号的特定含义。（各个记号和记号所表示的对象之间的关系）语用（Pragmatics）：表示在各个记号所出现的行为中，它们的来源、使用和影响。语言概述每种语言具有两个可识别的特性，即语言的形式和该形式相关联的意义。语言的实例若在语法上是正确的，其相关联的意义可以从两个观点来看，其一是该句子的创立者所想要表示的意义，另一是接收者所检验到的意义。这两个意义并非总是一样的，前者称为语言的语义，后者是其语用意义。幽默、双关语和谜语就是利用这两方面意义间的差异。形式语言如果不考虑语义和语用，即只从语法这一侧面来看语言，这种意义下的语言称作形式语言。形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述。形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。语言的一般描述程序设计语言是由一切程序所组成的集合，而程序是由保留字，字母和数字这样一些基本符号所组成，从字面上看，每个程序都是一个“基本符号”串，设有一基本符号集，那么程序设计语言可看成是在这个基本符号集上定义的、按一定规则构成的一切基本符号串组成的集合.定义和记号符号：可以相互区别的记号（元素）。字母是符号，数字也是符号。字母表∑：符号（元素）的非空有穷集合。因此字母表也称为符号集。不同的语言可以有不同的字母表，例如汉语的字母表中包括汉字、数字及标点符号等。C语言的字母表是由字母、数字、若干专用符号。定义和记号符号串：由字母表中的符号组成的任何有穷序列称为符号串.例如001110是字母表=｛0，1｝上的符号串.字母表A=｛a,b,c｝上的一些符号串有：a,b,c,ab,aaca。在符号串中，符号的顺序是很重要的，符号串ab就不同于ba,abca和aabc也不同。可以使用字母表示符号串，如x=STR表示“x是由符号S、T和R，并按此顺序组成的符号串”。符号串的长度：如果某符号串x中有m个符号，则称其长度为m，表示为｜x｜=m，如001110的长度是6。空符号串：即不包含任何符号的符号串，用ε表示，其长度为0，即｜ε｜=0。符号串的运算符号串的头、尾、固有头和固有尾：如果z=xy是一符号串，那么x是z的头，y是z的尾，如果x是非空的，那么y是固有尾；同样如果y非空，那么x是固有头。例:设z=abc,那么z的头是ε,a,ab,abc,除abc外，其它都是固有头；z的尾是ε,c,bc,abc,z的固有尾是ε,c,bc。当对符号串z=xy的头感兴趣而对其余部分不感兴趣时，采用省略写法：z=x…；如果只是为了强调x在符号串z中的某处出现，则可表示为：z=…x…；符号t是符号串z的第一个符号，则表示为z=t…。符号串的运算符号串的连接：设x和y是符号串，它们的连接xy是把y的符号写在x的符号之后得到的符号串.由于ε的含义，显然有εx=xε=x。例如x=ST，y=abu，则它们的连接xy=STabu，看出｜x｜=2，｜y｜=3，｜xy｜=5符号串的方幂：符号串自身连接n次得到的符号串an定义为aa…aa（n个a），a1=a,a2=aa且a0=ε例；若x=AB则:x0=εx1=ABx2=ABABx3=ABABABxn=xxn-1=xn-1x(n>0)符号串的运算符号串集合：若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。两个符号串集合A和B的乘积定义为AB=xy|xA且yB若集合A=ab,cde集合B=0,1则AB=ab1,ab0,cde0,cde1使用*表示上的一切符号串（包括ε）组成的集合,称为Σ的闭包。上的除ε外的所有符号串组成的集合记为+,称为Σ的正闭包。例：Σ={a,b}Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}Σ+={a,b,aa,ab,ba,bb,aaa,aab,…}定义和记号语言是由句子组成的集合，是由一组符号所构成的集合。换言之,字母表上的一个语言是上的一些符号串的集合(字母表上的每个语言是*的一个子集)。例如：字母表Σ={a,b},Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}集合{ab,aabb,aaabbb,…,anbn,…}或表示为{w|w∈Σ*且w=anbn,n≥1}为字母表上的一个语言。集合{a,aa,aaa,…}或表示为{w|w∈Σ*且w=an,n≥1}为字母表上的一个语言。ε是一个语言，即是一个语言。语言上的有关运算设L是上的一个语言,M是上的一个语言,语言L和M的并，交，差，补是一个语言。语言L和M的并为LM，是一个语言:{w|wisinLorisinM}如：L1={a,b,…y,z}M1={1,2…8,9}L1M1={a,b,…y,z，1,2…8,9}语言L和M的连接是一个语言，记为LMLM={st|s∈L且t∈M}如：L1M1={a1,b1,…y1,z1,a2,b2…a9…z9}有Lε=εL=L。L的n次连接Ln=LL...L语言上的运算语言L的闭包记为L*，L*=L0L1L2...L0=ε，Ln=LLn-1=Ln-1L,n1语言L的正闭包记为L+，L+=L1L2L3...L+=LL*=L*L，L*=L+ε如：L1={a,b,…y,z}M1={1,2…8,9}（L1M1）={a,b,…y,z，1,2…8,9}（L1M1）*={a,b,…y,z，1,2…8,9，aa,1a,…xyz,6789st..}L1（L1M1）*={所有字母打头的字母和数字符号串}文法和语言的形式定义如何来描述一种语言？如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示如果语言是无穷的，找出语言的有穷表示。语言的有穷表示有两个途经：生成方式（文法）：语言中的每个句子可以用严格定义的规则来构造。识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要麽能停止并回答“不是”，（要麽永远继续下去。）文法和语言的形式定义文法即是通过生成方式描述语言的：语言中的每个句子可以用严格定义的规则来构造。下面给出文法的定义。进而在文法定义的基础上，给出推导的概念，句型、句子和语言的定义。文法的定义文法G定义为四元组(VN，VT，P，S)其中VN为非终结符号(或语法实体，或变量)集；VT为终结符号集；P为产生式(也称规则)的集合；VN，VT和P是非空有穷集。S称作识别符号或开始符号，它是一个非终结符，至少要在一条产生式中作为左部出现。VN和VT不含公共的元素，即VN∩VT=φ用V表示VN∪VT，称为文法G的字母表或字汇表规则，也称产生式或生成式，是形如α→β或α∷=β的(α，β)有序对，其中α是字母表V的正闭包V+中的一个符号，β是V*中的一个符号。α称为规则的左部，β称作规则的右部。文法的定义例:文法G=（VN，VT，P，S）VN={S},VT={0,1}P={S→0S1,S→01}S为开始符号文法的定义例文法G=（VN，VT，P，S）VN={标识符，字母，数字}VT={a,b,c,…x,y,z,0,1,…,9}P={<标识符>→<字母><标识符>→<标识符><字母><标识符>→<标识符><数字><字母>→a,…,<字母>→z<数字>→0,…,<数字>→9}S=<标识符>文法的习惯写法－只写出产生式1G：S→aAb,A→ab,A→aAb,A→ε2G[S]：S→aAb,A→ab,A→aAb,A→ε3G[S]:S→aSb,A→ab|aAb|ε大写字母：非终结符小写字母：终结符推导的定义1直接推导“”如果α→β是文法G的产生式，γ和δ是V*中的任意符号，若有v,w满足：v=γαδ,w=γβδ则称v直接产生w,或说w是v的直接推导，也称w直接归约到v，记作vw例：G：S→0S1，S→010S100S1100S11000S111000S11100001111S0S1推导的定义2若存在直接推导的序列：v=w0w1...wn=w(n>0)则称这个序列是一个从v至w的长度为n的推导(简称推导)。或说v推导出w（推导长度为n）,或说w归约到v.如果n≥1,记为vw如果n≥0,记为vw(若有vw，或v=w)推导的定义2例：G：S→0S1，S→010S100S1100S11000S111000S11100001111S0S100S11000S11100001111S00001111S0000111100S11=>*00S11句型、句子的定义句型:有文法G，若S=>*x，则称x是文法G的句型。句子:有文法G，若S=>*x，且x∈VT*，则称x是文法G的句子。例：G：S→0S1，S→01S0S100S11000S11100001111G的句型：S,0S1,00S11,000S111,00001111G的句子：00001111,01句型、句子的定义例：G[E]：E→E+T|TT→T*F|FF→(E)|aEE+TT+TF+Ta+Ta+T*Fa+F*Fa+a*Fa+a*a则该文法的句子：用符号a，+，*，()构成的算术表达式语言的定义由文法G生成的语言记为L(G),它是文法G的一切句子的集合:L(G)={x|S=>*x，S为文法开始符号，且x∈VT*}例：G：S→0S1，S→01L(G)={0n1n|n≥1}语言的定义例:文法G[S]：（1）S→aSBE（2）S→aBE（3）EB→BE（4）aB→ab（5）bB→bb（6）bE→be（7）eE→eeL(G)={anbnen|n≥1}语言的定义SaSBE(S→aSBE)aaBEBE(S→aBE)aabEBE(aB→ab)aabBEE(EB→BE)aabbEE(bB→bb)aabbeE（bE→be)aabbee（eE→ee)G生成的每个串都在L(G)中L(G)中的每个串确实能被G生成语言的定义使用产生式(1)n-1次，得到推导序列：S=>*an-1S(BE)n-1，然后使用产生式(2)1次，得到：S=>*an-1S(BE)n-1an(BE)n。然后从an(BE)n继续推导，总是对EB使用产生式(3)的右部进行替换，而最终在得到的串中，所有的B都先于所有的E。例如，若n=3,aaaBEBEBEaaaBBEEBEaaaBBEBEEaaaBBBEEE。即有：S=>*anBnEn接着，使用产生式(4)一次，得到S=>*anbBn-1En，然后使用产生式(5)n-1次得到：S=>*anbnEn，最后使用产生式(6)一次，使用产生式(7)n-1次，得到：S=>*anbnen也能 证明 住所证明下载场所使用证明下载诊断证明下载住所证明下载爱问住所证明下载爱问 ，对于n≥1，串anbnen是唯一形式的终结符号串文法的等价若L(G1）=L（G2），则称文法G1和G2是等价的。文法G1[A]：A→0R与G2[S]：S→0S1等价A→01S→01R→A1文法的类型通过对产生式施加不同的限制，Chomsky将文法分为四种类型：0型文法：对任一产生式α→β，都有α∈(VN∪VT)*，且至少要包含一个非终结符,β∈(VN∪VT)*1型文法：对任一产生式α→β，都有|β|≥|α|，仅仅S→ε除外2型文法：对任一产生式α→β，都有α∈VN，β∈(VN∪VT)*3型文法：任一产生式α→β的形式都为A→aB或A→a，其中A∈VN，B∈VN，a∈VT文法的类型－1型文法例：1型（上下文有关）文法文法G[S]：S→CDAb→bAC→aCABa→aBC→bCBBb→bBAD→aDC→εBD→bDD→εAa→bD文法的类型－2型文法例：2型（上下文无关）文法文法G[S]：S→ABA→BS|0B→SA|1文法的类型－3型文法G[S]：S→0A|1B|0A→0A|1B|0SB→1B|1|0G[I]：I→lTI→lT→lTT→dTT→lT→d文法的类型2型文法1型文法0型文法四种文法之间的逐级“包含”关系3型文法文法和语言0型文法产生的语言称为0型语言1型文法或上下文有关文法（CSG）产生的语言称为1型语言或上下文有关语言（CSL）2型文法或上下文无关文法（CFG）产生的语言称为2型语言或上下文无关语言（CFL）3型文法或正则（正规）文法（RG）产生的语言称为3型语言正则（正规）语言（RL）文法和语言四种文法之间的关系是将产生式做进一步限制而定义的。语言之间的关系依次：有不是上下文有关语言的0型语言，有不是上下文无关语言的1型语言，有不是正则语言的上下文无关语言。文法和识别系统间的关系0型文法（短语结构文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且任何0型语言都是递归可枚举的1型文法（上下文有关文法）：产生式的形式为α1Aα2→α1βα2，即只有A出现在α1和α2的上下文中时，才允许β取代A。其识别系统是线性界限自动机。文法和识别系统间的关系2型文法（上下文无关文法CFG）：产生式的形式为A→β，β取代A时与A的上下文无关。其识别系统是不确定的下推自动机。3型文法（正规文法RG）：产生的语言是有穷自动机（FA）所接受的集合文法描述文法G=(｛E｝,｛+,*,i,(,)｝,P,E)其中P为：{E→i,E→E+E,E→E*E,E→(E)}E表示算术表达式,i表示程序的“变量”，该文法定义了由变量，+，*,()组成的算术表达式的语法结构，即：变量是算术表达式；若E1和E2是算术表达式，则E1+E2，E1*E2和(E1)也是算术表达式描述一种简单赋值语句的产生式：〈赋值语句〉→i∶=E描述条件语句的产生式：〈条件语句〉→if〈条件〉then〈语句〉｜if〈条件〉then〈语句〉else〈语句〉句型、推导G[E]：E→E+T|TT→T*F|FF→(E)|aEE+TT+TF+Ta+Ta+T*Fa+F*Fa+a*Fa+a*aEE+TE+T*FE+T*aE+F*aE+a*aT+a*aF+a*aa+a*aEE+TT+TT+T*FF+T*FF+F*Fa+F*Fa+F*aa+a*a规范推导规范句型最左（最右）推导：在推导的任何一步αβ，其中α、β是句型，都是对α中的最左（右）非终结符进行替换最右推导被称为规范推导。由规范推导所得的句型称为规范句型语法树设G=(VN,VT,P,S)为一CFG，若一棵树满足下列4个条件，则此树称作G的语法树(推导树)(派生树）：1.每个结点都有一个标记，此标记是V的一个符号2.根的标记是S3.若一结点n至少有一个它自己除外的子孙，并且有标记A，则肯定A∈VN4.如果结点n有标记A,其直接子孙结点从左到右的次序是n1，n2，…，nk，其标记分别为A1，A2，…，Ak，那么A→A1A2，…，Ak一定是P中的一个产生式语法树－句型推导的表示给定文法G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的语法树(推导树)定理：G为上下文无关文法，对于α≠ε，有S=>*α，当且仅当文法G有以α为结果的一棵语法树(推导树)语法树的构造G=((S,A),(a,b),P,S)P:1.S->aAS2.A->SbA3.A->SS4.S->a5.A->baSaASSbAaaba句子aabbaa的推导过程S=>aAS=>aAa=>aSbAa=>aSbbaa=>aabbaaS=>aAS=>aSbAS=>aabAS=>aabbaS=>aabbaaS=>aAS=>aSbAS=>aSbAa=>aabAa=>aabbaa如果在推导的任何一步αβ(句型)，都是对α中的最左(最右)非终结符进行替换，则称这种推导为最左(最右)推导.在形式语言中，最右推导被称为规范推导.右规范推导得到的句型称为规范句型语法树构造EE+TT+TF+Ta+Ta+T*Fa+F*Fa+a*Fa+a*aEE+TE+T*FE+T*aE+F*aE+a*aT+a*aF+a*aa+a*aEE+TT+TT+T*FF+T*FF+F*Fa+F*Fa+F*aa+a*aEE+TTT*FFFaaa看不出句型中的符号被替代的顺序G[E]：E→E+T|TT→T*F|FF→(E)|a语法树实例例:G[S]:S→aASA→SbAA→SSS→aA→baSaASSbAaaba句型aabbaa的语法树（推导树）叶子结点：树中没有子孙的结点。从左到右读出推导树的叶子标记连接成的文法符号串，为G[S]的句型。也把该推导树称为该句型的语法树。上下文无关文法的语法树推导过程中施用产生式的顺序例:G[S]:S→aASA→SbAA→SSS→aA→baSaASSbAaabaSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa语法树问题一棵语法树表示了一个句型的种种可能的(但未必是所有的)不同推导过程，包括最左(最右)推导。但是，一个句型是否只对应唯一的一棵语法树呢?一个句型是否只有唯一的一个最左(最右)推导呢?语法树问题例：G[E]:E→iE→E+EE→E*EE→(E)EE+EE*EiiiEE*EiE+Eii句型i*i+i的两个不同的最左推导：推导1：EE+EE*E+Ei*E+Ei*i+Ei*i+i推导2：EE*Ei*Ei*E+Ei*i+Ei*i+i二义文法若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的。判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的，但可以为无二义性寻找一组充分条件二义文法文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法G和G′，其中G是二义的，但是却有L(G)=L(G′)，也就是说，这两个文法所产生的语言是相同的。如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。二义文法二义文法改造为无二义文法G[E]:E→iG[E]：E→T|E+TE→E+ET→F|T*FE→E*EF→（E）|iE→(E)规定优先顺序和结合律句型的分析句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序。分析算法又称识别算法。从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号，直到分析结束。句型的分析算法分类自上而下分析法：从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导。从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串句型的分析算法分类自下而上分析法：从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。是从输入符号串开始，以它做为语法树的结果，自底向上地构造语法树自上而下的语法分析例：文法G：S→cAdA→abA→a识别输入串w=cabd是否为该文法的句子SSScAdcAdab推导过程：ScAdcAdcabd自下而上的语法分析例：文法G：S→cAdA→abA→a识别输入串w=cabd是否该文法的句子SAAcabdcabdcabd规约过程构造的推导：cAdcabdScAd自上而下的语法分析(1)S→cAd(2)A→ab(3)A→a识别输入串w=cabd是否为该文法的句子若ScAd后选择(3)扩展A，ScAdcad那将会w的第二个符号可以与叶子结点a得以匹配，但第三个符号却不能与下一叶子结点d匹配,分析失败,识别程序不能为串cabd构造语法树，即cabd不是句子.自下而上的语法分析(1)S→cAd(2)A→ab(3)A→a识别输入串w=cabd是否为该文法的句子对串cabd的分析中，如果不是选择ab用产生式(2)而是选择a用产生式(3)将a归约到了A，那么最终就达不到归约到S的结果，因而也无从知道cabd是一个句子句型分析的有关问题在自上而下的分析方法中如何选择使用哪个产生式进行推导？假定要被代换的最左非终结符号是B，且有n条规则：B→A1|A2|…|An，那么如何确定用哪个右部去替代B？在自下而上的分析方法中如何识别可归约的串？在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”。句柄文法G[S]句型的短语SαAδ且Aβ，则称β是句型αβδ相对于非终结符A的短语句型的直接短语若有Aβ，则称β是句型αβδ相对于非终结符A的直接短语句型的句柄一个句型的最左直接短语称为该句型的句柄例：i*i+i的短语、直接短语和句柄EE+TTFT*Fi3短语：i1*i2+i3，i1*i2，Fi2i1，i2，i3。i1直接短语：i1，i2，i3。句柄：i1G[E]：E→E+T|TT→T*F|FF→(E)|i句型：i*i+i化简文法文法中不含有有害规则和多余规则有害规则：形如U→U的产生式。会引起文法的二义性多余规则：指文法中任何句子的推导都不会用到的规则，此规则在文法中以两种形式出现：1.文法中某些非终结符不在任何规则的右部出现，该非终结符称为不可到达的。2.文法中某些非终结符，由它不能推出终结符号串，该非终结符称为不可终止的。化简文法例：G[S]：1.S→Be2.B→CeD为不可到达3.B→AfC为不可终止4.A→Ae5.A→e6.C→Cf7.D→f产生式2，6，7为多余规则应去掉。非终结符条件对于文法G[S]，为了保证任一非终结符A在句子推导中出现，必须满足如下两个条件：1.A必须在某句型中出现即有SαAβ，其中α，β属于V*2.必须能够从A推出终结符号串t来即At，其中t∈VT*上下文无关文法中的ε规则上下文无关文法中某些规则可具有形式A→ε，称这种规则为ε规则因为ε规则会使得有关文法的一些讨论和证明变得复杂,有时会限制这种规则的出现两种定义的唯一差别是ε句子在不在语言中文法构思的启示是要找出语言的有穷描述，而如果语言L有一个有穷的描述，则L1=L∪｛ε｝也同样有一个有穷的描述，并且可以证明，若L是上下文有关语言、上下文无关语言或正规语言，则L∪｛ε｝和L-｛ε｝分别是上下文有关语言、上下文无关语言和正规语言。