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

2.3.2 语法分析树与二义性 上下文无关文法及其语法树 l用上下文无关文法描述程序语言 l句型和语法树 l一个句型对应的不同推导序列 l文法二义性 l有关文法的实用限制 (文法化简) 1.用上下文无关文法描述程序语言 Ei | E+E | E*E | (E) | | i:=E if then | if else var :integer i | , i 补充例补充例 2. 句型和语法树 (推导树) 复习: 句型、句子、推导 E (E) E + E E* E i i i p31p31 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) 句型 补 充 例 GS: SaAS ASbA ASS Sa Aba 句型 aabbaa 补充补充: : 定理 G为上下文无关文法, 对于有S ，当且仅当当且仅当 G有以为结果的一棵语法树 问题 : 如何证明一个符号串是句型? 如何证明一个符号串是句子? * GS:SaAS ASbA ASS Sa Aba 句型:aabbaa l语法树是推导序列的几何描述 l根据一棵语法树只能得到一个文法的部分产 生式 l一棵语法树的不同构造过程对应了不同的推 导序列 l如果我们坚持用最左(最右)推导, 那么一棵 语法树就完全等价于一个最左(最右)推导. 上下文无关上下文无关 文法文法 句型 语 法树 3.一个句型对应的不同推导序列 最左推导 最右推导 (规范推导) 最左归约 (规范规约) 最右推导的逆过程 最右归约 最左推导的逆过程 补充补充 规范句型: 由规范推导所得的句型称为规 范句型。 4. 文法二义性 一个句型是否只对应唯一的一棵语 法树? G: Ei | E+E | E*E | (E) 补充例补充例 : : 句型: i*i+i P31P31例例 : : 句型: (i*i+i) 二义 Ambiguous (1) 什么是文法的二义性 (2) 先天二义的语言 (补充) (3) 文法的二义性和语言的二义性 (4) 二义性的判定 (5) 二义性的消除 (1) 什么是文法的二义性 p32p32 如果一个文法存在某个句子对应两棵不同 的语法树，则说这个文法是二义的 (2) 先天二义的语言 (补充) 如果产生上下文无关语言的每一个 文法都是二义的，则说此语言是先天 二义的 . (3) 文法的二义性和语言的二义性 二者是不同的概念 例如: 两个等价的文法,一个是二义 的,一个是非二义的,但产生的语言是 相同的 (4) 二义性的判定 如何证明一个文法是二义的？ 二义性问题不可判定二义性问题不可判定 不存在一个算法，它能在有 限步骤内，确切判定任给的一个文 法是否为二义的 我们所能做的事是为无二义 性寻找一组充分条件 存在性证明存在性证明 只要找到一个句子, 该句子 对应两个不同的语法树, 即证明该 文法是二义的. 二义性证明 举例 : 证明以下语句是 二义的 语句 if条件then语句 | if条件then语句else语句 | 其他语句 可以定义其等价的无二义文法 p35 找到一个句子, 该句子对应两个不同的语法树 if c1 then if c2 then s1 else s2 (5). 二义性的消除 G：EE+E | E*E | (E) | i G：E T | E+T, T F | T*F, F (E) | i p33 p33 图图2.42.4 二义文法在规定了优先级顺序和结合 顺序后, 推导速度通常快于其等价的 非二义文法. 5.有关文法的实用限制 (文法化简) 不含有害规则: PP 每个非终结符P必须有用处 存在推导 S P (可到达) 存在终结符串VT* , 使得 P (可终止) * + 补充补充 例：例： 文法文法 化简化简 G: (1)SBe (2)BCe (3)BAf (4)AAe (5)Ae