形式语言与文法

形式语言与文法第1页，共93页，2023年，2月20日，星期四§1.符号串

符号串是形式语言中最基本的名词.一,字母表与符号串

1,字母表∑

定义:元素的非空有穷集合例:∑={a,b,c}(a,b,c字母表)

∑={0,1}(二进制数字字母表)

∑={汉字,数字,标点符号,…}(汉字组成的字母表)

注:元素可是字母、数字或其他符号.

字母表中至少有一个元素.第2页，共93页，2023年，2月20日，星期四2.符号(字符)

定义：字母表中的元素.

注:符号是字母表中不可再分解的最小单位.

3.符号串定义：字母表中的符号组成的有穷序列.

例:∑={a,b,c}

符号:a,b,c

符号串:a,b,c,ab,ac,aa,ba,ca,abc,…

例;设字母表A={0,1}A中的符号:0,1A中的符串:0,1,01,10,00,11,001,010,

…,01000,…第3页，共93页，2023年，2月20日，星期四

显然:字母表上的符号串可形成一个集合(可数无穷)注:1.符号串的组成与符号串组成的顺序有关.如01≠10,ab≠ba2.空符号串为不包含任何符号的符号串,记为:ε3.符号串的长度:符号串所含符号的个数.设符号串为x,则x的长度为∣x∣。

例:∣a∣=1∣abc∣=3

特别：|ε|＝0即空符号串的长度为零．二．符号串的运算１．连接运算

定义：设x和y为符号串，则xy被称为x与y的连接．设x＝abc，y＝10a则xy＝abc10a；yx＝10aabc第4页，共93页，2023年，2月20日，星期四２．符号串的方幂设有符号串x，则x的n次连接称为x的n次方幂，记为:x例：x＝ε

（注:x≠１）

x＝x

x＝xx

x＝xx＝xx＝xxx

……

x＝x

x＝xx＝xx…x

n次连接例:x＝abc则x＝ε

，x＝abc，x＝abcabc

即︱x︱＝０，︱x︱＝３，︱x︱＝６n0012322nn－1n－1011022第5页，共93页，2023年，2月20日，星期四３．符号串集合的乘积

设AB＝｛xy︱x∈Ａ，y∈Ｂ｝即:AB是x∈Ａ,且y∈Ｂ的所有符号串xy构成的集合．例:设A＝｛a，b｝，B＝｛c，d｝则AB＝｛ac，ad，bc，bd｝

注：{ε

}A=A{ε}=AA=A=A(其中为空集)={}

注:ε

不属于，即空符号串并不属于空集

第6页，共93页，2023年，2月20日，星期四4.符号串集合的方幂

设A为符号串集合,则定义

A={ε}A=AA=AAA=AA=AA=AAA

……A=AA=AA=AA……A(n个)

例:设A={a,b}A={ε}A={a,b}A={aa,ab,ba,bb}(A共有2=4个长度为2的元素)

A=AA={aa,ab,ba,bb}{a,b}={aaa,aba,baa,bba,aab,abb,bab,bbb}

(A共有2=8个长度为3的元素)012322nn－1n－101232233第7页，共93页，2023年，2月20日，星期四5.符号串集合的正闭包A和闭包A⑴.符号串集合的正闭包A

设A为符号串集合,则A定义为:

A=AUAUAU……UAU……

例设A={a,b}则

A={a,b}U{aa,ab,ba,bb}U……={a,b,aa,ab,ba,bb,aaa,…,bbb,……}={a,b}

即:A包括了由A上的元素a,b构成的所有符号串.⑵.符号串集合A的闭包A.A=AUAUAU…UAU……(A=AUA)

即A={ε}UA=AU{ε}(A=A－{ε})＋＊＋＋＋123n＋＋＊＊012n＊0＋＊＋＋＋＊+第8页，共93页，2023年，2月20日，星期四例设A={a,b}则

A={ε,a,b,aa,ab,ba,bb,aaa,…,bbb,……}={a,b}

显然:对于所有的A,有ε

∈A＊＊＊第9页，共93页，2023年，2月20日，星期四§2.文法和语言的形式定义一.文法与语言的关系

●语言:由定义在该语言字母表上,且按一定组成规则所构成的句子的集合.

即:字母表{字符串(句子)}(语言)

●语言的描述

⑴.当语言为有穷个句子的集合时,可用枚举的方法表示语言.

⑵.当语言为无穷个句子的集合时,则用有无穷的语法规则(文法)描述无穷的句子的结构.语法规则第10页，共93页，2023年，2月20日，星期四例:汉语:人们无法列出全部的句子.但人们可以给出一些规则,用这些规则来说明(或定义)句子的组成结构.

