chapter 8-上下文无关语言的性质

形式语⾔与编译⼋上下⽂⽆关⽂法、及其⼆义性、对⼆义性⽂法的正规化上下⽂⽆关⽂法(context free grammar)语法分析的数学基础。

正则语⾔不能描述所有的语⾔，因此引⼊上下⽂⽆关⽂法(注意它也不能描述所有的语⾔，只是相对正则语⾔，描述范围增⼤)它的功能⽐RE和DFA要强许多，可以描述句⼦的结构对于嵌套结构，⽐如程序中的括号⾮常有⽤，上下⽂⽆关⽂法可以处理⽂法四元组定义：G=<V N,V T,S,P>之前⽤正则语⾔⽐较难以定义下⾯这个语⾔，但是现在⽤上下⽂⽆关语⾔，就很容易定义这个CFG产⽣式如下形式：变量—>（变量 |终结符）* 形式化：A−>α,A⊂V N,α⊂(V T∪V N)∗在使⽤上下⽂⽆关⽂法产⽣式的时候，名字"上下⽂⽆关"由来：S−>0S1,S=>00S11 替换的时候对于S不⽤管S的左边0，右边1；⽽是直接替换(可以说产⽣式头的核⼼，其核⼼左右边有⽆东西，意义不⼤，不影响，因此可以忽略，认为左边产⽣式头只有⼀个)对于0S−>0S11, 我们需要"瞻前顾后"，只有字符串是0S的时候，才可以被替换为0S11;(产⽣式头不只⼀个核⼼，核⼼左右也有⾮常重要的字符，需要观察配对){V T={0,1},V N={S},S,{S−>01,S−>0S1}}迭代式推导（间接推导）：=>∗上⾯E+E,a+E,a+E∗E,a+1∗E含有⾮终结符的叫做句型；(语法单位与串的混合；全部变量，和全部终结符也是特殊句型)a+1∗0不含有⾮终结符的叫做句⼦。

————————————————————————————w是终结符号串，S是开始符号G=<V N,V T,S,ϵ>L(G)=w|S=>∗w,w∈V∗T正则语⾔⼀定是上下⽂⽆关语⾔(可以由上下⽂⽆关⽂法强于正规⽂法的⾓度看)实际应⽤（编程）中，可以对CFG进⾏扩充，最著名BNF范式：::=,|,…(⼀到多),正规式⽤ +，前⾯Lex还⽤花括号{1，2，3，4}，不同规范定义⼀到多标准不⼀样，但是含义都⼀样。

上下文无关文法例题【原创实用版2篇】目录（篇1）1.什么是上下文无关文法2.上下文无关文法的特点3.例题解析4.上下文无关文法在自然语言处理中的应用正文（篇1）一、什么是上下文无关文法上下文无关文法（Context-Free Grammar，简称 CFG）是形式语言理论中的一种文法，用于描述由终结符（即单词）和非终结符（即符号）组成的字符串。

它是一种上下文无关的文法，意味着字符串的生成只与当前符号有关，而与前面的符号无关。

二、上下文无关文法的特点上下文无关文法具有以下特点：1.唯一性：每个非终结符对应唯一的产生式规则。

2.线性性：每个产生式规则的右部都是线性的，即由一个或多个非终结符组成。

3.穷尽性：文法能够生成所有可能的字符串。

三、例题解析假设有一个上下文无关文法如下：```S → ABA → aB → bB | ε```其中，S 表示字符串，A 和 B 表示非终结符，a 和 b 表示终结符，ε表示空字符串。

根据这个文法，可以生成如下字符串：```S1: aBbS2: abBS3: aBbBS4: abBb```可以看到，这个文法可以生成所有以"ab"、"bB"开头的字符串。

四、上下文无关文法在自然语言处理中的应用上下文无关文法在自然语言处理（Natural Language Processing，简称 NLP）中有广泛应用，例如：1.词性标注：通过训练上下文无关文法，可以为文本中的每个单词分配正确的词性标签。

2.句法分析：利用上下文无关文法可以对自然语言句子进行句法分析，生成句子的句法结构树。

