第一章 第5节 CFG 的分析树

• 根节点 的标号为 文法开始符号
• 内部节点 表示对一个产生式 A -> β 的应用 ，该节点的标号是此产生式左部A 该节点的子节点的标号 从左到右构成了产生式的右部β
• 叶节点的标号既可以是非终结符，也可以是终结符。从左到右排列叶节点得到的符号串称为这个树的产出或者边缘

分析树是推导的图形化表示

image.png

（句型的）短语

给定一个句型，其分析树中的每一课子树的边缘称为该句型的一个短语

image.png

如果子树只有父子两代节点，那么这个子树的标远称为该句型的一个直接短语

例子：

image.png

直接短语一定是某个产生式的右部，一个产生式的右部不一一定是直接短语

二义性文法

如果一个文法可以为某个句子生成多个分析树，则称这个文法是二义性的

编译器不希望出现二义性

image.png

大多数语言都有消歧规则 ：每个else 和最近的尚未匹配的if匹配

二义性文法的判定

对于任意一个上下文无关文法，不存在一个短发判定它是无二义性的；但是能给出一组 充分条件 ，满足这组充分条件的文法是无二义性的