如:汉语句子结构:<句子>=<主语>+<谓语><谓语>=<动词>+<直接宾语><主语>=<代词>︱<名词>…………

用扩充BNF来表示这种句子的结构:<句子>∷=<主语><谓语>(∷=表示“定义为”，“产生”，“生成”)<主语>∷=<代词>︱<名词>(︱表示“或者”)<代词>∷=我︱你︱他(<>表示非终结符)<名词>∷=王明︱大学生︱工人︱英语

<谓语>∷=<动词><直接宾语>(不加<>表示终结符)第11页，共93页，2023年，2月20日，星期四

<动词>∷=是∣学习

<直接宾语>∷=<代词>∣<名词>利用以上规则(文法)推导句子:我是大学生.<句子><主语><谓词><代词><谓语>

我<谓语>

我<动词><直接宾语>

我是<直接宾语>

我是<名词>

我是大学生利用上列文法:可以产生的句子:我学习英语,他学习,语,他是工人,….(很多句子)第12页，共93页，2023年，2月20日，星期四

利用上列文法不可产生“我大学生是”.它不符合以上规则.

文法的作用:不仅严格定义句子的结构,也是为了用有限的规则把语言的全部句子描述出来。它是用有穷的集合刻画无穷集合的工具.

文法:语言的语法规则的有穷表示.(文法又称元语言)注:1.有穷的文法通过推导的方法,可以推导出给定字母表上的所有句子.2.描述文法的所有字符构成了语言的字母表.3.通过文法在推导合法句子过程中会有多个句型产生.4.合法的句型和句子是用字符串表示的.第13页，共93页，2023年，2月20日，星期四二.文法的形式定义1.规则(产生式,生成式,重写规则)是一个符号与一个符号串的有序对(A,β)

常写成:A∷=β或A→β

其中:A是规则的左部.它是某个字母表∑的正闭包∑中的一个符号.即A∈∑.β是规则的右部.它是∑中一个符号串.(包括ε)2.文法的形式定义定义:文法G是一个四元组,它是规则的非空有穷集合.G=(V,V,P,S)

其中:V是文法规则式中的非终结符号集.V是文法规则式中的终结符号集.＋＋NTNT﹡第14页，共93页，2023年，2月20日，星期四

V∩V=Ф P是文法的规则式集。

S是文法的开始符号（识别符号）。S∈V非终结符号：出现在产生是左边，能派生出符号和符号串的符号,常用大写字母表示，即，每一个非终结符号表示一定的符号串。它至少要在产生式左边出现一次。终结符号：不能派生出符号串的符号，它是组成语言不可再分的基本符号，一般用小写字母表示。NTN第15页，共93页，2023年，2月20日，星期四例：文法G=(V,V,P,S)其中VN={S} VT={0,1} P={S→0S1,S→01}一般约定:1.只写出文法的产生式

2.第一条产生式的左部是开始符号，且习惯用G（开始符号）表示。上例文法可写成：

G[S]:S::=0S1 S::=01NT第16页，共93页，2023年，2月20日，星期四例：G[<标识符>]:

<标识符>::=<字母>|<标识符><字母>|<标识符><数字>

<字母>::=a|b|c|…|z

<数字>::=0|1|2|…|9

其中：VN={<标识符>，<字母>，<数字>} S={<标识符>} VT={a,b,c,…,z,0,1,2,…,9

}字母表：V=VN∪VT={<标识符>,<字母>,<数字>,a,b,c,…,z,0,1,2,…,9

}第17页，共93页，2023年，2月20日，星期四3.推导有了文法，怎样由文法推导出与该文法相应的语言？为此引入了“推导”等概念。直接推导设x,y是V*中任意符号串，若用一次规则式可以从x推出y，则称y是x的直接推导，记为：xy。（或称符号串x直接产生了符号串y，或称y直接归约到x）第18页，共93页，2023年，2月20日，星期四例：设G[S]:S::=0S1|01

则有如下一些直接推导：S01（利用S::=01）S0S1（利用S::=0S1）0S10011（利用S::=01）0S100S11（利用S::=0S1）说明：每利用文法中的一条规则U::=u一次，均可得到一次直接推导：

Uu第19页，共93页，2023年，2月20日，星期四推导（＋推导） 若使用若干次规则式可以从x推出y，则称y为x的推导，记为：x＋y（或称x产生y，或称y规约到x），或记为：xy例：上例：

0S100S11000S11100001111∴0S1+00001111

（推导长度为3）＋第20页，共93页，2023年，2月20日，星期四广义推导（＊推导） 若x＋y或者x＝y（表示0步推导），则写为x＊y（反之亦然，即：x＊y，当且仅当x＋y或者x＝y）例，上例中：0S1+00001111也可记为：0S1*00001111注：直接推导、推导、广义推导的区别： 推导长度n不同： 直接推导：n＝1

