樹-鄰接文法(TAG)是 Aravind Joshi 定義的文法形式化。樹-鄰接（adjoining）文法在某種意義上類似於上下文無關文法，但是基本的重寫單位是樹而不是符號。上下文無關文法有把符號重寫為其他符號的規則，而樹-毗連文法有把樹的節點重寫為其他樹的規則。
基本介紹
- 中文名：樹-鄰接文法
- 外文名：TAG
文法規則,文法緣起,上下文無關文法,
文法規則
TAG 中的規則是帶有叫做“足節點”的特殊葉子的樹，它們錨接（anchor）到一個字。在 TAG 中有兩個種類的基本樹：“初始”樹和“輔助”樹。初始樹表示基本的價（valency）關係，而輔助樹允許遞歸。輔助樹有標記（label）上同樣符號的根（頂）節點和足節點。推導開始於初始樹，通過要么“代換”要么“附加”來結合。代換把末梢節點替換為其頂節點有同樣符號的另一個樹。附加把一個輔助樹插入到另一個樹的中心。輔助樹的根/足標記必須匹配它所鄰接的節點的標記。其他 TAG 的變體允許多種成分的樹，帶有多個足節點的樹，和其他擴展。
樹-鄰接文法經常被描述為“適度上下文有關的”，這意味著它們有（在弱生成能力方面上）特定性質使其有比上下文無關文法更強力，但有比附標文法或上下文有關文法更弱的能力。適度上下文有關文法被推測為足夠強力可以建模自然語言，而仍保持在一般情況下有效解析。由於它們的形式特性，TAG 經常被用於計算語言學和自然語言處理。
文法緣起
TAG 起源於 Joshi 和他的學生對附加文法（AG）家族和Zellig Harris的“字元串文法”的研究。AG 以自然和高效的方式處理語言的向心性質，但是沒有對離心構造的好特徵描述；重寫文法或短語-結構文法（PSG）正好反過來。在 1969 年，Joshi 通過混合兩種類型的規則介入了開拓出這種補足的文法家族。一些非常簡單的重寫規則足夠生成附加規則的字元串的辭彙表。這個家族不同於喬姆斯基層級，但是有所交疊。
TAG 可以描述有平方的語言（在其中某個任意字元串被重複），和語言{\displaystyle \{a^{n}b^{n}c^{n}d^{n}|n\geq 1\}}，有立方的語言（就是三倍的字元串）或有相等長度的多於四個不同字元的字元串的語言不可以被樹-鄰接文法所生成。為此，樹-毗連文法生成的語言被稱為“適度上下文有關語言”。
上下文無關文法
上下文無關文法重要的原因在於它們擁有足夠強的表達力來表示大多數程式設計語言的語法；實際上，幾乎所有程式設計語言都是通過上下文無關文法來定義的。另一方面，上下文無關文法又足夠簡單，使得我們可以構造有效的分析算法來檢驗一個給定字串是否是由某個上下文無關文法產生的。例子可以參見LR 分析器和LL 分析器。
BNF（巴克斯-諾爾範式）經常用來表達上下文無關文法。
