| 前面我们介绍了句型、推导等概念,现在介绍一种描述上下文无关文法的句型推导的直观方法,即语法树,也称推导树。 给定文法G=(VN,VT,P,S),对于G的任何句型都能构造与之关联的语法树(推导树)。 这棵树满足下列4个条件: ① 每个结点都有一个标记,此标记是V的一个符号。 ② 根的标记是S。 ③ 若一结点n至少有一个它自己除外的子孙,并且有标记A,则A肯定在Vn中。 ④ 如果结点n的直接子孙,从左到右的次序是结点n1,n2,…,nk,其标记分别为A1,A2,…,Ak,那么A→A1A2,…,Ak一定是P中的一个产生式。 |