推导：n≥1

广义推导：n≥0(0步推导：如S＝s)＊包涵＋包涵第21页，共93页，2023年，2月20日，星期四4.句型和句子设有文法G[S],若有S＊x,则称符号串x为文法G[S]的句型。换句话说：凡是由识别符号推导出来的任意符号串称为句型。句子：仅有终结符号组成的句型称为句子。区别：符号串x∈(VN∪VT)*;x称为句型，

符号串x∈VT*;x称为句子。第22页，共93页，2023年，2月20日，星期四例：G[S]:S::=01|0S1 S01S0S100S11000111可见：01,0S1,00S11,000111均为文法G[S]的句型。其中：01，000111为句子（说明句型包含了句子，句子是特殊的句型）但是：符号串000S11,0000111都不是文法G[S]的句型。第23页，共93页，2023年，2月20日，星期四例：已知文法G[E]：E::=E+E|E*E|(E)|i (其中:VN={E} VT={+,*,i,(,)})试证明:符号串(i*i+i)是文法G[E]的一个句子。证明：只要证明(i*i+i)是文法G[E]的一个存在的推导）(需从开始符号出发)

E=>(E) =>(E+E) =>(E*E+E) =>(i*E+E) =>(i*i+E) =>(i*i+i)即：E=>＊(i*i+i)所以,符号串(i*i+i)是文法G[E]的一个句子。第24页，共93页，2023年，2月20日，星期四三、语言的形式定义：定义：由文法G[S]产生的所有句子的集合。即：

L(G[S])={x|S=>+x,且x∈V*}注：一旦文法给定，语言就确定。语言L(G)是V*的子集。（语言是字母表中终结符号串闭包的子集） 即：属于L(G)的句子属于V*

反之,属于V*的符号串x不一定属于L(G)。TTTT第25页，共93页，2023年，2月20日，星期四例：已知文法G[S]：

S::=0S1|01求:L(G)=?解：分析：S=>0S1

=>00S11

=>000S111

…

=>0n-1S1n-1

=>0n1n

即：S=>＊0n1n ∴G描述的语言：L(G[S])={0n1n|n≥1}但：VT’＝{0,1,00,01,10,11,000,…,111,0000,…,0011,…,1111,…}，可见L(G)仅是VT‘的真子集。＋＋第26页，共93页，2023年，2月20日，星期四例：已知文法：G[S]:S∷=0S|1S|ε,求L(G)=?解：L(G[S])={ε,0,1,01,11,00,10,…}

={x|x∈{0,1}*}第27页，共93页，2023年，2月20日，星期四例：已知： S∷=aB|bA A∷=a|aS|bAA B∷=b|bS|aBB求：L＝？解： S=>aB=>ab S=>aB=>abS=>abaB=>abab S=>aB=>aaBB=>aabB=>aabb又∵S=>bA=>ba

S=>bA=>baS=>babA=>baba

S=>bA=>bbAA=>bbaA=>bbaa∴L(G[S])={x|x∈{a,b},且x中a，b个数相同}

反过来，给定语言L(G)后，若要写出能正确描述此语言的文法，是有一定难度的。+第28页，共93页，2023年，2月20日，星期四例：试对语言L(G)={(n)n|n=0,1,2,…}构造相应的文法G。解：（1）首先分析L是由怎样的符号串x组成的。 当n=0时，x=ε

当n=1时，x=()

当n=2时，x=(())

当n=3时，x=((())) … ∴L(G)={ε,(),(()),((())),…}第29页，共93页，2023年，2月20日，星期四(2)归纳集合L(G)的组成特点：L(G)中每个符号串呈对称形式，即(和)成对出现。L(G)为无穷集合，因此描述出的规则中必然含有递归定义。L(G)中的终结符号只有两个:(和)。(3)写出规则：S∷=(S)|ε即，定义此语言L(G)的文法：

G:VT={(,)},VN={S},S为开始符号，产生式：

P：

S∷=(S)|ε第30页，共93页，2023年，2月20日，星期四例：给出语言L(G)＝{anbncm|n≥1,m≥0}的对应文法解：分析：将anbn看成一个整体用一个非终结符号A来表示，cm看成另一个整体用非终结符B来表示。设S为G的识别符号，则有S∷=AB，而由A推出anbn，B推出cm。保证anbn成立，即a,b个数相等，且大于等于1。所以可以用产生式：A∷=aAb|ab

又因为m可以为0,所以S::=AB改写为S::=AB|A;

