语法分析树（先看例子再看定义）

先讲例子

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

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

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

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

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

9 - 5 + 2

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

 digit
   |
   9

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

     list
   /  |  \
list  -  digit

然后是5，5是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）

语法分析树的性质

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

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

   比如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中产生式右部list和digit就是非终结符。

   另一个需要注意的方面

   作为一个特殊情况，如果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

• 语法分析

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