CFG分析树
G: ① E -> E + E, ② E -> E * E, ③ E -> -E ④ E -> (E), ⑤ E -> id
根节点的标号为 文法开始符号
内部节点表示对一个产生式A -> β 的应用,该节点的标号就是此产生式的左部A, 该节点的子节点的标号从左到右构成了产生式的右部β
上图中分析树的根节点就是③, ③的左部构成了产生树的根节点, 右部则是树的子节点, 然后依次往下进行分解,就够成了分析树
叶节点的标号既可以是非终结符,又可以是终结符,从左到右排列叶节点得到的符号串就是这棵树的产出 或者边缘
分析树是推导的图形化表示
给定一个推导S => a1 => a2 => …=> an, 对于推导过程中得到的每一句子ai ,都可以构造出一个边缘为ai 的分析树
例:
E => -E => - (E + E) => - (id + E) => -(id + id)
(句型的) 短语
给定一个句型,其分析树的每一颗子树的边缘称为该句型的一个短语(phrase)
如果子树只有父子两代节点, 那么这棵树的边缘称为该句型的一个 直接短语
如上的分析树中
- (E + E) 就是一个短语
(E + E) 也是一个短语
E + E 也是一个短语,并且是 直接短语,因为子树是2层
直接短语一定是某产生式的右部,某产生式的右部, 不一定是直接短语
二义性文法
如果一个文法可以为某个句子生成多颗分析树, 则称这个文法是二义性的
文法:
S -> if E then S if E then S else S other
句型:
if E1 then if E2 then S1 else S2
产生如下分析树, 由于 后边的 else既可以根最前边的if 匹配,又可以跟中间的if匹配,所以就产生了歧义,也就产生了两颗分析树
其实大多数编程语言都规定 else 跟 最近的尚未匹配的 if 来进行匹配,这样的话就会消除歧义,那么第一个分析树就是对的
对于任意一个上下文无关文法, 不存在一个算法,判断他是否有二义性, 只能通过给定的一组充分条件, 满足这个组充分条件的文法就是无二义性.
满足充分条件则是无二义性, 不满足条件也不一定有二义性.
