第2章文法和语言ppt课件.ppt

《第2章文法和语言ppt课件.ppt》由会员分享，可在线阅读，更多相关《第2章文法和语言ppt课件.ppt（82页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值第二章第二章 文法和语言文法和语言 2023/3/221资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值内容提要字母表与符号串文法(定义,推导,句型与句子)语言递归规则与递归文法语法树（短语、简单短语和句柄）语法树与文法的二义性2023/3/222资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值2.1 字母表与符号串字母表

2、符号串符号串及集合的运算2023/3/223资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值2.1.1 字母表字母表是符号的非空有穷集合。例如：1.机器语言字母表：由符号“0”和“1”组成的字母表,=0，1 2.ASCII字符集3.Pascal字母表为：=AZ,az,09,+,-,*,/,:,;，.，,(,),2023/3/224资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值2.1.2 符号串定义：(1)是上的一个符号串。(2)若x是上的符号

3、串，而a是的元素,则xa是上的符号串。(3)y是上的符号串,当且仅当它由(1)和(2)导出。即：符号串由字母表中的符号所组成的任何有穷序列。2023/3/225资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值2.1.3 2.1.3 符号串及其集合的运算符号串及其集合的运算1.符号串的长度：指符号串x中所含符号的个数，记为|x|。如|xyz|=3，|123+321|=7，而|=02.符号串相等：若x、y是字母表上的两个符号串，当且仅当组成x的各符号与组成y的各符号依次相等时，则符号串x与符号串y相等，记作x=y。如：当x

4、=abbc，y=abbc时，则x=y；而当x=ab，y=ba 时，则xy3.符号串的前缀：指从符号串x的末尾删除0或多个符号后得到的符号串，如u、uni、university都是university的前缀。4.符号串的后缀：指从符号串x的开头删除0或多个符号后得到的符号串，如ty、sity、university都是university的后缀。2023/3/226资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值5.符号串的子串：指从符号串x的开头和末尾删除0或多个符号后得到的符号串，如ver是university的子串,

5、符号串的前缀、后缀都是它的子串。6.符号串的连接：若x、y是两个符号串，则xy表示连接，是将符号串y连接在符号串x的后面。若x、y是字母表上的两个符号串，则xy也是字母表上的符号串。例如：x=ab，y=ba，则 xy=abba注意：连接没有交换律，即 xy yx 而对于空串有 x=x=x2023/3/227资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值7 7.集集合合的的乘乘积运运算算：令A、B为两个符号串集合，A和B的乘积AB定义为：AB=xy|xA，yB例如：A=a，b B=c，d，则AB=ac，ad，bc，bd

6、 对于空集合有有：A=A=A8.8.符号串的符号串的幂运算：运算：若x是符号串，则x的幂运算定义为：x0=,x1=x,x2=xx,，xn=xxx=xx n-1=xn-1x,其中n0例如：x=abc,x0=,x1=abc,x2=abcabc,2023/3/228资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值9.9.集合的集合的幂运算：运算：设A为符号串集合，则A的幂运算定义为：A0=A1=A A2=AA An=AAA=AAn-1=An-1A，其中 n0例如：例如：A=aA=a，bb，则则 A A0 0=A=A1 1=a

7、,b A=a,b A2 2=aa,ab,ba,bb=aa,ab,ba,bb2023/3/229资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值10.10.集集合合的的正正闭闭包包和和集集合合的的闭闭包包：设A为一个集合，则集合A的正闭包用A+表示，定义为：A A+=A=A1 1AA2 2 A An n集合集合A A的闭包用的闭包用A*表示，定义为：A A*=A=A0 0AA+例如：A=a，b，则A+=a,b,aa,ab,ba,bb,aaa,aab,A*=,a,b,aa,ab,ba,bb,aaa,aab,2023/3/2

