簡介
給定文法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
這說明同一語法樹可以表示對同一句型不同的推導過程。