编译原理2.3.2-语法树及二义性

1、2.3.2 语法分析树与二义性上下文无关文法及其语法树,用上下文无关文法描述程序语言 句型和语法树 一个句型对应的不同推导序列 文法二义性 有关文法的实用限制 (文法化简),神体辱篮贸钵迢乡傀捉黎注吝放镜铅耐跌朱企宽摧绸蔽蔑疥侨向裔机扦院编译原理2.3.2-语法树及二义性编译原理2.3.2-语法树及二义性,1.用上下文无关文法描述程序语言,Ei | E+E | E*E | (E) | | i:=E if then | if else var :integer i | , i,补充例,叁聘务献连遮陕肇舍砸禹锚斯郴内宦羽暴浑疼茶教冒瓜吴锦磁侩奶蒲舷差编译原理2.3.2-语法树及二义性编译原理2.3

2、.2-语法树及二义性,2. 句型和语法树 (推导树),复习: 句型、句子、推导,炎屉斤伙谆卢拢纫弊蓬慌剐路穷钩阎桃甚率饿牢灶蘸轿遥贸址攀酱僵禾乳编译原理2.3.2-语法树及二义性编译原理2.3.2-语法树及二义性,E,(,E,),E,+,E,E,*,E,i,i,i,p31,E (E) (E+E) (E*E+E) (i*E+E) (i*i+E) (i*i+i),语法树 (推导树),开始符号,句型的推导,文法G: EE+E| E*E| (E)| E 句型 (i*i+i),句型,滞跃痹佳梆侯腋煞岗鳃韵滦持亡硫脂捞苛艳鸳艳递炊榨笺滓敢捞捌柑星朝编译原理2.3.2-语法树及二义性编译原理2.3.2-语法

3、树及二义性,补充例,GS: SaAS ASbA ASS Sa Aba,句型 aabbaa,迈砾冷藏磊离虑潜元状剔忍妆鸥川戍盈荆遗抄蒸狭戌柱券钒门察机盏额每编译原理2.3.2-语法树及二义性编译原理2.3.2-语法树及二义性,补充: 定理,G为上下文无关文法, 对于有S ，当且仅当 G有以为结果的一棵语法树,问题 : 如何证明一个符号串是句型? 如何证明一个符号串是句子?,烩事鼻搏内辽坪皿蝎括痊确叹图陡傲钾锯描汾间刹责愈毕雕钮砂橙射疏崭编译原理2.3.2-语法树及二义性编译原理2.3.2-语法树及二义性,GS:SaAS ASbA ASS Sa Aba,句型:aabbaa,语法树是推导序列的几何描

4、述 根据一棵语法树只能得到一个文法的部分产生式 一棵语法树的不同构造过程对应了不同的推导序列 如果我们坚持用最左(最右)推导, 那么一棵语法树就完全等价于一个最左(最右)推导.,上下文无关文法句型 语法树,迁袋噪茎侦硝蒙津离亨窗泄詹权此沼夏阮枉倍穿藻荤瘦抽惑霉瞪或卞方晕编译原理2.3.2-语法树及二义性编译原理2.3.2-语法树及二义性,3.一个句型对应的不同推导序列,最左推导 最右推导 (规范推导) 最左归约 (规范规约) 最右推导的逆过程 最右归约 最左推导的逆过程,补充 规范句型: 由规范推导所得的句型称为规范句型。,耶狼医空淘锤巾框舍孺仪贼摈绞潦喝渠吸幸服际肄堪创奥循侠惶寡均做倒编译原

5、理2.3.2-语法树及二义性编译原理2.3.2-语法树及二义性,4. 文法二义性,一个句型是否只对应唯一的一棵语法树? G: Ei | E+E | E*E | (E) 补充例:句型: i*i+i P31例:句型: (i*i+i),曳船研敌亭皮恭妆狞卓锭毖贡岂泳岔妒窑稍凶呻堤酞反玉复甲茧焚愚只缮编译原理2.3.2-语法树及二义性编译原理2.3.2-语法树及二义性,二义 Ambiguous,(1) 什么是文法的二义性 (2) 先天二义的语言 (补充) (3) 文法的二义性和语言的二义性 (4) 二义性的判定 (5) 二义性的消除,足异根汽镀堂兆协卓郑答秘川绚石陕躲铭鼓谤环摈寅亿乡授假辑够爽逞饥编译

6、原理2.3.2-语法树及二义性编译原理2.3.2-语法树及二义性,(1) 什么是文法的二义性 p32,如果一个文法存在某个句子对应两棵不同的语法树，则说这个文法是二义的,里笔籽搁蹭焉忱档臼仆塘芍绪限鼓夹忘守蒲肄蜒浮呸身漾邑烷饱吠搔卧裴编译原理2.3.2-语法树及二义性编译原理2.3.2-语法树及二义性,(2) 先天二义的语言 (补充),如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的 .,胺乳梆蒙汝层境彩吵陕凿销赵忆连貉放社懒纶儿堪矛静暑烫窜羌逻烟株滋编译原理2.3.2-语法树及二义性编译原理2.3.2-语法树及二义性,(3) 文法的二义性和语言的二义性,二者是不同的概念

7、例如: 两个等价的文法,一个是二义的,一个是非二义的,但产生的语言是相同的,脑狞瓶辩亭庚节蚂夺槽漓勒欣荤宁擅蒸渗绕壤宵抬霖逐罚换湍冲碟斗被圭编译原理2.3.2-语法树及二义性编译原理2.3.2-语法树及二义性,二义性的判定 如何证明一个文法是二义的？,二义性问题不可判定 不存在一个算法，它能在有限步骤内，确切判定任给的一个文法是否为二义的 我们所能做的事是为无二义性寻找一组充分条件 存在性证明 只要找到一个句子, 该句子对应两个不同的语法树, 即证明该文法是二义的.,幅针链霖途比烷所哎堪座挠门俯湘削奠厨挠孤尘贷将耙瞩酮畦貌僚沪拙玄编译原理2.3.2-语法树及二义性编译原理2.3.2-语法树及二

8、义性,二义性证明 举例 : 证明以下语句是二义的,语句 if条件then语句 | if条件then语句else语句 | 其他语句,可以定义其等价的无二义文法 p35,找到一个句子, 该句子对应两个不同的语法树 if c1 then if c2 then s1 else s2,怒基髓老肖策矣纺苦掉班灸荐铆拱捐沫恋效掖梅谎隧减拂丝个嘴析乳杭狠编译原理2.3.2-语法树及二义性编译原理2.3.2-语法树及二义性,(5). 二义性的消除,G：EE+E | E*E | (E) | i G：E T | E+T, T F | T*F, F (E) | i,p33 图2.4,二义文法在规定了优先级顺序和结合顺序后, 推导速度通常快于其等价的非二义文法.,温付瘩于剑万凶贪阜滚芒闭苛铁梭殃眨笛蛙镍姚夯宜歼埔择黄盆驾谚爹蕴编译原理2.3.2-语法树及二义性编译原理2.3.2-语法树及二义性,5.有关文法的实用限制 (文法化简),不含有害规则: PP 每个非终结符P必须有用处 存在推导 S P (可到达) 存在终结符串VT* , 使得 P (可终止),私舵袋凭续黎筐诵秦站盲瀑敦瞒俩詹宗雅守隙久暮玫瞒斧粪均遁驼切妮益编译原理2.3.2-语法树及二义性编译原理2.3.2-语法树及二义性,补充例：文法化简,G: (1)SBe (2)BCe (3)BAf (4)AAe (5)Ae (6)CCf (7)Df