8、210资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值2.2 2.2 文法文法 u文法是描述语言语法结构的形式规则。u文法需要说明语言的语法成分，句子中的符号以及语法结构。例：能够描述句子例：能够描述句子“the monkey ate the monkey ate the banana”the banana”的文法：的文法：该例中语法成分，句子中的符号，语法结构是什么？2023/3/2211资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值2.2

9、.1 2.2.1 文法形式定义文法形式定义文法的形式定义：文法的形式定义：文法可表示为一个四元组 G=G=（V Vn n ，V Vt t，P P，Z Z）Vn:非空有穷集合,其元素为非终结符号。V Vt t:非空有穷集合,其元素为终结符号且VtVn=,VtVn是该文法的字母表。P P：非空有穷集合,其元素为产生式或规则。产生式的形式为:或:=；是产生式左部且不能为空,是产生式右部,并且、（VtVn)*,“”或“:=”含义相同，表示“定义为”或“由组成”。Z Z：Vn中一个特殊的非终结符号，称为文法的识别符号或开始符号。必须至少在某个产生式的左部出现一次。2023/3/2212资金是运动的价值，

10、资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值2.2.1 2.2.1 文法形式定义文法形式定义按文法形式定义表示“the monkey ate the bananathe monkey ate the banana”文法。解：根据文法的形式定义，文法G1=（Vn，Vt，P，Z）非终结符号集合:Vn=句子，主语，谓语，冠词，名词，动词，直接宾语终结符号集合:Vt=the，ate，banana，monkey 产生式集合P由下面8条规则组成:识别符号Z：theatebananamonkey2023/3/2213资金是运动的价值，资金的价值是

11、随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值2.2.1 2.2.1 文法形式定义文法形式定义上下文无关文法：上下文无关文法：产生式左部是一个非终结符，右部是由非终结符和终结符组成的有穷符号串。可以简化表示。例：有如下简化表示文法，只给出规则集，写出该文法的终结符号集合、非终结符号集合和识别符号。1.2.3.4.05.16.27.38.49.510.611.712.813.9解：非终结符号集合：Vn=,终结符号集合：Vt=0,1,2,3,4,5,6,7,8,9识别符号Z：2023/3/2214资金是运动的价值，资金的价值是随时间变化而变化的，是时

12、间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值2.2.2 2.2.2 文法的文法的EBNFEBNF表示表示 EBNF在书写文法的规则时采用一些特殊的符号，提高文法规则的表达能力。各种元符号的含义如下。1.1.元符号元符号“|”|”：表示“或”，对于具有相同左部的那些规则,如1 1、2 2、n n，可缩写为:1 1|2 2|n n上例文法的13条规则可缩写成：|0|1|2|3|4|5|6|7|8|90|1|2|3|4|5|6|7|8|9 1.2.3.4.05.16.27.38.49.510.611.712.813.92023/3/2215资金是运动的价值，资金的价值是随时

13、间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值2.2.2 2.2.2 文法的文法的EBNFEBNF表示表示2.2.元符号元符号“”：用于括起由中文字组成的非终结符号或由多个字母组成的符号。如、等。3.3.元符号元符号“”和和“”：表示可重复连接连接，tnm表示符号串t可重复连接连接n到m次，而，而t表示符号串t可重复连接连接0到无穷次。例如，1 13 3 与|相同 EE+T|T EE+T|T 与 ET+TET+T相同而字母打头、后面可跟数字或字母的不超过8个字符的标识符文法则为：|0 07 72023/3/2216资金是运动的价值，资金的价值是随时间

14、变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值2.2.22.2.2文法的文法的EBNFEBNF表示表示4.4.元符号元符号“”和和“”：表示括起的内容可选。例如：IF THEN IF THEN ELSE 可写成：IFIF IF THEN THEN ELSE ELSE 5.5.元元符符号号“（”和和“）”：表示括号内的成分优先。常用于在规则中提取公因子。例如，Uxy|xw|xzUxy|xw|xz 可写成：UxUx（y|w|zy|w|z）2023/3/2217资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分

