当前位置：文档之家 › chapter 6-上下文无关语言

chapter 6-上下文无关语言

  • 格式：ppt
  • 大小：1.10 MB
  • 文档页数：27

下载文档原格式

  / 27

合集下载

形式语言自动机——上下文无关文法与下推自动机(一)

形式语言自动机——上下文无关文法与下推自动机(一)

y1 y2
y3 y4 y5
11
归约过程自下而上构造了一棵树 如对于文法Gexp ，关于 v (v＋d) 的一个归约过程可以认为是构造了如下一棵树：
E
EO v
E (E )
EO E v＋ d
(1) E EOE (2) E (E) (3) E v (4) E d (5) O ＋
(6) O
（5）
翻译 2型文法对应的识别器——下推自动机
PDA（Push Down Automata)由输入带、有限 控制器和下推栈构成（书P152 图）
2
回顾：在第一讲中介绍过如下内容 设 T= 0, 1 ， L = 0n1n n 1，
如 0011, 000111, 01 L, 而10, 1001 , , 010 L .
递归推理出字符串 v (v＋d) 的一个归约过程为
（5）
v (v＋d) （4）
（1）
vO(EOE)
v (v＋E) （6）
（3）
vO(v＋E)
vO(E＋E)
（2）
（3）
（1）
vO(E)
vOE
EOE
E
5
归约与推导
推导过程举例
对于CFG Gexp = ({E,O}, { (, ),＋, , v, d }, P , E ) ，P 为
基础 步数为 1. 一定有产生式 A w . w 可以归约到 A.
归纳 设步数大于 1，第一步使用了产生式A X1X2…Xk . 该推导如 A X1X2…Xk w . 可以将 w 分成 w = w1w2…wk，其中 (a) 若 Xi 为终结符，则 wi = Xi. (b) 若 Xi 为非终结符，则 Xi wi. 由归纳假设， wi 可以归约到 Xi . 这样，wi 或者为Xi，或者可以归约到 Xi ，使用产生 式A X1X2…Xk ，得出w 可以归约到 A.

形式语言和自动机上下文无关文法与下推自动机课堂PPT

形式语言和自动机上下文无关文法与下推自动机课堂PPT

(3)由(q1,)(q1, 1, X) 得 [q1 ,X ,q1] 1;
(4)由(q2,)(q1, , Z0) 得 [q1 ,Z0 ,q2] ;
(5)由(q0,XZ0)(q0, 0, Z0) 得 [q0 ,Z0 ,qj] 0[q0 ,X ,qi] [qi ,Z0 ,qj] , i, j = 0,1,2;
从上下文无关文法构造等价的下推自动机
定理4.5.1（由CFG可导出PDA）： 设上下文无关文法G＝（N，T，P，S），产生语
言L（G），则存在PDA M，以空栈接受语言Lφ(M), 使Lφ(M)=L(G)。
证明：构造下推自动机M，使M按文法G的最左推导 方式工作。
1
从上下文无关文法构造等价的下推自动机
q0 b, A/ε
b, A/ε ε, A/ε
q1 ε, z0/ε
（3） 对①式δ（q0,a,z0）={( q0, A z0)} ， ∵所有可能的状态序列为：q0q0，q1q0，q0q1，q1q1 ∴可构造出产生式：
[q0,z0,q0]→ a [ q0,A, q0 ][ q0,z0, q0 ] [q0,z0,q0]→ a [ q0,A, q1 ][ q1,z0, q0 ] [ q0,z0,q1]→ a [ q0,A, q0 ][ q0,z0, q1 ] [ q0,z0,q1]→ a [ q0,A, q1 ][ q1,z0, q1 ]
then A w.
归纳于 (q, w,A)├*(q, , ) 的步数 n.
基础 n=1，必有 w = ，且 A 为 G 的产生式，所以 A w.
归纳 n>1，设第一步使用产生式 AX1X2…Xm ， 可以将w 分为 w = w 1 w 2… w m ，满足 (q, wi , Xi )├*(q, , )，

形式语言与自动机理论--第六章 上下文无关语言2(第十五周)

