语法分析树
# 语法分析树
# CFG(2 型文法) 分析树
示意图
分析树的特征
- 根节点的标号为文法开始符号
- 内部结点表示对一个产生式
的应用 - 该结点的标号是此产生式左部
,其是一个非终结符 - 该结点的子结点的标号从左到右构成了产生式的右部
- 该结点的标号是此产生式左部
- 叶结点的标号既可以是非终结符,也可以是终结符
- 从左到右排列叶节点得到的符号串称为是这棵树的产出( yield )或边缘(frontier)
# 分析树是推导的图形化表示
由推导可得分析树
- 给定一个推导
,对于推导过程中得到的每一个句型 ,都可以构造出一个边缘为 的分析树
示例
- 对应于此推导过程,相当于每推导一步将树增加一层
# 短语, 直接短语和句柄
定义
- 给定一个句型,其语法分析树中的每一棵子树的边缘称为该句型的一个短语(phrase)
- 如果子树只有父子两代结点,那么这棵子树的边缘称为该句型的一个直接短语(immediate phrase)
- 直接短语一定是某产生式的右部
- 因为分析树的内部结点一定是非终结符
- 但产生式的右部不一定是给定句型的直接短语
- 直接短语一定是某产生式的右部
- 一个句型的最左直接短语称为该句型的句柄
- 此处的最左是指向分析树的最左一棵只有父子两代结点的子树
- 定义为最左是为了自底向上进行语法分析时使用
提示
短语,直接短语和句柄都是针对特定句型的
示例 1
- 此示例的句型是
- 句柄为
示例2
- 句子: 提高人民生活水平
- 短语
- 提高人民生活水平
- 提高
- 人民生活水平
- 人民
- 生活水平
- 生活
- 水平
- 直接短语
- 提高
- 人民
- 生活
- 水平
- 句柄
- 提高
- 短语
# 二义性文法 (Ambiguous Grammar)
- 如果一个文法可以为某个句子生成多棵分析树,则称这个文法是二义性的
if else 语句的二义性
- 二义性可以通过消歧规则来消除
- 如对于
if
语句,其消歧规则为每个else
和最近的尚未匹配的if
匹配则只有下列一种语义
- 如对于
# 二义性文法的判定
对于任意一个上下文无关文法,不存在一个算法,判定它是无二义性的;
但能给出一组充分条件,满足这组充分条件的文法是无二义性的
- 满足,肯定无二义性
- 不满足,也未必就是有二义性的
后续讲述的 LL(1) 文法即是判断 CFG 是否是无二义性的一组充分条件
编辑 (opens new window)