15、资金就是原有资金的时间价值2.3 2.3 推导推导 给定文法，可从文法的开始符号根据文法规则进行推导产生文法定义的句型或句子。根据文法规则可从从开开始始符符号号出出发发，使用产生式构造出符号串。例如：其中“”表示一步推导,上述推导过程表示经过两步推导，从可推导出。2023/3/2218资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值直接推导的定义(1)是文法G=(VN,VT,P,S)的规则，和是(VN VT)*中的任意符号,若有符号串V,W满足：V=，W 则说V是直接产生W 或W是V的直接推导 或W直接归约到V记作记作

16、VW2.3 2.3 推导推导推导：用产生式右部替代左部资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值V=S，W0S1W是否是V的直接推导直接推导：直接推导：S 0S1V=0S1，W=00S11 W是否是V的直接推导直接推导：0S100S11例：文法文法G=（VN,VT,P，S）,其中其中VN=S，VT=0，1，P=S0S1，S01 V0S1，W=0011W是否是V的直接推导直接推导：0S1 0011使用规则：S 01 0，1，S，01 规则：S 0S1 ，S，0S1 规则：S 0S1 0，1S，0S1 资金是运动的价

17、值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值(3)若有 VW或 V=W，则记作VW 例：V0S1 00S11 000S111 00001111 W记作：0S1 00001111 0S1 00001111+*(2)若存在直接推导的序列：V=W0 W W1 1 W W2 2 W Wn n W(n0)W(n0)则则 称称V V推导推导W(W(或或W W归约到归约到V)V)，记作，记作V V W W *相同文文法法G=(VN，VT，P，S)，其其 中中 VN=S，VT=0，1，P=S0S1，S01资金是运动的价值，资金的价值是随时间变化

18、而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值例：G=(S,A,a,b,P,S)，其中P为：S aASA SbAA SSS aA ba请构造aabbaa的推导过程?（1）每次替换最右边非终结符?SaAS aAa aSbAa aSbbaa aabbaa?（2）每次替换最左边非终结符?SaAS aSbASaabASaabbaSaabbaa?（3）无固定的推导方向）无固定的推导方向?SaAS aSbASaSbAaaabAaaabbaa 每步推导只能替换一个非终结符资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资

19、金就是原有资金的时间价值练习：文法GS=(S,A,B,a,b,c,d,e,S aAcBe A b A Ab B d,S）构符号串abbcde的推导过程 S aAcBe aAbcBe abbcBe abbcdeS aAcBe aAcde aAbcde abbcde2023/3/2223资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值2.3 2.3 规范推导规范推导 规范推导：亦称最右推导，即每步推导只变换最右边的非终结符号。其形式定义为：对直接推导对直接推导xyxy xyxy，如果，如果y y只包含终结符号或为空符号串只

20、包含终结符号或为空符号串,则该推导称为规范推导或最右推导（则该推导称为规范推导或最右推导（如果只包含终结符号或如果只包含终结符号或为空符号串为空符号串,则为最左推导则为最左推导），记作），记作:x xy yx xy,y,其中其中yVyVt t*。如果推导0n的每一步都是规范的,则推导0n称为规范的,记作:0 n+2023/3/2224资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值2.4 2.4 句型和句子句型和句子 文法GS （1）句型：x是句型 S x,且xV*；（2）句子：x是句子 S x,且xVT*；（3）语言

21、：L（GS）=x|xVT*,S x；+文法GS所产生的所有句子的集合*句子是所有终结符号组成的句型GE：EE+E|E*E|(E)|i 句型：E+EE+E*EE+E*iE+i*i句子：i+ii*ii+i*i(i+i)*i 2023/3/2225资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值2.4 2.4 句型和句子句型和句子规范句型：用规范推导产生的句型。每个句子都有一个规范推导,但并非每个句型都有规范推导。例如，对文法：；|；0|1|2|3|4|5|6|7|8|9 0|1|2|3|4|5|6|7|8|9 有句型“2”

22、,其推导过程如下:2第步推导变换的不是最右边非终结符号，故句型“2”不是规范句型。对于句型“3”，其推导过程如下:=3=3每一步推导都变换的是最右边非终结符号，故句型“3”是规范句型。Why?2023/3/2226资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值2.5 2.5 语言语言 定义：文法GZ所产生的所有句子的集合L(GZ),称为文法GZ所定义的语言,即:L(GZ)=x|x VL(GZ)=x|x Vt t*,且且Z=x Z=x 形式语言理论可以证明以下两点：形式语言理论可以证明以下两点：（1 1）G LG L（

23、G G）；）；（2 2）L(G)G1L(G)G1，G2G2，GnGn；。已知文法，求语言，通过推导；已知语言，构造文法，无形式化方法，更多是凭经验 +2023/3/2227资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值2.5 2.5 语言语言例例:已知文法已知文法GZGZ为：为：1)ZaZb1)ZaZb2)Zab2)Zab求该文法确定的语言。求该文法确定的语言。解：从识别符号开始推导解：从识别符号开始推导,反复用规则反复用规则1 1可得可得:Z=aZb=aZ=aZb=a2 2ZbZb2 2=a=an-1n-1ZbZb