又由于A∷=aAb|ab，则对B容易看出B∷=cB|c ∴ S∷=AB|A S∷=AB A∷=aAb|ab 或者： A∷=aAb|ab B∷=cB|c B∷=cB|c|ε第31页，共93页，2023年，2月20日，星期四例：设字母表∑＝{a,b},试设计一个文法，描述语言L＝{a,b|n≥1}解：分析语言由怎样的符号串组成。 当n=1时，L={aa,bb}

当n=2时，L={aaaa,bbbb}

当n=3时，L={aaaaaa,bbbbbb} … L={aa,bb,aaaa,bbbb,aaaaaa,bbbbbb,…}即：语言由偶数个a和偶数个b的符号串组成。所以，描述语言的文法：G[A]: A∷=aa|aaB|bb|bbD B∷=aa|aaB D∷=bb|bbD2n2n第32页，共93页，2023年，2月20日，星期四可以写出另一个文法：G1[A]: A∷=B|D B∷=aa|aBa D∷=bb|bDb可见，对于给定语言，描述该语言的文法不是唯一的。注：①描述一个语言的文法不是唯一的 ②若不同的文法产生相同的语言，则称这些文法是等价的。第33页，共93页，2023年，2月20日，星期四例：设有文法G1={VN,VT,P,A}其中： VN={A} VT={a,b} P={A::=ab}显然： L(G1)={ab}文法 G2={VN,VT,P,A}其中： VN={A,B} VT={a,b} P={A::=Bb,B::=a}显然： L(G2,)={ab}即：L(G1)=L(G2)，且G1=G2③若语言在语法上等价，并不一定意味着语义上等价。第34页，共93页，2023年，2月20日，星期四例：G3[S]和G4[S]它们的VN和VT相同：

VN={S,A},VT={a,b,c}而,G3[S]的P为：

S::=A|S-A A::=a|b|c G4[S]的P为：

S::=A|A-S A::=a|b|c显然：G3[S]和G4[S]等价（语法），因为它们都产生相同的句子：

{a,b,c,a-b-c,a-b-b-c,…}但：句子的含义（语义）不一定相同：例如：由G3[S]推导出的句子：a-b-c其含义为(a-b)-c

由G4[S]推导出的句子：a-b-c其含义为a-(b-c)第35页，共93页，2023年，2月20日，星期四④文法应该能准确地描述语言，不能扩大或缩小。例：设计一个表示所有标识符的文法。解：分析：标识符：字母|字母开头的字母数字串,用B表示标识符；L-字母；D-数字：则G[B]的产生式P: B::=L|BL|BD L::=a|b|c|…|x|y|z D::=0|1|2|…|9 ……可以表示a1b2c3第36页，共93页，2023年，2月20日，星期四若将产生式设计成P1：

B::=L|BD L::=a|b|c|…|x|y|z D::=0|1|2|…|9 表示：字母开头，后面全是数字：abc1， 不能表示a1b2c3显然：P1缩小了标识符的表示，比P描述的范围缩小了若将产生式设计成P2：

B::=L|BL|BD|D L::=a|b|c|…|x|y|z D::=0|1|2|…|9 显然:P2也不能准确地描述，扩大了P的描述范围第37页，共93页，2023年，2月20日，星期四§3与语法分析有关的概念

一、短语、简单短语与句柄短语：设有文法G[S]，W=αβδ是G的一个句型。若有识别符号S=>＊αAδ,且A=>+β,则称β是相对非终结符A的句型w的短语。 特别，如果上式A=>+β为：

A=>β

则称β为句型w的简单短语（直接短语）第38页，共93页，2023年，2月20日，星期四例：设有文法G=({S,A,B},{a,b},P,S)其中P为：1.S::=AB2.A::=Aa3.A::=bB4.B::=a5.B::=Sb试求句型baSb,bBABb和baabaab全部短语，简单短语。解：先讨论句型w=baSb,其中子串b,a,S,ba,aS,Sb,baS,aSb.是句型w的短语吗？ 根据短语定义，可由句型的推导中找到全部短语及简单短语。最左推导：第39页，共93页，2023年，2月20日，星期四由此可见，下式成立：①∵S=>*S,且S=>+baSb∴baSb是短语(句型本身是短语)(注意:主要求异于句型本身的短语). ②又∵

S=>*AB,且B=>Sb∴句型baSb中子串Sb也该句型（相对于B）的短语,且是简单短语。③又∵

S=>*bBSb,且B=>a∴句型baSb中子串a也该句型（相对于B）的短语,且是简单短语。④又∵

S=>*ASb,且A=>+ba∴句型baSb中子串ba也该句型（相对于A）的短语.注:短语是句型中的子串,在推导中不是句型中的子串不能作短语。如:S=>*ASb,A=>bB;则由于bB不是句型baSb中子串,所以他不是该句型的短语.第40页，共93页，2023年，2月20日，星期四∴sb，a，ba是句型baSb异于自身的短语(句型本身是短语),其中Sb,a是简单短语。最右推导：同样可求出同上的该句型的短语,同学们可自求.

可用同样的方法分析句型bBABb和baabaab的全部短语和简单短语（略）同学们也可自求。句柄：句型的最左简单短语特征：句柄至少是简单短语（某规则的右部），且为最左简单短语（具有最左性）。例如：上例中a是最左简单短语――句柄。第41页，共93页，2023年，2月20日，星期四注:短语、简单短语与句柄的关系:

●它们都是针对某个句型而言的,离开了句型来谈短语、简单短语与句柄,是毫无意义的.

●句柄一定是简单短语和短语,反之不成立.

●简单短语和句柄一定是某个产生式的右部符号串,短语不是(他作为我们寻找和判断句型的简单短语的依据);但文法中产生式的右部符号串不见得都是简单短语或句柄.二、最右（左）推导，规范推导和规范规约，规范句型(1)最右（左）推导：在推导过程中，任何一步α=>β都是对α中最右（左）非终结符进行替换。称为最右（左）推导。特别：最右推导称为规范推导。得到的句型称为规范句型。第42页，共93页，2023年，2月20日，星期四例：设有文法G的规则集P为：

S::=AB A::=Aa|bB B::=a|Sb给出babaab的最右（左）推导解：最右推导：

S=>AB=>ASb=>AABb=>AAab=>AbBab=>Abaab=>bBbaab=>babaab规范推导。最左推导：S=>AB=>bBB=>baB=>baSb=>baABb=>babBBb=>babaBb=>babaab忽左忽右推导：第43页，共93页，2023年，2月20日，星期四归约：将句型中某一个子串用一个非终结符替换的过程。 若有A::=α,则xAy=>xαy，有：

xαy=>xAy……规约(2)规范归约（又称最左规约）：规范推导（最右推导）的逆过程。例：G[N1]: N1::=N N::=ND|D D::=0|1|2

最右推导：N1=>N=>ND=>N2=>D2=>12

最左规约：

12=>D2=>N2=>ND=>N=>N1第44页，共93页，2023年，2月20日，星期四三、文法的递归1．递归规则若文法中有形如规则:A::=A…，称为规则左递归。若文法中有形如规则:A::=…A，称为规则右递归 。若文法中有形如规则:A::=…A…，称为规则递归。（规则递归称为直接递归）２．文法的递归性如果有推导A=>+A…，称文法左递归如果有推导A=>+…A，称文法右递归 如果有推导A=>+…A…，称文法递归（文法递归称为间接递归）第45页，共93页，2023年，2月20日，星期四例：G[N1]: N1::=N N::=ND（规则左递归：直接递归）例：G[U]: U::=Vx V::=Uy|a∵U=>Vx=>Uyx (左递归文法:间接递归)

G[U]的规则中无规则左递归，但在推导过程中存在左递归，所以G[U]是左递归文法。作用：用递归规则可以定义无穷集合的语言。例：G[A]:

A::=B

B::=D|DD|DDD…，

D::=0|1|2|…结论：若语言为无穷集合，描述语言的文法一定是递归的。可用A::=AD替代第46页，共93页，2023年，2月20日，星期四四、语法树与文法的二义性句型的语法树(1)作用：直观地求出一个句型的短语，简单短语和句柄。直观地表示一个句型（或句子）的推导或归约过程，即它是语法分析的工具。可以判断一个文法的二义性问题。第47页，共93页，2023年，2月20日，星期四(2)句型推导的语法树表示用树型结构直观地表示一个句型的推导过程，称为该句型的一棵语法树（又称推导树）语法树的构成：树的根为文法的识别符号；树的中间结点是文法的非终结符；叶子结点为文法的终结符号或非终结符号。若一个标记为U的结点，它有标记依次为x1x2x3……xn的直接后继结点，即U::=x1x2x3……xn必定是文法G的一条规则。一个句型的推导过程用语法树表示：第48页，共93页，2023年，2月20日，星期四例：设有文法G[E]：

E::=E+T|E-T|T T::=T*F|T/F|F F::=(E)|i根据推导，画出句型（T+I)＊i-F的语法树：最右推导：E=>E-T=>E-F=>T-F =>T*F-F=>T*i-F=>F*i-F=>(E)*i-F =>(E+T)*i-F =>(E+F)*i-F =>(E+i)*i-F =>(T+i)*i-F第49页，共93页，2023年，2月20日，星期四第50页，共93页，2023年，2月20日，星期四最左推导：从左向右画子树。子树：由某一结点连同所有分支组成的部分。简单子树：包括叶子在内的单层子树。(3)语法树中的短语，简单短语和句柄的概念短语：子树的末端结点形成的符号串是相对子树根的短语。简单短语：简单子树末端结点形成的符号串是相对于简单子树根的简单短语。句柄：最左简单子树的末端结点形成的符号串是句柄。第51页，共93页，2023年，2月20日，星期四例：设有文法G[E]：