形式语言与自动机理论--第六章 上下文无关语言2(第十五周)
SAB|a|BB，Aa，Cb|ABa
先用算法6-1，文法被化简成：
Sa，Aa，C b
再用算法6-2，可得到文法：
S a
14
2.1去无用符号
例 6-2-1 设有如下文法
SAB|a|BB，Aa，Cb|ABa
先用算法6-2，文法被化简成：
SAB|a|BB，Aa
再用算法6-1，可得到文法：
S a，Aa
11
2.1去无用符号
定理 6-5 算法6-2是正确的。
证明要点： (1) 施归纳于派生步数n，证明如果Sn αXβ，则
当 X∈V 时 ， X 在 算 法 中 被 语 句 (3) 或 者 语 句 (8) 放入NEWV；当X∈T时，它在算法中被语句(4) 或者语句(9)放入NEWT。 (2) 对 循环 次 数 n施 归 纳， 证 明如 果 X被放 入 NEWT 或 者 NEWV 中 ， 则 必 定 存 在 α ， β∈(NEWV∪NEWT)*，使得Sn αXβ。 (3) 证明L(G′)=L(G) 。
26
2.3 去单一产生式
（3）删除G2中的无用符号。 由于在删除单一产生式后，文法中可能出现新的 无用符号，因此，我们还需要再次删除新出现的无 用符号。 此外，在去ε-产生式后可能会产生新的单一产生式， 也可能会引进新的无用符号。这是值得注意的。
27
2.3 去单一产生式
例：
SA|B Aa BbB|b
G4：S0|0A A0|1|0A|1A| _C
C0用符号、 ε产生式和 单一产生式。
3
2.1 去无用符号
定义6-8：无用符号(useless symbol)
对于任意X∈V ∪ T，如果存在w∈L(G)， X出现在w的派生过程中，即存在α， β∈(V∪T)*，使得S*αXβ*w，则称X 是有用的，否则，称X是无用符号。

上下文无关文法

上下文无关文法

第三部分上下文无关语言和下推自动机前面介绍的有限自动机是计算的初级模型，它所接受的正规语言不太关心字符串自身的结构。

上下文无关文法（CFL）是一种简单的描述语法规则的递归方法，语言中的字符串由这些规则产生。

所有的正规语言都能用上下文无关文法描述，它也可以描述非正规语言。

上下文无关文法描述的语法规则更复杂多变，可以在相当大的程度上，描述高级程序设计语言的语法和其他一些形式语言。

类似正则语言对应的抽象机模型是有限自动机，CFL也有对应的抽象机模型。

CFL对应的计算模型是在有限自动机的基础上增加存储空间得到，并被设想成无限空间（对应有限自动机的有限空间），采用了一种简单的管理模式，栈（stack），这种新的计算模型（或抽象机）称为下推自动机（pushdown automata），下推是栈最典型的操作。

有必要在下推自动机中保留非确定性，确定型下推自动机不能接受所有的CFL，但给定一个CFG，容易构造一个相应的非确定型下推自动机，它在识别字符串过程中的移动模拟了文法的推导过程，这个过程称为分析（parse）。

分析不是一定需要下推自动机来完成。

CFL仍然不够通用，不能包括所有有意义的、或有用的形式语言。

采用类似第五章的技术，我们将给出一些不是CFL的简单例子，这些技术也用于解决与CFL相关的判定问题。

6 上下文无关文法6.1 上下文无关文法的定义为了描述我们在第二部分考察的各种语言，包括一些非正则语言，我们引入一种语言的递归定义方法，称为文法。

文法与我们熟悉的语言的语法描述相近，是描述语言和分析语言的有力工具。

问题：文法的形式化定义似乎可以模仿有限自动机，比如5元组或6元组之类。

例子6.1 正如我们在例子2.16中所见，字母表{a, b}上的回文语言pal可以用下面的递归方法描述：1.Λ, a, b∈pal2.对每个S∈pal，aSa和bSb也属于pal3.pal中不包含其他字符串如果将上面的符号S看成一个变量，代表了所有我们希望计算（比如某种递归算法）的pal 的元素，那么上面的规则1和规则2可以非正式地重新表述如下：1.S的值可以是Λ, a, b2.每个S可以写成aSa或bSb的形式如果我们用→表示“可以取值为”，则可以写出下面的式子：S→aSa→abSba→abΛba=abba上面的产生过程可以总结成下面的两组产生式（或称规则）：S→a | b | ΛS→aSa | bSb符号“|”表示“或”的含义。

