前后文无关文法和语言

前后文无关文法和语言第1页，共52页，2023年，2月20日，星期三2.1文法及语言的表示首先，我们确定一个概念：什么是语言？据统计，目前在世界各地，人们所使用的语言达2700多种。Webster的定义：“为相当大地区的公众所懂得并使用的‘话’，以及组成这些‘话’的方法的统一体”上述定义对于建立语言的数学理论的目的而言不够精确。所以，有人又将语言定义为：“某一字母表上符号串（句子）的集合”此定义仍需精确化。因为：1）还应为所定义的句子提供一种结构性的描述（语法规则）；2）最好能再提供一种手段，以便能准确地判别什么是该语言中的正确句子（即识别方法、分析方法等）。第2页，共52页，2023年，2月20日，星期三2.2

文法和语言的定义

2.2.1基本概念和术语1。字母表（符号表、符号集）由若干元素（符号、字母）组成的有限非空集合。例：={a，b，c}2。符号串用字母表中符号所组成的任何有限序列。

例：a,aa,ac,abc，..符号串的长度

=符号串中所含符号的个数例：aba的长度为3。记为：|aba|=3空串不含任何符号的符号串，记为

。显然，||=0。本课约定

用A、B、C、等表示字母表或符号串集；用a,b,c,S,T,U