24、n-1 n-1 最后用规则最后用规则2 2可得可得:Z=aZb=aZ=aZb=a2 2ZbZb2 2=a=an-1n-11Zb1Zbn-1n-1=a=an nb bn n所以该文法确定的语言为：所以该文法确定的语言为：L(GZ)=(aL(GZ)=(an nb bn n|n1)|n1)若Z aZb|,如何？2023/3/2228资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值已知文法，求语言，通过推导练习1：GS S bA A aA|aL(GS)=ban|n1练习2：GS S AB A aA|a B bB|bL(GS)=

25、ambn|m,n1练习3：GS S 0A A 1B B 0|0SL(GS)=(010)n|n12023/3/2229资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值2.5 2.5 语言语言例2.5，已知语言为:L(G)=abna|n1，构造产生该语言的文法。解：根据语言的形式，可构造其文法G为:ZaBaBBb|b还可构造文法G1为:ZaBaBbB|b可见G与G1是两个不同的文法，但都可以描述语言abna|n1。文法和语言之间无一一对应关系。文法唯一确定语言，反之不成立！定义：G和G是两个不同的文法，若 L(G)=L(G

26、),则G和G为等价文法。2023/3/2230资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 练习：已知语言构造文法 GS：S AB A aAb|ab BcB|LG(S)=wcwR|w(a|b)*LG(S)=anbnci|n1,i 0 LG(S)=anbncmdm|n 1，m 1 GS：SaSd|aAdA bAc|bcLG(S)=anbmcmdn|n 1,m 1 GS：S aSa|bSb|c GS：S ABA aAb|abB cBd|cd2023/3/2231资金是运动的价值，资金的价值是随时间变化而变化的，是时间的

27、函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值思考题：设G=(VT=a,b,VN=S,A,B,P,S)P由下列产生式组成（1）SaB|bA （2）Aa|aS|bAA （3）Bb|bS|aBB L(G)=w|wa,b+,且w中有相同个数的a和b。用归纳法证明下面结论（对w的长度）：(1)S w,当且仅当w中含有相同个数的a和b。(2)A w,当且仅当w中a的个数比b的个数多一个。(3)B w,当且仅当w中b的个数比a的个数多一个。*2023/3/2232资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值

28、2.6 2.6 递归规则与递归文法递归规则与递归文法给定文法，就确定了语言。句子的个数是有穷还是无穷取决于文法是否递归。1.递归规则：规则右部有与左部相同的符号 左递归规则：AA 右递归规则：AA 自嵌入递归规则：AA2.递归文法：含有递归规则的文法，为直接递归文法2023/3/2233资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值递归文法递归文法直接递归：若文法中至少包含一条递归规则,则称文法是直接递归的。间接递归：经过几步推导造成文法的递归性，则称为间接递归。例如，有文法为:UVx，VUy|v 有推导过程U=Vx