[VIP专享]上下文无关文法

[VIP专享]上下文无关文法

第三部分上下文无关语言和下推自动机前面介绍的有限自动机是计算的初级模型，它所接受的正规语言不太关心字符串自身的结构。

上下文无关文法（CFL）是一种简单的描述语法规则的递归方法，语言中的字符串由这些规则产生。

所有的正规语言都能用上下文无关文法描述，它也可以描述非正规语言。

上下文无关文法描述的语法规则更复杂多变，可以在相当大的程度上，描述高级程序设计语言的语法和其他一些形式语言。

类似正则语言对应的抽象机模型是有限自动机，CFL也有对应的抽象机模型。

CFL对应的计算模型是在有限自动机的基础上增加存储空间得到，并被设想成无限空间（对应有限自动机的有限空间），采用了一种简单的管理模式，栈（stack），这种新的计算模型（或抽象机）称为下推自动机（pushdown automata），下推是栈最典型的操作。

有必要在下推自动机中保留非确定性，确定型下推自动机不能接受所有的CFL，但给定一个CFG，容易构造一个相应的非确定型下推自动机，它在识别字符串过程中的移动模拟了文法的推导过程，这个过程称为分析（parse）。

分析不是一定需要下推自动机来完成。

CFL仍然不够通用，不能包括所有有意义的、或有用的形式语言。

采用类似第五章的技术，我们将给出一些不是CFL的简单例子，这些技术也用于解决与CFL相关的判定问题。

6上下文无关文法6.1上下文无关文法的定义为了描述我们在第二部分考察的各种语言，包括一些非正则语言，我们引入一种语言的递归定义方法，称为文法。

文法与我们熟悉的语言的语法描述相近，是描述语言和分析语言的有力工具。

问题：文法的形式化定义似乎可以模仿有限自动机，比如5元组或6元组之类。

例子6.1 正如我们在例子2.16中所见，字母表{a, b}上的回文语言pal可以用下面的递归方法描述：1.Λ, a, b∈pal2.对每个S∈pal，aSa和bSb也属于pal3.pal中不包含其他字符串如果将上面的符号S看成一个变量，代表了所有我们希望计算（比如某种递归算法）的pal的元素，那么上面的规则1和规则2可以非正式地重新表述如下：1.S的值可以是Λ, a, b2.每个S可以写成aSa或bSb的形式如果我们用→表示“可以取值为”，则可以写出下面的式子：S→aSa→abSba→abΛba=abba上面的产生过程可以总结成下面的两组产生式（或称规则）：S→a | b | ΛS→aSa | bSb符号“|”表示“或”的含义。

上下文无关文法的概念

上下文无关文法的概念

上下文无关文法的概念上下文无关文法的概念一、引言上下文无关文法（Context-Free Grammar，CFG）是形式语言理论中的一种重要的语法描述工具，它是由 Noam Chomsky 在 1956 年提出的。

CFG 是一种用于产生形式语言的形式化体系，它可以描述自然语言、编程语言等各种形式语言。

二、基本概念1. 文法（Grammar）文法是一个四元组 G = (V, T, P, S)。

其中 V 是非终结符集合，T 是终结符集合，P 是产生式规则集合，S 是起始符号。

非终结符表示语法规则中可以被替换的部分，终结符表示不能被替换的部分。

2. 产生式规则（Production Rule）产生式规则也称为产生式或规则，它是一个形如A → α 的表达式。

其中A 是一个非终结符号，α 是由非终结符号和终结符号组成的字符串。

3. 推导（Derivation）推导也称为生成或演算，它是指根据 CFG 的产生式规则从起始符号开始逐步推导出一个字符串的过程。

4. 句子（Sentence）句子也称为字符串或序列，它是由 CFG 的终结符号构成的序列。

三、上下文无关文法的特征CFG 的产生式规则中，只有一个非终结符号可以被替换成一个字符串，而且这个非终结符号出现在产生式规则左侧。