3.机器翻译：在机器翻译任务中，可以使用上下文无关文法对源语言句子进行分析，然后生成目标语言句子。

目录（篇2）1.概览上下文无关文法2.上下文无关文法的特点3.应用实例：例题解析4.总结正文（篇2）一、概览上下文无关文法上下文无关文法（Context-Free Grammar，简称 CFG）是一种用来描述自然语言或其他形式语言的文法。

8 上下文无关语言和非上下文无关语言8.1 上下文无关语言的泵引理从第6章到第7章，我们给出了两种描述CFL的模型，CFG和PDA。

这两种模型都没有提供直接、明确的方法来判断一个形式语言不是CFL。

然而，正如例子6.7对自然语言的一个简单考察，我们发现CFG存在描述能力的局限。

本节中，我们精确定义和讨论CFL的一个性质，它类似于正则语言的泵引理。

利用这个性质能够发现许多不是CFL的语言。

正则语言的泵引理基于这样的事实，如果一个足够长的输入字符串x导致FA在状态转移中，到达某个状态超过一次，即接受路径上存在回路，根据回路容易将x分成三部分，u是回路之前的字符串，v是回路的字符串，w是回路后的字符串，那么在回路上的多次重复，得到的新的字符串也应该被FA接受，即对任意的m>=0，uv m w被FA接受。

如果我们用CFG生成（而不是PDA移动）CFL，容易得到类似的观察。

设CFG G的一个推导出现同一个非终结符的嵌套重复，如下面的形式，S⇒*vAz⇒*vwAyz⇒*vwxyz其中，v, w, x, y, z∈∑*。

推导过程中，出现了A⇒*wAy，我们可以多次重复这个推导过程，如S⇒*vAz⇒*vwAyz⇒*vw2Ay2z⇒*vw3Ay3z⇒*...⇒*vw m Ay m z又由于A⇒*x，因此所有这类字符串vxz, vwxyz, vw2xy2z, ..., vw m xy m z都输入语言L(G)。

为了将上面的观察总结成CFL的泵引理，我们必须说明对于足够长的字符串的推导过程中都会出现非终结符的嵌套重复。

同时我们也尽量发现分解得到的5个子串：v, w, x, y, z，的一些性质。

这类似于我们处理正则语言的泵引理。

在6.6节，我们证明了所有的CFG产生式都可以改写成Chomsky范式，而不会影响CFG 接受语言的能力（唯一的影响是不能接受空字符，由于此处仅仅关心足够长的字符串，因此这个影响可以忽略）。

8 上下文无关语言和非上下文无关语言8.1 上下文无关语言的泵引理从第6章到第7章，我们给出了两种描述CFL的模型，CFG和PDA。

这两种模型都没有提供直接、明确的方法来判断一个形式语言不是CFL。

然而，正如例子6.7对自然语言的一个简单考察，我们发现CFG存在描述能力的局限。

本节中，我们精确定义和讨论CFL的一个性质，它类似于正则语言的泵引理。

利用这个性质能够发现许多不是CFL的语言。

正则语言的泵引理基于这样的事实，如果一个足够长的输入字符串x导致FA在状态转移中，到达某个状态超过一次，即接受路径上存在回路，根据回路容易将x分成三部分，u是回路之前的字符串，v是回路的字符串，w是回路后的字符串，那么在回路上的多次重复，得到的新的字符串也应该被FA接受，即对任意的m>=0，uv m w被FA接受。

如果我们用CFG生成（而不是PDA移动）CFL，容易得到类似的观察。

设CFG G的一个推导出现同一个非终结符的嵌套重复，如下面的形式，S⇒*vAz⇒*vwAyz⇒*vwxyz其中，v, w, x, y, z∈∑*。

推导过程中，出现了A⇒*wAy，我们可以多次重复这个推导过程，如S⇒*vAz⇒*vwAyz⇒*vw2Ay2z⇒*vw3Ay3z⇒*...⇒*vw m Ay m z又由于A⇒*x，因此所有这类字符串vxz, vwxyz, vw2xy2z, ..., vw m xy m z都输入语言L(G)。

为了将上面的观察总结成CFL的泵引理，我们必须说明对于足够长的字符串的推导过程中都会出现非终结符的嵌套重复。

