《上下文无关语言与分析树教学PPT.ppt》由会员分享，可在线阅读，更多相关《上下文无关语言与分析树教学PPT.ppt（63页珍藏版）》请在三一办公上搜索。
1、Yinliang ZhaoXian Jiaotong University2013,上下文无关语言与分析树,2023/3/3,2,非形式注释,上下文无关文法 是描述语言的手段.比FA及RE功能更强，但仍然不能定义所有可能的语言.对于嵌套的结构有用,如,程序语言中的括号.,2023/3/3,3,非形式注释续,基本的概念是使用“变元”表示串集合(即,语言).这些变元一个基于另一个递归定义.递归规则(“产生式”)仅涉及连接操作.一个变元的候选规则允许并起来.,2023/3/3,4,例:定义 0n1n|n 1的CFG,产生式:S 01S 0S1基:01 属于该语言.归纳:若w 属于该语言,那么0w1也
2、属于.,2023/3/3,5,CFG 形式,终结符=要定义的语言的字母表中的符号.变元=非终结符=另一些符号的有穷集合,其中每个代表一个语言.开始符号=这样的变元它的语言就是要定义的语言.形式地,CFG G=(V,T,S),2023/3/3,6,产生式,产生式有下面形式 变元 变元和终结符组成的串.形式地,A,AV,(VT)*惯用法:A,B,C,是变元.a,b,c,是终结符.,X,Y,Z 是终结符或者变元.,w,x,y,z 只是终结符串.,终结符和/或变元组成的串.,2023/3/3,7,例:形式化 CFG,CFG G=(S,0,1,S01,S0S1,S),0n1n|n 1的形式化CFG.终结
3、符=0,1.变元=S.开始符号=S.产生式=S01 S0S1,2023/3/3,8,推导 直觉地,我们推导 CFG定义的语言中的串：从开始符号开始，重复地替代某个变元A为它的产生式的右部.也就是,“A 的产生式”是那些以A为左部的产生式.,2023/3/3,9,推导 形式地,我们说 A 如果 A 是一个产生式.Example:S 01;S 0S1.S 0S1 00S11 000111.,2023/3/3,10,迭代式推导,*意思是“0或多个推导步骤.”基础:*对任意串.归纳:若*且,那么*.,2023/3/3,11,例子:迭代式推导,S 01;S 0S1.S 0S1 00S11 000111.
4、所以S*S;S*0S1;S*00S11;S*000111.,2023/3/3,12,例子:简单算术表达式,CFG G=(V,T,S)V=E,FT=0,1,a,+,(,)S=E:E E+E:E E E:E(E):E a:E 0:E 1E E+E a+E a+EE a+1E a+10,2023/3/3,13,句型,从开始符号推导出来的由变元和/或终结符组成的串称为句型.形式地,是一个句型 当且仅当 S*.,2023/3/3,14,由文法定义的语言,若G 是一个 CFG,那么G的语言L(G),为w|S*w.注:w 必须是终结符串,S 是开始符号.G=(V,T,S)L(G)=w|S*w,wT*.例子:
5、G 有产生式S 和 S 0S1.是一个合法的右部.L(G)=0n1n|n 0.,2023/3/3,15,上下文无关语言,CFG定义的语言context-free language.注意存在不是正则语言的 CFL.,2023/3/3,16,BNF 记号,程序语言的文法通常用BNF(Backus-Naur Form)写成.变元是中的词,e.g.,.终结符多是多字符串加粗或带下划线;e.g.,while or WHILE.,2023/3/3,17,BNF 记号续,符号:=通常用于表示.符号|用于表示“或.”一种有相同左部的产生式的简写.Example:S 0S1|01 是S 0S1 和S 01的简写
6、.,2023/3/3,18,BNF 记号 Kleene 闭包,符号 用于表示“一到多.”Example:=0|1|2|3|4|5|6|7|8|9:=注:跟RE的*不完全相同.Translation:用新变元A替换 并且有产生式 A A|.Example:无符号整数的文法可被替换为:U UD|D D 0|1|2|3|4|5|6|7|8|9,2023/3/3,19,BNF 记号:可选成员,将一到多个符号用中括号括起来 使它们变成可选的.Example:=if then;else Translation:用一个新变元A替换，即使用产生式 A|.Example:if-then-else的文法可以替换为
7、:S iCtSAA;eS|,2023/3/3,20,BNF 记号 成组,使用 将一个符号序列（需要作为一个单位对待）括起来.典型地,它们后跟一个 表示“一到多.”Example:=;,2023/3/3,21,翻译:成组,如果愿意，你可为新建一个变元A.一个产生式为:A.用A 替换.,2023/3/3,22,BNF 记号 Example:成组,L S;S上面的用 L S A A;S替代A 代表;S.然后变成L SB B A|A;SB 代表A(0到多个A).最后变成 L SB B C|C AC|A A;SC 代表A,2023/3/3,23,最左与最右推导,推导允许我们替换串中的任意变元.会导致同一
8、个串有多个推导存在.通过强制最左边变元(或另一选择,最右边变元)被替换,we avoid these“distinctions without a difference.”,2023/3/3,24,最左推导,说wA lm w 若w 是终结符串且A 是一个产生式.另外,*lm 若通过0到多个 lm 步骤使得 变成.,2023/3/3,25,Example:最左推导,平衡括号文法:S SS|(S)|()S lm SS lm(S)S lm()S lm()()因此,S*lm()()S SS S()(S)()()()是一个推导,但不是最左推导.,2023/3/3,26,最右推导,说Aw rm w 若w
9、是一个终结符串且 A 是一个产生式.同样地,*rm 若 通过0到多个rm步骤变成.,2023/3/3,27,Example:最右推导,平衡括号文法S SS|(S)|()S rm SS rm S()rm(S)()rm()()因此,S*rm()()S SS SSS S()S()()S()()()既不是最左推导也不是最右推导.,2023/3/3,28,最左&最右推导,从G推导出串a(ab+10):,E EE FE aE a(E)a(E+E)a(F+E)a(aF+E)a(abF+E)a(ab+E)a(ab+F)a(ab+1F)a(ab+10F)a(ab+10),E*a(ab+10),最左推导:,E E
10、E E(E)E(E+E)E(E+F)E(E+1F)E(E+10F)E(E+10)E(F+10)E(aF+10)E(abF+0)E(ab+10)F(ab+10)aF(ab+10)a(ab+10),最右推导:,G:E E+E|EE|(E)|F F aF|bF|0F|1F|,总是替换最左边变元,总是替换最右边变元,2023/3/3,29,小结,Homeworkp122-123:5.1.1a;5.1.2,形式化推导Backus-Naur 范式最左与最右推导阅读Section 5.1,2023/3/3,30,Parse Trees（分析树/语法树）,分析树 是以具体的CFG的符号做为结点标记的树.叶子:
11、用终结符或标记.内结点:标记为变元.孩子用双亲的产生式的右部标记.根:必须用开始符号标记.,2023/3/3,31,Example:分析树,S SS|(S)|(),2023/3/3,32,分析树的产物,以从左到右的次序将叶子连接起来即,以先根遍历的次序.称为该分析树的产物.Example:这个分析树的产物是()(),S,S,S,S,),(,(,),(,),2023/3/3,33,Example:分析树,产物a0+1b1,G:E E+E|EE|(E)|F F aF|bF|0F|1F|,2023/3/3,34,分析树,最左、最右推导,对任意分析树,有唯一的最左和唯一的最右推导.将证明:定理5.14
12、.若有一个分析树的根标记为A并且产物是 w,则 A*lm w.定理5.12.若A*lm w,则有一个以A为根产物是w的分析树存在.,2023/3/3,35,证明 第一部分,按树高归纳（从根开始的最长路径的长度）.基:高度为 1.树如下,A a1an 必定是一个产生式.因此,A*lm a1an.,2023/3/3,36,第一部分 归纳,因此,A lm X1Xn*lm w1X2Xn*lm w1w2X3Xn*lm*lm w1wn.,假定(1)高度 h的树成立,不妨令树高为h:根据归纳假设,Xi*lm wi.注:若Xi 是一个终结符,那么Xi=wi.,2023/3/3,37,证明:第二部分,给定一个终
13、结符串的最左推导，我们需要证明分析树存在.证明的过程是对推导长度的归纳.,2023/3/3,38,第二部分 基础,若A*lm a1an 是通过一步推导得到,那么一定有如下分析树,2023/3/3,39,第二部分 归纳,假定(2)对于推导长度k 1 步成立,并令 A*lm w 是一个k步推导.第一步 A lm X1Xn.关键点:w 可被划分以使得第一部分从X1推导出,下一部分从X2推导出来,等等以此类推.若Xi 是一个终结符,那么wi=Xi.,2023/3/3,40,归纳(2),即,Xi*lm wi 对于所有 i 而言Xi 是个变元.并且推导花费了小于k个步骤.根据归纳假设,若Xi 是一个变元,
14、那么存在一个分析树的根是Xi而产物是.因此,有如下分析树,2023/3/3,41,分析树与最右推导,思路本质上是对于证明最左推导的镜像.留作思考.,2023/3/3,42,分析树与任意推导,证明你能从最左推导得出一个分析树但不是真正依赖于“最左.”第一步仍然必定是 A X1Xn.w 仍能被推导出来，即第一部分来自X1,下一部分推导自 X2,以此类推.,2023/3/3,43,二义性文法,一个 CFG 是二义的 若该语言中存在一个串是两个或多个分析树的产物.Example:S SS|(S)|()()()()的两个分析树见下面.,2023/3/3,44,Example 续,S,S,S,S,S,S,
15、2023/3/3,45,Example:CFG二义性,一个 CFG 说是ambiguous（二义的）若存在一个串有多于一个最左推导.,LM 推导#1:S AS 0A1S 0A11S 00111S 00111,Example:S AS|A A1|0A1|01,输入串:00111可有两种最左推导过程,LM 推导#2:S AS A1S 0A11S 00111S 00111,2023/3/3,46,Example:CFG二义性,产物a0+1b1,E E+E|EE|(E)|F F aF|bF|0F|1F|,2023/3/3,47,二义性,最左/最右推导,定理5.29如果有两个不同的分析树,根据定理证明中
16、的构造方法必定产生两个不同的最左推导.相反地,根据证明中的另一部分,两个不同的最左推导产生不同的分析树.最右推导类似.,2023/3/3,48,二义性,等.(2),因此,“二义性文法 等价的定义有:语言中有一串有两个不同的最左推导.语言中有一串有两个不同的最右推导.,2023/3/3,49,小结,Homeworkp131:5.2.1,定义最左/最右推导间的关系文法的二义性阅读Section 5.1,2023/3/3,50,二义性是文法的性质,二义性是文法的性质不是语言的性质对于平衡括号语言,有另一个CFG,这个没有二义性.B(RB|R)|(RRB,开始符号,从它推导串平衡括号串.R 生成左括号
17、比右括号多一个的串.,2023/3/3,51,Example:无二义性文法,B(RB|R)|(RR对于给定的平衡的括号的串通过从左到右扫描该串,构造一个唯一最左推导.如果我们需要扩展B,那么使用B(RB 若下一个符号是“(”并且 为结尾.如果我们需要扩展R,使用R)若下一个符号是“)”并且使用R(RR 若下一个符号是“(”.,2023/3/3,52,分析过程,剩余输入串:()(),最左推导步骤:B,下一符号,B(RB|R)|(RR,2023/3/3,53,The Parsing Process,剩余输入串:()(),最左推导步骤:B(RB,下一符号,B(RB|R)|(RR,2023/3/3,5
18、4,The Parsing Process,剩余输入串:)(),最左推导步骤:B(RB(RRB,下一符号,B(RB|R)|(RR,2023/3/3,55,The Parsing Process,剩余输入串:)(),最左推导步骤:B(RB(RRB()RB,下一符号,B(RB|R)|(RR,2023/3/3,56,The Parsing Process,剩余输入串:(),最左推导步骤:B(RB(RRB()RB()B,下一符号,B(RB|R)|(RR,2023/3/3,57,The Parsing Process,剩余输入串:),最左推导步骤:B(RB(RRB()RB()B()(RB,下一符号,B(
19、RB|R)|(RR,2023/3/3,58,The Parsing Process,剩余输入串:,最左推导步骤:B(RB(RRB()RB()B()(RB()()B,下一符号,B(RB|R)|(RR,2023/3/3,59,The Parsing Process,剩余输入串:,最左推导步骤:B(RB(RRB()RB()B()(RB()()B()(),下一符号,B(RB|R)|(RR,2023/3/3,60,固有的二义性,如果对于每一个二义性文法都可以像平衡括号文法那样消除二义性的话多好.不幸的是,肯定有一些CFL是 固有的二义的,意思是该种语言的每一个文法都是二义性的.,2023/3/3,61,
20、Example:固有的二义性,语言0i1j2k|i=j or j=k 是固有的二义的.直觉地,至少一些串形如 0n1n2n 必定是由两个不同分析树产生的,一个基于对0和1的个数进行检测,而另 一个基于对1和2的个数进行检测.,2023/3/3,62,一个可能是二义的文法,S AB|CDA 0A1|01B 2B|2C 0C|0D 1D2|12,A 产生相等个0和1,B 产生任意个数的 2,C 产生任意数目的 0,D 产生相等个1 和2,每个有相等数目的0,1,和2的串都有两个最左推导.如:S AB 01B 012S CD 0D 012,2023/3/3,63,小结,Homeworkp147:5.4.1;5.4.3,阅读Section 5.4,
