2上下文无关文法与上下文无关语言

第二讲

上下文无关文法与上下文无关语言

上下文无关文法的基本概念

归约与推导

上下文无关语言

文法与语言的Chomsky分类

语法分析树

归约、推导与分析树之间关系上下文无关文法与上下文无关语言

文法和语言的二义性

回顾：在第一讲中介绍过如下内容

设

=0,1

，L=0n1n

n

1

，如0011,000111,01

L,而10,1001,,010

L.

如下是一个可接受该语言的上下文无关文法

S

01S

0S1上下文无关文法的基本概念

另一个例子

E

EOEE

(E)E

vE

dO

＋

O

上下文无关文法的基本概念

上下文无关文法(context-freegrammars)

的四个基本要素1.终结符(terminals)的集合

有限符号集，相当于字母表E

EOEE

(E)E

vE

dO

＋O

终结符2.非终结符(nonterminals)的集合

有限变量符号的集合非终结符3.开始符号(startsymbol)

一个特殊的非终结符开始符号4.产生式(productions)的集合

形如：<head>

<body>产生式集合上下文无关文法的基本概念终结符的集合

一个上下文无关文法

CFG

(context-freegrammars)

是一个四元组

G=(V,

T,P

,S).

上下文无关文法的形式定义非终结符的集合产生式的集合开始符号满足

V

T=S

V产生式形如

A

,

其中A

V,

(V

T)*上下文无关文法的基本概念(1)CFG

G01=({S},

{0,1},P

,S).其中产生式集合P为

S

01S

0S1

上下文无关文法举例(2)CFG

Gexp=({E,O},

{(,),＋,

,v,d},P

,E).

其中产式集合P为

E

EOEE

(E)E

vE

dO

＋

O

上下文无关文法的基本概念

产生式集合的缩写记法

形如

A

1,A

2,…,A

n的产生式集合可简缩记为A

1

2

…

n，如

S

01S

0S1S

01

0S1E

EOEE

(E)E

vE

dO

＋O

E

EOE

(E)

v

dO

＋

上下文无关文法的基本概念

用于推理字符串是否属于文法所定义的语言

一种是自下而上的方法，称为递归推理（recursiveinference），递归推理的过程习称为归约；另一种是自上而下的方法，称为推导（derivation）

归约过程

将产生式右部（body）形式的符号串替换为产生式左部（head）的符号

推导过程

将产生式左部的符号替换为产生式右部的符号串归约与推导

归约过程举例

对于CFG

Gexp=({E,O},

{(,),＋,

,v,d},P

,E)，P为

（1）E

EOE

（2）

E

(E)

（3）

E

v

（4）

E

d

（5）

O

＋

（6）

O

递归推理出字符串v

(v＋d)的一个归约过程为v

(v＋d)（4）v

(v＋E)（6）vO(v＋E)（3）vO(E＋E)（5）vO(EOE)（1）vO(E)（2）vOE（3）EOE（1）E归约与推导

推导过程举例

对于CFG

Gexp=({E,O},

{(,),＋,

,v,d},P

,E)，P为

（1）EEOE

（2）

E

(E)

（3）

E

v

（4）

E

d

（5）

O

＋

（6）

O

从开始符号到字符串v

(v＋d)的一个推导过程为v

(v＋d)（4）v

(v＋E)（6）E

(E)（3）（1）v

(EOE)（5）（3）EOE（1）EE

E（2）v

(E)v

(E＋E)归约与推导

推导关系

对于

CFGG=(V,

T,P

,S)，上述推导过程可用关系

描述.设

,(V

T)*，A

是一个产生式，则定义

A

.

若G在上下文中是明确的，则简记为

A

.GG

扩展推导关系到自反传递闭包

定义上述关系的传递闭包，记为

，可归纳定义如下：

基础

对任何

(V

T)*，满足

.

归纳设

,,(V

T)*，若

，

成立，则

.GGGGG

归约与推导E

EOEE

(E)E

vE

dO

＋O

v

(v＋d)v

(v＋E)v

(EOE)EOEEv

(E)vOEv

Ev

(vOE)

lm

最左推导（leftmostderivations）若推导过程的每一步总是替换出现在最左边的非终结符，则这样的推导称为最左推导.为方便，最左推导关系用

表示，其传递闭包用表示.

如对于文法Gexp

，下面是关于v

(v＋d)

的一个最左推导：

lmlm

lm

lm

lm

lm

lm

lm

lm归约与推导E

EOEE

(E)E

vE

dO

＋O

v

(v＋d)E

(v＋d)EO(E＋d)EOEEEO(EOd)EO(E)EO(EOE)EO(v＋d)

