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