前后文无关文法和语言

前后文无关文法和语言第一页，共六十七页，编辑于2023年，星期五重点和难点重点：本章中涉及的概念和术语的理解文法和语言的形式定义难点：短语和句柄的识别二义性文法的判定第二页，共六十七页，编辑于2023年，星期五2.1语言及其表示方法规定一种语言首先要规定它各种构造成分的形式，词汇、句子等的构造规则及表示法。编译原理则应建立有关语言的数学化（形式化）模型，以便对程序语言进行研究。第三页，共六十七页，编辑于2023年，星期五定义1：相当大的地区内公众所懂得并使用的“话”，以及组成这些“话”的方法的统一体。缺点：不够形式化和精确化定义2：某一个字母表上的符号串的（句子）的集合。缺点：缺乏语言句子的结构性组成描述，缺乏判断任一符号串是否为合法句子判断机制。因此，如果能刻画一个语言句子，就定义了该语言。1、语言第四页，共六十七页，编辑于2023年，星期五1956年，chomsky建立文法的数学模型，对形式化语言和自动机理论的研究取得较大的成果。1960年。P.Nuaur和J.Boukas首先用BNF成功对ALGOL语言的文法进行了描述，虽然对语义形式化描述不理想，但在程序设计语言的语法描述上有足够的能力。至此，程序语言就有了形式化表述。第五页，共六十七页，编辑于2023年，星期五枚举（句子有限）例：L={Wearelearningcomputerscience,itisinteresting}数学表示(句子无限)例:{1,1/2,1/3,……1/n}→{1/n|n∈N}

制定有限条规则，用来产生所需描述语言中的句子全部，这些规则即文法。建立一种算法能对于任给的符号串，判别是否为给定语言的合法句子——自动机理论。2、表示方法第六页，共六十七页，编辑于2023年，星期五

语言可以看成在一个基本符号集上定义的，按一定规则构成的一切基本符号串组成的集合。第七页，共六十七页，编辑于2023年，星期五2.2文法的定义1、例：“我是大学生”是汉语的一个句子。〈句子〉∷=〈主语〉〈谓语〉〈主语〉∷=〈代词〉｜〈名词〉〈代词〉∷=我｜你｜他〈名词〉∷=王明｜大学生｜工人｜英语〈谓语〉∷=〈动词〉〈直接宾语〉〈动词〉∷=是｜学习〈直接宾语〉∷=〈代词〉｜〈名词〉返回第八页，共六十七页，编辑于2023年，星期五∷=左端的规则由∷=右端的符号串代替：〈句子〉〈主语〉〈谓语〉

〈代词〉〈谓语〉我〈谓语〉我〈动词〉〈直接宾语〉

我是〈直接宾语〉

我是〈名词〉

我是大学生按照如下方式用它们导出句子：第九页，共六十七页，编辑于2023年，星期五大学生〈句子〉〈主语〉〈谓语〉〈代词〉〈动词〉〈直接宾语〉〈名词〉我是“我大学生是”是否为<句子>?第十页，共六十七页，编辑于2023年，星期五sentence–><subject><verb-phrase><object>subject–>This|Computers|Iverb-phrase–><adverb><verb>|<verb>adverb–>neververb–>is|run|am|tellobject–>the<noun>|a<noun>|<noun>noun–>university|world|cheese|liesThisisauniversity.Computersruntheworld.Iamthecheese.Inevertelllies.英语句子第十一页，共六十七页，编辑于2023年，星期五2、文法的形式化表示符号：<>表示一个语法单位；∷=（–>）表示“定义为”；

|表示为“或”。文法：描述语言的形式结构的规则。产生式，产生式左部，产生式右部第十二页，共六十七页，编辑于2023年，星期五文法的一般构成：一组终结符号：仅出现在产生式右部的符号VT；一组非终结符号：至少在产生式左部出现过一次的符号VN；一个开始符号：特殊的非终结符，表示了定义语言中最感兴趣的语法范畴。S；一组规则：P

G={VT，VN，S，P}

例如

第十三页，共六十七页，编辑于2023年，星期五VN，VT和P是非空有穷集；

VN和VT不含公共的元素，即VN∩VT=φ；用V表示VN∪VT，称文法G的字母表或字汇表；产生式是形如→或∷=的（，）有序对，其中是字母表V的一个非空符号串(V+)，是V中的一个符号串，可为空串(V*)。称为产生式左部，称作产生式右部。

说明：第十四页，共六十七页，编辑于2023年，星期五2.3由文法产生句子1、推导〈句子〉

〈主语〉〈谓语〉

〈代词〉〈谓语〉

我〈谓语〉

……过程：文法的开始符号开始，每次把当前串的一个非终结符号用于之对应的产生式右部来代换，得到一个新符号串，称一步推导。2、推导长度第十五页，共六十七页，编辑于2023年，星期五文法的作用就是用有限条规则产生无限多句子。某一文法产生的全部句子所组成的集合——该文法产生的语言。第十六页，共六十七页，编辑于2023年，星期五一、基本定义1、符号：可以相互区别的记号（元素）。2、字母表：符号（元素）的非空有穷集合。3、符号串：由字母表中的符号组成的任何有穷序列。空符号串ε(没有符号的符号串)是上的符号串。若x是上的符号串，a是的元素，则xa是上的符号串。

y是上的符号串，当且仅当它可以由1和2导出。例如：Σ={a,b}ε，a，b，aa，ab，aabba…都是上的符号串2.4有关定义和记号第十七页，共六十七页，编辑于2023年，星期五4、符号串s的头（前缀）：移走符号串s尾部的零个或多于零个符号得到的符号串。如：b是符号串banana的一个前缀.banana是banana前缀。

5、符号串s的尾（后缀）：删去符号串s头部的零个或多于零个符号得到的符号串。如:nana是符号串banana的一个后缀.banana是banana后缀。第十八页，共六十七页，编辑于2023年，星期五6、符号串s的子串：从s中删去一个前缀和一个后缀得到的符号串。如:ana是符号串banana的一个子串。7、符号串s的真前缀，真后缀，真子串：任何非空符号串x，是s的前缀，后缀或子串，并且sx。8、符号串的长度：符号串中符号的个数。符号串s的长度记为|s|。ε的长度为0。对于每个符号串s，s和ε两者都是符号串s的前缀，后缀和子串。第十九页，共六十七页，编辑于2023年，星期五1、连接：符号串x、y的连接，是把y的符号写在x的符号之后得到的符号串xy。如：x=ba,y=ck则xy=back有εa=aε2、方幂：符号串自身连接n次得到的符号串。

an定义为aa…aan个aa1=a,a2=aaa0=ε二、符号串的运算第二十页，共六十七页，编辑于2023年，星期五三、符号串集合若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。1、符号串集合乘积：两个符号串集合A和B的乘积定义为

AB=xy|xA且yB例如：若集合A=ab，cdeB=0，1则AB=ab1，ab0，cde0，cde12、Σ的闭包：上的一切符号串（包括ε）组成的集合。记为Σ*

第二十一页，共六十七页，编辑于2023年，星期五3、Σ的正闭包：上的除ε外的所有符号串组成的集合。记为Σ+例：Σ={a,b}，求Σ*和Σ＋。Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}Σ+={a,b,aa,ab,ba,bb,aaa,aab,…}第二十二页，共六十七页，编辑于2023年，星期五Σ*包含Σ上的所有符号串，Σ+包含Σ上除空串ε外的任意符号串。第二十三页，共六十七页，编辑于2023年，星期五1、语言：由句子组成的集合，为一符号串集合。即：字母表上的一个语言是上的一些符号串的集合，是*的一个子集。

L={S|S∈*}{}、{ε}都是语言例如：字母表Σ={a,b}

集合{w|w∈Σ*且w=anbn,n≥1}为上的一个语言。集合{w|w∈Σ*且w=an,n≥1}为上的一个语言。四、语言上的有关运算第二十四页，共六十七页，编辑于2023年，星期五2、语言“并”运算：语言L和M的并为LM，是一个语言:{w|wisinLorisinM}如：L1={a,b,…y,z}，M1={1,2…8,9}

L1M1={a,b,…y,z，1,2…8,9}设L是（上的）一个语言，M是（上的）一个语言，语言L和M的“并”，“交”，“差”，“连接”运算结果是一个语言。第二十五页，共六十七页，编辑于2023年，星期五3、语言L和M的连接运算：记为L•M(可简记为LM)。

LM={st|s∈L且t∈M}如：L={a,b,…y,z}，M={1,2…8,9}

LM={a1,b1,…y1,z1,a2,b2…a9…z9}特别的：有L

ε=εL=L。

L的n次连接Ln=LL...L第二十六页，共六十七页，编辑于2023年，星期五4、语言L的

闭包：记为L*，L*=L0L1L2...L0=ε

，Ln=L

Ln-1=Ln-1L(n1)5、语言L的正

闭包：记为L+，L+=L1L2L3...L+=LL*=L*L

L*=L+

ε

如：L1

={a,b,…y,z}M1={1,2…8,9}

（L1M1）={a,b,…y,z，1,2…8,9

}

（L1M1）*={a,b,…y,z，1,2…8,9,aa,1a,…,xyz,6789st..}

L1（L1M1）*={所有字母打头的字母和数字符号串}第二十七页，共六十七页，编辑于2023年，星期五练习1：L={A,B,C,……Z,a,b,c……z}D={0,1,2,3,4,5,6,7,8,9}计算：L∪D，LD，L4

，L*，L(L∪D)*，D+练习2：考虑一个文法G1:S→bAA→aA|a它定义了一个什么语言呢？从开始符S出发，我们可以推出如下句子：

SbAbaSbAbaAbaaSbAbaA…baa…a可以写为：L(G1)={ban|n≥1}第二十八页，共六十七页，编辑于2023年，星期五2.5语言和文法的形式定义一个上下文无关文法G定义为四元组(VN，VT，P，S)其中：VN：非终结符号(或语法实体，或变量)集；VT：终结符号集；P：产生式(也称规则)的集合；A→其中，∈(VN∪

VT)*，A∈VN

VN，VT和P是非空有穷集。

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

VT=φ

用V表示VN∪

VT

，称为文法G的字母表或字汇表1、上下文无关文法第二十九页，共六十七页，编辑于2023年，星期五例<1>文法G=（VN，VT，P，S）

VN={S},VT={0,1} P={S→0S1,S→01} S为开始符号对此产生式可进行推导产生句子。第三十页，共六十七页，编辑于2023年，星期五2、推导直接推导“”

α→β是文法G的产生式，若有v,w满足：v=γαδ,w=γβδ,其中γ∈V*,δ∈V*

则称v直接推导到w,记作vw；也称w直接归约到v例：G：S→0S1，S→01

0S100S1100S11000S111000S11100001111S0S1第三十一页，共六十七页，编辑于2023年，星期五例：G：S→0S1，S→01S0S100S11000S11100001111SS00S1100S11S00001111推导长度为4

若存在v=w0w1...wn=w(n>0)

则记为vw，称作v推导出w，或w归约到v

若有vw或v=w，则记为vw

推导的长度（长度为n的推导）第三十二页，共六十七页，编辑于2023年，星期五3、句型和句子例：G：S→0S1，S→01S0S100S11000S11100001111G的句型S，0S1，00S11，000S111，00001111G的句子00001111，01

句型

有文法G[S]，若Sx，x∈V*，则称x是文法G的句型。

句子

有文法G[S]，若Sx，且x∈VT*，则称x是文法G的句子。第三十三页，共六十七页，编辑于2023年，星期五例：G[E]：E→E+T|T

T→T*F|F

F→(E)|a

判断：a+a*a是否为该文法的句子EE+TT+TF+Ta+Ta+T*F

a+F*Fa+a*Fa+a*a句子：用符号a，+，*，(和)构成的算术表达式第三十四页，共六十七页，编辑于2023年，星期五4、语言由文法G生成的语言记为L(G)，它是文法G的一切句子的集合:语言中的每个句子可以由上下文无关文法的开始符号产生。例：G=（{0，1}，{S}，S，P）

P:S→0S1，S→01L(G)={0n1n|n≥1}L(G)={x|Sx，S为文法的开始符号，且x∈VT*}第三十五页，共六十七页，编辑于2023年，星期五G生成的每个串都在L(G)中，L(G)中的每个串确实能被G生成。文法所产生的语言L(G)是无限语言，原因是所定义的文法中含有递归。第三十六页，共六十七页，编辑于2023年，星期五5、文法的递归性递归、直接递归：如果文法中有形如A→γAδ的产生式，其中γ，δ不同时为ε，则称产生式A→是直接递归。例：G[E]：

E→E+T|TT→T*F|F

F→(E)|aAγAδ，直接递归AγAδ，递归A称为递归和直接递归的非终结符号若存在A

γAδ,则称A→是递归的。

左递归、右递归

γ=ε，δ≠ε左递归

γ≠ε，δ=ε右递归第三十七页，共六十七页，编辑于2023年，星期五直接递归是递归的一种特殊情况，如果一个语言是无限的，则定义此语法的文法必然是递归的。

例：语言L={anbbn|n1},写出产生L的文法。

G[S]:SaAbAaAb|b第三十八页，共六十七页，编辑于2023年，星期五从语法定义的角度，递归定义是一种较好的方式，因为它不仅使文法形式简练，而且也给无限语言的有限表示提供了一种有效的方法。然而左递归会影响某些语法分析方法实现，因此有时需要对文法进行等价改造，以便消除其中的左递归。第三十九页，共六十七页，编辑于2023年，星期五6、文法的等价性

若L（G1）=L（G2），则称文法G1和G2是等价的。

如文法G1[A]：A→0R与G2[S]：S→0S1等价

A→01S→01R→A1第四十页，共六十七页，编辑于2023年，星期五2.6句型的分析如何表示语言中的句子？任给的一个符号串是否为某一文法的句子（型）？需要进行句型分析。自顶向下：从文法的开始符号，以给定的符号串为目标，试图推导出串。自底向上：给定符号串出发，反复用文法中有关产生式的左部替换当前符号串中的相应子串，以期最后归约为文法开始符号。第四十一页，共六十七页，编辑于2023年，星期五例：G[E]：

E→E+T|T

T→T*F|F

F→(E)|a

E判定a+a*a是否为文法的句子？E+TT+TF+Ta+Ta+T*F

a+F*Fa+a*Fa+a*a第四十二页，共六十七页，编辑于2023年，星期五1、规范推导规范句型最左（最右）推导：推导的每一步αβ，其中α、β是句型，都是对α中的最左（右）非终结符进行替换。规范推导：最右推导称为规范推导。规范句型：由规范推导所得的句型称为规范句型。注意：文法中的每个句子都必定有最左(右)推导，但对于一个句型，则不一定。G[E]：E→E+T|T

T→T*F|F

F→(E)|a

对句型T+a+T的推导：EE+TT*F+TT*a+T第四十三页，共六十七页，编辑于2023年，星期五

问题：对于推导中的每一步，SαXβ,如果X→α1|α2|α3|……|αk，（α，β）∈V*，X∈VN，则面临选哪一个αi去匹配当前串的问题。使用不当易引起回溯。2、句型分析过程自顶向下分析方法

从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导。例：文法G：S→cAd

A→ab

A→a

识别输入串w=cabd是否为该文法的句子

S S S

c A d

c A d

a

b推导过程：S

cAd

cAd

cabd第四十四页，共六十七页，编辑于2023年，星期五自底向上分析方法从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。例：文法G：S→cAd

A→ab

A→a

识别输入串w=cabd是否该文法的句子

S

A

A

cabd

ca

bd

ca

b

d

归约过程构造的推导：cAd

cabdScAd第四十五页，共六十七页，编辑于2023年，星期五在自下而上的分析方法中，在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”。归约的子串应是当前句型的句柄。第四十六页，共六十七页，编辑于2023年，星期五3、语法树和二义性语法树：设G=(VN,VT,P,S)为一cfg，若一棵树满足下列4个条件，则此树称作G的语法树：每个结点都有一个标记，此标记是V的一个符号；根的标记是S

若某结点至少有一个子孙，并且该结点标记为A，则A∈VN；若某结点标记A，其直接子孙结点从左到右的次序是n1，n2，…，nk，其标记分别为A1，A2，…，Ak，那么A→A1A2，…，Ak定是P中的一个产生式第四十七页，共六十七页，编辑于2023年，星期五语法树---句型推导的直观表示给定上下文无关文法G=(VN,VT,P,S)，对于G的任何句型都能构造与之相关的语法树(推导树)

定理：G为上下文无关文法， 对于

≠ε，有S=>*

，当且仅当文法G有以为结果的一棵语法树(推导树)第四十八页，共六十七页，编辑于2023年，星期五例:G[S]: S→aAS A→SbA A→SS S→a A→ba句子aabbaa的语法树（推导树）叶子结点：树中没有子孙的结点。

SaASSbAaaba第四十九页，共六十七页，编辑于2023年，星期五推导过程中使用产生式的顺序

例:G[S]:S→aASA→SbA|SS|baS→aSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa

SaASSbAaaba第五十页，共六十七页，编辑于2023年，星期五一棵语法树可表示一个句子的多种可能的不同推导过程，包括最左(最右)推导。