29、=Uyx构成递归。递归文法能用有穷的文法刻画无穷的语言。ZaBaBbB|b 2023/3/2234资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值令GS是一文法，是文法G的一个句型。(1)如果有SA 且 A，则称是句型相对于非终结符A的短语。(2)若有A，则称是句型 相对A的简单短语。(3)一个句型的最左简单短语称为该句型的句柄。*+2.7 2.7 短语、简单短语和句柄短语、简单短语和句柄 资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值2.7

30、 2.7 短语、简单短语和句柄短语、简单短语和句柄 对于文法G,确定句型1的短语、简单短语和句柄。解：首先构造句型1的推导过程如下：11)由于 ,而 1,对照定义，子串1是由非终结符号推出的，所以是相对的短语。2)由于 ,而 数字串1,所以子串1是相对的短语。3)由于 ,而1，且1是由非终结符号直接推出的，所以子串1是相对的短语,而且是简单短语。在句型1中,只有一个简单短语1,所以是该句型的句柄。*+*+*2023/3/2236资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值例：文法GE：E T|E+TT F|TFF(

31、E)|i求句型iii的短语，简单短语和句柄。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值记ii+i 为i1i2+i3j EFi2+i3 且F i1，i1是句型i1i2+i3的相对非终结符F的短语和简单短语，而且是句柄。*i1 i2+i3 (=,=i1,=i2+i3)A Fi2+i3 (=,A=F,=i2+i3)A F i1根据短语定义，是句型，SA，A，则是句型 相对A的短语。*+E T|E+TT F|TFF(E)|iEE+T T+T TF+T FF+T FF+F FF+i3 Fi2+i3 i1i2+i3 资金是运

32、动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值记ii+i 为i1i2+i3kEi1F+i3 且Fi2，i2是句型i1i2+i3的相对非终结符F的短语和简单短语。*i1 i2+i3 (=i1,=i2,=+i3)A i1F+i3 (=i1,A=F,=+i3)A F i2E T|E+TT F|TFF(E)|iEE+T T+T TF+T FF+T FF+F FF+i3 i1F+i3 i1i2+i3资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值Ei1 i2+

33、F且Fi3，i3是句型i1i2+i3的相对非终结符F的短语和简单短语。i1i2+i3 (=i1i2+,=i3,=)A i1i2+F (=i1i2+,A=F,=)A F i3E T|E+TT F|TFF(E)|iEE+T T+T TF+T FF+T FF+F Fi2+F i1i2+F i1i2+i3资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值ETi2+i3 且Ti1，i1是句型i1i2+i3的相对于T的短语。*+根据短语定义，根据短语定义，是句型，是句型，SA，A，则则 是句型是句型 相对相对A的短语。的短语。*+i

34、1i2+i3 (=,=i1,=i2+i3)A Ti2+i3 (=,A=T,=i2+i3)A T i1E T|E+TT F|TFF(E)|i+EE+T T+T TF+T TF+F Ti2+F Ti2+i3Fi2+i3 i1i2+i3资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值E i1 i2+T 且Ti3，i3是句型i1i2+i3的相对于T的短语。*+根据短语定义，是句型，SA，A，则是句型 相对A的短语。*+i1i2+i3 (=i1i2+,=i3,=)A i1 i2+T (=i1i2+,A=T,=)A T i3E T

35、|E+TT F|TFF(E)|i+EE+T T+T TF+T FF+T i1F+T i1i2+T i1i2+F i1i2+i3资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值ET+i3 且T i1i2，i1 i2是句型i1i2+i3相对于T的短语。*i1i2+i3 (=,=i1i2,=+i3)A T+i3 (=,A=T,=+i3)A T i1i2E T|E+TT F|TFF(E)|i+EE+T T+T T+F T+i3 TF+i3 FF+i3 i1F+i3 i1i2+i3 资金是运动的价值，资金的价值是随时间变化而变化

