语法分析树(先看例子再看定义)

2023-12-24 07:15:15

语法分析树(先看例子再看定义)

先讲例子

书上讲问题,先讲定义,一顿学术操作,让人云里雾里,然后出例子。其实这样往往让人觉得看书的过程就是放弃的过程。

关于语法分析树,我先从上篇文章的例子讲起。

书接上回,9-5+2的产生式表达为

list -> list + digit | list - digit | digit
digit -> 0|1|2|3|4|5|6|7|8|9

对应于语法分析树,首先把表达式作为写在树的最下面

9 - 5 + 2

然后从底往上构建语法表达树,首先看99digit,因此9可以表示为

 digit
   |
   9

-list->list-digit的中间部分,因此-的语法表达式部分为

     list
   /  |  \
list  -  digit

然后是55digit,且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)

语法分析树的性质

  1. 根节点的标号为文法的开始符号。比如list

  2. 每个叶子结点的标号为一个终结符号或ee为空集。

    比如9-5形成的语法分析树

            list
           /  |  \
          /   |   \
        list  -  digit
         |         |     
       digit       5
         |    
         9   
    

    可以看到叶子结点分别为9,-,5,对于子树

     digit
       |
       9
    

    而言。可以看到digit非终结符作为根节点,9作为叶子结点,那么依据语法分析树的定义A->XYZ可知,YZ都是空集。

  3. 每个内部结点的标号是一个非终结符号

    即,除了叶子结点之外都必须是非终结符

  4. 如果非终结符号A是某个内部结点的标号,并且它的子结点的标号是从左至右分别是X1,X2,X3,...,Xn,,那么必然存在产生式A->X1X2X3...Xn。其中,X1,X2,X3,...,Xn既可以是终结符号,也可以是非终结符号。

    例如

            list
           /  |  \
          /   |   \
        list  -  digit
         |         |     
       digit       5
         |    
         9   
    

    list->list-digit中产生式右部listdigit就是非终结符

    另一个需要注意的方面

    作为一个特殊情况,如果A->e是一个产生式,那么一个标号为A的结点可以只有一个标号为e的子结点。
    

有关术语

对于术语(term),我更喜欢用英文表述,因为有些书翻译成中文的时候词不达意(本人雅思7分,口语单项8分)。

在这里插入图片描述

  • 语法分析树相关的术语
英文中文备注
node结点
label标号list,digit等
root最上面的list
parent父结点叶子结点以外的结点
child子结点父结点的下级
sibling兄弟节点同一父结点下的同级结点。sibling是兄弟姐们的意思
leaf叶子结点没有子结点的结点称为叶子结点
interior node内部结点有一个或多个子节点的结点
descendant后代节点N的后代要么是N本身,要么是N的子结点
ancestor祖先结点M是结点N的后代,那么N是M的祖先
yield结果一颗语法树的叶子结点从左到右构成了树的结果。在上述的例子中就是9-5+2
  • 语法分析

为一个给定的终结符号串构建一颗语法分析树的过程称为对该符号串进行语法分析

文章来源:https://blog.csdn.net/JimFire/article/details/135176414
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。