E::=E+T|E-T|T T::=T*F|T/F|F F::=(E)|i求(T+i)*i–F的短语，简单短语和句柄。

(T+i)*i–F为句型的相对根E的短语。

(T+i)*i为句型的相对于以T为根的子树的短语。

(T+i)为句型的相对于以F为根的子树的短语。

T+i为句型的相对于以E为根的子树的短语。

T为句型的相对于以E为根的子树的短语，且为简单短语。第一个i为句型的相对于以F为根的子树的短语，且为简单短语。第二个i为句型的相对于以F为根的子树的短语，且为简单短语。F为句型的相对于以T为根的子树的短语，且为简单短语。在四个简单短语T，i，i，F中，T为句型的句柄第52页，共93页，2023年，2月20日，星期四例：设有文法G[S]： S::=(T)|a|ε T::=T,S|S求句子（a,(a,a)）最右推导的逆过程（最左规约）每一步的句柄。——最右推导：S =>(T) 句柄:（T）

=>(T,S) 句柄:T,S =>(T,(T)) 句柄:(T) =>(T,(T,S))句柄:T,S =>(T,(T,a))句柄:第三个a =>(T,(S,a)) 句柄:S =>(T,(a,a)) 句柄:第二个a =>(S,(a,a)) 句柄:S =>(a,(a,a)) 句柄:第一个a第53页，共93页，2023年，2月20日，星期四第54页，共93页，2023年，2月20日，星期四文法的二义性所谓文法的二义性是指文法存在的某个句子对应两棵不同的语法树（或说存在两个不同的最左（右）推导）。例：文法G[E]：E::=E+E|E*E|(E)|i

句子i*i+i有两个不同的语法树（最左推导）

E=>E+E=>E*E+E =>i*E+E =>i*i+E =>i*i+i第55页，共93页，2023年，2月20日，星期四E=>E*E=>i*E =>i*E+E =>i*i+E =>i*i+i∴G[E]具有二义性文法的二义性会导致对二义性文法的句子结构产生多种不同的理解，造成语法分析和语义理解的不确定性。希望描述语言的文法是无二义性的。第56页，共93页，2023年，2月20日，星期四文法二义性的消除(1)

不改变文法中原有的语法规则，仅加进一些语法的非形式规定。例如，对于上例文法G[E],不改变已有的4条规则，仅加入运算符的优先顺序和结合规则；即*优先于+；+,*服从左结合。这样，句子i*i+i只有唯一的一棵语法树（如上例的第一个图）。(2)改写文法。把排除二义性的规则合并到原文法中，构造一个等价的无二义性的文法。第57页，共93页，2023年，2月20日，星期四例如，对于上例文法G[E],将运算符的优先顺序及结合规则（*优先于+；+,*服从左结合）加到原文法中：

E::=E+T|T T::=T*F|F F::=(E)|i

则句子i*i+i只有唯一的语法树可见：对于有二义性文法描述的语言，有时可以找到等价的无二义性文法来描述它。第58页，共93页，2023年，2月20日，星期四例：某语言的条件语句的文法G为：

S::=ifbS|ifbSelseS|A(A为其它语句)证明G具有二义性，并消除之。分析：该文法的句子ifbifbAelseA对应的两棵不同的语法树

第59页，共93页，2023年，2月20日，星期四所以G是具有二义性的文法。消除二义性：

(1).不改变已有规则，仅加入一项非形式语法规定：else与前面最接近的if配对。这时句子ifbifbAelseA只唯一对应语法树(a).(2).改造文法G为G’:S::=S1|S2S1::=ifbS1elseS1|AS2::=ifbS|ifbS1elseS2

第60页，共93页，2023年，2月20日，星期四注：文法的二义性和语言的二义性是两个不同的概念。通常只说文法的二义性，而且不说语言的二义性，因为描述语言的文法不唯一，可能存在一个文法G有二义性，一个文法G’无二义性：使L(G)=L(G’)如果语言是二义性的，则它不存在无二义性的文法，这样的语言称为先天二义性语言。如：L={abc|i=j或j＝k,i,j,k≥1}便是这种语言。已证明，不存在一个算法，它能在有限步骤内确切地判定任意给定一个上下文无关文法是否为二义性文法，或它是否会产生一个先天二义性的上下文无关语言。ijk第61页，共93页，2023年，2月20日，星期四§4文法与语言的分类分类的依据：将文法中的规则施加不同的限制。文法被划分为4类：0～3型文法一、0型文法（短语文法） 若文法G的规则式具有形式：α::=β(其中α∈(VN∪VT)+,β∈(VN∪VT)*)即α，β都是符号串对它们没有作任何限制。（也可以|α|>|β|）由0型文法产生的语言称为0型语言0型文法的能力相当于图灵机。第62页，共93页，2023年，2月20日，星期四例：有产生式P：