rm

最右推导（rightmostderivations）若推导过程的每一步总是替换出现在最右边的非终结符，则这样的推导称为最右推导.为方便，最右推导关系用

表示，其传递闭包用表示.

如对于文法Gexp

，下面是关于v

(v＋d)

的一个最右推导：

rmrm

rm

rm

rm

rm

rm

rm

rm归约与推导

句型

(sententialforms)

设

CFGG=(V,

T,P

,S)，称

(V

T)*

为G的一个句型，当且仅当S

.

若S

，则

是一个左句型（left-sententialform）;

若S

，则

是一个右句型（right-sententialform）.

若句型

T*，则称

为一个句子（sentence）.

lmrm

归约与推导

上下文无关文法的语言设

CFGG=(V,

T,P

,S)，定义G的语言为

L(G)={

w

w

T*

S

w}G

上下文无关语言CFG

Gexp=({E,O},

{(,),＋,

,v,d},P

,E)

的语言

L(Gexp)=？E

EOEE

(E)E

vE

dO

＋O

归纳定义：

1基础

v,d

L(Gexp)2归纳

ife

L(Gexp)

,then(e)

L(Gexp)ife1,e2

L(Gexp),thene1

＋

e2

L(Gexp)ife1,e2

L(Gexp),thene1

e2

L(Gexp)

上下文无关语言（context-freelanguages）

如果一个语言L是某个

CFGG

的语言，即

L(G)=L，则是上下文无关语言.上下文无关语言上下文无关语言

文法设计

例给出语言L=0n1n

n

1

的一个文法。

如下是一个可接受该语言的上下文无关文法G[S]

S

01

S

0S1

课堂练习？

证明给定语言L是某个文法G的语言

一般步骤

ifw

Lthenw

L(G)

ifw

L(G)thenw

L.

对于前者，多数情况下可以归纳于w的长度|w|；对于后者，一般情况下可以归纳于推导w的步数.

一个例子

见定理5.7.上下文无关语言

证明给定语言L是某个文法G的语言

举例

!!Exercise5.1.8考虑定义了下面的产生式的CFGG：

S

aSbS|bSaS|ε

证明L(G)是所有有相同个数的a和b的串的集合。证明思路用归纳法证明：若串w中包含相同个数的a和b，则w

L(G).

（通过对|w|进行归纳来证明w在L(G)中，即S

*w）若

w

L(G)，即S

*w，则w中包含相同个数的a和b.

（对从S到w的推导过程的步数进行归纳）（留作练习）上下文无关语言

证明给定语言L是某个文法G的语言

举例设G为上下文无关文法，其终结符集合为{a,b}，开始符号为S，产生式集合如下：

S

aB

bAA

a

aS

bAAB

b

bS

aBB试证明L(G)={w

w

{a,b}*,occur(a,w)=occur(b,w)

}.其中，对于符号a和串w，occur(a,w)表示a在w中出现的次数.

证明思路用互归纳法证明：对所有的w

{a,b}*，如下三个等价式成立：

1）S

*w

iff

occur(a，w)=occur(b，w)

；

2）A

*w

iff|w|>0

occur(a，w)=occur(b，w)+1

；

3）B

*w

iff|w|>0

occur(b，w)=occur(a，w)+1

（留作思考题）上下文无关语言

文法（grammar）文法是一个四元组

G=(V,

T,P

,S)，

V、T、P及S的含义如前.Chomsky通过对产生式施加不同的限制，把文法分成四种类型，即0型、1型、2型和3型.文法与语言的Chomsky分类0型文法

0型文法G=(V,

T,P

,S)的产生式形如

,

其中

,(V

T)*，但

中至少包含一个非终结符.

能够用0型文法定义的语言称为0型语言.

结论

0型文法的能力相当于图灵机（Turingmachines）.文法与语言的Chomsky分类

1型文法

1型文法

G=(V,

T,P

,S)的产生式形如

,

满足

，仅S

例外，且要求S不得出现在任何产生式的右部.1型文法也称谓上下文有关文法（context-sensitivegrammars）.

能够用1型文法定义的语言称为1型语言或上下文有关语言.

与1型文法的能力相当的一种自动机模型为线性有界自动机.文法与语言的Chomsky分类

2型文法

2型文法G=(V,

T,P

,S)的产生式形如A

,

其中

A

V，

(V

T)*.2型文法即上下文无关文法.

能够用2型文法定义的语言称为2型语言，即上下文无关语言.

结论与2型文法的能力相当的一种自动机模型为下推自动机（PushdownAutomata）.文法与语言的Chomsky分类3型文法

