Tree -adjoining grammatik TAG ) är en formell grammatik uppfunnen av Aravind Joshi ( engelska Denna grammatik generaliserar den sammanhangsfria grammatiken genom att de elementära enheterna i slutledningsreglerna är träd snarare än enskilda tecken. Sålunda definierar grammatiken reglerna för att ersätta trädnoder med underträd (se träd i grafteori och träd i datavetenskap ).
TAG uppstod som ett resultat av forskning av Joshi och hans elever i en familj av tilläggsgrammatiker [1] . Bifogade grammatiker är väl lämpade för att analysera fraser som innehåller ett huvudord och många beroende ord som begränsar betydelsen av huvudordet (till exempel "ett mycket stort hus"). Men de karakteriserar inte tydligt fraser där inte ett enda ord kan bära hela strukturens funktion. Detsamma gäller grammatik med frasstruktur . 1969 introducerade Joshi en familj av grammatiker som utnyttjade denna komplementaritet genom att blanda två typer av regler. Denna familj är inte en del av Chomsky-hierarkin [2] och tillhör svagt kontextkänsliga grammatiker , det vill säga när det gäller genererande egenskaper är den starkare än sammanhangsfria grammatiker , men svagare än sammanhangskänsliga [3] . Trädadditionsgrammatik är svagt likvärdiga med linjärt indexerade grammatiker , kombinatoriska kategoriska grammatiker och rubrikgrammatik [4] (för vilken trädadditionsgrammatik som helst kan man konstruera en motsvarande grammatik från vilken som helst av dessa tre familjer som kommer att generera samma strängar).
En TAG-regel är ett träd med en lövnod till vilken ett ord (LTAG) kan fästas.
Det finns två typer av träd: "initial" (ofta kallad ' ') och "hjälp" (' '). De initiala träden representerar frasens huvudsakliga valenser, medan hjälpträden tillåter användning av rekursion [5] . Hjälpträd har toppnoden och lövnoden markerade med samma symbol.
Ersättningar börjar från det ursprungliga trädet och görs genom substitution eller tillägg . En ersättare ersätter en nod med ett träd vars toppnod är märkt med samma symbol som den som ersätts. Append infogar ett extra underträd i mitten av trädet [6] . Ett hjälpträd måste märkas med samma etikett som noden som det är fäst vid.
På engelska: