编译原理形式语言基础

（优选）编译原理第章形式语言基础当前第1页\共有152页\编于星期六\18点1一、语言的定义

任何一种语言都是在某个特定字母表上定义的、按照一定的规则构成的字符串的集合。当前第2页\共有152页\编于星期六\18点2二、形式语言提出

形式语言是研究符号的语言，它仅考虑符号间的关系，不考虑含义，即用数学方法（主要是代数方法）对语言进行形式化描述。

1956年N.Chomsky(乔姆斯基）在研究自然语言过程中提出一种文法数学模型，为形式语言理论打下了基础，成为计算机科学理论一个重要分支，即形式语言与自动机。当前第3页\共有152页\编于星期六\18点3三、语言描述方法枚举法文法生成法：就是用有限个规则来产生出语言中无限个句子，这种规则集合称文法。自动机识别法：用自动机对语言中的句子进行识别当前第4页\共有152页\编于星期六\18点4四、与语言有关的几个概念元语言：可用来描述其它语言的一种语言语法：是在字母表上构造句子的一组规则语义：是按照语法规则所构成结构的含义语用：是表示语言符号与使用者关系当前第5页\共有152页\编于星期六\18点5§2.2符号和符号串

一、字母表二、符号串三、符号串集合当前第6页\共有152页\编于星期六\18点6一、字母表

有限个元素的非空集合称字母表，也称符号集。它是组成一个语言最基本的成分。字母表中元素称符号。习惯上用V、Σ或其它大写字母表示。例如V={a,b,c}，V={α,β…ω}|V|表示字母表中符号的个数。对于不同程序设计语言有不同字母表。例如，机器语言字母表={0,1}，PASCAL语言的字母表由字母、数字以及一些特殊符号，如+，-，*，/，·，(，)，=，…等组成。

注意：在一个语言中不能出现字母表以外的符号。当前第7页\共有152页\编于星期六\18点7二、符号串

1、定义

符号串是字母表中的符号所组成的任何有穷序列(有时也称为符号行或字)例如：设V={a,b,c},则符号串有a,b,c,aa,ab,ac,ba,abc…又如：设V={0,1},则符号串有

0，1，00，01，10，11，000…

由上例可以看出，符号串与符号组成顺序有关，如符号串ab不同于ba，符号串01不同于10，今后我们常用t,u,v,…x,y,z等小写字母表示符号串。当前第8页\共有152页\编于星期六\18点82、空符号串

不包含任何符号的符号串称为空符号串，记为ε。3、符号串长度

符号串中所含符号个数称为该符号串的长度，设符号串为x，则用|x|来表示x的长度。例如：x=abc，则|x|=3,显然,|ε|=0。当前第9页\共有152页\编于星期六\18点94、关于符号串的几种运算

（1）符号串的联结设有符号串x和y，则它们的联结xy是将符号串y直接拼接在符号串x之后，即

x=x1x2x3…xm,y=y1y2y3…yn

则

xy

=x1x2x3…xmy1y2y3…yn

显然εx=x，xε=x

当前第10页\共有152页\编于星期六\18点10（2）符号串的方幂

若x是符号串则x0=ε，x1=x，x2=xx，x3=xxx，…xn=xx…x(n个）如x=abc则x0=ε,x1=abc,x2=abcabcX3=abcabcabc∩当前第11页\共有152页\编于星期六\18点11三、符号串集合举例：字母表V={a,b}，问用V中的符号，可以组成哪些符号串？解：ε,a,b,aa,ab,ba,bb,aaa,…bbb,…1、定义：若集合A中的一切元素都是字母表V上的符号串，则称A为字母表V上的符号串集合当前第12页\共有152页\编于星期六\18点12V*定义：字母表V上各种长度符号串构成串集合，记为V*，不包括空行的集合记为V+即V*={x|x是V上符号串且包括空符号串}V+={x|x是V上符号串且不包括空符号串}V+=V*-{ε}如：V={a,b}，则V*={ε,a,b,aa,ab,ba,bb,aaa,…bbb,…}V+={a,b,aa,ab,ba,bb,aaa,…bbb,…}当前第13页\共有152页\编于星期六\18点132、关于串集合的运算（1）串集合乘积设A和B为两个符号串集合，并包含于V*，则A和B的乘积定义为：AB={xy|x∈A且y∈B}由此定义，乘积AB是满足x∈A且y∈B的所有符号串xy所组成的集合。如：V={0，1}V*={ε,0,1,00,01,10,11,000,001，010，011，100,101…}如果A={0，101}B={10，11，110}则AB={010，011，0110，10110，10111，101110}符号ø表示空集

当前第14页\共有152页\编于星期六\18点14（2）符号串集合的方幂设符号串集合A则A的方幂运算定义为：A0={ε},A1=A,A2=AA,A3=AAA,…An=AAA…A(n个）如：设A={a,b}，则A0={ε},A1={a,b}A2={a,b}{a,b}={aa,ab,ba,bb}A3={aaa,aab,aba,abb,baa,bab,bba,bbb}当前第15页\共有152页\编于星期六\18点15(3)符号串集合的闭包和正闭包

设A为符号串集合，则A的正闭包定义为A+=A1∪A2∪…∪An∪…符号串集合A的闭包定义为A*=A0∪A+={ε}∪A+

如A={a,b}则A+={a,b}∪{aa,ab,ba,bb}∪…={a,b,aa,ab,ba,bb,aaa,…,bbb,…}A*={ε,a,b,aa,ab,ba,bb,aaa,…bbb,…}我们可以证明：A+=AA*=A*AAA*=A（A0∪A1∪A2∪…An∪…）=A1∪A2∪…An∪…=A+当前第16页\共有152页\编于星期六\18点16作业：

P.38：习题2、3当前第17页\共有152页\编于星期六\18点17§2.3文法与语言一、巴科斯范式BNF(BackusNormalForm)二、语法树三、产生式（规则）四、文法五、推导和归约六、句型和句子七、语言八、递归文法九、短语和简单短语十、最左推导和最右推导十一、文法二义性当前第18页\共有152页\编于星期六\18点18一、巴科斯范式BNF例子：Themanhasadog.(这人有一条狗）我们以“∷=”符号(或“→”符号)表示”定义为”，以“|”符号表示“或”，以“<>”符号表示语法实体(语法单位)，这些符号是元语言符号，当前第19页\共有152页\编于星期六\18点19①<句子>∷=<主语><谓语>②<主语>∷=<冠词><名词>③<冠词>∷=the|a④<名词>∷=man|book|dog⑤<谓语>∷=<动词><宾语>⑥<动词>∷=has⑦<宾语>∷=<冠词><名词>我们把这种描述语法规则方法称巴科斯范式，也称为巴科斯--瑙尔范式(BackusNormalForm)，简称BNF。那么上面叙述<句子>的语法规则可写为：当前第20页\共有152页\编于星期六\18点20例如,在高级语言中大家所熟知的<标识符>这种语法成分,它用巴科斯范式描述为:<标识符>∷=<字母>|<标识符><字母>|<标识符><数字><字母>∷=A|B|C|D|…|Z|a|b|…|z<数字>∷=0|1|2|…|9这样便刻画出了<标识符>是以字母开始的一串字母和数字任意组合这种特点。当前第21页\共有152页\编于星期六\18点21如果定义<句子>的巴科斯范式改为：①〈句子〉∷=<主语><谓语>②〈主语〉∷=We|He|I③〈谓语〉∷=ran|ate|sat则下面9个句子都是正确的：①Weran②Heran③Iran④Weate⑤Heate⑥Iate⑦Wesat⑧Hesat⑨Isat可见，如果一个语言有无穷多个句子，那么用上述规则来描述更有实际意义.它用一组规则来代替枚举法，用有穷来描述无限。当前第22页\共有152页\编于星期六\18点22二、语法树

除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。

当前第23页\共有152页\编于星期六\18点23<句子>（句子themanhasabook的推导过程及对应的语法树）当前第24页\共有152页\编于星期六\18点24（句子themanhasabook的推导过程及对应的语法树）<句子><主语><谓语>①<句子>∷=<主语><谓语>当前第25页\共有152页\编于星期六\18点25（句子themanhasabook的推导过程及对应的语法树）<句子><谓语><主语><名词><冠词>①<句子>∷=<主语><谓语>②<主语>∷=<冠词><名词>当前第26页\共有152页\编于星期六\18点26（句子themanhasabook的推导过程及对应的语法树）<句子><主语><谓语>the<名词><冠词>①<句子>∷=<主语><谓语>②<主语>∷=<冠词><名词>③<冠词>∷=the|a当前第27页\共有152页\编于星期六\18点27（句子themanhasabook的推导过程及对应的语法树）<句子><主语><谓语><名词>manthe<冠词>①<句子>∷=<主语><谓语>②<主语>∷=<冠词><名词>③<冠词>∷=the④<名词>∷=man当前第28页\共有152页\编于星期六\18点28（句子themanhasabook的推导过程及对应的语法树）<句子><主语><谓语><名词><动词><宾语>manthe<冠词>①<句子>∷=<主语><谓语>②<主语>∷=<冠词><名词>③<冠词>∷=the④<名词>∷=man⑤<谓语>∷=<动词><宾语>当前第29页\共有152页\编于星期六\18点29（句子themanhasabook的推导过程及对应的语法树）<句子><主语><谓语><名词><动词><宾语>manhasthe<冠词>①<句子>∷=<主语><谓语>②<主语>∷=<冠词><名词>③<冠词>∷=the④⑤<谓语>∷=<动词><宾语>⑥<动词>∷=has当前第30页\共有152页\编于星期六\18点30（句子themanhasabook的推导过程及对应的语法树）<句子><主语><谓语><名词><动词><宾语>manhas<名词><冠词>the<冠词>①<句子>∷=<主语><谓语>②<主语>∷=<冠词><名词>③<冠词>∷=the④⑤<谓语>∷=<动词><宾语>⑥⑦当前第31页\共有152页\编于星期六\18点31（句子themanhasabook的推导过程及对应的语法树）<句子><主语><谓语><名词><动词><宾语>manhas<名词><冠词>athe<冠词>①<句子>∷=<主语><谓语>②<主语>∷=<冠词><名词>③<冠词>∷=the④⑤<谓语>∷=<动词><宾语>⑥⑦③当前第32页\共有152页\编于星期六\18点32（句子themanhasabook的推导过程及对应的语法树）<句子><主语><谓语><名词><动词><宾语>manhas<名词><冠词>abookthe<冠词>①<句子>∷=<主语><谓语>②<主语>∷=<冠词><名词>③<冠词>∷=the④⑤<谓语>∷=<动词><宾语>⑥⑦③④当前第33页\共有152页\编于星期六\18点33（句子themanhasabook的推导过程及对应的语法树）<句子><主语><谓语><名词><动词><宾语>manhas<名词><冠词>abookthe<冠词>当前第34页\共有152页\编于星期六\18点34其中：<句子>称为语法树根带<>和不带<>的都称为语法树的结点一个结点以及向下射出部分称为子树没有向下射出部分的结点称为末端结点当前第35页\共有152页\编于星期六\18点35三、产生式（规则）

1.定义

产生式(规则)就是一个符号与另一个符号串的有序偶(U,x),通常记为U→x或U∷=x其中：U是符号,x是有限非空符号串。

U称为规则的左部,x称为规则的右部如果U→x1，U→x2，U→x3，…，U→xn可以写成U→x1|x2|…|xn,并称xi是U的一个候选式。当前第36页\共有152页\编于星期六\18点362.字汇表(符号表)

（1）定义用于规则左部和右部中所有符号形成集合为字汇表，记为V。

当前第37页\共有152页\编于星期六\18点37（2）分类1）非终结符号

出现在规则左部,且能派生出符号或符号串的那些符号称为非终结符,也称语法实体或语法单位,它们的全体构成一个非终结符的集合,记为VN

2）终结符

规则中不属于VN的那些符号,称为终结符,它们的全体组成终结符的集合,记为VT。终结符一般出现在规则的右部。显然,V=VN∪VT,VN∩VT=ø当前第38页\共有152页\编于星期六\18点38如：在PASCAL中，对标识符的定义规则为：<标识符>∷=<字母>|<标识符><字母>|<标识符><数字><字母>∷=a|b|…|z|A|B|…|Z<数字>∷=0|1|…|9由此得：VN

={<字母>,<数字>,<标识符>}VT={a,b,…,z,A,B,…Z,0,1,…9}当前第39页\共有152页\编于星期六\18点39例如：有产生式:S∷=0S1S∷=01则VN={S}VT={0,1}V={S,0,1}当前第40页\共有152页\编于星期六\18点40四、文法为研究方便，下面给出文法的形式定义定义：文法是规则的有穷集合,形式定义为四元组形式为G=(VN,VT,P,Z)其中：VN是非终结符集合,VT是终结符集合,P代表产生式集,Z∈VN是文法G开始符号,也称识别符号,它至少要在一条产生式左部出现。文法G通常记为G［Z］。当前第41页\共有152页\编于星期六\18点41对于前面英语句子的例子中用7条文法规则来描述英语句子,其文法可表示为G=(VN,VT,P,Z)其中:VN={<句子>，<主语>，<谓语>，<宾语>，<冠词>，<动词>，<名词>}VT={the,a,man,book,dog}P是前述7条规则Z=<句子>当前第42页\共有152页\编于星期六\18点42又例如：标识符文法可定义如下:G［Z］=(VN,VT,P,Z)VN={<字母>,<数字>,<标识符>}VT={a,b,…,z,A,B,…,Z,0,1,…9}Z=<标识符>P由下列规则组成:<标识符>∷=<字母>|<标识符><字母>|<标识符><数字><字母>∷=a|b|…|z|A|B|…|Z<数字>∷=0|1|…|9当前第43页\共有152页\编于星期六\18点43五、推导和归约

定义1设G为一个文法，U∷=u是G中一个规则，x和y是V*上符号串，使得v=xUy与w=xuy则称符号串v直接推导出符号串w，或称w直接归约到v，并把w叫做v直接派生式，记作vw若x=y=ε，则v=xUy=U，w=xuy=u可见vw即Uu说明一个规则就是一个直接推导例如<句子>直接推导到<主语><谓语>，而<主语><谓语>直接归约到<句子>。

当前第44页\共有152页\编于星期六\18点44例如:

G=(VN,VT,P,S)VN={S},VT={0,1}P:S∷=0S1S∷=01

令v=xSy,w=x01y,因S∷=01(U∷=u)即vwxSyx01y若x=y=ε则S01(一个规则就是一个直接推导)同样S∷=0S1

v=00S11，w=000S111Uu即vw00S11000S111当前第45页\共有152页\编于星期六\18点45又如：标识符文法定义如下:G［Z］=(VN,VT,P,Z)VN={<字母>,<数字>,<标识符>}VT={a,b,…,z,A,B,…,Z,0,1,…9}P由下列规则组成:

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

<字母>∷=a|b|…|z|A|B|…|Z<数字>∷=0|1|…|9Z=<标识符>则有：<标识符><标识符><字母>

<标识符>a当前第46页\共有152页\编于星期六\18点46定义2

设u0,u1,u2,…,un均为V*上符号串,若w是v经过一系列直接推导得到的,即v=u0

u1

u2

…un-1

un=w(n>0)则称v推导到w,或称w归约到v,记作v+w称这个直接推导序列为长度为n的推导。如果v+w或者v=w(表示0步推导),则记作v*w称v广义推导到w或称w广义归约到v。

显然,直接推导的长度为1,推导

+的长度≥1,而广义推导

*的长度≥0例如在前面的例子中,因S∷=0S1

S∷=01

0S100S11000S11100001111所以0S1+00001111(n=3)当前第47页\共有152页\编于星期六\18点47例设有文法G［<整数>］:(1)<整数>∷=<数字串>(2)<数字串>∷=<数字串><数字>(3)<数字串>∷=<数字>(4)<数字>∷=0(5)<数字>∷=1(6)<数字>∷=2(7)<数字>∷=3(8)<数字>∷=4(9)<数字>∷=5(10)<数字>∷=6(11)<数字>∷=7(12)<数字>∷=8(13)<数字>∷=9整数23的推导过程:<整数><数字串><数字串><数字><数字><数字>2<数字>23因此,<整数>+23,其推导长度为5。显而易见,在推导时,任意地选取规则(4)到(13),就可以推导得到任意整数。当前第48页\共有152页\编于星期六\18点48六、句型和句子定义：设G［Z］是一文法,若符号串x是由识别符Z推导而得,即Z*xx∈V*则称符号串x为该文法G的一个句型。如果一个句型x仅由终结符组成,即Z*xx∈VT*则称句型x为该文法一个句子。例如：在书中的例2.16中,<整数>,<数字><数字>,2<数字>,23等都是文法G[<整数>]的句型,其中仅23是句子。

可见：句子一定是句型，而句型未必是句子。一个正确的源程序是句子。当前第49页\共有152页\编于星期六\18点49七、语言定义：设G［Z］为一文法,由该文法所产生的一切句子的集合称为由该文法所定义的语言,记为L(G［Ｚ］)(或记为L(G)),即L(G)={x|Z*x且x∈VT*}有时我们称这样定义的语言为形式语言，以区别于自然语言。上述公式包含两层意思：语言是句子集合，是VT*一个子集合，即VT中行集合子集。句子必须由该语言文法识别符推导出。当前第50页\共有152页\编于星期六\18点50例如：G[S]=(VN,VT,P,S)VN={S}VT={0,1}P:{S∷=01,S∷=0S1}S:识别符很容易推出：L（G）={0n1n|n≥1}当前第51页\共有152页\编于星期六\18点51又如：写一个文法，使其语言为偶整数集合。首先分析以下偶整数（1）偶整数最后一个数字应该是偶数字0，2，4，6，8（2）偶整数前面符号可以是+，-或不带符号由此得其文法应由下列规则组成：<偶整数>∷=<符号><偶数字>|<偶数字>|<符号><数字串><偶数字>|<数字串><偶数字><偶数字>∷=0|2|4|6|8<数字>∷=1|3|5|7|9|<偶数字><数字串>∷=<数字>|<数字串><数字><符号>∷=+|-所以文法可表示为：G=(VN,VT,P,<偶整数>)其中：VN={<偶整数>，<偶数字>，<数字>，<数字串>，<符号>}VT={0，1，2，3，4，5，6，7，8，9，+，-}当前第52页\共有152页\编于星期六\18点52对于通常的程序设计语言其文法为:G［程序］=(VN,VT,P,<程序>)其中VN={<程序>,<说明>,<语句>,…}VT={0,1,…,9,a,…,z,-,(,),…}P={<程序>∷=…,<说明>∷=…,<语句>∷=…,…}L(G)={w|<程序>*w且w∈VT*}由此可知,每一个w就是一个源程序，所谓PASCAL语言也就是所有PASCAL程序的集合。当前第53页\共有152页\编于星期六\18点53作业：P.38习题6、7当前第54页\共有152页\编于星期六\18点54八、递归文法构成一个语言的句子集合可以是有穷的，也可以是无穷的，例如文法G［<句子>］所描述的语言L(G［<句子>］)是有穷的。但文法G［<整数>］所描述的语言L(G［<整数>］)是无穷的，它包含无穷多个句子。

当前第55页\共有152页\编于星期六\18点55例如：文法G(<句子>)包含的下列规则如下：①〈句子〉∷=<主语><谓语>②〈主语〉∷=We|He|I③〈谓语〉∷=ran|ate|sat所描述的语言为：①Weran②Heran③Iran④Weate⑤Heate⑥Iate⑦Wesat⑧Hesat⑨Isat当前第56页\共有152页\编于星期六\18点56例如文法G［<整数>］的规则如下：(1)<整数>∷=<数字串>(2)<数字串>∷=<数字串><数字>(3)<数字串>∷=<数字>(4)<数字>∷=0(5)<数字>∷=1(6)<数字>∷=2(7)<数字>∷=3(8)<数字>∷=4(9)<数字>∷=5(10)<数字>∷=6(11)<数字>∷=7(12)<数字>∷=8(13)<数字>∷=9所描述的语言包括无穷多个句子。当前第57页\共有152页\编于星期六\18点57不难发现，两个文法其根本差别在于文法G［<整数>］有形如<数字串>∷=<数字串><数字>的规则。在这个规则中左部和右部皆出现非终结符<数字串>。这种借助于自己来定义自己的规则，即在规则左部和右部具有相同的非终结符规则称为递归规则。

当前第58页\共有152页\编于星期六\18点58八、递归文法

1.

定义对于一个文法,若有一个规则U∷=…U…,则称直接递归,若有规则U∷=U…,则称直接左递归,若有规则U∷=…U,则称直接右递归。若有推导式U+…U…,则称间接递归,若有推导式U+U…,则称间接左递归,若有推导式U+…U,则称间接右递归。非终结符U称递归非终结符。如果一个文法中至少含有一个递归非终结符,则将此文法称为递归文法。当前第59页\共有152页\编于星期六\18点59例如：规则S∷=0S1是直接递归规则A∷=Aa是直接左递归规则B∷=aBB是直接右递归

当前第60页\共有152页\编于星期六\18点60例如：设有文法G的规则P为S∷=Qc|cQ∷=Rb|bR∷=Sa|a在这些条规则中,无直接递归规则,但有如下推导:QRbSabQcab所以Q+Qcab因此是间接左递归。文法G为递归文法显然，直接递归是间接递归一种特殊情况。

当前第61页\共有152页\编于星期六\18点61八、递归文法

2.说明

如果一个语言是无穷的，则描述该语言的文法必定是递归的。一般说，程序设计语言是无穷的，因此描述它们的文法必定是递归的。应当指出，从语法定义的角度来看，递归定义使文法的形式比较简练，给无限的语言有限的表示提供了一种可用的方法。然而在后面我们将会看到，文法的左递归性将会给某些语法分析方法的实现带来很大的麻烦。

当前第62页\共有152页\编于星期六\18点62九、短语和简单短语

1.短语和简单短语2.句柄(柄短语)

3.再谈语法树当前第63页\共有152页\编于星期六\18点631.短语和简单短语定义：设G［Z］是一文法，w=xuy是其中一句型，若有Z*xUy,U∈VN且U+u,u∈V+则称u是一个相对于非终结符U、句型w的短语。若Z*xUy且Uu则称u是一个相对于非终结符U、句型w的简单短语。当前第64页\共有152页\编于星期六\18点64例设有文法G［S］=({S,A,B},{a,b},P,S),其中P为S∷=ABA∷=Aa|bBB∷=a|Sb找出句型baSb的全部短语，简单短语.当前第65页\共有152页\编于星期六\18点65根据句型推导过程有

SABbBBbaBbaSb由上可见，下式成立：S*baB且BSb所以子串Sb是相对于非终结符B，句型baSb的简单短语。同样有SABASbbBSbbaSb即S*bBSb且Ba子串a是相对于B，句型baSb的简单短语。还有S*ASb且A+ba即子串ba是相对于非终结符A，句型baSb的短语。对于句型baSb，再没有其它能产生新的短语推导了，所以句型baSb有短语ba简单短语a和Sb当前第66页\共有152页\编于星期六\18点662、句柄(柄短语)

定义

一个句型最左边的简单短语称为该句型的句柄(或柄短语)，而且句柄最左边的符号称句柄的头，句柄最右边的符号称句柄的尾。

如上例句型baSb简单短语为a和Sb，由于a是最左简单短语，所以a又是句柄。

当前第67页\共有152页\编于星期六\18点67例如：设文法G[S]S∷=AA∷=B|A+BB∷=C|B*CC∷=|(A)现在我们看w=C+B*C句型∵SAA+BB+BC+BC+B*C∴S*C+BBB*C∴B*C是相对于B和句型C+B*C的简单短语同样∵SAA+BB+BB+B*CC+B*C∴S*B+B*CBC∴C是相对于B，句型C+B*C的简单短语。由于C在左边，所以C是句柄，柄头和柄尾都是C当前第68页\共有152页\编于星期六\18点683.再谈语法树

前面我们曾利用语法树直观地描述句子语法结构关系，现在我们仍然借助于语法树进行句型和句子的推导，同时，利用它寻找短语和简单短语也是十分直观和方便的。（1）语法树形式定义设有文法G=（VN，VT，P，Z），满足下列条件的树即为一个语法树

a.树中每一个结点都有标记，且该标记是VN∪VT中某一符号b.树根标记是识别符号c.若有一个结点至少有一个后继结点，则该结点标记必为非终结符d.若一个标记为U的结点，它有标记依次为X1，X2,X3，…，Xn的直接后继结点，则U∷=X1X2…Xn必定是G的一条规则。当前第69页\共有152页\编于星期六\18点69SABbBSba我们以书中的例2.22的文法G［S］为例，句型baSb的推导,设有文法G［S］=({S,A,B},{a,b},P,S),其中P为S∷=ABA∷=Aa|bBB∷=a|SbSABbBBbaBbaSb画出语法树如下图所示

当前第70页\共有152页\编于星期六\18点70语法树中的几个术语：①结点：每个符号(终结符或非终结符)对应于一个结点，以符号名为结点名称；②边：两个结点间的连线称为边；③根结点：由文法识别符号标记，如S；④分支：从某结点向下射出的边连同边上的结点称为分支，分支的深度为1。分支的名字是射出该分支结点的名字，分支的各个结点称为分支结点；⑤子树：语法树的某结点连同从它向下射出的部分称为该语法树的子树，该结点称为子树根结点；⑥末端结点/叶结点。当前第71页\共有152页\编于星期六\18点71（2）语法树构造过程句型baSb的语法树构造过程如下：(1)从识别符号S开始,向下画一分支,表示第一个直接推导(SAB,规则S∷=AB)。SAB当前第72页\共有152页\编于星期六\18点72（2）语法树构造过程句型baSb的语法树构造过程如下：(1)从识别符号S开始,向下画一分支,表示第一个直接推导(SAB),(规则S∷=AB)。(2)从分支结点A出发,向下画一分支,表示第二个直接推导(ABbBB),(规则A∷=bB)。SAB当前第73页\共有152页\编于星期六\18点73（2）语法树构造过程句型baSb的语法树构造过程如下：(1)从识别符号S开始,向下画一分支,表示第一个直接推导(SAB),(规则S∷=AB)。(2)从分支结点A出发,向下画一分支,表示第二个直接推导(ABbBB),(规则A∷=bB)。SABbB当前第74页\共有152页\编于星期六\18点74（2）语法树构造过程句型baSb的语法树构造过程如下：(1)从识别符号S开始,向下画一分支,表示第一个直接推导(SAB),(规则S∷=AB)。(2)从分支结点A出发,向下画一分支,表示第二个直接推导(ABbBB),(规则A∷=bB)。(3)再由分支A的分支结点B向下画分支,表示第三个直接推导(bBBbaB),(规则B∷=a)。SABbB当前第75页\共有152页\编于星期六\18点75（2）语法树构造过程句型baSb的语法树构造过程如下：(1)从识别符号S开始,向下画一分支,表示第一个直接推导(SAB),(规则S∷=AB)。(2)从分支结点A出发,向下画一分支,表示第二个直接推导(ABbBB),(规则A∷=bB)。(3)再由分支A的分支结点B向下画分支,表示第三个直接推导(bBBbaB),(规则B∷=a)。SABbBa当前第76页\共有152页\编于星期六\18点76（2）语法树构造过程句型baSb的语法树构造过程如下：(1)从识别符号S开始,向下画一分支,表示第一个直接推导(SAB),(规则S∷=AB)。(2)从分支结点A出发,向下画一分支,表示第二个直接推导(ABbBB),(规则A∷=bB)。(3)再由分支A的分支结点B向下画分支,表示第三个直接推导(bBBbaB),(规则B∷=a)。(4)最后由句型baB中标记B的结点向下画分支,表示最后一个推导(baBbaSb),(规则B∷=Sb)。SABbBa当前第77页\共有152页\编于星期六\18点77（2）语法树构造过程句型baSb的语法树构造过程如下：(1)从识别符号S开始,向下画一分支,表示第一个直接推导(SAB),(规则S∷=AB)。(2)从分支结点A出发,向下画一分支,表示第二个直接推导(ABbBB),(规则A∷=bB)。(3)再由分支A的分支结点B向下画分支,表示第三个直接推导(bBBbaB),(规则B∷=a)。(4)最后由句型baB中标记B的结点向下画分支,表示最后一个推导(baBbaSb),(规则B∷=Sb)。SABbBSba当前第78页\共有152页\编于星期六\18点78（2）语法树构造过程句型baSb的语法树构造过程如下：(1)从识别符号S开始,向下画一分支,表示第一个直接推导(SAB),(规则S∷=AB)。(2)从分支结点A出发,向下画一分支,表示第二个直接推导(ABbBB),(规则A∷=bB)。(3)再由分支A的分支结点B向下画分支,表示第三个直接推导(bBBbaB),(规则B∷=a)。(4)最后由句型baB中标记B的结点向下画分支,表示最后一个推导(baBbaSb),(规则B∷=Sb)。SABbBSba这时末端结点自左至右排列起来就是句型baSb。这棵语法树形象地表示了句型baSb上述推导过程。当前第79页\共有152页\编于星期六\18点79结论：对于每一个语法树（或者子树）至少对应一个推导（可能是直接推导。可能是n步推导）对于每个推导必存在有一个语法树，画语法树过程中，每个分支对应于一个直接推导。不同推导可能有相同的语法树。如：SABbBBbaBbaSbSABASbbBSbbaSb同一句型的两个不同的推导对应的语法树确是相同的。树的末端结点标记从左到右连接起来就是要推导的句型或句子当前第80页\共有152页\编于星期六\18点80作业P.38：习题8；P.39：习题11(1)、(2)当前第81页\共有152页\编于星期六\18点81（3）语法树的作用1）利用语法树可以构造文法的句型；（前面我们已经讲了句型baSb的语法树构造过程）2）根据语法树可以确定短语、简单短语和句柄；树末端结点的符号串是相对于子树根的短语，分支结点的符号串是相对于分支名字的简单短语，最左简单子树(只有父子两代)的末端结点的符号串是句柄。从右图语法树可直观看出：ba是句型baSb，相对于A的短语，Sb是句型baSb相对于B的简单短语，a是句型baSb相对于B简单短语，也是句柄。

3）当给定文法G后，我们可借助于推导语法树的逆过程把句型推导构造出来（见下页举例）SABbBSba当前第82页\共有152页\编于星期六\18点82对于右图baSb语法树，最左末端分支是文法G中一条规则B∷=a，若剪去此分支(将a归约为B)，则得句型bBSb的语法树，也就是重新构造了一个直接推导为bBSbbaSbSABbBSba当前第83页\共有152页\编于星期六\18点83对于右图baSb语法树，最左末端分支是文法G中一条规则B∷=a，若剪去此分支(将a归约为B)，则得句型bBSb的语法树，也就是重新构造了一个直接推导为bBSbbaSbSABbBSb当前第84页\共有152页\编于星期六\18点84对于右图baSb语法树，最左末端分支是文法G中一条规则B∷=a，若剪去此分支(将a归约为B)，则得句型bBSb的语法树，也就是重新构造了一个直接推导为bBSbbaSb此时该语法树最左末端分支相应规则为A∷=bB，再剪去此分支(即将bB归约为A)，又得到句型ASb的语法树，于是又构造了推导为ASbbBSbbaSbSABSbbB当前第85页\共有152页\编于星期六\18点85对于右图baSb语法树，最左末端分支是文法G中一条规则B∷=a，若剪去此分支(将a归约为B)，则得句型bBSb的语法树，也就是重新构造了一个直接推导为bBSbbaSb此时该语法树最左末端分支相应规则为A∷=bB，再剪去此分支(即将bB归约为A)，又得到句型ASb的语法树，于是又构造了推导为ASbbBSbbaSbSABSb当前第86页\共有152页\编于星期六\18点86对于右图baSb语法树，最左末端分支是文法G中一条规则B∷=a，若剪去此分支(将a归约为B)，则得句型bBSb的语法树，也就是重新构造了一个直接推导为bBSbbaSb此时该语法树最左末端分支相应规则为A∷=bB，再剪去此分支(即将bB归约为A)，又得到句型ASb的语法树，于是又构造了推导为ASbbBSbbaSb继续下去，再剪去最左末端分支(将Sb归约为B)，则得句型AB的语法树，又建立了推导为ABASbbBSbbaSbSABSb当前第87页\共有152页\编于星期六\18点87对于右图baSb语法树，最左末端分支是文法G中一条规则B∷=a，若剪去此分支(将a归约为B)，则得句型bBSb的语法树，也就是重新构造了一个直接推导为bBSbbaSb此时该语法树最左末端分支相应规则为A∷=bB，再剪去此分支(即将bB归约为A)，又得到句型ASb的语法树，于是又构造了推导为ASbbBSbbaSb继续下去，再剪去最左末端分支(将Sb归约为B)，则得句型AB的语法树，又建立了推导为ABASbbBSbbaSbSAB当前第88页\共有152页\编于星期六\18点88对于右图baSb语法树，最左末端分支是文法G中一条规则B∷=a，若剪去此分支(将a归约为B)，则得句型bBSb的语法树，也就是重新构造了一个直接推导为bBSbbaSb此时该语法树最左末端分支相应规则为A∷=bB，再剪去此分支(即将bB归约为A)，又得到句型ASb的语法树，于是又构造了推导为ASbbBSbbaSb继续下去，再剪去最左末端分支(将Sb归约为B)，则得句型AB的语法树，又建立了推导为ABASbbBSbbaSb最后剪去分支AB(将AB归约为S)，得到树根S，建立了句型baSb推导为SABASbbBSbbaSbSAB当前第89页\共有152页\编于星期六\18点89对于右图baSb语法树，最左末端分支是文法G中一条规则B∷=a，若剪去此分支(将a归约为B)，则得句型bBSb的语法树，也就是重新构造了一个直接推导为bBSbbaSb此时该语法树最左末端分支相应规则为A∷=bB，再剪去此分支(即将bB归约为A)，又得到句型ASb的语法树，于是又构造了推导为ASbbBSbbaSb继续下去，再剪去最左末端分支(将Sb归约为B)，则得句型AB的语法树，又建立了推导为ABASbbBSbbaSb最后剪去分支AB(将AB归约为S)，得到树根S，建立了句型baSb推导为SABASbbBSbbaSbS当前第90页\共有152页\编于星期六\18点90结论：从语法树构造推导也就是不断地重复构造最后直接推导和剪去相应分支直到无分支可剪过程。对于每个语法树至少存在一个推导。上例我们选用了最左归约，即每次剪去最左末端分支，实际上每次归约是句柄。如果改变剪去相应分支顺序便将得到不同推导。当前第91页\共有152页\编于星期六\18点91十、最左推导和最右推导对于一给定的文法来说，从其开始符号到某一句型，或从某一句型到另一句型间的推导序列可能不唯一。为了使句型或句子能按照一确定的推导序列来产生，通常我们仅考虑最左推导或最右推导。当前第92页\共有152页\编于星期六\18点92定义1：在任何一步推导vw中，都是对符号串v的最左(右)的非终结符进行替换，则称最左(右)推导。

例如：G[S]S∷=ABA∷=Aa|BbB∷=a|SSABbBBbaB------最左推导SABASbAABbAAabAbBab-------最右推导SABASbbBSbbaSb------非左非右推导当前第93页\共有152页\编于星期六\18点93定义2：最右推导叫规范推导，即在规范推导过程中，每步直接推导xUyxuy中，符号串y只含有终结符。如果推导v+w中每一步直接推导是规范的，则称推导v+w为规范推导。当前第94页\共有152页\编于星期六\18点94相关概念：规范句型：由规范推导所得的句型称为规范句型。规范归约：我们把最左推导的逆过程称最右归约最右推导的逆过程称最左归约最左归约也称为规范归约

当前第95页\共有152页\编于星期六\18点95应当指出，对于文法中的每一句子都必定有最左和最右推导，但对于一句型来说则不尽然。例如，对于文法G［E］E∷=E+T|TT∷=T*F|FF∷=(E)|i中句型T*i+T，仅有唯一的推导EE+TT+TT*F+TT*i+T显然，推导E+T*i+T既非最左推导亦非最右推导。当前第96页\共有152页\编于星期六\18点96十一、文法二义性1.定义2.文法二义性消除3.几点说明当前第97页\共有152页\编于星期六\18点971.定义

如果一个文法中某个句型对应两棵不同的语法树，则称这个文法是二义性的。也就是说，若一个文法中的某句型对应两个不同的最左推导或最右推导，则这个文法是二义性的。当前第98页\共有152页\编于星期六\18点98例如：文法G［E］E∷=E+E|E*E|(E)|i符号串i+i*i是L(G)中一个句子,有两个不同的最右推导

EE+EE+E*EE+E*iE+i*ii+i*i(1)

EE*EE*iE+E*iE+i*ii+i*i(2)对应两棵不同的语法树推导序列(1)和(2)分别对应两棵不同的语法树,所以文法G［E］是二义性的。若将+，*看成算术运算符，则出现对表达式i+i*i是先做+还是先做*的不确定问题。EE+EiEEii*EE*EiEEii+当前第99页\共有152页\编于星期六\18点99对于不少高级语言中，例如PASCAL语言，在描述条件语句(IF语句)时，使用文法G［C］，其规则P为C∷=ifBthenCC∷=ifBthenCelseCC∷=SB∷=B1|B2S∷=S1|S2其中C是开始符号，B代表布尔表达式，S代表语句，显然，句子ifB1thenifB2thenS1elseS2存在两种不同最右推导。当前第100页\共有152页\编于星期六\18点100①CifBthenC

ifB1thenifB2thenCelseCifB1thenifB2thenS1elseS2

CifBCthenifBCthenelseCSSB1B2S1S2当前第101页\共有152页\编于星期六\18点101②CifBthenCelseCifB1thenCelseS2

ifB1thenifB2thenC

elseS2

ifB1thenifB2thenS1elseS2

CifBCthenelseCifBCthenSSB1S2S1B2当前第102页\共有152页\编于星期六\18点1022.文法二义性消除由于二义性文法的存在，使得在语法分析时带来了麻烦，为此，们可以具体采用两种途径来解决文法二义性问题。

（1）在语义上加些限制，或者说加一些语法非形式规定。例如对于上例中G［E］文法，我们可以通过规定运算符之间的优先级来避免文法的二义性。又例如对于条件语句文法G[C]，我们可以规定else永远与最靠近它前面一个尚未匹配then配对，这样就避免文法二义性。（2）对原二义性文法加上一定条件，将其改造成一个等价的无二义性文法。当前第103页\共有152页\编于星期六\18点103例如对于上述G［E］文法可以构造出一个无二义性文法G’[E]。即E∷=T|E+TT∷=F|T*FF∷=(E)|iEE+TTFiTFFii*当前第104页\共有152页\编于星期六\18点1043.几点说明（1）业已证明，文法的二义性是不可判定的。（2）文法的二义性和语言的二义性是两个不同的概念。产生该语言的文法都是二义性文法，称该语言为二义性语言，也称先天二义性。至少有一个非二义文法产生该语言称此语言为非二义性语言。对于由二义性文法描述的语言，有时可以找到等价的无二义性文法描述它，如上例文法G［E］和G’[E]，因此，我们只说文法二义性，而不说语言的二义性。当前第105页\共有152页\编于星期六\18点105作业P.39：习题15P.41：习题22当前第106页\共有152页\编于星期六\18点106

§2.4语法分析初步若已有文法G，如果给定一个符号串w，如何来确定该符号串是否是文法的句子呢?当前第107页\共有152页\编于星期六\18点107一、自顶向下语法分析

1.分析基本思想2.分析方法二、自底向上语法分析

1.分析基本思想2.分析方法当前第108页\共有152页\编于星期六\18点108一、自顶向下语法分析（导出法）

1.分析基本思想

自顶向下分析就是从文法的开始符号出发，利用其中产生式，逐步推导出要分析的符号串。换言之，对于任何给定的输入串，试图用一切可能的办法，从文法开始符号出发，自上而下、从左到右地为输入串建立语法树。这种分析过程本质上是一个试探过程，是反复使用不同规则谋求匹配输入串的过程。当前第109页\共有152页\编于星期六\18点1092.分析方法例如：设有文法G=(VN，VT,P,S),其中VN={S,A}VT={a,b,c,d}P:S∷=cAdA∷=ab|a试分析符号串x=cad是否是文法G的句子.根据推导ScAdcad容易判断出x=cad是该文法的句子。若用画语法树的方法我们同样可以判断出cad是文法的句子。SAdca当前第110页\共有152页\编于星期六\18点110（1）为了自上而下为符号串x建立语法树，首先将文法的开始符号S作为树的根结点，并设输入串指针i指向其第一个符号c，然后用S为左部的产生式来扩展这棵树.若按自上而下语法分析程序的步骤进行分析判断，其过程如下：P:S∷=cAdA∷=ab|aSAdcScAdcadi当前第111页\共有152页\编于星期六\18点111（2）此时该树最左边末结点c与x的第一个符号c相匹配，于是调整指针i使其指向输入串下一符号a。我们再试图让树的中间端末结点A去匹配a，显然，由于A是非终结符，它不可能直接与终结符a匹配，我们只得在文法中选择以A为左部的产生式，这里以A为左部的产生式有两个，我们试着用第一个选择来匹配输入串,并扩展语法树。若按自上而下语法分析程序的步骤进行分析判断，其过程如下：P:S∷=cAdA∷=ab|aSAdcScAd

cabdcadiab当前第112页\共有152页\编于星期六\18点112（3）此时子树A最左端末结点a与i所指的符号a匹配。于是再调整i使其指向下一输入符号d，并试图用A的最右端末结点b与之匹配。但它们不匹配，因此，子树A的匹配失败，这意味着选用A的第一个候选式对此时的情况不适合，不能构造出输入串x的语法树，在这种情况下，我们应该回头看看(回溯)是否还有其它的候选式可供利用.若按自上而下语法分析程序的步骤进行分析判断，其过程如下：P:S∷=cAdA∷=ab|aSAdcScAd

cabdcadiabERROR!当前第113页\共有152页\编于星期六\18点113（4）我们应把A的第一个候选式所扩展的子树剪掉，还应把指针i恢复到进入A时所指的输入符号a，再选用A第二个候选式来构造语法树.若按自上而下语法分析程序的步骤进行分析判断，其过程如下：P:S∷=cAdA∷=ab|aSAdcScAdcadi当前第114页\共有152页\编于星期六\18点114（5）此时子树A的唯一端末结点a与i所指的输入符号a匹配，因此A匹配成功，调整指针i，使其指向下一个输入符号d。若按自上而下语法分析程序的步骤进行分析判断，其过程如下：P:S∷=cAdA∷=ab|aSAdcScAdcadcadia当前第115页\共有152页\编于星期六\18点115（6）最后考虑S的第三个端末结点d，它与i所指的最后一个输入符号匹配，因此完成了构造输入串x的语法树的任务，从而证明了x是所给文法推导出一个句子。若按自上而下语法分析程序的步骤进行分析判断，其过程如下：P:S∷=cAdA∷=ab|aSAdcScAdcadcadiaSUCCESS!当前第116页\共有152页\编于星期六\18点116下面我们将上述分析过程总结一下：（1）自根开始建树试图生成一个和所给的符号串相一致的终结符号串

（2）选择不同的规则反复试探在建树过程中，反复选择不同的规则，每一步试图将语法树最左的叶子与所给的符号串进行匹配

（3）匹配失败退回出错点当匹配失败时，必须回到出错点，然后再选择其他规则进行试探这种方法称为回溯采用自顶向下分析时，不仅可能遇到回溯问题，而且还可能由于文法中有左递归规则而陷入无限循环。我们将在第四章中要介绍这两方面问题及其解决办法。

当前第117页\共有152页\编于星期六\18点117二、自底向上语法分析1.分析基本思想

自底向上分析是从所给的符号串w开始，在其中寻找与文法规则右部相匹配的子串，并用该规则的左部取代此子串(即归约)，重复此过程，步步向上归约，最后试图将符号串w归约到文法识别符号，如归约成功，则符号串w是文法的句子。

当前第118页\共有152页\编于星期六\18点118二、自底向上语法分析

2.分析方法例2.24设有文法G=(VN,VT,P,S),其中VN={A,B,S}VT={a,b,c,d,e}P:S∷=aAcBeA∷=Ab|bB∷=d试分析w=abbcde是否为此文法的句子。

当前第119页\共有152页\编于星期六\18点119归约过程描述:

先设立一个符号栈，即将输入串中符号逐个移进栈，当栈顶符号串形成一个句柄时，就进行一次归约，把栈顶句柄那个符号串用相应规则左部的非终结符号来代替，接着再检查在栈顶是否形成新的句柄，若出现新的句柄，那么再进行归约；若没有形成新句柄，则再从输入符号串中移进新符号，……，如此继续到整个输入符号串处理完毕。最终，如栈底为开始符号，则输入符号串是该文法的句子，报告成功，否则，是不合法的符号串，报告错误。当前第120页\共有152页\编于星期六\18点120为了具体实现方便，我们统一以符号“#”作为待分析符号串左右分界符，作为初始状态，先将符号串的左分界符压入符号栈，作为栈底符号。对符号串abbcde分析过程如下所示。步骤符号栈输入符号串动作#abbcde#左界符进栈#abbcde#a进栈#abbcde#b进栈#aAbcde#用A→b归约#aAbcde#b进栈#aAcde#用A→Ab归约#aAcde#c进栈#aAcde#d进栈#aAcBe#用B→d归约#aAcBe#e进栈#S#用S→AcBe归约#S

#接受P:S∷=aAcBeA∷=Ab|bB∷=d当前第121页\共有152页\编于星期六\18点121归约过程描述:

先设立一个符号栈，即将输入串中符号逐个移进栈，当栈顶符号串形成一个句柄时，就进行一次归约，把栈顶句柄那个符号串用相应规则左部的非终结符号来代替，接着再检查在栈顶是否形成新的句柄，若出现新的句柄，那么再进行归约；若没有形成新句柄，则再从输入符号串中移进新符号，……，如此继续到整个输入符号串处理完毕。最终，如栈底为开始符号，则输入符号串是该文法的句子，报告成功，否则，是不合法的符号串，报告错误。当前第122页\共有152页\编于星期六\18点122§2.5文法和语言分类一、文法分类二、文法和自动机三、压缩过文法当前第123页\共有152页\编于星期六\18点123如前所述，文法G形式定义为G=(VN,VT,P,Z)其规则P呈如下形式:U∷=w其中,U∈VN,w∈V*但仅有这种文法,还不足以描述许多语言,例如语言L(G)={anbncn|n≥1}便不能完全用上述形式规则来描述,因此还得定义其它类型的文法。根据对P中规则施加不同限制,Chomsky将文法和语言分为四类。一、文法分类当前第124页\共有152页\编于星期六\18点124一、文法分类1.0型文法2.1型文法3.2型文法4.3型文法当前第125页\共有152页\编于星期六\18点1251.0型文法若在文法G中，P中规则具有如下形式：α∷=β其中α∈V+，且至少含一个非终结符，β∈Ｖ*,则文法G称为0型文法或称短语结构文法，简记为PSG(PhraseStructureGrammar)。由0型文法所描述和定义的语言称为0型语言,记PSL,即L0

当前第126页\共有152页\编于星期六\18点126例2.25设文法G=(VN,VT,P,S),其中VN={S,A,B,C,D,E}VT={a}P:①S∷=ACaB,②Ca∷=aaC③CB∷=DB,④CB∷=E⑤aD∷=Da⑥AD∷=AC⑦aE∷=Ea⑧AE∷=ε这是一个0型文法,它所产生语言为L(G)={ai|i是2的正整次方}即L(G)={aa,aaaa,aaaaaaaa,…}当前第127页\共有152页\编于星期六\18点1272.1型文法

若在文法G中，P中规则具有如下形式：αAβ∷=αwβ其中α,β∈V*,A∈ＶＮ,w∈Ｖ＋,则称文法G为1型文法或上下文有关文法，也称上下文敏感文法，简记为CSG(ContextSensitiveGrammar)。

之所以如此命名，是因为在一个句型中，只有当