同时我们也尽量发现分解得到的5个子串：v, w, x, y, z，的一些性质。

这类似于我们处理正则语言的泵引理。

在6.6节，我们证明了所有的CFG产生式都可以改写成Chomsky范式，而不会影响CFG 接受语言的能力（唯一的影响是不能接受空字符，由于此处仅仅关心足够长的字符串，因此这个影响可以忽略）。

§4.6 上下文无关语言的性质1. 2型语言的泵浦引理：设L 是上下文无关语言，存在常数p ，如果ω∈L ， 且︱ω︱≥p ，则ω可以写为ω＝ω1ω2ω0ω3ω4，使ω2ω3≠ε，∣ω2ω0ω3∣≤p ，对于i ≥0有ω1ωi2ω0ωi3ω4∈L 。

（不含L ＝{ε}的情况） 物理意义：线性语言的泵浦引理是说，在正规集合中，每个足够长的字符串都包含一个短的字串，随便将这个子串在原处重复插入多少次，所得的新字串还是在原正规集中。

2型语言的泵浦引理是说，有两个靠得很近的子串，它们可以重复任意多次（但二者重复的次数相同），所得的新串依然属于该2型语言。

证明：设G 是Chomsky 文法（形如A →BC,A →a ）,产生语言L －{ε} 若ω∈L 且ω有一定的长度，则边缘为ω的推导树有一定长度的路径。

对于Chomsky 范式，设路径长度为n ，则有边缘长度 ︱ω︱≤ 2n －1，如下图所示a 路径 ＝1︱ω︱＝︱a ︱＝21－ 1＝1a a路径 ＝2︱ω︱＝︱aa ︱＝22－ 1＝2设文法G 有n 个非终结符，取p ＝2n若ω∈L ，且︱ω︱≥p （即︱ω︱≥ 2n）则必有︱ω︱≥ 2n －1，即存在一条长度 > n 的路径，至少为n+1。

