上下文無關文法與推導

剖析樹的果實(yield of a parse tree)

如果剖析樹是字串如何被建造的圖像,那麼果實就是字串本身,直接從樹的底緣讀出。把手指沿著所有葉節點由左到右滑過,把看到的寫下來:這串終端符號就是果實,也稱為樹的「邊界(frontier)」。樹顯示結構;果實則是該結構所產生的那個扁平句子。

形式上,剖析樹的果實是把葉節點標籤按由左到右順序串接而得的字串。在上下文無關文法的剖析樹中,葉節點是終端符號(或來自形如 A → ε 之規則的空字串 ε,它不貢獻任何字元),所以果實永遠是終端符號字母表 Σ(Sigma)上的字串。例如,一棵根為 S、葉節點由左到右拼出 a, a, b, b 的樹,其果實為「aabb」。關鍵在於:「許多」不同的樹可以有相同的果實卻有不同的內部形狀——這正是歧義的情形。

果實是樹的結構世界與字串、語言的扁平世界之間的橋樑。一個字串 w 在文法所生成的語言中,恰當且唯當存在一棵根為起始符號、果實為 w 的剖析樹。所以 CFG 的語言可定義為所有根為 S 的合法剖析樹之所有果實所成的集合。注意措辭:果實只從「葉節點」(終端符號)讀出,不從內部節點讀出;標記內部節點的變數是結構的一部分,但絕非果實的一部分。

一棵根為 S、有內部節點 A、葉節點(由左到右讀)為 a, b, a 的樹,其果實為「aba」。變數標籤 S 與 A「不」屬於果實——只讀終端符號葉節點。

果實 = 葉節點標籤由左到右串接;w 在語言中,當且唯當存在某棵根為 S 的樹其果實為 w。

果實只從「葉節點」(終端符號)讀出。兩棵不同的剖析樹可共有相同的果實——依定義,這正是文法歧義之所在。

又称
frontierleaf string葉串邊界字串