第3章文法和语言

第3章文法和语言

当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。3.1文法的直观概念

以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明(或者定义)句子的组成结构，比如汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语，我们采用EBNF来表示这种句子的构成规则。BNF范式和语法图1.巴科斯范式:EBNF <句子>→<主语><谓语> <主语>→<代词>|<名词> <代词>→你|我|他 <名词>→王明|大学生|工人 <谓语>→<动词><宾语> <动词>→是|学习 <宾语>→<代词>|<名词>带<>的叫非终止符,不带<>的叫终止符。<逻辑值>→True|False例子：<句子><主语><谓语>

<代词><谓语>

我<谓语>我<动词><直接宾语>

我是<直接宾语>

我是<名词>我是大学生“我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据，换句话说，这些规则看成是一种元语言，用它描述汉语。这里仅仅涉及汉语句子的结构描述。其中一种描述元语言称为文法。语言概述

语言是由句子组成的集合，是由一组符号所构成的集合。汉语--所有符合汉语语法的句子的全体英语--所有符合英语语法的句子的全体程序设计语言--所有该语言的程序的全体研究语言内容包括：每个句子构成的规律每个句子的含义每个句子和使用者的关系研究程序设计语言每个程序构成的规律每个程序的含义每个程序和使用者的关系语言研究的三个方面语法Syntax语义Semantics语用Pragmatics语法--表示构成语言句子的各个记号之间的组合规律语义--表示各个记号的特定含义。（各个记号和记号所表示的对象之间的关系）语用--表示在各个记号所出现的行为中，它们的来源、使用和影响。每种语言具有两个可识别的特性，即语言的形式和该形式相关联的意义。语言的实例若在语法上是正确的，其相关联的意义可以从两个观点来看，其一是该句子的创立者所想要表示的意义，另一是接收者所检验到的意义。这两个意义并非总是一样的，前者称为语言的语义，后者是其语用意义。幽默、双关语和谜语就是利用这两方面意义间的差异。

如果不考虑语义和语用，即只从语法这一侧面来看语言，这种意义下的语言称作形式语言。形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述。形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。例子:整数(1)单个数字是整数(2)整数再接上数字仍是整数用BNF范式表示:

<1><整数>→<数字><数字>→0|1|2|…|9<2><整数>→<整数><数字><整数>→<数字>|<整数><数字>所以合起来有：

<整数>→<数字>|<整数><数字><数字>→0|1|2|…|9

标识符:以字母开头以后由字母和数字组成的符号串。例子：<标识符>的巴科斯范式

<标识符>→<字母><标识符>→<标识符><字母><标识符>→<标识符><数字><字母>→a|b|…|z

<数字>→0|1|…|9例子：判定字符串a4y是<标识符>

<标识符><标识符><字母>

<标识符>y

<标识符><数字>y

<标识符>4y

<字母>4y

a4y2、语法图作用：直观、形象的描述语法规则。例子：标识符的语法图表示标识符字母字母数字例子：无符号数的语法图表示2.45E+12无符号数无符号整数数字E无符号整数3.2符号和符号串1、字母表:它是非空有穷集。例如：∑={a,b,c}或∑={1,2,3}2、符号：字母表中的元素称为符号。3、符号串：符号的有穷序列，符号串也称为字。用ε来表示空符号串。例如：a,ab,abc,dsfsd4、长度：符号串的长度是指该串所包含的符号个数。用|x|表示符号串x的长度。例如：|a|=1，|abn|=35、连结：设x和y为符号串，则称xy为他们的连结。

例如：x=aa,y=bb,则xy=aabb6、空集：不含任何元素的集合,记为。7、乘积：设A和B是符号串集，则用AB表示A和B的乘积。A={a,b},B={c,d},则AB={ac,ad,bc,bd}8、方幂：设A为符号串集，则定义A0={ε}A1=AAn=An-1A例如：A={a,b}则有：A0={ε}A1={a,b}A2={aa,ab,ba,bb}9、正闭包：设A为符号串集，则用A+表示A的正闭包，其具体定义如下：A+=A1∪A2∪A3∪…例如：A={a},A+={a,aa,aaa,……}10、星闭包：设A为一集合，则定义A的星闭包为A*，其具体定义如下A*=A0∪A+例如：A={a},A*={ε,a,aa,aaa,……}一、引言

