第2章编译原理课程讲解ppt文法和语言讲解课件.ppt

为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能第二章第二章 文法和语言文法和语言 2023/4/201为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能内容提要字母表与符号串文法(定义,推导,句型与句子)语言递归规则与递归文法语法树（短语、简单短语和句柄）语法树与文法的二义性2023/4/202为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.1字母表与符号串字母表符号串符号串及集合的运算2023/4/203为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.1.1字母表字母表是符号的非空有穷集合。例如：1.机器语言字母表：由符号“0”和“1”组成的字母表,=0，1 2.ASCII字符集3.Pascal字母表为：=AZ,az,09,+,-,*,/,:,;，.，,(,),2023/4/204为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.1.2符号串定义：(1)是上的一个符号串。(2)若x是上的符号串，而a是的元素,则xa和ax都是上的符号串。(3)y是上的符号串,当且仅当它由(1)和(2)导出。即：符号串由字母表中的符号所组成的任何有穷序列。2023/4/205为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.1.3 2.1.3 符号串及其集合的运算符号串及其集合的运算1 11.符号串的长度：指符号串x中所含符号的个数，记为|x|。如|xyz|=3，|123+321|=7，而|=02.符号串相等：若x、y是字母表上的两个符号串，当且仅当组成x的各符号与组成y的各符号依次相等时，则符号串x与符号串y相等，记作x=y。如：当x=abbc，y=abbc时，则x=y；而当x=ab，y=ba 时，则xy3.符号串的前缀：指从符号串x的末尾删除0或多个符号后得到的符号串，如u、uni、university都是university的前缀。4.符号串的后缀：指从符号串x的开头删除0或多个符号后得到的符号串，如ty、sity、university都是university的后缀。2023/4/206为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.1.3 2.1.3 符号串及其集合的运算符号串及其集合的运算2 25.符号串的子串：指从符号串x的开头和末尾删除0或多个符号后得到的符号串，如ver是university的子串,符号串的前缀、后缀都是它的子串。6.符号串的连接：若x、y是两个符号串，则xy表示连接，是将符号串y连接在符号串x的后面。若x、y是字母表上的两个符号串，则xy也是字母表上的符号串。例如：x=ab，y=ba，则 xy=abba注意：连接没有交换律，即 xy yx 而对于空串有 x=x=x2023/4/207为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.1.3 2.1.3 符号串及其集合的运算符号串及其集合的运算3 37 7.集集合合的的乘乘积运运算算：令A、B为两个符号串集合，A和B的乘积AB定义为：AB=xy|xA，yB例：A=a，b B=c，d，则AB=ac，ad，bc，bd 对于空集合有有：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/4/208为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.1.3 2.1.3 符号串及其集合的运算符号串及其集合的运算4 49.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,b A=a,b A2 2=aa,ab,ba,bb=aa,ab,ba,bb2023/4/209为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.1.3 2.1.3 符号串及其集合的运算符号串及其集合的运算4 410.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/4/2010为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.2 2.2 文法文法 u文法是描述语言语法结构的形式规则。u用文法描述语言时，要说明语言允许的符号，语法成分，语法结构。例：能够描述句子例：能够描述句子“the the monkey ate the monkey ate the banana”banana”的文法：的文法：该例中，语言允许的符号，语法成分，语法结构是什么？2023/4/2011为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.2.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/4/2012为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能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：theatebananamonkey思考：思考：（1 1）该文法还能描述其它句子吗？）该文法还能描述其它句子吗？（2 2）如果增加句子）如果增加句子“the monkey the monkey ate the appleate the apple”，该如何修改文法，该如何修改文法？2023/4/2013为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能P=P=SaSPQ,SabQ,QPPQ,SaSPQ,SabQ,QPPQ,bPbb,bQbc,cQccbPbb,bQbc,cQcc 例：文法GS：（S,P,Q，a,b,c，P，S）2023/4/2014为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能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/4/2015为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.2.2 2.2.2 文法的文法的EBNFEBNF表示表示EBNF(Extended Backus Normal Form)在书写文法的规则时采用一些特殊的符号，提高文法规则的表达能力。各种元符号的含义如下。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/4/2016为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能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/4/2017为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能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/4/2018为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.3 2.3 推导推导给定文法，可从文法开始符号根据文法规则进行推导产生文法定义的句型或句子。根据文法规则可从从开开始始符符号号出出发发，使用产生式构造出符号串。例如：其中“”表示一步推导,上述推导过程表示经过两步推导，从可推导出。2023/4/2019为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能直接推导的定义(1)是文法GS:(VN,VT,P,S)的产生式，和是(VN VT)*中的任意符号,若有符号串V,W满足：V=，W 则：V是直接产生W 或W是V的直接推导 或W直接归约到V记作记作VW2.3 2.3 推导推导推导：用产生式右部替代左部为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能V=S，W0S1W是否是V的直接推导直接推导：直接推导：S 0S1V=0S1，W=00S11 W是否是V的直接推导直接推导：0S100S11例：文法文法GS:（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 为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能(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为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能例：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 为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.3 2.3 规范推导规范推导 规范推导亦称最右推导，即每步推导只变换最右边的非终结符号。其形式定义为：对直接推导对直接推导xyxy xyxy，如果，如果y y只包含终结符号或为只包含终结符号或为,则该则该推导称为规范推导或最右推导（推导称为规范推导或最右推导（如果只包含终结符号或为如果只包含终结符号或为,则为最左推导则为最左推导），且记作），且记作:x xy yx xy,y,其中其中yVyVt t*。如果推导0 n的每一步都是规范的,则推导0 n称为规范的,记作:0 n+2023/4/2024为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.4 2.4 句型和句子句型和句子 文法GS （1）句型：x是句型 S x,且xV*；（2）句子：x是句子 S x,且xVT*；（3）语言：L（GS）=x|xVT*,S x；+文法GS所产生的所有句子的集合*句子是所有终结符号组成的句型GE：EE+E|E*E|(E)|i|NUM句型：E+EE+E*EE+E*iE+i*i句子：i+ii*ii+i*i(i+i)*i 2023/4/2025为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能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”,其推导过程如下:2第步推导变换的不是最右边非终结符号，故句型“2”不是规范句型。对于句型“3”，其推导过程如下:3 3每一步推导都变换的是最右边非终结符号，故句型“3”是规范句型。2023/4/2026为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.5 2.5 语言语言 定义：文法GS所产生的所有句子的集合L(GS),称为文法GS所定义的语言,即:L(GZ)=x|x VL(GZ)=x|x Vt t*,且且S=x S=x 形式语言理论可以证明以下两点：形式语言理论可以证明以下两点：（1 1）G LG L（G G）；）；（2 2）L(G)G1L(G)G1，G2G2，GnGn；。已知文法，求语言，通过推导；已知语言，构造文法，无形式化方法，更多是凭经验 +2023/4/2027为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.5 2.5 语言语言例：已知文法例：已知文法GZGZ为：为：1)ZaZb1)ZaZb2)Zab2)Zab求该文法确定的语言。求该文法确定的语言。解：从解：从 开始符号开始推导开始符号开始推导,反复用规则反复用规则1 1可得可得:Z ZaZb=aaZb=a2 2ZbZb2 2a an-1n-1ZbZbn-1 n-1 最后用规则最后用规则2 2可得可得:Z Z aZbaZba a2 2ZbZb2 2a an-1n-11Zb1Zbn-1n-1 a an nb bn n所以该文法确定的语言为：所以该文法确定的语言为：L(GZ)=(aL(GZ)=(an nb bn n|n1)|n1)若Z aZb|,如何？2023/4/2028为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能已知文法，求语言，通过推导练习1：GS S bA A aA|aL(GS)=ban|n1练习2：GS S AB A aA|a B bB|bL(GS)=ambn|m,n1练习3：GS S 0A A 1B B 0|0SL(GS)=(010)n|n12023/4/2029为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能P=SaSPQ,SabQ,QPPQ,bPbb,bQbc,cQccP=SaSPQ,SabQ,QPPQ,bPbb,bQbc,cQcc求该文法确定的语言求该文法确定的语言例：文法GS：（S,P,Q，a,b,c，P，S）S SaSPQaSPQ aaSPQPQaaSPQPQa an-1n-1S S（PQPQ）n-1n-1a an-1n-1abQabQ（PQPQ）n-1n-1=a an nbQbQ（PQPQ）n-1n-1=a an nbQPQbQPQ（PQPQ）n-2n-2a an nbPQQbPQQ（PQPQ）n-2n-2=a an nbPQQPQbPQQPQ（PQPQ）n-3n-3a an nbPQPQQbPQPQQ（PQPQ）n-3n-3a an nbPPQQQbPPQQQ（PQPQ）n-3n-3a an nbPbPn-1n-1Q Qn n=a an nbbPbbPn-2n-2Q Qn na an nb bn nQ Qn n=a an nb bn-1n-1bQQbQQn-1n-1a an nb bn-1n-1bcQbcQn-1n-1=a an nb bn ncQcQn-1n-1a an nb bn nccQccQn-2n-2=a an nb bn ncQQcQQn-2n-2a an nb bn nc cn n2023/4/2030为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.5 2.5 语言语言例：已知语言为:L(G)=abna|n1，构造产生该语言的文法。解：根据语言的形式，可构造其文法G为:ZaBaBBb|b还可构造文法G1为:ZaBaBbB|b可见G与G1是两个不同的文法，但都可以描述语言abna|n1。文法和语言之间无一一对应关系。文法唯一确定语言，反之不成立！定义：G和G是两个不同的文法，若 L(G)=L(G),则G和G为等价文法。2023/4/2031为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能例：构造文法GS使得L(GS)=a2n+1|n 0GS：SaSaEEaS例：构造文法GS使得L(GS)=a2n+1bn+1|n 0Ua2nbn+2|n 0由于a2n+1bn+1=a2nabbna2nbn+2=a2nbbbn因此有GS：SaaSb|ab|bb2023/4/2032为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 练习：已知语言构造文法 GS：S AB A aAb|ab BcB|L(GS)=wcwR|w(a|b)*L(GS)=anbnci|n1,i 0 L(GS)=anbncmdm|n 1，m 1 GS：SaSd|aAdA bAc|bcL(GS)=anbmcmdn|n 1,m 1 GS：S aSa|bSb|c GS：S ABA aAb|abB cBd|cd2023/4/2033为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能思考题：设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/4/2034为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.6 2.6 递归规则与递归文法递归规则与递归文法给定文法，就确定了语言。句子的个数是有穷还是无穷取决于文法是否递归。1.递归规则：规则右部有与左部相同的符号 左递归规则：AA 右递归规则：AA 自嵌入递归规则：AA2.递归文法：含有递归规则的文法，为直接递归文法2023/4/2035为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能递归文法递归文法直接递归：若文法中至少包含一条递归规则,则称文法是直接递归的。间接递归：经过几步推导造成文法的递归性，则称为间接递归。例：文法GU：UVx，VUy|v 有推导过程UVxUyx构成递归。递归文法能用有穷的文法刻画无穷的语言。ZaBa BbB|b 2023/4/2036为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能令GS是一文法，是文法G的一个句型。(1)如果有SA 且 A，则称是句型相对于非终结符A的短语。(2)若有A，则称是句型 相对A的简单短语。(3)一个句型的最左简单短语称为该句型的句柄。*+2.7 2.7 短语、简单短语和句柄短语、简单短语和句柄 最左的含义：在句型的推导过程中，会替换一个或多个非终结符，在这些非终结符中可能有多个非终结符产生简单短语，但总有一个非终结符在最左边，该非终结符所对应的简单短语的位置为最左。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.7 2.7 短语、简单短语和句柄短语、简单短语和句柄 对于文法G,确定句型1的短语、简单短语和句柄。解：首先构造句型1的推导过程如下：11)由于 ,而 1,对照定义，子串1是由非终结符号推出的，所以是相对的短语。2)由于 ,而 数字串1,所以子串1是相对的短语。3)由于 ,而1，1是由非终结符号直接推出的，所以子串1是相对的短语,而且是简单短语。在句型1中,只有一个简单短语1,所以是该句型的句柄。*+*+*2023/4/2038为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能例：文法GE：E T|E+TT F|TFF(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+TE+FE+i3T+i3TF+i3 Ti2+i3 Fi2+i3 为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能记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+TE+FE+i3T+i3TF+i3 FF+i3 i1F+i3 为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能Ei1 i2+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+TE+FT+FTF+FT i2+F F i2+F i1 i2+F 为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能ETi2+i3 且Ti1，则i1是句型i1i2+i3的相对于T的短语。*+根据短语定义，根据短语定义，是句型，是句型，SA，A，则则 是句型是句型 相对相对A的短语。的短语。*+i1i2+i3 (=,=i1,=i2+i3)A Ti2+i3 (=,A=T,=i2+i3)A T i1E T|E+TT F|TFF(E)|i+EE+TE+FT+FTF+FT i2+F T i2+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|E+TT F|TFF(E)|i+EE+TT+TTF+TT i2+T F i2+T i1 i2+T 为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能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+TT+TT+FT+i3 为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能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+TE+FE+i3 为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 i1，i2，i3，i1i2和i1i2+i3都是句型i1i2+i3的短语，且i1，i2，i3均为简单短语，其中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+为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.8 2.8 语法树语法树 设G=（VN，VT，P，S）,G的一棵语法树满足如下条件：1.每个结点有一个标记，此标记是VTVN中的符号。2根的标记是S。3如果一个结点是内部结点，其标记A必在VN中。4如果结点有标记A,则其儿子结点从左到右分别有标记X1,X2,Xk，则AX1X2Xk必须是P中的产生式。2023/4/2048为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能例 G=(VN，VT，P，S),其中P:SaASa A SbA SS baASaSbSAaaba2023/4/2049为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 根据推导序列，对每步推导画相应分枝ASaSbSAaaba aSbAS aabAS aabbaS aabbaa aAS S画出语法树(自顶向下）P:SaASa A SbA SSba该推导是最左推导，由其最右推导构造的语法树是否相同？2023/4/2050为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能根据归约序列，对每步归约画相应分枝ASaSbSAaaba aAa aSbAa aSbbaa aabbaa aAS S画出语法树(自底向上）P:SaASa A SbA SSba2023/4/2051为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能1.一个句型推导用一棵树结构图示，反映一个句子语法结构的层次。2.对于一个句子的多种推导（若文法是无二义性的），采用各种推导过程，画出的语法树相同。3.用画语法树的过程解释语法分析过程，用语法树图解语法结构。关于语法树的几点说明2023/4/2052为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.9 2.9 子树与短语子树与短语 语法树的子树是由该树的某个节点（子树的根）连同其所有的后裔构成。SAbSaSbaAaa2023/4/2053为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能用子树解释短语，简单短语，句柄子树与短语一一对应，原则上语法树中有多少棵子树，就有多少个短语。短语：一棵子树的所有叶子节点自左至右排列起来形成一个相对于子树根的短语。简单短语：仅有父子两代的一棵子树，其所有叶子节点自左至右排列起来所形成的符号串。句柄：一个句型的语法树中最左那棵只有父子两代的子树的所有叶子节点的自左至右排列。2023/4/2054为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能例例:根据文法根据文法G，找句子，找句子123的短语、简单短语和句柄。的短语、简单短语和句柄。解：首先画出产生句子123的语法树。无符号整数数字串数字串数字串数字数字数字123|0|1|2|3|4|5|6|7|8|90|1|2|3|4|5|6|7|8|92023/4/2055为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能子树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都是简单短语。而子树5位于其中的最左端，所以短语1还是句柄。2023/4/2056为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能练习：文法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的短语，且i1，i2，i3均为简单短语，其中i1是最左简单短语（句柄）2023/4/2058为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.10 2.10 由树构造推导过程由树构造推导过程 根据已有的语法树，即可从上而下、也可从下到上建立推导。从上而下：从树根开始由上而下逐层地用子节点代替父节点；当一层中有多棵子树根时，原则上可任选一棵；若每次都替换最右边的树根，则构造出的推导是规范推导（最右推导）。由下而上：逐层地修剪子树末端节点来建立推导；当有多棵子树时，原则上可任意修剪一棵；若每次都修剪最左边的子树，则称为“最左归约”或“规范归约”。规范推导（最右推导）与规范归约（最左归约）互为逆过程。2023/4/2059为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能例：G句型10=0 0=0=110=规范推导2023/4/2060为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能01=0=10 0=规范规约与规范推导互为逆过程2023/4/2061为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能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/4/2062为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 EE+E a+E a+E*E a+a*E a+a*a E E*EE+E*E a+E*Ea+a*E a+a*aEE+EE*EaaaEE*E+EEaaa最左推导2023/4/2063为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 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/4/2064为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.11 2.11 文法的二义性文法的二义性例2.10 IF语句文法如下：IFTHEN|IFTHENELSE|说明该文法是二义性文法。解：假设有一个IF语句嵌套的句型为：IFTHEN IFTHENELSE 根据文法可构造两棵语法树：2023/4/2065为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.11 2.11 文法的二义性文法的二义性语句语句 布尔表达式布尔表达式 IF THEN 语句语句 布尔表达式布尔表达式 IF THEN 语句语句 ELSE 语句语句 语句语句 布尔表达式布尔表达式