36、的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值EE+i3 且 Ei1i2，则i1i2是句型i1i2+i3相对于E的短语。*i1i2+i3 (=,=i1i2,=+i3)A E+i3 (=,A=E,=+i3)A E i1i2E T|E+TT F|TFF(E)|i+EE+T E+F E+i3 T+i3 TF+i3 FF+i3 i1F+i3 i1i2+i3 资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 i1，i2，i3，i1i2和i1i2+i3都是句型i1i2+i3的短语，且i1，i2，i3

37、均为简单短语，其中i1是最左简单短语（句柄）问题：如何有效的找出所有短语？EE 且 Ei1i2+i3，i1i2+i3是句型i1i2+i3相对于E的短语。*+i1i2+i3 (=,=i1i2+i3,=)AE (=,A=E,=)A E i1i2+i3E T|E+TT F|TFF(E)|i+EE+T E+F E+i3 T+i3 TF+i3 FF+i3 i1F+i3 i1i2+i3 资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值练习：G=(S,A,a,b,P,S)，其中P为：S aASA SbAA SSS aA baSaAS

38、 aAa aSbAa aSbbaa aabbaa求句子的短语、简单短语，句柄。2023/3/2246资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值2.8 2.8 语法树语法树 设G=（VN，VT，P，S）,G的一棵语法树满足如下条件：1.每个结点有一个标记，此标记是VTVN中的符号。2根的标记是S。3如果一个结点是内部结点，其标记A必在VN中。4如果编号为n的结点有标记A,结点n1,n2,nk是点n的从左到右的儿子并分别有标记X1,X2,Xk，则AX1X2Xk必须是P中的产生式2023/3/2247资金是运动的价值，