这时,该路径上的结点数为n+2(包括最高层顶点及最底层叶子）。

∵G 中只有n 个非终结符∴在这条路径上必然有某两个结点相同设为v 1= v 2=A, v 1靠近树根，v 1到叶子的最长路径为n+1。

路径＝4︱ω︱≤24－ 1＝8 （第i 层最多有2i个非终结符。

第i+1层若全为终结符，则与第i 层非终结符个数相等。

）ω2 ω0 ω3=εv 1靠近根，其子树为T 1，Z 1v 2远离根，其子树为T 2，ω0如图：Z 1＝ω2ω0ω3︱Z 1∣≤2 n ＝p （∵v 1到叶子的路径最多为n+1） 而v 1* =>ω2v 2ω3， v 2* =>ω0∵v 1＝v 2＝A ∴v 1 *=>ω2v 2ω3 =>ω2ω2v 2ω3ω3=>ωi2ω2v 2ω3ωi3 =>ωi2v 2ωi3 =>ωi2ω0ωi3∴ S =>ω1ω2ω0ω3ω4 *=>ω1ωi 2ω0ωi3ω4 v 1的子树得证＃2型文法泵浦引理的用途：判断一给定语言是否是上下文无关文法。

上下⽂⽆关⽂法与语⾔第 5 章上下⽂⽆关⽂法及语⾔现在我们把注意⼒从正则语⾔转移到另外⼀⼤类语⾔上来，它们叫做“上下⽂⽆关语⾔”。

这个语⾔类有着⾃然、递归的表⽰⽅法，这种表⽰⽅法叫做“上下⽂⽆关⽂法”。

从1960年以来，上下⽂⽆关⽂法⼀直在编译技术中扮演着重要的⾓⾊。

它们能够把分析器（⼀类⽤来在编译过程中发掘源程序结构的程序）的实现从⼀种费时的、不通⽤⽅式的设计⼯作转变成为⼀种能够很快完成的⼯作。

近年来，上下⽂⽆关⽂法也被⽤来描述⽂档格式：XML（eXtensible Markup Language 可扩展标记语⾔）中使⽤的DTD（Document-Type Definition ⽂档类型定义）就是⽤来描述Web上的信息交换格式的。

在本章中，我们将⾸先介绍上下⽂⽆关⽂法的表⽰⽅法，然后将介绍怎样⽤⽂法来定义语⾔。

我们将会讨论到“语法分析树”──对⼀个⽂法处在它所表⽰的语⾔的字符串中结构的图形描述。

语法分析树是对⼀个编程语⾔的语法分析器的产物，也是通常⽤来获得程序结构的途径。

上下⽂⽆关语⾔还有另外⼀种等价的⾃动机表⽰叫做“下推⾃动机”。

我们将在第6章介绍下推⾃动机。

虽然它不如有穷⾃动机重要，但仍然要介绍它，原因是作为⼀种语⾔的定义机制来说，它跟上下⽂⽆关⽂法具有等价性，后⾯在第7章研究如何判定上下⽂⽆关语⾔以及研究上下⽂⽆关语⾔的封闭性时，这种等价性是⾮常有⽤的。

5.1 上下⽂⽆关⽂法这⼀章的内容将从⾮形式化地介绍上下⽂⽆关⽂法的表⽰法开始。

形式化的定义会在读者了解到这些⽂法的⼀些重要的能⼒之后给出。

届时我们将会说明怎样形式地定义⼀个⽂法，并将介绍⼀种叫作“推导”的过程：它能够决定在⼀个⽂法的语⾔中到底有哪些串。

5.1.1⼀个⾮形式化的例⼦下⾯来考虑⼀个“回⽂（palindrome）”的语⾔。

“回⽂”是指正向和反向读起来都⼀样的串，⽐如otto或者madamimadam（“Madam, I’m Adam,”引⾃Eve在Eden的花园⾥听到的第⼀句话）。

⾃⼰动⼿开发编译器（六）上下⽂⽆关语⾔和⽂法上回我们已经学习了语法分析第⼀阶段——词法分析的原理和⼯具，介绍了正则表达式、正则语⾔和DFA等⼯具。

今次我们要开始涉及编译器前端最重要的阶段——语法分析。

简单⽽⾔，这⼀步就要完整地分析整个编程语⾔的语法结构。

上回说到词法分析的结果是将输⼊的字符串分解成⼀个个的单词流，也就是诸如关键字、标识符这样有特定意义的单词。

⼀种完整的编程语⾔，必须在此基础上定义出各种声明、语句和表达式的语法规则。

观察我们所熟悉的编程语⾔，其语法⼤都有某种递归的性质。

例如四则运算与括号的表达式，其每个运算符的两边，都可以是任意的表达式。

⽐如1+a是表达式，(1+a)*(2 – c)也是表达式，((a+b) + c) * (d – e)也是表达式。

再⽐如if语句，其if的块和else的块中还可以再嵌套if语句。

我们在词法分析中引⼊的正则表达式和正则语⾔⽆法描述这种结构，如果⽤DFA来解释，DFA只有有限个状态，它没有办法追溯这种⽆限递归。

所以，编程语⾔的表达式，并不是正则语⾔。

我们要引⼊⼀种表现能⼒更强的语⾔——上下⽂⽆关语⾔。

要介绍上下⽂⽆关语⾔，我们先来了解⼀下定义上下⽂⽆关⽂法的⼯具——产⽣式的写法。

我们还是使⽤编程语⾔的表达式作为例⼦，但这次我们假设表达式只有三种——单个表⽰变量名标识符、括号括起来的表达式和两个表达式相加。

⽐如a是⼀个变量表达式，a+b是两个变量表达式相加的表达式，(a+b)是⼀个括号表达式。

我们⽤符号E来表⽰⼀个表达式，那么这三种表达式分别可以定义为：E → idE → E + EE →( E )这种形式的定义就叫做产⽣式。

出现在→左侧符号E称作⾮终结符（nonterminal symbol），代表可以继续产⽣新符号的“⽂法变量”。

符号→表⽰⾮终结符可以“产⽣”的东西。

⽽上述产⽣式中的蓝⾊id、+、（等符号，是具有固定意义的单词，它们不再会产⽣新的东西，称作终结符（terminal symbol）。