一个句子是否只对应唯一的一棵语法树?一个句子是否只有唯一的一个最左(最右)推导?第五十一页，共六十七页，编辑于2023年，星期五例：G[E]:

E→i E→E+E E→E*E E→(E)句型i*i+i的推导，有两个不同的最左推导：推导1：EE+EE*E+Ei*E+Ei*i+Ei*i+i推导2：EE*Ei*Ei*E+Ei*i+Ei*i+i

EE+EE*Eiii

EE*EiE+Eii第五十二页，共六十七页，编辑于2023年，星期五

二义性文法若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的

注意：

判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的，但可以为无二义性寻找一组充分条件。第五十三页，共六十七页，编辑于2023年，星期五一个文法兼有左右递归是导致二义性的最常见原因。二义文法改造为无二义文法

G[E]:E→iG[E]：E→T|E+T E→E+ET→F|T*F E→E*EF→（E）|i E→(E)改写文法，消除同时存在的左右递归。第五十四页，共六十七页，编辑于2023年，星期五4、短语和句柄SαAδ且A

β，则称β是句型αβδ相对于非终结符A的短语对于文法G[S]：

句型的短语

句型的直接短语若有A

β，则称β是句型αβδ相对于非终结符A的直接短语

句型的句柄一个句型的最左直接短语称为该句型的句柄第五十五页，共六十七页，编辑于2023年，星期五i*i+i的短语、直接短语和句柄EE+T

TFT*F

i3

短语：i1*i2+i3，

i1*i2

，Fi2

i1

，

i2

，

i3

。i1

直接短语：

i1

，

i2

，

i3

。句柄：i1

例：

G[E]：

E→E+T|T

T→T*F|F

F→(E)|i句型：i*i+i第五十六页，共六十七页，编辑于2023年，星期五G[S]: S→aAS

S→a A→SbA A→SS A→ba句子aabbaa的最左推导，指出此句子的全部短语、各步直接推导所得句型的句柄、该句子的句柄

S1a1A1S3S2b1A2a2a3b2a4练习第五十七页，共六十七页，编辑于2023年，星期五通过对产生式施加不同限制，Chomsky将文法分为四类：0型文法：对任一产生式α→β，有α∈V+，β∈V*;1型文法：对任一产生式α→β，有|β|≥|α|(α,β∈V+)，仅S→ε除外。或者形如αAβ→αγβ产生式,A∈VN,γ∈V+,α,β∈V*2型文法：对任一产生式A→β，都有A∈VNβ∈V*;3型文法：任一产生式的形式都为A→αB或A→α(右线性)，A→Bα或A→α（左线性）其中A∈VN

，B∈VN

，a∈VT+2.8文法的类型第五十八页，共六十七页，编辑于2023年，星期五四种文法之间的逐级“包含”关系0型文法1型文法2型文法3型文法第五十九页，共六十七页，编辑于2023年，星期五AhierarchyofgrammarsType0:freeorunrestrictedgrammarsThesearethemostgeneral.Productionsareoftheformu–>vwherebothuandvarearbitrarystringsofsymbolsinV,withunon-null.Therearenorestrictionsonwhatappearsontheleftorright-handsideotherthantheleft-handsidemustbenon-empty.Type1:context-sensitivegrammarsProductionsareoftheformuXw–>uvwwhereu,vandwarearbitrarystringsofsymbolsinV,withvnon-null,andXasinglenonterminal.Inotherwords,Xmaybereplacedbyvbutonlywhenitissurroundedbyuandw.第六十页，共六十七页，编辑于2023年，星期五Type2:context-freegrammarsProductionsareoftheformX–>vwherevisanarbitrarystringofsymbolsinV,andXisasinglenonterminal.WhereveryoufindX,youcanreplacewithv(regardlessofcontext).Type3:regulargrammarsProductionsareoftheformX–>aorX–>aYwhereXandYarenonterminalsandaisaterminal.Thatistheleft-handsidemustbeasinglenonterminalandtheright-handsidecanbeeitherasingleterminalbyitselforwithasinglenonterminal.Thesegrammarsarethemostlimitedintermsofexpressivepower.第六十一页，共六十七页，编辑于2023年，星期五例：1型（上下文有关）文法文法G[S]： S→CD Ab→bA C→aCA Ba→aB C→bCB Bb→bB AD→aD