S::=0AB 1B::=0 B::=SA|01 A1::=SB1 A0::=S0B|α|>|β|为0型文法该文法推不出任何句子：L={}第63页，共93页，2023年，2月20日，星期四二、1型文法（上下文有关文法）若文法G中规则呈现下列的形式：

αAβ::=αuβ其中：A∈VN，u∈(VN∪VT)+,α,β∈(VN∪VT)*则称G为1型文法，所产生的语言为1型语言。 由于利用规则将A替换为u时，必须考虑A在上下文α…β中出现的情况，即与上下文有关，故又称为下文有关文法。特点：每个规则式：|左边|≤|右边|；规则右部符号个数至少与左部符号个数一样多。第64页，共93页，2023年，2月20日，星期四例：设有G=(VN

，VT

，P，S) VN={S,B,C} VT={a,b,c} P: S::=aSBC S::=aBC CB::=BC aB::=ab bB::=bb bC::=bc cC::=cc这是一个1型文法，它描述了如下语言

L(G)={anbncn|n≥1}第65页，共93页，2023年，2月20日，星期四三、2型文法（上下文无关文法） 若文法G中规则呈现如下形式：

A::=β

其中，A∈VN，β∈（VN∪VT）* 则称G为2型文法，由它产生的语言称2型语言。 由于利用规则将A替换成β时与其上下文无关，即与A在上下文出现的情况无关，所以又称这种文法为上下文无关文法。例：文法G的产生式P：

E::=E+E|E*E|(E)|i

属于2型文法。特点：2型文法产生式的左部是单个的非终结符，右部为终结符和非终结符组成的符号串。注：上下文无关文法可以描述当今的程序语言第66页，共93页，2023年，2月20日，星期四四、3型文法（正规文法） 如果对2型文法的产生式作进一步的限制，限制产生式的右部是单一终结符或单一终结符和单一非终结符组成。若文法G中的规则式，呈现如下形式： 右线性文法 A::=aB A::=a

或左线性文法 A::=Ba A::=a其中：A，B∈VN，a∈VT

称G为3型文法。或称正规（正则）文法，由它产生的语言为3型语言或正规语言。＊+第67页，共93页，2023年，2月20日，星期四例：设有G=(V,V,P,S) P: S::=A0|B1 A::=0|1 B::=0|1左线性文法注：①文法类型是由产生式的形式来划分：NT第68页，共93页，2023年，2月20日，星期四即：G0G1G2G3表格：文法类型与产生式文法类型产生式限制0α::=β(|α|≠0,|α|>|β|)：无限制文法1α::=β(1≤|α|≤|β|):上下文有关文法2A::=δ(δ∈（VN∪VT)+):上下文无关文法3A::=aA::=aA::=aB或A::=Ba:正则（规）文法或左（右）线性文法第69页，共93页，2023年，2月20日，星期四②文法的分类对于程序设计语言的编译程序有重要的意义。程序语言的词法规则属于正则文法编译程序词法扫描器采用正则文法识别技术。程序语言的语法和语义部分的规则属于上下文有关文法。但考虑高功效而采用上下文无关文法定义语法编译程序语法分析器采用上下文文法识别技术。程序语言的词法由正则文法描述。第70页，共93页，2023年，2月20日，星期四程序语言中与局部语法有关的规则属于上下文无关文法。程序语言中全局的语法与语义有关的部分属于上下文有关文法。（如标识符类型匹配问题（说明部分与语句部分）。过程调用中实参与形参要求一致的问题等等）第71页，共93页，2023年，2月20日，星期四§5文法的实用限制

在实际使用中，对文法要作一些假定或限制。例如限制文法不含有有害规则或多余的规则。一、文法中不能含有有害规则U::=U这样的规则显然没有必要，而且会引起二义性。例如，文法G[S]:S::=0S1|01是无二义性的，若将规则写成：S::=0S1|01|S则文法G不再是无二义性的。就句子0011而言，可画出多棵语法树。第72页，共93页，2023年，2月20日，星期四二、文法中不能含有多余的规则文法的规则中不含有无用的非终结符和不可到达的符号。1.无用的非终结符号（不可终止符号） 如果从文法中某个非终结符推不出终结符号串，则称该非终结符号为无用的非终结符2.不可到达的符号 如果文法规则中的一个非终结符（不是识别符号），不出现在文法的任何一条产生式的右部，则称该非终结符为不可到达的符号.第73页，共93页，2023年，2月20日，星期四例：已知文法G=(VN，VT，P，Z)

