给定文法G=(Vn,Vt,P,S),对于G的任何句型都能构造与之关联的语法树(推导树).树中的每一个节点都有一个标记,此标记是V= Vn∪Vt中的一个符号。语法树是句子结构的图形表示,它代表了句子的推导结果,有利于理解句子语法结构的层次。简单说,语法树就是按照某一规则进行推导时所形成的树。
一棵语法树包括了一个句型的所有可能的推导过程。
这个语法树满足:
(1) 树中每一个结点都有一个标记,此标记是V= VN∪VT中的一个符号。
(2) 根的标记是S。
(3) 若树的一结点A至少有一个子女,则A∈VN。
(4) 如结点A的子女结点从左到右次序为B1,B2...Bn,则必有产生式A→B1B2...Bn。
例:G[S]: S→aAS | a
A→SbA |SS |ba
对句型aabbaa的推导过程可表示为下图所示语法树。
下面两个推导过程均可由右图表示。
(1) SÞaASÞaSbASÞaabASÞaabbaSÞaabbaa
(2) SÞaASÞaAaÞaSbAaÞaSbbaaÞaabbaa
这说明同一语法树可以表示对同一句型不同的推导过程。