等表示符号；用s,t,u,x,y,z,,,等表示符号串。任何程序语言都有自己的字母表。1.计算机语言:由符号“0”和“1”组成的字母表:∑={0，1}2.Pascal语言字母表：∑={AZ,az,09,+,-,*,/,<,=,>,:,‘,”,;，.，,(,),{,},[,]}3.C语言字母表：∑={AZ,az,09,+,-,*,/,<,=,>,_,&,^,~,\,:,‘,”,;，.，?,(,),{,},[,],空格,!,#,%}第3页，共52页，2023年，2月20日，星期三2.2.1

基本概念和术语（续）3.符号串的前（后）缀及子串

设,,，x是符号串，若x=,则称是x的子串；特别地，当=（=）时，称是x的前（后）缀。（符号串s=banana）前缀：,b,ba,ban,bana,banan,banana后缀：banana,anana,nana,ana,na,a,子串:banana,anana,banan,anan,…,4.符号串相等：若x、y是集合上的两个符号串，则x＝yiff（当且仅当）组成x的每一个符号和组成y的每一个符号依次相等。

第4页，共52页，2023年，2月20日，星期三6.符号串集合的乘积运算：令A、B为符号串集合，定义AB＝{xy|x∈A,y∈B}例：A＝{a,b},B={c,d},AB=？{ac，ad，bc，bd}因为εx＝xε＝x，所以{ε}A={ε}A=A5.符号串的联接：若x、y是定义在Σ是上的符号串，且x＝XY，y＝YX，则x和y的联接xy＝XYYX也是Σ上的符号串。注意：一般xy≠yx，而εx＝xε2.2.1

基本概念和术语（续）第5页，共52页，2023年，2月20日，星期三8.符号串集合的闭包运算：设A是符号串集合，定义

A＋＝A1∪A2∪A3∪……∪An∪……

称为集合A的正闭包。

A*＝A0∪A＋

称为集合A的闭包。例：A={x,y}A＋＝？

A*＝？7.符号串集合的幂运算：有符号串集合A，定义A0={ε}, A1=A,A2=AA,A3=AAA,…………An＝An-1A=AAn-1，n>0{x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,……}

A1

A2

A3{ε,x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,……}

A0A1

A2

A32.2.1

基本概念和术语（续）第6页，共52页，2023年，2月20日，星期三

为什么对符号、符号串、符号串集合以及它们的运算感兴趣？若A为某语言的基本字符集

A＝{a,b,……z,0,1,……,9,+,－,×,_/,(,),=……}B为单词集

B={begin,end,if,then,else,for,……,<常量>,……}

则BA*。语言的句子是定义在B上的符号串。若令C为句子集合，则CB*,程序C形式语言：是一个字母表上按照某种规则构成的所有的串的集合，它用文法和自动机所描述的没有语义的语言。（形式语言是数学范畴）第7页，共52页，2023年，2月20日，星期三2.2.2文法和语言的形式定义我们从“产生语言”的角度出发,讨论文法和语言的形式定义。产生语言 指制定出有限条规则，借助它们就能产生出些语言的句子。我们以几个英语句子构成的语言为例进行讨论。并设每个句子都是“主-谓-宾”结构。语法规则见右。其中，每个用<>括起来的部分是所要定义语言中的一个语法实体（称为语法单位、语法结构、语法范畴、语法变量等）。“::=”是用于定义语法结构的符号，其含义（并读作）“定义为”.语法规则也称为产生式(Production)①<句子>::=<主语短语><动词短语>②<主语短语>::=the<名词>③<动词短语>::=<动词><宾语短语>④<宾语短语>::=<冠词><名词>⑤<名词>::=monkey⑥<名词>::=banana⑦<动词>::=eat⑧<动词>::=has⑨<冠词>::=the⑩<冠词>::=a第8页，共52页，2023年，2月20日，星期三2.2.2文法和语言的形式定义现在，我们讨论如何用上述规则推导出相应语言的全部句子。推导 从语言最大的一个语法范畴（本例中是<句子>）开始，反复用语法规则中“::=”

右侧的符号串取代其左侧符号，直到所得的符号串中不再含有可被替换语法范畴。每次替换称为一步（直接）推导，并用符号“”表示。例如，我们首先用规则①进行第一步推导(derivation)，就可得到 <主语短语><动词短语>，记为

<句子><主语短语><动词短语>所得的符号串<主语短语><动词短语>含有两个语法范畴，可对其中任一个（例如对<动词短语>）进行新的推导（替换）：<句子><主语短语><动词短语> <主语短语><动词><宾语短语>重复上述过程，可得到一个推导序列（见下页）。第9页，共52页，2023年，2月20日，星期三用语法规则进行推导所得的推导序列推导步骤所用规则 所得的符号串

1 ① <句子><主语短语><动词短语>2 ③ <主语短语><动词><宾语短语>3 ② the<名词><动词><宾语短语>

4

④ the<名词><动词><冠词><名词>

5 ⑤ themonkey<动词><冠词><名词>6

⑦ themonkeyeat<冠词><名词>

7⑩ themonkeyeata<名词>

8 ⑥ themonkeyeatabanana第10页，共52页，2023年，2月20日，星期三2.2.2文法和语言的形式定义从前面的推导看，从<句子>出发，经8步推导得到了一个英语句子。故前面的推导称为长度为8的推导。若不关心推导的中间过程，可将从一符号串到另一符号串的推导用记号第11页，共52页，2023年，2月20日，星期三规则的简化表示在前面的语法规则定义中，有些语法范畴（如<名词>、<动词>）有若干条不同的规则来定义它，为简明起见，我们可以将它们写在同一个左部语法范畴下，将其定义值用符号“|”（读作‘或’）隔开。如<名词>、<动词>、<冠词>的定义规则可简记为<名词>::=monkey|banana<动词>::=eat|has<冠词>::=the|a第12页，共52页，2023年，2月20日，星期三语法规则及其产生的语言前面的语法规则可以产生16个不同的句子，由这16个句子组成的集合，就是该规则所定义（或所产生）的语言。应指出，所产生的句子中，有些句子的含义是荒谬的（如thebananaeatamonkey和thebananaeatthebanana等）。然而，若不考虑语义，则我们就必须承认它们是语法上合法的句子。第13页，共52页，2023年，2月20日，星期三定义1.文法G[S]=(VN，VT，P，S) VN

：非终结符号集

VT

：终结符号集

P：产生式或规则的集合

S：开始符号（识别符号）S∈VNV＝VN∪VT称为文法的字汇表规则：U→xU∈VN,x∈V*非终结符是指在文法的语法范畴，出现在产生式P中，通常用大写字母或用“<>”括起来的符号串表示，终结符是指不需要进一步定义的基本符号，通常用小写字母表示文法的定义第14页，共52页，2023年，2月20日，星期三P={<无符号整数>→<数字串>；

<数字串>→<数字串><数字>；

<数字串>→<数字>；

<数字>→0；

<数字>→1；

…………

<数字>→9；}E=<无符号整数>；例：无符号整数的文法：

G[<无符号整数>]=（Vn，Vt，P，E）

Vn＝{<无符号整数>,<数字串>,<数字>} Vt={0,1,2,3,……9}第15页，共52页，2023年，2月20日，星期三<句子>

<主语><谓语>

<代词><谓语>

我<谓语>

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

我是<名词>

我是大学生<句子>→<主语><谓语><主语>→<代词>|<名词><代词>→你|我|他<名词>→王民|大学生|工人|英语<谓语>→<动词><直接宾语><动词>→是|学习<直接宾语>→<代词>|<名词>推导方法：从一个要识别的符号开始推导，即用相应规则的右部来替代规则的左部，每次仅用一条规则去进行推导。第16页，共52页，2023年，2月20日，星期三定义：设文法G[S]=(VN，VT，P，S)，若U→u∈P，x、y∈V*

，则xUy∈V*若用规则U→u的右部u替换U，即xuy∈V*,则称xuy是xUy的直接推导。xUy是xuy的直接规约。记为xUy==>xuy(推导)和xuyxUy(规约)推导的形式定义==>

△第17页，共52页，2023年，2月20日，星期三<无符号整数><数字串><数字串><数字><数字><数字>1<数字>10==>=>==>==>==>当符号串已没有非终结符号时，推导就必须终止。例如：G[<无符号整数>](1)<无符号整数>→<数字串>；

(2)<数字串>→<数字串><数字>(3)<数字串>→<数字>(4)<数字>→0;(5)<数字>→1;

…………(13)<数字>→9;第18页，共52页，2023年，2月20日，星期三定义3：文法G，U0,U1,U2,……，Un

∈V+

ifv=U0==>U1==>U2==>……==>Un＝w(n>0)

则称v推导出w,或w规约到v，或v经+推导出w，或w+规约到v，分别记为：

vw或wv＋==>例：<无符号整数>==><数字串>==><数字串><数字>==><数字><数字>==>1<数字>==>10即<无符号整数>10＋==>＋==>△定义4：文法G，v，w∈V+

ifvw,或v=w，则vw则称v经*推导出w，或w经*规约到v，＋==>

*==>第19页，共52页，2023年，2月20日，星期三定义6：文法G[S] （1）句型：x是句型

Sx,且x∈V*； （2）句子：x是句子

Sx,且x∈VT*； （3）语言：L（G[S]）={x|x∈VT*,Sx}；++文法G[S]所产生的所有句子的集合形式语言理论可以证明以下两点：

（1）G→L（G）；

（2）L(G)→G1，G2，……，Gn；已知文法，求语言，通过推导；已知语言，构造文法，无形式化方法，更多是凭经验。*语言的形式定义第20页，共52页，2023年，2月20日，星期三例：{abna|n≥1},构造其文法

G1[S]：S→aBa, B→b|bBG2[S]：S→aBa, B→b|Bb定义7.G和G’是两个不同的文法，若L(G)=L(G’),则G和G’为等价文法。第21页，共52页，2023年，2月20日，星期三1.递归规则：规则右部有与左部相同的符号 对于U→xUy 若x=ε,即U→Uy，左递归； 若y=ε,即U→xU，右递归；2.递归文法：文法G，存在U

∈VnifU==>…U…,则G为递归文法；ifU==>U…,则G为左递归文法；ifU==>…U,则G为右递归文法；+++2.2.4文法的递归性第22页，共52页，2023年，2月20日，星期三4.递归文法的优点：可用有穷条规则，定义无穷语言例：对于前面给出的无符号整数的文法是有递归文法，用13条规则就可以定义出所有的无符号整数。若不用递归文法，那将要用多少条规则呢？!3.左递归文法的缺点：不能用自顶向下的方法来进行语法分析会造成死循环（后面将详细论述）第23页，共52页，2023年，2月20日，星期三2.3

句型的分析句型的分析：构造一算法，用以判断所给的符号串是否为某文法的句型（句子）常见分析方法有自顶向下分析和自底向上分析两类；自顶向下从开始符出发试图推导出给定的符号串；自底向上推导的逆过程（称归约）：从已给的符号串出发，试图将其归约为开始符。第24页，共52页，2023年，2月20日，星期三2.3.1规范推导和规范归约对于一文法而言，从开始符到某句型的推导过程可能不唯一。例如，文法G[E]中从E到i+i*i

的推导有：(1)EE+TE+T*FT+T*FT+T*iF+T*ii+T*ii+F*ii+i*i(2)EE+TT+TF+Ti+Ti+T*Fi+F*Fi+i*Fi+i*Fi+i*i(3)EE+TE+T*FE+T*iE+F*iE+i*iT+i*iF+i*ii+i*i(4)…

…

第25页，共52页，2023年，2月20日，星期三规范推导最左（右）推导：在推导序列的每一步直接推导中，被替换的总是当前句型中最左（右）的非终结符。形式上，从符号串到符号串的推导序列 *xUy

xuy*

总有xVT*(yVT*)时，称为最左（右）推导定义：最左（右）推导所得句型称为左（右）句型；最右推导称为规范推导；右句型称为规范句型。最左推导：若符号串中有两个以上的非终结符时，先推左边的。最右推导：若符号串中有两个以上的非终结符时，先推右边的。最右推导称为规范推导第26页，共52页，2023年，2月20日，星期三句子、句型的推导方法每个句子都有相应的最左和最右推导，因此，句子即是左句型也是右句型（规范句型）并不是每个句型都有最左和最右推导例如，E+E+i*T即不是左句型，也不是右句型对于给定的符号串w，采用自顶向下的分析来判断w是否为L(G[S])的句子的常见方法是：试图建立从开始符S到w最左推导: S*w

显然，每步推导时，对应于最左非终结符相应的产生式可能会有多个，若无特殊的办法，只能一个一个地试探。因此，推导过程可能是带回溯的。为提高效率，就应尽量避免回溯第27页，共52页，2023年，2月20日，星期三自底向上的语法分析~就是从已给的符号串w出发，试图以相反的方向为w建立一个规范推导，最终得到文法的开始符。推导的逆过程称作归约，它是把当前的符号串中的构成文法某个产生式A右部的子串替换成产生式的左部符号A，得到一个新的符号串A

。这样的一步动作，称为进行了一步归约。例如，符号串F+i*i中的F可按产生式TF归约为T，从而得到新的符号串T+i*i。若从给定的符号串w出发，一步步地将其归约，最终得到文法的开始符号，则说明w是该文法定义的一个句子。归约成功，否则，归约失败。若归约的每一步都归约的是当前符号串中最左边的某产生式的右部，则称该归约是规范归约（即最左归约）。规范归约是规范推导的逆过程。第28页，共52页，2023年，2月20日，星期三符号串i+i*i的归约过程由上表可以看出，归约过程是最左归约，它恰好是规范推导的逆过程。这正是把最左归约定义为规范归约的原因。第29页，共52页，2023年，2月20日，星期三关于归约的一点说明注意，前面例子中归约的第五步中，当前的符号串为E+T*i，除了可将i归约成F外，还可将E+T或T归约成E，分别得到符号串E*i和E+E*i。但是，若真按这两个方案进行归约，则当我们把其归约成E*E或E+E*E时，就再也归约不下去了。这就告诉我们在第五步时，唯一正确的归约是将i归约为F，也就是说，i是唯一可被归约的最左子串。那么，对于规范归约的每一步，如何确定符号串中的当前应被归约的最左子串呢？第30页，共52页，2023年，2月20日，星期三2.3.2语法树和二义性语法树用于直接地描述一个句型右句子的语法结构语法树是一有向树（连通的）1）有且仅有一个无任何前驱的结点，称为根（S）；2）除根外，每个结点恰有一个直接前驱；3）对于任一结点m，从根到m可达;4)每个结点的后继是有序的（从左到右）设G=(VN,VT,P,S)是一文法，则满足下述条件的树称为语法树：1）每个结点有一标记X，XV；2）根的标记为S（开始符）；3）若结点X有后继，则XVN；4）A有k个后继，自左至右为X1,X2,…,Xk，则AX1X2…Xk

P第31页，共52页，2023年，2月20日，星期三语法树的性质及实例语法树的所有叶结点自左至右排列构成了文法G的一个句型对一语法树而言，其构造过程不同对应了不同的推导（归约）过程例如，文法G[E]的句型i+i*i相应的语法树见右图。EE+TTFiT*FFii第32页，共52页，2023年，2月20日，星期三存在这样的文法G，其某个句子wL(G),可对应结构不同的语法树，即w对应了多个不同的最左（右）推导，这类文法称为二义性文法。例如，G3[E]：EE+E|E*E|(E)|i的句型i+i*i及文法CifBthenC|ifBthenCelseC CS

的句型：ifB1

then

ifB2

thenS1

elseS2上面两个句型均有两个不同的语法推导树（见下页），所以，它们是二义性文法文法的二义性第33页，共52页，2023年，2月20日，星期三EEEEE+*iiiEEEEE+*iiiifB1thenCelse C

S1 S2CifB2

thenCCifB1

thenCS1S2ifB1thenCelseC二义性语法的例子第34页，共52页，2023年，2月20日，星期三关于二义性文法应指出，二义性是一种常见的语法现象，然而，对于编译程序而言，二义性文法是有害的。为解决二义性文法带来的不确定性问题，通常的方法一是修改文法，例如，文法G3可用本章（P20(2.2)式）定义的文法G2[E]取代，而G2不是二义性的。二是利用附加条件。例如，

