铜川做网站的公司,济南源聚网络公司,大型网页游戏有哪些,平面广告怎么设计语法分析树#xff08;先看例子再看定义#xff09;
先讲例子
书上讲问题#xff0c;先讲定义#xff0c;一顿学术操作#xff0c;让人云里雾里#xff0c;然后出例子。其实这样往往让人觉得看书的过程就是放弃的过程。
关于语法分析树#xff0c;我先从上篇文章的例…语法分析树先看例子再看定义
先讲例子
书上讲问题先讲定义一顿学术操作让人云里雾里然后出例子。其实这样往往让人觉得看书的过程就是放弃的过程。
关于语法分析树我先从上篇文章的例子讲起。
书接上回9-52的产生式表达为
list - list digit | list - digit | digit
digit - 0|1|2|3|4|5|6|7|8|9对应于语法分析树首先把表达式作为写在树的最下面
9 - 5 2然后从底往上构建语法表达树首先看99是digit因此9可以表示为 digit|9-是list-list-digit的中间部分因此-的语法表达式部分为 list/ | \
list - digit然后是55是digit且5是-后面的字符对应于上面的语法树直接放在digit下面 list/ | \/ | \list | digit| |- 5这个时候可以看到左侧的list没有放任何东西我们试着看看能不能把9对应的语法树部分放上去 list/ | \/ | \list - digit| | digit 5| 9 我们发现在产生式中
list - digit即list可以具有形式如digit。也就是二者是等价关系上述图是可以的。然后一次类推。最后形成图如下。 再看定义
定义
如果非终结符A有一个产生式A-XYZ那么在语法分析树种就可能有一个标号为A的内部结该结点有3个子结点从左到右标号分别为X、Y、Z。如图 即给定一个上下文无关文法则该文法就有一颗语法分析树parse tree
语法分析树的性质 根节点的标号为文法的开始符号。比如list 每个叶子结点的标号为一个终结符号或e。e为空集。 比如9-5形成的语法分析树 list/ | \/ | \list - digit| | digit 5| 9 可以看到叶子结点分别为9,-,5对于子树 digit|9而言。可以看到digit是非终结符作为根节点9作为叶子结点那么依据语法分析树的定义A-XYZ可知YZ都是空集。 每个内部结点的标号是一个非终结符号。 即除了叶子结点之外都必须是非终结符 如果非终结符号A是某个内部结点的标号并且它的子结点的标号是从左至右分别是X1,X2,X3,...,Xn,那么必然存在产生式A-X1X2X3...Xn。其中X1,X2,X3,...,Xn既可以是终结符号也可以是非终结符号。 例如 list/ | \/ | \list - digit| | digit 5| 9 list-list-digit中产生式右部list和digit就是非终结符。 另一个需要注意的方面 作为一个特殊情况如果A-e是一个产生式那么一个标号为A的结点可以只有一个标号为e的子结点。有关术语
对于术语(term)我更喜欢用英文表述因为有些书翻译成中文的时候词不达意本人雅思7分口语单项8分。 语法分析树相关的术语
英文中文备注node结点label标号list,digit等root根最上面的listparent父结点叶子结点以外的结点child子结点父结点的下级sibling兄弟节点同一父结点下的同级结点。sibling是兄弟姐们的意思leaf叶子结点没有子结点的结点称为叶子结点interior node内部结点有一个或多个子节点的结点descendant后代节点N的后代要么是N本身要么是N的子结点ancestor祖先结点M是结点N的后代那么N是M的祖先yield结果一颗语法树的叶子结点从左到右构成了树的结果。在上述的例子中就是9-52
语法分析
为一个给定的终结符号串构建一颗语法分析树的过程称为对该符号串进行语法分析。
