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

《编译原理2.3.2-语法树及二义性》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2.3.2语法分析树与二义性上下文无关文法及其语法树用上下文无关文法描述程序语言句型和语法树一个句型对应的不同推导序列文法二义性有关文法的实用限制(文法化简)1.用上下文无关文法描述程序语言E→i

2、E+E

3、E*E

4、(E)<语句>→<条件语句>

5、<赋值语句>

6、<循环语句><赋值语句>→i:=E<条件语句>→if<条件>then<语句>

7、if<条件〉then<语句>else<语句><说明语句>→var<变量列表>:integer<变量列表>→i

8、<变量列表>,i补充例2.句型和语法树(推导树)复习:句型、句子、推导E(E)E+EE*Eiiip31E(E)(E+E)(E*E+E

9、)(i*E+E)(i*i+E)(i*i+i)语法树(推导树)开始符号句型的推导文法G:E→E+E

10、E*E

11、(E)

12、E句型(i*i+i)句型补充例G[S]:S→aASA→SbAA→SSS→aA→ba句型aabbaa补充:定理G为上下文无关文法,α≠ε对于有Sα，当且仅当G有以α为结果的一棵语法树问题:如何证明一个符号串是句型?如何证明一个符号串是句子?*G[S]:S→aASA→SbAA→SSS→aA→ba句型:aabbaa语法树是推导序列的几何描述根据一棵语法树只能得到一个文法的部分产生式一棵语法树的不同构造过程对应了不同的推导序列如果我们坚持用最左(最右)推导,那么一棵

13、语法树就完全等价于一个最左(最右)推导.上下文无关文法句型语法树3.一个句型对应的不同推导序列最左推导最右推导(规范推导)最左归约(规范规约)最右推导的逆过程最右归约最左推导的逆过程补充规范句型:由规范推导所得的句型称为规范句型。4.文法二义性一个句型是否只对应唯一的一棵语法树?G:E→i

14、E+E

15、E*E

16、(E)补充例:句型:i*i+iP31例:句型:(i*i+i)二义Ambiguous(1)什么是文法的二义性(2)先天二义的语言(补充)(3)文法的二义性和语言的二义性(4)二义性的判定(5)二义性的消除(1)什么是文法的二义性p32如果一个文法存在某个句子对应两棵不同的语法

17、树，则说这个文法是二义的(2)先天二义的语言(补充)如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的.(3)文法的二义性和语言的二义性二者是不同的概念例如:两个等价的文法,一个是二义的,一个是非二义的,但产生的语言是相同的二义性的判定如何证明一个文法是二义的？二义性问题不可判定不存在一个算法，它能在有限步骤内，确切判定任给的一个文法是否为二义的我们所能做的事是为无二义性寻找一组充分条件存在性证明只要找到一个句子,该句子对应两个不同的语法树,即证明该文法是二义的.二义性证明举例:证明以下语句是二义的〈语句〉→if〈条件〉then〈语句〉

18、if〈条件〉then

19、〈语句〉else〈语句〉

20、其他语句可以定义其等价的无二义文法p35找到一个句子,该句子对应两个不同的语法树ifc1thenifc2thens1elses2(5).二义性的消除G：E→E+E

21、E*E

22、(E)

23、iG′：E→T

24、E+T,T→F

25、T*F,F→(E)

26、ip33图2.4二义文法在规定了优先级顺序和结合顺序后,推导速度通常快于其等价的非二义文法.5.有关文法的实用限制(文法化简)不含有害规则:P→P每个非终结符P必须有用处存在推导SαPβ(可到达)存在终结符串γ∈VT*,使得Pγ(可终止)*+补充例：文法化简G:(1)S→Be(2)B→Ce(3)B→Af(4)A→Ae(

27、5)A→e(6)C→Cf(7)D→f删除有害规则删除不可到达(7)D→f删除不可终止(6)C→Cf(2)B→CeG:(1)S→Be(3)B→Af(4)A→Ae(5)A→e