i+i*i的归约过程中，若规定*比+优先级高，则可强制性地让系统先按E*E进行归约，而不是先按E+E进行归约；又比如，若强制规定else只能和距其最近的尚未被匹配的then进行匹配，就可解决else悬空的问题。第35页，共52页，2023年，2月20日，星期三2.3.3短语和句柄问题:在自底向上(简记为)的语法分析中,对于每一步直接归约,应如何正确地确定当前句型中应被归约的最左子串?考虑文法G2[E]的句型=E+T*F+i,从开始符E推导出的语法树见右图该树中含有若干子树,如T(2)为根的子树对应的叶结点为T(3)*F(3),由于它是一直接子树,文法中必有产生式T->T*F;因此,称T*F是句型相对于产生式T->T*F的直接短语.同理,F(1)对应的直接短语为i.以E(1)为根的子树相应的叶结点为E(2)+T(3)*F(3),所以,称为句型相对于非终结符E的短语.同理,i是相对于T(1)的短语EE(1) +T(1)E(2)+T(2)T(3)*F(3)F(1)i第36页，共52页，2023年，2月20日，星期三短语、直接短语及句柄的定义例如，对句型=E+T*F+i，由定义，有：(1)E*E+T+i(=E+,A=T,=+i)及TT*F(=),故T*F是相对于产生式T->T*F的直接短语;(2)E*E+T*F+FFi,i是相对于产生式F->i的直接短语;(3)E*E+i与E+E+T*F,E+T*F是相对于非终结符E的短语;(4)E*E及E*E+T*F+i(=),是相对于E的短语注:由定义可知,直接短语也是短语,但短语不一定是直接短语.第37页，共52页，2023年，2月20日，星期三归约时被替换子串的选择从句型=E+T*F+i的语法树可知,E+T绝不是它的一个直接短语,因为虽然E->E+T是G2的一个产生式,但不存在从E到E*F+i的推导,所以,当判断一符串是否为某一句型的短语时,须检查定义2.8的两个条件是否同时满足.采用分析时,每步归约就是将一个产生式右部替换其左部,也就是把该句型的语法树中的一棵直接子树的末端结点剪去.即每次归约的符号串必是当前句型的一个直接短语.但是,对一句型而言,其直接短语可能不唯一.为了让分析能够机械地进行,我们只考虑规范归约(最左归约),即归约过程替换的是归左直接短语.我们以L(G2)的句子i+i*i+i为例,给出其最右推导(规范归约的逆过程),来说明每次规范归约的子符号串第38页，共52页，2023年，2月20日，星期三句柄的定义EE+TE+FE+iE+T+iE+T*F+iE+T*i+iE+F*i+iE+i*i+iT+i*i+iF+i*i+ii+i*i+i上面的推导过程的逆过程就是规范归约的过程。从其逆过程可看出，每步归约的均是当前句型的最左直接短语（最左直接子树的叶结点）。我们把它称为当前句型的句柄。定义2.9