四、上下文无关文法的形式定义一个 CFG G = (V, T, P, S) 是上下文无关的，当且仅当它的产生式规则集合 P 中的每个规则都是形如A → α 的形式，其中A ∈ V，α ∈ (V ∪ T)*。

五、上下文无关文法的应用CFG 可以描述自然语言、编程语言等各种形式语言。

在编译器设计和自然语言处理中，CFG 是一种常用的工具。

六、总结上下文无关文法是一种用于产生形式语言的形式化体系。

它可以描述自然语言、编程语言等各种形式语言。

CFG 的特征是产生式规则中只有一个非终结符号可以被替换成一个字符串，并且这个非终结符号出现在产生式规则左侧。

上下文无关文法

上下文无关文法

mcy
35
3.2 上下文无关文法的形式定义
1.
2. 3. 4. 5. 6. 7. 8.
上下文无关文法(即2型文法)的形式定义 chomsky文法的分类 推导和规约的定义 句型和句子的定义 最左和最右推导 文法定义的语言 递归产生式和递归文法 文法和语言
mcy
36
5. 最左和最右推导
最左推导 对于文法G[S]: S * 是一个最左推导 是指：在推导过程中的任何一步直接推导α β ， 都是对字符串α 中的最左非终结符进行替换，其中 α 、β 是句型。 简单整型算术表达式文法：
mcy
20
3型文法：通常，我们把右线性文法及左线性文法
统称为3型文法或正规文法。 若文法G中任一产生式α→β的形式都为A→aB 或 A→a，其中 A∈VN ，B∈VN ，a∈VT ，则称G 为右线性文法； 类似地，如果G中仅含有形如A→Ba 或 A→a的 产生式，则称G为左线性文法；
mcy
mcy
32
4. 句型和句子的定义
定义4 句型和句子:设G=(VN , VT , P , S)是一文 法,且 V=VN∪VT 若S =>*α,α∈V*,则称α为文法G的句型；
若S=>+α,α∈VT*,则称α为文法G的句子；
mcy
33
简单整型算术表达式文法：
exp → exp op exp|(exp)|number op → +|-|* 给出算术表达式（34-3）*42的一个推导，请 列出推导过程中出现的句型和句子。
28
例：G[S]：S→0S1，S→01 直接推导： S 0S1 0S1 00S11 00S11 000S111 000S111 00001111

形式语言 第6章 上下文无关语言

形式语言 第6章 上下文无关语言

2020/10/13
25
6.1.2 二义性
• 简单算术表达式的二义性文法 Gexp2： EE+E|E-E|E/E|E*E
E E↑E|(E)|N(L)|id Nsin|cos|exp|abs|log|int LL,E|E
2020/10/13
26
6.1.2 二义性
句子x+x/y↑2在文法中的三个不同的最左派生
…
*α1α2…αm
2020/10/13
16
6.1.1 上下文无关文法的派生树
2020/10/13
17
6.1.1 上下文无关文法的派生树
• 例6-1设Gbra：SS(S)|ε，(()(()))和(S)((S)) 的派生树。
2020/10/13
18
6.1.1 上下文无关文法的派生树
• 关于标记ε的结点
– 最左归约。
2020/10/13
22
6.1.1 上下文无关文法的派生树
定理6-2 如果α是CFG G的一个句型，则G中 存在α的最左派生和最右派生。
证明： 基本思路：对派生的步数n施归纳，证明对于
任意A∈V，如果Anα，在G中，存在对 应的从A到α的最左派生：An左α。
2020/10/13
23
6.1.1 上下文无关文法的派生树
的个数均不大于k。
2020/10/13
12
6.1.1 上下文无关文法的派生树
X1*α1 X2*α2 … Xm*αm 而且 α=α1α2…αm
2020/10/13
13
6.1.1 上下文无关文法的派生树
AX1X2…Xm *α1X2…Xm *α1α2…Xm … *α1α2…αm
2020/10/13

上下文无关语言与分析树教学PPT

上下文无关语言与分析树教学PPT