其中， VN={Z,A,B,C,D},VT={e,f} P:Z::=Be A::=Ae|e B::=Ce|Af C::=Cf D::=f C为无用的非终结符，因为C在推导中没有终结符号替换。∴C::=cf和B::=Ce多余应该删去。第74页，共93页，2023年，2月20日，星期四

D为不可到达的符号，即D::=f在推导中不起作用，应该删去。删除多余的规则后的文法为：

Z::=Be A::=Ae|e B::=Af第75页，共93页，2023年，2月20日，星期四文法中不含多余规则的充要条件：U(U∈VN)必须出现在某个推导的句型中，即：Z=>＊x∪y。（U为文法的非终结符）能从U推出终结符号串，即：U=>+t(t∈VT)

满足上述条件的文法称为压缩过的或化简了的。对文法的限制还有：文法中不含有左递归规则U::=U…。（消除左递归在后面会讲到）对于上下文无关文法，限制U::=ε，即不含有空规则。（可以变换消除）等等第76页，共93页，2023年，2月20日，星期四§6小结本章主要解决的问题：已知文法，确定该文法描述的语言已知语言，设计描述该语言的文法求句型的短语，简单短语及句柄文法二义性的判断第77页，共93页，2023年，2月20日，星期四一、已知文法，确定该文法描述的语言1.语言的定义：文法G产生句子的全体。即L(G[S])={x|S=>+x,且x∈VT*}2.语言的描述：用自然语言：L={x|x∈{a,b}+,且x中a，b个数相同}用式子：L={a2nbb|n≥0}用正规式：L={bna|n≥0}，可用：L=b*a来描述。3.求法：根据给定文法，从文法的识别符号开始，推导出所有的句子，然后归纳写出语言描述的三种形式之一。第78页，共93页，2023年，2月20日，星期四例：有如下文法G[S]：

S::=AB A::=aAb|ab B::=BC|ε求：L(G[S])=?解：S=>AB=>abB=>ab S=>AB=>abB=>abBc=>abc S=>AB=>aAbB=>aabbB=>aabb S=>AB=>aAbB=>aabbB=>aabbBC=>aabbc ……∴L(G[S])={anbnc|n≥1,m≥0}m第79页，共93页，2023年，2月20日，星期四例：已知文法G[S]为：

S::=dAB A::=aA|a B::=Bb|εG[S]产生的语言是什么？G[S]能否改写为等价的正规文法？解：首先分析G[S]产生的语言：语言的句子都是d开头，后跟a或b，且a，b个数不等。

L(G[S])={danbm|n≥1,m≥0}

根据语言的特点：a,b的个数n与m没有相互制约的关系，所以将an与bm分别构造，得到正规文法：G[S]：S::=dA A::=aA|aB|a B::=bB|b第80页，共93页，2023年，2月20日，星期四二、已知语言，设计描述该语言的文法文法的形式定义：四元组G[S]=(VN,VT,P,S)，主要求产生式P。分析已知语言句子的结构特征，设计相应的产生式，但求出的文法不唯一。设计出的文法必须能准确地定义已知的语言，不能超出或缩小所定义的语言范围。若语言是句子的无穷集合，则设计的文法一定是递归的。第81页，共93页，2023年，2月20日，星期四例：已知L={x|x∈{a,b,c}*,且x中符号的排列是对称的。（例如：aabcbaa或aabbaa等）}

试写出产生该语言的文法。解：句子x中符号有多个，所以有递归产生式存在。又因为句子x中符号是对称的，保证对称的推导出每个符号就可以了。

G[Z]:Z::=aZa|bZb|cZc|a|b|c|ε例：给出描述：L={a2m+1bm+1|m≥0}∪{a2mbm+2|m≥0}的文法。解：将句子的描述变形：

a2mabbm和a2mbbbm发现句子中前后的a和b的个数有倍数关系于是：G[Z]:Z::=aaZb|ab|bb第82页，共93页，2023年，2月20日，星期四例：写一文法，使其语言是偶整数的集合（不允许0开头，且不考虑带符号数）解：根据题意，将偶整数结构划分如图所示的三个部分：最高位允许1～9，用非终结符B表示中间位允许任意多位数字0～9，每位用非终结符D表示最低位只允许出现0，2，4，6，8偶数，用A表示。第83页，共93页，2023年，2月20日，星期四 由于中间部分可以出现任意位，所以引入一个非终结符M，它包括最高位和中间位。所求文法G[N]:N::=A|MA M::=B|MD A::=0|2|4|6|8 B::=1|2||3|4|5|6|7|8|9 D::=0|B类似问题：写出带符