一个句型的最左直接短语称为此句型的句柄。问题：如何确定一规范句型的句柄？句柄应被归约成哪个非终结符？EE+TE+TT*FTFiFFiii1234567891011第39页，共52页，2023年，2月20日，星期三(3)子树与短语子树：语法树中的某个结点（子树的根）连同它向下派生的部分所组成。某子树的末端结点按自左向右顺序为句型中的符号串，则该符号串为该句型的相对于该子树根的短语。定理定义：简单子树：仅有父子两代的子树。第40页，共52页，2023年，2月20日，星期三句柄：该语法树的最左简单子树的末端结点从左到右排列的字符串是该句型的句柄。某简单子树的末端结点按自左向右顺序为句型中的符号串，则该符号串为该句型的相对于该简单子树根的直接短语。定理只需画出句型的语法树，然后根据子树找

短语→直接短语→句柄。第41页，共52页，2023年，2月20日，星期三句型推导过程<==>句型语法树的生长过程 由推导构造语法树1从识别符号开始，自左向右建立推导序列。由根结点开始，自上而下建立语法树。语法树与推导第42页，共52页，2023年，2月20日，星期三 由语法树构造推导2自上而下地修剪子树的末端结点，直至把整棵树剪掉（留根），每剪一次对应一次规约。从句型开始，自右向左地逐步进行规约，建立推导序列。第43页，共52页，2023年，2月20日，星期三2.4文法的化简与改造2.4.1无用符号和无用产生式的删除设G=(VN,VT,P,S)是一文法,XVNVT,X称为是有用的,若X至少出现在一个句子的推导过程中,即X满足:(1)存在,V*,有S*X (2.12)(2)存在wVT*,使 X*w (2.13)否则,称X是无用的.若一产生式含有无用符号,则此产生式称为无用产生式.无用产生式给语法分析带来了许多麻烦,应予以删除.第44页，共52页，2023年，2月20日，星期三消除无用产生式的算法算法2.1

