编译原理形式语言基础

（优选）编译原理第章形式语言基础现在是1页\一共有152页\编辑于星期一1一、语言的定义

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

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

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

一、字母表二、符号串三、符号串集合现在是6页\一共有152页\编辑于星期一6一、字母表

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

注意：在一个语言中不能出现字母表以外的符号。现在是7页\一共有152页\编辑于星期一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页\编辑于星期一82、空符号串

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

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

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

x=x1x2x3…xm,y=y1y2y3…yn

则

xy

=x1x2x3…xmy1y2y3…yn

显然εx=x，xε=x

现在是10页\一共有152页\编辑于星期一10（2）符号串的方幂

若x是符号串则x0=ε，x1=x，x2=xx，x3=xxx，…xn=xx…x(n个）如x=abc则x0=ε,x1=abc,x2=abcabcX3=abcabcabc∩现在是11页\一共有152页\编辑于星期一11三、符号串集合举例：字母表V={a,b}，问用V中的符号，可以组成哪些符号串？解：ε,a,b,aa,ab,ba,bb,aaa,…bbb,…1、定义：若集合A中的一切元素都是字母表V上的符号串，则称A为字母表V上的符号串集合现在是12页\一共有152页\编辑于星期一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页\编辑于星期一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页\编辑于星期一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页\编辑于星期一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页\编辑于星期一16作业：

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

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

现在是23页\一共有152页\编辑于星期一23<句子>（句子themanhasabook的推导过程及对应的语法树）现在是24页\一共有152页\编辑于星期一24（句子themanhasabook的推导过程及对应的语法树）<句子><主语><谓语>①<句子>∷=<主语><谓语>现在是25页\一共有152页\编辑于星期一25（句子themanhasabook的推导过程及对应的语法树）<句子><谓语><主语><名词><冠词>①<句子>∷=<主语><谓语>②<主语>∷=<冠词><名词>现在是26页\一共有152页\编辑于星期一26（句子themanhasabook的推导过程及对应的语法树）<句子><主语><谓语>the<名词><冠词>①<句子>∷=<主语><谓语>②<主语>∷=<冠词><名词>③<冠词>∷=the|a现在是27页\一共有152页\编辑于星期一27（句子themanhasabook的推导过程及对应的语法树）<句子><主语><谓语><名词>manthe<冠词>①<句子>∷=<主语><谓语>②<主语>∷=<冠词><名词>③<冠词>∷=the④<名词>∷=man现在是28页\一共有152页\编辑于星期一28（句子themanhasabook的推导过程及对应的语法树）<句子><主语><谓语><名词><动词><宾语>manthe<冠词>①<句子>∷=<主语><谓语>②<主语>∷=<冠词><名词>③<冠词>∷=the④<名词>∷=man⑤<谓语>∷=<动词><宾语>现在是29页\一共有152页\编辑于星期一29（句子themanhasabook的推导过程及对应的语法树）<句子><主语><谓语><名词><动词><宾语>manhasthe<冠词>①<句子>∷=<主语><谓语>②<主语>∷=<冠词><名词>③<冠词>∷=the④⑤<谓语>∷=<动词><宾语>⑥<动词>∷=has现在是30页\一共有152页\编辑于星期一30（句子themanhasabook的推导过程及对应的语法树）<句子><主语><谓语><名词><动词><宾语>manhas<名词><冠词>the<冠词>①<句子>∷=<主语><谓语>②<主语>∷=<冠词><名词>③<冠词>∷=the④⑤<谓语>∷=<动词><宾语>⑥⑦现在是31页\一共有152页\编辑于星期一31（句子themanhasabook的推导过程及对应的语法树）<句子><主语><谓语><名词><动词><宾语>manhas<名词><冠词>athe<冠词>①<句子>∷=<主语><谓语>②<主语>∷=<冠词><名词>③<冠词>∷=the④⑤<谓语>∷=<动词><宾语>⑥⑦③现在是32页\一共有152页\编辑于星期一32（句子themanhasabook的推导过程及对应的语法树）<句子><主语><谓语><名词><动词><宾语>manhas<名词><冠词>abookthe<冠词>①<句子>∷=<主语><谓语>②<主语>∷=<冠词><名词>③<冠词>∷=the④⑤<谓语>∷=<动词><宾语>⑥⑦③④现在是33页\一共有152页\编辑于星期一33（句子themanhasabook的推导过程及对应的语法树）<句子><主语><谓语><名词><动词><宾语>manhas<名词><冠词>abookthe<冠词>现在是34页\一共有152页\编辑于星期一34其中：<句子>称为语法树根带<>和不带<>的都称为语法树的结点一个结点以及向下射出部分称为子树没有向下射出部分的结点称为末端结点现在是35页\一共有152页\编辑于星期一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页\编辑于星期一362.字汇表(符号表)

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

现在是37页\一共有152页\编辑于星期一37（2）分类1）非终结符号

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

2）终结符

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

={<字母>,<数字>,<标识符>}VT={a,b,…,z,A,B,…Z,0,1,…9}现在是39页\一共有152页\编辑于星期一39例如：有产生式:S∷=0S1S∷=01则VN={S}VT={0,1}V={S,0,1}现在是40页\一共有152页\编辑于星期一40四、文法为研究方便，下面给出文法的形式定义定义：文法是规则的有穷集合,形式定义为四元组形式为G=(VN,VT,P,Z)其中：VN是非终结符集合,VT是终结符集合,P代表产生式集,Z∈VN是文法G开始符号,也称识别符号,它至少要在一条产生式左部出现。文法G通常记为G［Z］。现在是41页\一共有152页\编辑于星期一41对于前面英语句子的例子中用7条文法规则来描述英语句子,其文法可表示为G=(VN,VT,P,Z)其中:VN={<句子>，<主语>，<谓语>，<宾语>，<冠词>，<动词>，<名词>}VT={the,a,man,book,dog}P是前述7条规则Z=<句子>现在是42页\一共有152页\编辑于星期一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页\编辑于星期一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页\编辑于星期一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页\编辑于星期一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页\编辑于星期一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页\编辑于星期一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页\编辑于星期一48六、句型和句子定义：设G［Z］是一文法,若符号串x是由识别符Z推导而得,即Z*xx∈V*则称符号串x为该文法G的一个句型。如果一个句型x仅由终结符组成,即Z*xx∈VT*则称句型x为该文法一个句子。例如：在书中的例2.16中,<整数>,<数字><数字>,2<数字>,23等都是文法G[<整数>]的句型,其中仅23是句子。

可见：句子一定是句型，而句型未必是句子。一个正确的源程序是句子。现在是49页\一共有152页\编辑于星期一49七、语言定义：设G［Z］为一文法,由该文法所产生的一切句子的集合称为由该文法所定义的语言,记为L(G［Ｚ］)(或记为L(G)),即L(G)={x|Z*x且x∈VT*}有时我们称这样定义的语言为形式语言，以区别于自然语言。上述公式包含两层意思：语言是句子集合，是VT*一个子集合，即VT中行集合子集。句子必须由该语言文法识别符推导出。现在是50页\一共有152页\编辑于星期一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页\编辑于星期一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页\编辑于星期一52对于通常的程序设计语言其文法为:G［程序］=(VN,VT,P,<程序>)其中VN={<程序>,<说明>,<语句>,…}VT={0,1,…,9,a,…,z,-,(,),…}P={<程序>∷=…,<说明>∷=…,<语句>∷=…,…}L(G)={w|<程序>*w且w∈VT*}由此可知,每一个w就是一个源程序，所谓PASCAL语言也就是所有PASCAL程序的集合。现在是53页\一共有152页\编辑于星期一53作业：P.38习题6、7现在是54页\一共有152页\编辑于星期一54八、递归文法构成一个语言的句子集合可以是有穷的，也可以是无穷的，例如文法G［<句子>］所描述的语言L(G［<句子>］)是有穷的。但文法G［<整数>］所描述的语言L(G［<整数>］)是无穷的，它包含无穷多个句子。

现在是55页\一共有152页\编辑于星期一55例如：文法G(<句子>)包含的下列规则如下：①〈句子〉∷=<主语><谓语>②〈主语〉∷=We|He|I③〈谓语〉∷=ran|ate|sat所描述的语言为：①Weran②Heran③Iran④Weate⑤Heate⑥Iate⑦Wesat⑧Hesat⑨Isat现在是56页\一共有152页\编辑于星期一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页\编辑于星期一57不难发现，两个文法其根本差别在于文法G［<整数>］有形如<数字串>∷=<数字串><数字>的规则。在这个规则中左部和右部皆出现非终结符<数字串>。这种借助于自己来定义自己的规则，即在规则左部和右部具有相同的非终结符规则称为递归规则。

现在是58页\一共有152页\编辑于星期一58八、递归文法

1.

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

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

现在是61页\一共有152页\编辑于星期一61八、递归文法

2.说明

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

现在是62页\一共有152页\编辑于星期一62九、短语和简单短语

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

3.再谈语法树现在是63页\一共有152页\编辑于星期一631.短语和简单短语定义：设G［Z］是一文法，w=xuy是其中一句型，若有Z*xUy,U∈VN且U+u,u∈V+则称u是一个相对于非终结符U、句型w的短语。若Z*xUy且Uu则称u是一个相对于非终结符U、句型w的简单短语。现在是64页\一共有152页\编辑于星期一64例设有文法G［S］=({S,A,B},{a,b},P,S),其中P为S∷=ABA∷=Aa|bBB∷=a|Sb找出句型baSb的全部短语，简单短语.现在是65页\一共有152页\编辑于星期一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页\编辑于星期一662、句柄(柄短语)

定义

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

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

现在是67页\一共有152页\编辑于星期一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页\编辑于星期一683.再谈语法树

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

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

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

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

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

现在是95页\一共有152页\编辑于星期一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页\编辑于星期一96十一、文法二义性1.定义2.文法二义性消除3.几点说明现在是97页\一共有152页\编辑于星期一971.定义

如果一个文法中某个句型对应两棵不同的语法树，则称这个文法是二义性的。也就是说，若一个文法中的某句型对应两个不同的最左推导或最右推导，则这个文法是二义性的。现在是98页\一共有152页\编辑于星期一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页\编辑于星期一99对于不少高级语言中，例如PASCAL语言，在描述条件语句(IF语句)时，使用文法G［C］，其规则P为C∷=ifBthenCC∷=ifBthenCelseCC∷=SB∷=B1|B2S∷=S1|S2其中C是开始符号，B代表布尔表达式，S代表语句，显然，句子ifB1thenifB2thenS1elseS2存在两种不同最右推导。现在是100页\一共有152页\编辑于星期一100①CifBthenC

ifB1thenifB2thenCelseCifB1thenifB2thenS1elseS2

CifBCthenifBCthenelseCSSB1B2S1S2现在是101页\一共有152页\编辑于星期一101②CifBthenCelseCifB1thenCelseS2

ifB1thenifB2thenC

elseS2

ifB1thenifB2thenS1elseS2

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

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

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

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

1.分析基本思想2.分析方法现在是108页\一共有152页\编辑于星期一108一、自顶向下语法分析（导出法）

1.分析基本思想

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

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

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

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

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

现在是117页\一共有152页\编辑于星期一117二、自底向上语法分析1.分析基本思想

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

现在是118页\一共有152页\编辑于星期一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页\编辑于星期一119归约过程描述:

先设立一个符号栈，即将输入串中符号逐个移进栈，当栈顶符号串形成一个句柄时，就进行一次归约，把栈顶句柄那个符号串用相应规则左部的非终结符号来代替，接着再检查在栈顶是否形成新的句柄，若出现新的句柄，那么再进行归约；若没有形成新句柄，则再从输入符号串中移进新符号，……，如此继续到整个输入符号串处理完毕。最终，如栈底为开始符号，则输入符号串是该文法的句子，报告成功，否则，是不合法的符号串，报告错误。现在是120页\一共有152页\编辑于星期一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页\编辑于星期一121归约过程描述:

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

现在是126页\一共有152页\编辑于星期一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页\编辑于星期一1272.1型文法

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

之所以如此命名，是因为在一个句型中，只有当非终结符A的上下文为α和β时，方可用w去替换A。同时产生式右部不得为空(仅仅S→ε例外，但S不得出现在产生式右部)。1型文法相应的语言称1型语言。记CSL,即L1

现在是128页\一共有152页\编辑于星期一1282.1型文法

1型文法还有另一种定义形式：G的每个产生式形为且满足： ||||,V+或||=0则G是1型文法上述两种定义形式是等价的。即任一种形式定义的文法所产生的语言都可由另一种形式定义的文