3型文法G=(V,

T,P

,S)中，除S

外的产生式形如

A

aB或A

a,

其中A,B

V，a

T；若P

中包含产

生式

S

，则S

不会出现在任何产生式的右边

正规文法也常用右线性文法或左线性文法来定义：

右线性文法：所有产生式形如

A

B

或

A

左线性文法：所有产生式形如A

B

或

A

3型文法也称为正规文法

能够用3型文法定义的语言称为3型语言，即正规语言.

结论

3型文法的能力等价于有限状态自动机.文法与语言的Chomsky分类(1)E

EOE(2)E

(E)(3)E

v(4)E

d(5)O

＋(6)O

归约过程自下而上构造了一棵树

如对于文法Gexp

，关于v

(v＋d)

的一个归约过程可以认为是构造了如下一棵树：v

(v＋d)（4）v

(v＋E)（6）vO(v＋E)（3）vO(E＋E)（5）vO(EOE)（1）vO(E)（2）vOE（3）EOE（1）EEEOEEOEEd＋v()

v语法分析树(1)E

EOE(2)E

(E)(3)E

v(4)E

d(5)O

＋(6)O

推导过程自上而下构造了一棵树

如对于文法Gexp

，关于v

(v＋d)

的一个推导过程可以认为是构造了如下一棵树：Ed＋v

vOEEE()EEOv

(v＋d)（4）v

(v＋E)（6）E

(E)（3）（1）v

(EOE)（5）（3）EOE（1）EE

E（2）v

(E)v

(E＋E)语法分析树

语法分析树（parsetrees）对于

CFGG=(V,

T,P

,S)，语法分析树是满足下列条件的树：

(1)

每个内部结点由一个非终结符标记.

(2)

每个叶结点或由一个非终结符，或由一个终结符，或由

来标记.但标记为

时，它必是其父结点唯一的孩子.(3)

如果一个内部结点标记为A，而其孩子从左至右分别标记为X1,X2,…,Xk，则A

X1X2…Xk是P中的一个产生式.注意：只有k=1时上述Xi才有可能为

，此时结点A只有唯一的孩子，且A

是P中的一个产生式.语法分析树

语法分析树的果实（

yield

）设

CFGG=(V,

T,P

,S).将语法分析树的每个叶结点按照从左至右的次序连接起来，得到一个(V

T)*中的字符串，称为该语法树的果实.

G

的每个句型都是某个根结点为S的分析树的果实;这些分析树中，有些树的果实为句子，它们构成了G的语言.语法分析树

三者之间的关系设

CFGG=(V,

T,P

,S).以下命题是相互等价的：

(1)

字符串

w

T*可以归约（递归推理）到非终结符A；

(2)

A

w；

(3)

A

w；

(4)

A

w；

(5)

存在一棵根结点为A的分析树，其果实为

w.

lm

rm归约、推导与分析树之间关系递归推理（归约）语法分析树最左推导最右推导推导

证明策略归约、推导与分析树之间关系

从归约到分析树设

CFGG=(V,

T,P

,S).如果字符串

w

T*可以归约到非终结符A，则存在一棵根结点为A的分析树，其果实为

w.

证明思路归纳于从

w归约到

A的步数.基础

步数为1.一定有产生式

A

w.存在右上图所示的分析树.归纳

设步数大于

1，且最后一步归约使用了产生式

A

X1X2…Xk.

存在右下图所示的分析树.wAX1X2Xkw1w2wk……A归约、推导与分析树之间关系

从分析树到推导设

CFGG=(V,

T,P

,S).如果存在一棵根结点为A的分析树，其果实为字符串

w

T*，则A

w，A

w，

A

w.lmrm

证明思路

只证明A

w，A

w可类似证明；同时也证明了A

w.

归纳于分析树的高度来证明A

w.lmlmrm

归约、推导与分析树之间关系

证明思路归纳于分析树的高度来证明A

w.lm

基础高度为1.分析树一定如右图所示，必定有产生式

A

w.因此，A

w.lm

从分析树到最左推导wAX1X2Xkw1w2wk……Alm归纳高度大于1的分析树一定如右下图所示，必定有产生式

A

X1X2…Xk.存在w1,w2,…,wk，wi

是Xi子树的果实或wi=Xi

（1

i

k），且

w=w1w2…wk，由归纳假设，

Xi

wi（1

i

k）.

在此基础上易证得A

w.lm

归约、推导与分析树之间关系基础步数为1.一定有产生式A

w.w可以归约到A.

从推导到归约设

CFGG=(V,

T,P

,S).如果对于非终结符A和字符串

w

T*，A

w，则w可以归约到A.