将文法G=(VN,VT,P,S),改造为G1=(V’N,VT,P’,S),使得L(G)=L(G1)(1)置V’N,P’为空;(2)对于P中每个产生式A,若(V’NVT)*,则将A加入V’N中;(3)重复(2),直到V’N不再增大;(4)对于每个AP,若(V’NVT)*,则置A

于P’中.算法2.2

任给文法G=(VN,VT,P,S),构造G’=(V’N,V’T,P’,S’),

使x(V’NV’T),,(V’NV’T)*,

有S*x(1)置V’T为空,V’N={S};(2)对于AP,若

AV’N则置中所有非终结符入V’N,所有终结符入V’T;(3)重复(2),直到V’不再增大;(4)令P’={A|AP,(V’NV’T)*,AV’N}第45页，共52页，2023年，2月20日，星期三消除无用产生式的例子例

G=({S,U,V,W},{a,b,c},P,S),其中,P:SaS|W|U UaVbV|acWaW现对G执行算法2.1:1.由Ua和Vac右部都是终结符,V‘N={U,V};2.对于SU,由UV’N有V’N={S,U,V};此外再无可放入V’N的符号;P1为SaS|UUaVbV|ac现对G1执行算法2.2:1.置V’N={S};2.由SU及Ua将U及a分别放入V’N(={S,U})和V’T(={a})中;3.此外,V’N和V’T不再增大;4.最后结果为:SaS|UUa注意,在删除无用符和无用产生式时,应先执行算法2.1再执行算法2.2,就可得到“干净”的文法;若先执行算法2.2,再执行算法2.1所得文法不一定“干净”第46页，共52页，2023年，2月20日，星期三2.4.2

-产生式的消除-产生式是指右部为一空符号串的产生式。因为某些语法分析算法要求不含~，此时应消除之若一语言不含（即L(G)),则可将其完全消除；若L(G),则可将文法改造为只有开始符S可推导出(即SP),而且,S不出现在任何产生式的右部,此外再无其它-产生式.本节中的算法2.3可用于找出所有可推导出的非终结符 W={A|A*,AVN}执行完算法2.3,通过检验SW与否可知L