例子：y:=a+b*x

3.3文法与语言的形式定义语法：赋值语句由变量加“:=”加表达式构成。语义：右边表达式求值与左变量结合赋值。用途：表达式的值的保存和计算。

形式化方法：用一整套带有严格规定的符号体系来描述问题的理论和方法。

表示文法需要一种工具，其中最常用的工具是所谓的巴克斯范式(BNF)。例子:

A={an|n≥1}A={a2n|n≥1}其BNF表示有：其BNF表示有：(1)

A→a|aA(1)

A→aa|aaA

(2)

A→a|Aa(2)

A→aa|Aaa例子：

A={abna|n≥1}其BNF表示有多种如下：

(1)

A→aBaB→b|Bb(2)

A→aBaB→b|bB(3)

A→aBB→ba|bB如何来描述一种语言？如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示如果语言是无穷的，找出语言的有穷表示。语言的有穷表示有两个途经：生成方式（文法）：语言中的每个句子可以用严格定义的规则来构造。识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要麽能停止并回答“不是”，（要麽永远继续下去。）

文法即是生成方式描述语言的：语言中的每个句子可以用严格定义的规则来构造.下面给出文法的定义.进而在文法的定义的基础上,给出推导的概念,句型、句子和语言的定义.定义文法G定义为四元组(VN，VT，P，S)其中VN为非终结符号(或语法实体，或变量)集；VT为终结符号集；P为产生式(也称规则)的集合；VN，VT和P是非空有穷集。

S称作识别符号或开始符号，它是一个非终结符，至少要在一条产生式中作为左部出现。VN和VT不含公共的元素，即VN∩

VT=φ用V表示VN∪

VT，称为文法G的字母表或字汇表规则，也称重写规则、产生式或生成式，是形如α→β或α∷=β的(α，β)有序对，其中α是字母表V的正闭包V+中的一个符号，β是V*中的一个符号。α称为规则的左部，β称作规则的右部。文法的定义例文法G=（VN，VT，P，S） VN={S},VT={0,1} P={S→0S1,S→01} S为开始符号例文法G=（VN，VT，P，S） VN={标识符，字母，数字} VT={a,b,c,…x,y,z,0,1,…,9} P={<标识符>→<字母> <标识符>→<标识符><字母> <标识符>→<标识符><数字><字母>→a,…,<字母>→z<数字>→0,…,<数字>→9} S表示<标识符>，是初始符号文法的写法1G：S→aAb

A→abA→aAb

A→ε2G[S]：S→aAb

A→abA→aAbA→ε3G[S]：S→aAb

A→ab|aAb|ε二、文法和语言形式定义1、规则式，产生式

例子：

B→b|Bb

A→a|A2、文法G[Z]：规则的非空有穷集合。Z：识别符号，开始符号。V：字母表，符号集合。 例子：G[S]={S→0，S，1} V＝{S，0，1}定义3.1

文法是一个四元组G(VN，VT，P，Z)。非终极符集记为VN(大写字母)终极符集记为VT(小写字母)产生式集记为P初始符记为Z例子：自然数G1(VN,VT,P,Z)和标识符G2(VN,VT,P,I) VN={N,D} VT={0,1,2,9} P={N→D|ND,D→0|1|2||9}G1：N→D|NDD→0|1|2||9标识符G2(VN,VT,P,I) VN={I,D,L} VT={0,1,2,9,a,b…z} P={I→L|IL|ID, L→a|b|…|zD→0|1|2||9}G2：I→L|IL|IDL→a|b|c||zD→0|1|2||9定义3.21、直接推导：设x和y是符号串，若用一次产生式可从x导出y，则称y为x的直接推导，并记为xy。

例子：x=Ab,y=ab,A→a,Abab2、推导：若用若干次产生式可从x串导出y串，则称y为x的推导，并记为xy。+

例子：X=AB,A→a,B→bABaBab即：ABab

+*3、星推导:xy(当且仅当x=y或xy)。

例子：ABAB0步

ABaB1步

ABab2步即：ABab

+*+4、句型：称x为句型，若有Zx，其中Z是文法的开始符。凡是由初始符推出的任意符号集合叫句型。例子：Z→AB,A→a,ZaB5、句子:称x为句子，若有Zx，且x中不包含非终极符的句型。不包含非终极符的句型叫句子。***