因此, S *lm (())()
S SS S() (S)() (())() 是一个推导, 但不是最左推导.
2014-10-25
25
最右推导
说Aw rm w 若w 是一个终结符串且 A 是 一个产生式. 同样地, *rm 若 通过0到多个rm步骤变成.
比FA及RE功能更强，但仍然不能定义所有可能的语 言.
对于嵌套的结构有用,如, 程序语言中的括号.
2014-10-25
2
非形式注释续
基本的概念是使用 “变元”表示串集合 (即,语言).
这些变元一个基于另一个递归定义.
递归规则 (“产生式”) 仅涉及连接操作.
一个变元的候选规则允许并起来.
2014-10-25
B A… |
B 代表[A…] (0到多个A).
最后变成 L SB A A ;S
C 代表A…
2014-10-25
B C |
C AC |
22
最左与最右推导
推导允许我们替换串中的任意变元.
会导致同一个串有多个推导存在.
通过强制最左边变元 (或另一选择, 最右边变元) 被替换, we avoid these “distinctions without a difference.”

+
E
F
b

F 1
F
产物
a0+1b1
F F
1


33
分析树, 最左、最右推导
对任意分析树, 有唯一的最左和唯一的最右推导.
将证明:
定理5.14. 若有一个分析树的根标记为A并且产物是 w, 则 A *lm w. 定理5.12. 若A *lm w, 则有一个以A为根产物是w的 分析树存在.

上下文无关文法与语言

上下文无关文法与语言

上下⽂⽆关⽂法与语⾔第 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的花园⾥听到的第⼀句话）。

上下文无关

上下文无关

上下文无关文法的基本概念
符号的使用约定 ：
6.
如果A → α1、A → α2、…、A → αk 是所 有以A为左部的产生式（称为A产生式）， 则可以把它们写成A → α1|α2|…|αk，我们 将α1、α2、…、αk称为A的候选式。除非另 有说明，否则第一个产生式左部的符号是开 始符号。
上下文无关文法的基本概念
文法的设计

消除二义性 － “悬挂else”的问题
stmt → if expr then stmt | if expr then stmt else stmt | other
文法的设计

消除二义性 － “悬挂else”的问题
每个else都同其前面最近的未匹配的then相匹配 改写后的文法如下：
stmt → matched_stmt | unmatched_stmt matched_stmt → if expr then matched_stmt else matched_stmt | other unmatched_stmt → if expr then stmt | if expr then matched_stmt else unmatched_stmt
文法的设计
例 考虑下面的算术表达式文法： E→E + T |T T→T * F |F F→( E ) | id 消除E和T的直接左递归，可以得到 E → T Eˊ Eˊ→ + T Eˊ|ε T → F Tˊ Tˊ→ * F Tˊ|ε F→( E )|id
文法的设计
例 考虑下面的文法： A→Ba|Aa|c B→Bb|Ab|d 令A1 = A，且A2 = B，当i = 1时，得到的文法是： A →B a Aˊ | c Aˊ Aˊ → a Aˊ |ε B → B b | A b| d 当i = 2得到了文法： A →B a Aˊ | c Aˊ Aˊ → a Aˊ |ε B → B b | B a Aˊb | c Aˊb | d

自己动手开发编译器（六）上下文无关语言和文法

自己动手开发编译器（六）上下文无关语言和文法

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

上下文无关语言和非上下文无关语言

