美文网首页
第一章 第5节 CFG 的分析树

第一章 第5节 CFG 的分析树

作者: 化二缺 | 来源:发表于2020-03-11 14:49 被阅读0次
  • 根节点 的标号为 文法开始符号
  • 内部节点 表示对一个产生式 A -> β 的应用 ,该节点的标号是此产生式左部A 该节点的子节点的标号 从左到右构成了产生式的右部β
  • 叶节点的标号既可以是非终结符,也可以是终结符。从左到右排列叶节点得到的符号串称为这个树的产出或者边缘

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

image.png

(句型的)短语

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


image.png

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

例子:


image.png

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

二义性文法

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

编译器不希望出现二义性

image.png

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

二义性文法的判定

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

相关文章

网友评论

      本文标题:第一章 第5节 CFG 的分析树

      本文链接:https://www.haomeiwen.com/subject/doqcjhtx.html