例子：G[S]:S→0S1S→01 解: S0S100S11000111 所以有: S={01,0011,000111…}L(G)={0n1n|n≥1}6、语言:所有句子的集合称为语言。设是G给定文法，Z是开始符，则语言L(G)可描述如下：定义3.3设G1,G2为给定文法，如果L(G1)=L(G2),则称G1和G2等价。L(G)=｛x|Zx,x∈VT*｝

*例1已知文法求语言并判断是否等价G1=(VN,VT,P,A)G2=(VN,VT,P,Z)VN={A}VN={A,B}VT={a,b}VT={a,b}P={A→ab}P={A→Bb,B→a}A1ab L(G1)={ab}A2Bbab

L(G2)={ab}G1与G2是等价的。例2:G3[S]:S→A|S-AA→a|b|cG4[S]:S→A|A-SA→a|b|c推导过程如下：SS-ASS-AAabcS-AS-A-AA-A-Aa-b-cG3与G4等价，但G3与G4的语义不同。推导过程如下：SA-SSA-SAA-SA-A-SA-A-Aa-b-cabca-b-c和a-b-c文法的等价若L（G1）=L（G2），则称文法G1和G2是等价的。

如文法G1[A]：A→0R与G2[S]：S→0S1等价A→01S→01R→A1定义3.4

0型文法(短语结构文法):产生式为：α→β，其中α和β是符号串。

1型文法(上下文有关文法)：产生式为：αAβ→αuβ，其中A∈VN，u为非空串。

2型文法(上下文无关文法):A→β，其中A∈VN，β为非空串。3.4文法的类型

3型文法(正则文法):产生式为：A→a,A→bB,其中A,B∈VN,#a,b∈VT是符号串。例子:

G[Z]:Z→a

Z→aA

A→b|bB

B→b

所以:G[Z]是3型文法文法的类型例：1型（上下文有关）文法文法G[S]： S→CD Ab→bA C→aCA Ba→aB C→bCB Bb→bB AD→aD C→ε BD→bD D→ε Aa→bD文法的类型例：2型（上下文无关）文法

文法G[S]： S→AB A→BS|0 B→SA|1

3型文法G[S]： S→0A|1B|0 A→0A|1B|0S B→1B|1|0G[I]： I→lT I→l T→lT

T→dT

T→l

T→d

文法的类型2型文法1型文法0型文法四种文法之间的逐级“包含”关系3型文法文法和语言0型文法产生的语言称为0型语言1型文法或上下文有关文法（CSG）产生的语言称为1型语言或上下文有关语言（CSL）2型文法或上下文无关文法（CFG）产生的语言称为2型语言或上下文无关语言（CFL）

3型文法或正则（正规）文法（RG）产生的语言称为3型语言正则（正规）语言（RL）

文法和语言四种文法之间的关系是将产生式做进一步限制而定义的。语言之间的关系依次：有不是上下文有关语言的0型语言，有不是上下文无关语言的1型语言，有不是正则语言的上下文无关语言。 根据形式语言理论,文法和识别系统间有这样的关系0型文法（短语结构文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且任何0型语言都是递归可枚举的。1型文法（上下文有关文法）：产生式的形式为α1Aα2→α1βα2，即只有A出现在α1和α2的上下文中时，才允许β取代A。其识别系统是线性界限自动机。3型文法（正规文法RG）：产生的语言是有穷自动机（FA）所接受的集合

2型文法（上下文无关文法CFG）：产生式的形式为A→β，β取代A时与A的上下文无关。其识别系统是不确定的下推自动机。

3型文法产生的语言是有穷自动机（FA）所接受的集合.定理

设G=（VN，VT，P，S）是3型文法，则存在一个有穷自动机M=(K,∑,f,A,Z)，使得L(M)=L(G)有穷自动机NFAM这样构造：·∑=VT·K=VN∪{N},N为一个新状态,它不在VN中·A=S·Z={N}·对G中的形如D→tB的产生式,t为终结符或ε,有f(D,t)=B；对G中形如D→t的产生式，t为终结符或ε,有f(D,t)=N;

对VT中的每一个a,有f(N,a)=φG［Ｓ］：S→aA|bB