证明思路归纳于推导A

w的步数.

归纳设步数大于

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.

归约、推导与分析树之间关系

文法的二义性(1)E

EOE(2)E

(E)(3)E

v(4)E

d(5)O

＋(6)O

二义文法（ambiguousgrammars）举例考虑右下文法，对于终结符串v＋

v

d，存在两棵不同的分析树，它们的根结点都为开始符号E

，果实都为v＋

v

d

.EEOEOEEd

v+vEEOEOEEd

v+v文法和语言中的二义性

二义文法概念

CFG

G=(V,

T,P

,S)为二义的，如果对某个w

T*，存在两棵不同的分析树，它们的根结点都为开始符号S

，果实都为w

.如果对每一w

T*，至多存在一棵这样的分析树，则G为无二义的.

二义性的判定一个CFG

是否为二义的问题是不可判定的，即不存在解决该问题的算法.(theorem9.20)

消除二义性将会看到，没有通用的办法可以通过等

价的文法变换来消除二义性.在实践中，对于特定的文法，

有可能找到消除二义性的办法.文法和语言中的二义性

文法的二义性

文法二义性的另一种定义

定义

CFG

G=(V,

T,P

,S)为二义的，如果存在某个

w

T*，存在两个不同的从开始符号S

到w

的最左推导.

该定义源于如下结论：

结论对CFG

G=(V,

T,P

,S)和w

T*，w

具有两棵不同的分析树，当且仅当存在两个不同的从开始符号S

到w

的最左推导.证明思路从不同的分析树可构造不同的最左推导；反之，从不同的最左推导可构造不同的分析树.

有时方便证明文法的无二义性例如，练习5.4.7.文法和语言中的二义性

语言中的二义性

如果上下文无关语言L的所有文法都是二义的，则称L

是固有二义的（inherentlyambiguous）

举例上下文无关语言

L={anbncmdm

n

1,m

1}

{anbmcmdn

n

1,m

1}

是固有二义的.以下是L的一个CFG

S

AB

CA

aAb

abB

cBd

cdC

aCd

aDdD

bDc

bc

推论没有通用的办法可以消除文法的二义性.文法和语言中的二义性

无二义文法的设计

课堂思考问题给出下列语言L

的一个无二义文法：

L={anbm|m

n

0}

文法和语言中的二义性文法和语言中的二义性

对于右上图的文法，采用

算符优先级联方法将其变换为左下图的文法，对于该文法，串v＋

v

d存在唯一的分析树.E

EAE

T

T

TMT

(E)

v

dA

＋

M

E

EOE

(E)

v

dO

＋

TTEEd

v+TTvEAM

消除二义性的几种文法变换方法文法和语言中的二义性

右上图的文法仍然是二义文法，串v＋

v＋

d存在不同的分析树（下图）.E

EAE

T

T

TMT

(E)

v

dA

＋

M

EEAEAEE+EEAEAEEd+++TvTvTTvTvdT

消除二义性的几种文法变换方法文法和语言中的二义性

采用左结合方法将右上图的文法变换为左下图，串v＋

v

＋d存在唯一的分析树（右下图）.E

EAT

T

T

TMF

FF

(E)

v

dA

＋

M

E

EAE

T

T

TMT

(E)

v

dA

＋

M

EE+TdFTEvFTvFA+A

消除二义性的几种文法变换方法文法和语言中的二义性

悬挂else二义性S

iS

iSe

Siie

S

消除二义性的几种文法变换方法

文法和语言中的二义性

采用最近嵌套匹配方法消除悬挂else二义性S

iS

iSeS串ii

e

存在唯一的分析树（右图）

消除二义性的几种文法变换方法S

iS

iMeSM

iMeM

将右上部的文法变换为下面的文法

必做题:*!Ex.5.1.1(b),

Ex.5.1.2(c)（最左推导和最右推导各一个）Ex.5.1.6(b),!!Ex.5.1.8,!Ex.5.2.2,Ex.5.4.7(a)附加1构造如下语言的上下文无关文法：（1）{anb2ncm|n，m≥0}

（2）{anbn+mcm|n，m≥0}

（3）{ambncpdq

n,m,p,q≥0及m+n=p+q

}

（4）{anbicjdm

n,m,i,j

0

n+m=i+j}

（5）{

uawb

u,w

{a,b}*

|u|=|w|}

（6）{aibjck

i,j,k

0,若

j=1

则

i=k}

附加2给出语言{ambn|m

2n

0}

的二义文法和非二义文法各一个附加3适当变换文法，找到下列文法所定义语言的一个无二义的文法：S

SaS

SbS

Sc