第四章 Chomsky文法体系及语言之间的运算 ●在第一章中已指出对于程序的语法分析和自然 语言的处理,形式化的文法描述方式起了重要 的作用。本章介绍 Chomsky的文法体系,语言 的运算和运算的封闭性
第四章 Chomsky文法体系及语言之间的运算 ⚫ 在第一章中已指出对于程序的语法分析和自然 语言的处理，形式化的文法描述方式起了重要 的作用。本章介绍Chomsky的文法体系，语言 的运算和运算的封闭性
41 Chomsky的文法体系 411文法的分类及文法之间的关系 ●对于一般的短语结构文法PsG=(∑,V,S,P), 产生式的形式是v→W,其中:v∈(∑UV),且 至少包含一个非终结符;w∈(∑UV)*
⚫ 4.1 Chomsky的文法体系 ⚫ 4.1.1 文法的分类及文法之间的关系 ⚫ 对于一般的短语结构文法PSG=(∑，V，S，P)， 产生式的形式是v→w，其中：v∈(∑UV)+，且 至少包含一个非终结符； w∈（∑ U V）*
定义4-1右线性文法的定义 对于文法G=(∑,V,S,P),若它的每个产生式 都是下列形式之 A→xC或者A八y; 其中:A,c∈V,X∈∑,y∈∑; 则文法G是右线性文法(也称为正则文法RG)。 ●如果一个语言L可以由右线性文法产生,则该语 言是右线性语言
⚫ 定义4-1 右线性文法的定义 ⚫ 对于文法G=(∑，V，S，P)，若它的每个产生式 都是下列形式之一： ⚫ A→xC或者A→y； ⚫ 其中：A，C∈V，x∈∑*，y∈∑+； ⚫ 则文法G是右线性文法（也称为正则文法RG）。 ⚫ 如果一个语言L可以由右线性文法产生，则该语 言是右线性语言
●定义4-2上下文无关文法的定义 ●对于文法G,如果对于G中的任意产生式v→少U, 而v只是一个非终结符,即A→u,A∈V,ω∈ (∑UV)*,则称文法G为上下文无关文法 CFG(简称无关文法)。 如果一个语言能由一个无关文法产生,则称这 个语言是上下文无关语言(简称无关语言)
⚫ 定义4-2 上下文无关文法的定义 ⚫ 对于文法G，如果对于G中的任意产生式ν→ω， 而ν只是一个非终结符，即A→ω，A∈V，ω∈ （∑ U V）*，则称文法G为上下文无关文法 CFG（简称无关文法）。 ⚫ 如果一个语言能由一个无关文法产生，则称这 个语言是上下文无关语言（简称无关语言）
定义4-3上卜文相关文法的足义 对于文法G,如果G的每个产生式形如u→,且 0<|usv;但若E∈L(G),则允许有S→E,且S不出 现在任何产生式的右边;则称文法G为上下文相关文 法cSG(简称相关文法)。 ●如果一个语言能由一个相关文法产生,则称这个语言 是上下文相关语言(简称相关语言) 根据以上的两个定义,可以看出,一个无关的文法不 定是相关的文法,主要是空串产生式的情况
⚫ 定义4-3 上下文相关文法的定义 ⚫ 对于文法G，如果G的每个产生式形如u→v，且 0<|u|≤|v|；但若ε∈L(G)，则允许有S→ε，且S不出 现在任何产生式的右边；则称文法G为上下文相关文 法CSG（简称相关文法）。 ⚫ 如果一个语言能由一个相关文法产生，则称这个语言 是上下文相关语言（简称相关语言）。 ⚫ 根据以上的两个定义，可以看出，一个无关的文法不 一定是相关的文法，主要是空串产生式的情况
某些文法不满足上述3类文法的要求;如 s→AB1 AB0 该文法不是右线性文法,不是无关文法,也不是 相关文法,只能属于短语结构文法
⚫ 某些文法不满足上述3类文法的要求；如 ⚫ S→AB1 ⚫ AB→0 ⚫ 该文法不是右线性文法，不是无关文法，也不是 相关文法，只能属于短语结构文法
● Chomsky将文法分为四类,关系为: 任意一个右线性文法本身是一个无关文法;本身 不一定是相关文法; ●任意一个无关文法本身不一定是相关文法;
⚫ Chomsky将文法分为四类，关系为： ⚫ 任意一个右线性文法本身是一个无关文法；本身 不一定是相关文法； ⚫ 任意一个无关文法本身不一定是相关文法；
设文法G=(∑,V,S,P),则判断G是哪类文法的方法如下 1、G是短语结构文法; 2、如果所有产生式都有右边部分长度大于等于左边部分,那么 G是上下文有关文法; 3、如果如果所有产生式的左边部分都是单个非终极符号,那么 G是上下文无关文法; 4、如果所有产生式的右边部分都是以终极符号开始、含有至多 个非终极符号、如果有非终极符号则出现在最右边,那么G 是正则文法
⚫ 设文法G=(∑，V，S，P)，则判断G是哪类文法的方法如下： ⚫ 1、G是短语结构文法； ⚫ 2、如果所有产生式都有右边部分长度大于等于左边部分，那么 G是上下文有关文法； ⚫ 3、如果如果所有产生式的左边部分都是单个非终极符号，那么 G是上下文无关文法； ⚫ 4、如果所有产生式的右边部分都是以终极符号开始、含有至多 一个非终极符号、如果有非终极符号则出现在最右边，那么G 是正则文法
41.2语言之间的关系 下面讨论语言之间的关系。 ●任意一个右线性语言文法本身是一个无关语言; 个上下文无关语言是不是一个上下文相关语言呢? 从第二章可知:一个无关文法 ●①没有任何空串产生式,或者 ②仅有一个空串产生式S→E,且S不出现在任何产生式的右 边 ●则该文法本身就是一个相关文法;它产生的无关语言也就是 个相关语言;那么,如果 关文法中有般的空串产 生式如A一E,A是一个非终结 且不是开始符号),它 产生的无关语言是不是相关语言呢?
⚫ 4.1.2语言之间的关系 ⚫ 下面讨论语言之间的关系。 ⚫ 任意一个右线性语言文法本身是一个无关语言； ⚫ 一个上下文无关语言是不是一个上下文相关语言呢？ ⚫ 从第二章可知：一个无关文法 ⚫ ①没有任何空串产生式，或者 ⚫ ②仅有一个空串产生式S→ε，且S不出现在任何产生式的右 边 ⚫ 则该文法本身就是一个相关文法；它产生的无关语言也就是 一个相关语言；那么，如果一个无关文法中有一般的空串产 生式（如A→ε，A是一个非终结符，且不是开始符号），它 产生的无关语言是不是相关语言呢？
据空甲定理: G是一个上下文无关文法,存在一般的空串产生式A→E,则 存在另一个上下文无关文法G使得: (1)L(G)=L(G); (2)若E!∈L(G),则G中没有任何空串产生式; (3若E∈L(G),则G中有一个空串产生式,S'→E,且S不出 现在G的其它任何产生式的右边;(S是G开始符号) 实际上,G是一个无关文法。也是一个相关文法。 即:任意一个无关文法都可以改造为等价的一个相关文法, 所以,在意一个无关语言也 相关语言
⚫ 根据空串定理： ⚫ G是一个上下文无关文法，存在一般的空串产生式A→ε，则 存在另一个上下文无关文法G′使得： ⚫ ⑴L(G)=L(G′)； ⚫ ⑵若ε！∈L(G)，则G′中没有任何空串产生式； ⚫ ⑶若ε∈L(G)，则G′中有一个空串产生式，S′→ε，且S′不出 现在G′的其它任何产生式的右边；（S′是G′开始符号） ⚫ 实际上，G’是一个无关文法。也是一个相关文法。 ⚫ 即：任意一个无关文法都可以改造为等价的一个相关文法， 所以，任意一个无关语言也是一个相关语言