上下文无关语言和非上下文无关语言

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 接受语言的能力（唯一的影响是不能接受空字符，由于此处仅仅关心足够长的字符串，因此这个影响可以忽略）。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
这个推导树共有6个叶节点，从左到右依次为2，9，6，10，11，8， 它们的标注符号构成一个终极符串aabbaa 。后面将证明，这个串就 是L(G) 中的一个元素。 上面的图中我们对每个节点加上序号，是为了便于说明问题。一般情 况下，推导树中的节点可以只写出标注符号，而不加序号或其它名称。 譬如，上面的推导树也可以画成
第六章、上下文无关语言
V ,T ,P ,S ) 为一个CFG， x L(G) 。如果在 S x 定义2: 设 G (
的推导过程中，每一步都是对句型中最右（左）边的变量使用产生 式，则称这个推导为最右（左）推导。
*
四、上下文无关文法的歧义性
再次考察前面的文法G。显然有多个推导过程推出L(G)中的一个串, 但是它们所对应的推导树都是一样的，都是前面给出的。换句话，我 们可以说只一个推导树。 有些CFG中，可能有这样的情况：一个终极符串对应两个（或两个以 上）不同的推导树。
第六章、上下文无关语言
上下文无关文法和它所描述的上下文无关语言，在定义程序设 计语言、语法分析、简化程序设计语言的翻译等方面有重要的 意义。 这是比有穷自动机和正则表达式能力更强的描述语言的方法。 内容：1、上下文无关文法 2、Chomsky 范式 3、对任何CFA都能找到一种具有特有形式的 等价的CFG (Context-Free Grammar) 例如:程序设计语言中的嵌套结构,用CFG描述而RG不行
*
第六章、上下文无关语言
情况2：对 (V T )* ，若S ，则 中不含X。即是X不出现 在任何句型中的字符。这种情况下的无用符号X既可能是变量，也可以 是终极符。 算法2是寻找这种不出现在任何句型中的变量或终极符的算法。这个算 法的基本思想是： 所有出现在 S 产生式右边的变量和终极符都可以出现在句型中； 若已知A是可以出现在句型中的变量，则所有出现在产生式右边的变量 和终极符都是可以出现在句型中的字符； 反复使用2），直到找不出新的字符为止，剩下的变量或终极符就是那 些不出现在任何句型中的字符。 在文法中删去无用字符时，同时要删去包含这些字符的产生式。
第六章、上下文无关语言
V ,T ,P ,S ) 为一个文法，如果G中的产生式都有 定义1：设 G (
A
A V , (V T )*
的形式，则称G为一个上下文无关文法（简记为 CFG） 上下文无关文法产生的语言称为上下文无关语言（简记为CFL）。 例如： G2 (V2 , T2 ; P 2, S) 其中， V2 {S , A, B}, T2 {a, b} 且
S aAS aAa aSbAa aSbbaa aabbaa S aAS aSbAS aSbbaS aSbbaa aabbaa
( (3)
推导式（1）、（2）和（3）的推导过程显见是不一样的。 不过仔细观察可以发现，它们都是通过5步推导从推导出 aabbaa 而且这3个推导过程中，所使用到的产生式（包括每个产生式的重复使 用次数）都是一样的，只是顺序不一样而已。（1）式的推导过程中， 每一步推导都是对句型中最左边的变量使用产生式；（2）式的推导过 程中，每一步推导都是对句型中最右边的变量使用产生式；（3）式的 推导过程中，各步推导使用产生式的变量在句型中的位置则是随意的。
S X w
*
*
, (V T ) *
w T *
那么就说 X 是文法G中的一个有用字符，否则说 X 是一个无用字符。 上下文无关文法化简的任务之一，就是要删去文法中出现的无用字符。 对文法中的无用字符，可以分成两种情况来讨论：
第六章、上下文无关语言
情况1 ：对 A V ，不存在 w T * 使得 A w 。这种情况的无用 字符只可能是变量。 算法1 是找出那些不能推导出终极符串的变量的算法。这个算法的基本 思想是： 若存在产生式 A w ，（w T *），那么从A可以推导出终极符串； 若已求出部分可以推导出终极符串的变量，且有产生式 A ，其 中 只含终极符和那些已知可推导出终极符串的变量，则从 A也可以 推导出终极符串； 反复使用2），直到再也不能求出新的可推出终极符串的变量。剩下的 变量就为所求。
S a S a A b b S A a a
图3.2 文法的另外一个推导树
第六章、上下文无关语言
二、推导树与推导的关系
上面给出的文法G的一个推导树，这个推导树的叶节点的标注符号 从左到右按顺序排成的终极符串为 aabbaa 。我们就说是由这个 推导树产生的。另一方面，中也存在一个推导
S aAS aSbAS aabAS aabbaS aabbaa (1)
从S推导出串 aabbaa 。 这种推导树与推导之间的关系不是偶然的。下面的定理说明这一 点。 定理1： 设 G (V , T ; P, S ) 为一个上下文无关文法，x T * 。
那么
Sx
*
当且仅当存在一个推导树产生 x。
第六章、上下文无关语言
三、最左推导与最右推导
再进一步考察前面给出的文法G和G的一个推导树T。这个推导树产生 的终极符串为 aabbaa 。前面我们给出了这个终极符串的一个推导 。另外，我们还可以给出这个串的另一些推导，如：
V ,T ,P ,S ) 为一个CFG。若存在 x L(G) 定义3 设 G ( ，使得有两个不同的推导树产生x，则称为一个歧义文法。
定义4 设L为一个CFL，如果产生L的每一个CFG都是歧义 文法，则称为一个固有歧义的CFL。
第六章、上下文无关语言
五、化简
对于一个上下文无关语言，可能有多个上下文无关文法产生它。 这其中可能不是最简的。所谓不是最简的，是指文法中包含无用的字 或无用的产生式。本节就是讨论怎样在一个文法中删去无用的字符和 无用的产生式。 1、无用字符 V ,T ,P ,S ) 为一个CFG，字符 X V T ，如果存在一个推导： 设G (
*
G4 ({S , A},{a, b}; P4 , S ) P4 : S SB | aS | a Bb
*
第六章、上下文无关语言
例4 ： 设 G1 ({S , A, B},{a, b}; P 1, S )
其中
P : S AB | a Aa
通过算法1 和算法2，可以找出B是第一种情况的无用符号，b是第二种 情况的无用符号。因此从 G1 中删去B和b（以及包含它们的产生式）， 得到
G2 ({S , A},{a}; P2 , S ) P2 : S a Aa
可见 L(G) ，但文法 G1 中有一个空产生式 B 。从上下文 无关文法化简的要求，应该把这个空产生式删去。但是，如果只是简 单地划去这个空产生式，变为
G2 ({S , A, B},{a, b}; P2 , S ) P2 : S AB A aA | a Bb
第六章、上下文无关语言
A X1 A X1
，当 G 中存在产生式
X i1 X i X i1 X i1 X i1
Xn Xn
时，在 G ' 中增加一个产生式
（3）、从 G 中删去所有的空产生式，得到文法 G ' 。 根据这3步，对于例5 G1，消去空产生式 B 后得到的等价文法 应为
G3 ({S , A, B},{a, b}; P 3, S )
n
因此，当我们在一个文法中删去空产生式时，还需要添加上另外 一些产生式，以便原文法中出现的各种可能的推导在新的文法中 有所替代。 具体做法可分为3步。 （1）、找出中那些能够推导出空串的那些变量，设这些变量的 * 集合为
V { A V | A }
第六章、上下文无关语言
（2）、对每个 X i V
其中 P3 : S AB | A A aA | a B b
第六章、上下文无关语言
3、单产生式 在CFG中，对 A, B V , A B 称为单产生式。单产生式在文法中 也是不必要的。在文法中消去单产生式的工作相对比较容易，下面 分两种情况讨论。 情况1 ，设 A B 是文法 G 中的一个单产生式，如果 G中不存在 * A 1 A 2 型的推导，那么在删去单产生式 A B 的同时，把其 它各产生式出现的变量B都改为变量A。 情况2，设 A B 是文法中的一个单产生式，如果G中存在
那么 G2 产生的语言为 L(G2 ) {a b | n 1} 显然 L(G2 ) L(G1 ) 。之所以会出现这样的情况，是因为简 单地划去空产生式 B ，使得丢失了一些文法的推导。在 文法 G1 中，我们存在 S AB Ab an b n S AB A a 和 两类推导，而在文法 G2 中， 就只保留上面一种情况的推导，而丢失了下面一种情况的推导。 这显然同化简的初衷不相符。
第六章、上下文无关语言
例2 ：设有一个上下文无关文法 其中 G ({S , A},{a, b}; P, S )
P:
S AS | a A SbA | SS | ba
1
下面给出的是文法的一个推导树
S A
4
a 2 S 5
9
3
S A
11
8
b 6
10
7
a
a
b
a
图3.1 文法的一个推导树
第六章、上下文无关语言
第六章、上下文无关语言
例 3：
G1 ({S , A, B},{a, b}; P, S )
其中 P: S SA | SB | a Ab B b
容易知道，ab L(G) 而且这个终极符串可以由两个不同的推导树 产生：
S S A
S S B
a
b
a
b
图3.3 两个不同的推导树
第六章、上下文无关语言
A 1 A 2 型的推导，那么在删去单产生式 A B 的同时，对 中的每一个 B 产生式 B 都添加一个产生式 A 。