語法樹

給定文法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。

語法樹(2張)

例：G[S]： S→aAS | a

A→SbA |SS |ba

對句型aabbaa的推導過程可表示為圖1所示語法樹。

下面兩個推導過程均可由圖1表示。

(1) SÞaASÞaSbASÞaabASÞaabbaSÞaabbaa

(2) SÞaASÞaAaÞaSbAaÞaSbbaaÞaabbaa

這説明同一語法樹可以表示對同一句型不同的推導過程。