A→bB|aD|aB→aA|bD|bD→aD|bD|a|bBASaaabbba,bDZabab使其右部为空字符串的产生式，称为空产生式。产生式记为A→或A→例子:G[S]:S→AaBA→AB|B→bB| 所以:G[S]含有空产生式定义3.5

直接左递归：若有产生式A→A…

直接右递归：若有产生式A→…A

左递归：若有推导式A

A…

右递归：若有推导式A…A

递归：若有产推导A…A…

+++例子： 直接递归：A→AaB→aBB 左递归：S→Qc|cQ→Rb|bR→Sa|a QRbSabQcab QQcab规范推导和句柄定义3.6

设xUyxuy是一直接推导。如果U是句型xUy中的最右非终极字符，则称该推导为规范直接推导并记为xUy

xuy。如果xy中的每步都是规范直接推导，则称该推导为规范推导并记为xy。

r+r+3.5上下无关文法及其语法树如果每步都是最右非终极字符，则也称该规范推导为最右推导。例子：G[S]：S→ABA→Aa|bBB→a|Sb SABbBBbaB(最左推导) SABASbAABbAAabAbBab(最右推导)

SABASbbBSbbaSb(非左非右)语法树与二义性定义3.8设G=(VN,VT,P,S)是给定文法,则称满足下面条件的树为G的一棵语法树。

每个结点都标有G的一个文法符号,且根结点标有初始符S,非叶结点标有非终极符。如果一个非叶结点A有n个儿子结点(从左到右)B1,B2,…,Bn,则A→B1B2…,Bn一定是G的一个产生式。定义3.9

由某一结点及其所属分枝组成的部分树称为原树的一棵子树。

只有单层分枝的子树称为简单子树。例子：Z→ABA→aB→bcSABacb定义3.7

假设Z

xUy，U

u，则称句型xuy中的u为该句型的短语，其中Z为初始符。

假设有ZxUy，Uu，则称句型xuy中的u为该句型的简单短语。

最左边的简单短语称为句柄。

*+*3.6句型的分析例子：G[S]：S→ABA→AaA→bBB→aB→Sb

解：SABbBBbaBbaSbyBSbuxUU

Sb是句型baSb的短语，简单短语SbaB*解：SABASbbBSbbaSbyBauxU

a是句型baSb的短语，且是简单短语。USbBSb*yuxU

ba是句型baSb的短语，但不是简单短语。所以：ba,a,Sb是句型baSb的短语a,Sb是句型baSb的简单短语a是句型baSb的句柄。 USASb*Aba＋解：SABASbbBSbbaSb定理3.11、每个句型都有一棵语法树，每个语法树的叶组成一句型。2、每棵子树的叶组成短语，每棵简单子树的叶组成简单短语，最左简单子树的叶组成句柄。3、用语法树可证明每个句子都有一规范推导。构造语法树G[E]：E→E+T|T

T→T*F|F

F→(E)|a

EE+TT+TF+Ta+Ta+T*F

a+F*Fa+a*Fa+a*a

EEE+TE+TTEE+TTFEE+TT+TF+Ta+Ta+T*F

a+F*Fa+a*Fa+a*aEE+TE+T*FE+T*aE+F*aE+a*a

T+a*aF+a*aa+a*aEE+TT+TT+T*FF+T*FF+F*F

a+F*Fa+F*aa+a*a

EE+TTT*FFFaaa看不出句型中的符号被替代的顺序例子：G[S]：S→ABA→Aa|bBB→a|Sb

字符串：bBABb短语：bB,AB,ABb简单短语：bB,AB句柄：bBSABbBbSBA上下文无关文法的语法树的用处用于描述上下文无关文法句型推导的直观方法例:G[S]: S→aAS A→SbA A→SS S→a A→baS

aASSbAa

a

b

a句型aabbaa的语法树（推导树）叶子结点：树中没有子孙的结点。

从左到右读出推导树的叶子标记连接成的文法符号串，为G[S]的句型。也把该推导树称为该句型的语法树。上下文无关文法的语法树推导过程中施用产生式的顺序例:G[S]: S→aAS A→SbA A→SS S→a A→baS

aASSbAa

a

b

aSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa一棵语法树表示了一个句型的种种可能的(但未必是所有的)不同推导过程，包括最左(最右)推导。但是，一个句型是否只对应唯一的一棵语法树呢?一个句型是否只有唯一的一个最左(最右)推导呢?例：G[E]:

E→i E→E+E E→E*E E→(E)EE+EE*EiiiEE*EiE+Eii句型i*i+i的两个不同的最左推导：推导1：EE+EE*E+Ei*E+Ei*i+Ei*i+i推导2：EE*Ei*Ei*E+Ei*i+Ei*i+i定义3.10如果一个文法G存在某个句子,使得它有两棵语法树,则称G为二义性文法。例子：证明G:E→E+E|E*EE→(E)|i是二义性文法。

因为句子i+i*i具有两棵语法树分别如图所示。EEE+i*EEiiEEE+i*EEii例子：证明G[S]:S→IfBThenSS→IfBThenSElseS是二义性文法。IfB1ThenIfB2ThenS2ElseS3

该句子具有二义性(其中S表示语句，Sx无条件语句，Bx表示布尔变量)，分析情况如下：IfB1ThenIfB2ThenS2ElseS3Ifx>1thenifx>2theny:=aelsey:=b解释1:Ifx>1thenifx>2theny:=aelsey:=b解释2:Ifx>1thenifx>2theny:=aelsey:=bIfB２ThenS２ElseS３SIfB１ThenS１第一种：IfB1ThenIfB2ThenS2ElseS3第二种：IfB１ThenS１ElseS３SIfB２ThenS２IfB1ThenIfB2ThenS2ElseS3改写文法如下：S→M|UM→IfBThenMElseM|S1U→IfBThenS|IfBThenMElseU怎样排除二义性：语义上限制。改写文法。M为匹配语句，U为非匹配语句。得到语法树如下：UIfB１ThenSSIfB２ThenS２ElseMMS33.7有关文法实用中的一些说明文法中不含有有害规则和多余规则有害规则：形如U→U的产生式。会引起文法的二义性多余规则：指文法中任何句子的推导都不会用到的规则文法中不含有不可到达和不可终止的非终结符1）文法中某些非终结符不在任何规则的右部出现，该非终结符称为不可到达。2）文法中某些非终结符，由它不能推出终结符号串，该非终结符称为不可终止。1.文法中不含有A→A的规则

例:S→0S1|01无二义性,可以改为:S→0S1|01|S句子0011有二义性。S0S101S0S101SS0S101S

2.文法中不包含多余规则

①不可到达：所有推导均不会用到此规则

②不可终止：推导不出终结符号串例子:文法G[S]：(1)S→Be(5)A→e(2)B→Ce不可终止(6)C→Cf不可终止(3)B→Af(7)D→f不可达(4)A→Ae对文法G=(VN,VT,S,P),为了保证其任一非终结符A在句子推导中出现,必须满足如下两个条件：

1.A必须在某句型中出现。即有SαAβ,其中α,β属(VT∪VN)*。

2.必须能够从A推出终结符号串t来。即At,其中t∈VT*。 因此检查文法是否包含多余规则是很有必要的。*+3.9文法的等价转变换定理3.2

对任一文法G1都可以构造文法G2使得L(G1)=L(G2)，并且G2有这样的特点，即文法的初始符不出现于产生式的右部。例子：G:E→E+E|E*E|(E)|i可改写为：G:E’→EE→E+E|E*E|(E)|i

定理3.3

对任一文法G1都可以构造文法G2使得L(G1)=L(G2)，并且G2的每个非终极符出现于某句型中。

定理3.4对任一文法G1均可构造文法G2使得L(G1)=L(G2)，且在G2中没有形如A→B的产生式,其中B∈VN。证明：我们称形如A→B的产生式为特型产生式。G2的构造算法是： 1、对每个A∈VN，求βA={D|AD,D∈VN} 2、令G1中所有的非特型产生式为G2的产生式。 3、若有D∈βA，且有D→x(非特型)，则令A→x∈G2 4、删除无用的产生式。*例子：G[A]:A→B|aB→b求解如下： 保留：A→aB→b 扩充：A→BB→b

A→b G[A]：A→a|bB→b(多余) G[A]:A→a|b例子：设有如下文法G1：A→B|dDB→A|C|bC→B|cD→d|DaA→BA→BB→A

A→AA→BB→