第四章 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（简称相关文法）。 ⚫ 如果一个语言能由一个相关文法产生，则称这个语言 是上下文相关语言（简称相关语言）。 ⚫ 根据以上的两个定义，可以看出，一个无关的文法不 一定是相关的文法，主要是空串产生式的情况