39、资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值例 G=(VN，VT，P，S),其中P:SaASa A SbA SS ba3124657891011SaASSbAaaba2023/3/2248资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 根据推导序列，对每步推导画相应分枝ASaSbSAaaba aSbAS aabAS aabbaS aabbaa aAS S画出语法树(自顶向下）P:SaASa A SbA SSba该推导是最左推导，由其最右推导构造的语法树是否

40、相同？2023/3/2249资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值根据归约序列，对每步归约画相应分枝ASaSbSAaaba aAa aSbAa aSbbaa aabbaa aAS S画出语法树(自底向上）P:SaASa A SbA SSba2023/3/2250资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值1.一个句型推导用一棵树结构图示，反映一个句子语法结构的层次。2.对于一个句子的多种推导（若文法是无二义性的），采用各种推导过程

41、，画出的语法树相同。3.用画语法树的过程解释语法分析过程，用语法树图解语法结构。关于语法树的几点说明2023/3/2251资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值2.9 2.9 子树与短语子树与短语 语法树的子树是由该树的某个节点（子树的根）连同其所有的后裔构成。SAbSaSbaAaa2023/3/2252资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值用子树解释短语，简单短语，句柄子树与短语一一对应，原则上语法树中有多少棵子树，就有多

42、少个短语。短语：一棵子树的所有叶子节点自左至右排列起来形成一个相对于子树根的短语。简单短语：仅有父子两代的一棵子树，其所有叶子节点自左至右排列起来所形成的符号串。句柄：一个句型的语法树中最左那棵只有父子两代的子树的所有叶子节点的自左至右排列。2023/3/2253资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值例例2.8根据文法根据文法G，找句子，找句子123的短语、简单短语和句柄。的短语、简单短语和句柄。解：首先画出产生句子123的语法树。无符号整数数字串数字串数字串数字数字数字123|0|1|2|3|4|5|6|7

43、|8|90|1|2|3|4|5|6|7|8|92023/3/2254资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值子树1：树根，叶节点1、2、3，短语为123子树2：树根，叶节点1、2、3，短语为123子树3：树根，叶节点1、2，短语为12子树4：树根，叶节点1，短语为1子树5：树根，叶节点1，短语为1，且为简单短语、句柄子树6：树根，叶节点2，短语为2，且为简单短语子树7：树根，叶节点3，短语为3，且为简单短语7个子树中，只有子树5、6、7的根节点与末端节点都是父子关系，所以这几个子树的末端节点形成的短语1、2、3

44、都是简单短语。而子树5位于其中的最左端，所以短语1还是句柄。2023/3/2255资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值练习：文法GE：E T|E+TT F|TFF(E)|i求句型iii的短语，简单短语和句柄。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值求句型iii的短语,简单短语和句柄。E T|E+TT F|TFF(E)|i+EETFTFTi3i2Fi1 i1，i2，i3，i1i2和i1i2+i3都是句型i1i2+i3的短语，且

45、i1，i2，i3均为简单短语，其中i1是最左简单短语（句柄）2023/3/2257资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值2.10 2.10 由树构造推导过程由树构造推导过程 根据已有的语法树，即可从上而下、也可从下到上建立推导。从上而下：从树根开始由上而下逐层地用子节点代替父节点；当一层中有多棵子树根时，原则上可任选一棵；若每次都替换最右边的树根，则构造出的推导是规范推导（最右推导）。由下而上：逐层地修剪子树末端节点来建立推导；当有多棵子树时，原则上可任意修剪一棵；若每次都修剪最左边的子树，则称为“最左归约”

46、或“规范归约”。规范推导（最右推导）与规范归约（最左归约）互为逆过程。2023/3/2258资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值例：G句型10=0 0=0=110=规范推导2023/3/2259资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值01=0=10 0=规范规约与规范推导互为逆过程2023/3/2260资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值

47、1、描述一个句子的文法不是唯一的；2、对于一个句子的分析应是唯一的。考虑下面的表达式文法 GE,其产生式如下：EE+EE*E(E)a对于句子a+a*a,有如下两个最左推导：EE+E a+E a+E*E a+a*E a+a*a E E*E E+E*E a+E*E a+a*E a+a*a 如果对文法的某个句子或句型，存在两棵不同的语法树，那么这个句子或句型是二义性的，则该文法是二义性文法。2.11文法的二义性2023/3/2261资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 EE+E a+E a+E*E a+a*E a

48、+a*a E E*EE+E*E a+E*Ea+a*E a+a*aEE+EE*EaaaEE*E+EEaaa最左推导2023/3/2262资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 EE+E E+E*E E+E*a E+a*a a+a*a E E*EE*a E+E*aE+a*a a+a*aEE+EE*EaaaEE*E+EEaaa最右推导2023/3/2263资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值2.11 2.11 文法的二义性文法的

49、二义性例2.10 IF语句文法如下：IFTHEN|IFTHENELSE|说明该文法是二义性文法。解：假设有一个IF语句嵌套的句型为：IFTHEN IFTHENELSE 根据文法可构造两棵语法树：2023/3/2264资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值2.11 2.11 文法的二义性文法的二义性语句语句 布尔表达式布尔表达式 IF THEN 语句语句 布尔表达式布尔表达式 IF THEN 语句语句 ELSE 语句语句 语句语句 布尔表达式布尔表达式 IF THEN 语句语句 布尔表达式布尔表达式 IF TH

50、EN 语句语句 ELSE 语句语句 图2.3(a)IF语句语法树1 图2.3(b)IF语句语法树2 由于这两棵语法树不同，该文法是二义性文法。图2.3(a)IF语句的语法树意味着ELSE和第2个IF配对（就近配对），而图2.3(b)IF语句的语法树表示ELSE和第1个IF配对。2023/3/2265资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值可以采用两种途径来解决文法的二义性问题 不改变文法中原有的规则，仅加进一些语法的非形式规定。例如：规定“*”运算优先级高于“+”运算，且服从左结合改写文法，把排除二义性的规则合