گرامر درخت مجاورت: تفاوت میان نسخه‌ها

اگرچه گرامرهای مستقل از متن قواعدی برای بازنویسی نمادها به عنوان رشته ای از سایر نمادها دارند، گرامرهای درخت مجاورت نیز قواعدی برای بازنویسی نودهای درخت ها به عنوان سایر درخت ها دارند. (بخش [[درخت (نظریه گراف)]] و [[درخت (ساختار داده)]] را ببینید.)

 

| mr =

| zbl =

 

در سال 1969، جوشی یک خانواده از [[دستور زبان]] معرفی کرد که مورد استفاده ی این مکمل، با ترکیب این دو نوع از قوانین قرار می گیرد. چند قانون بازنویسی بسیار ساده برای تولید واژگان رشته ها که برای بررسی قوانین مورد استفاده قرار می گیرد، کافی است. این خانواده از [[سلسله مراتب چامسکی-شواتزنبرگ]](Chomsky-Schützenberger) متمایز است اما به صورتی جالب و زبانی اتصال دارد.<ref name="Joshi1969">{{cite paper

| location = Upper Saddle River, NJ}}</ref>

گره ریشه و گره پایانی درختان کمکی با علامتی یکسان، نشاندار شده اند.

تعویض؛ گره مرزی را با درخت دیگری که گره بالای آن دارای همان برچسب می باشد، جایگزین می کند.

برچسب گره ریشه / پایانی درخت کمکی باید مطابق با برچسب گره ای باشد که به آن متصل شده است.

 

== پیچیدگی و کاربرد ==

TAG می تواند زبان مربعات (که در ان برخی از رشته های دلخواه تکرار شده است) و زبان <math>\{a^n b^n c^n d^n | 1 \le n \}</math> را توصیف کند.

این نو ع از پردازش می تواند توسط یک [[ماشین پذیرنده ی پشته ای]] تعبیه شده، نمایش داده شود.

 

به این دلایل، گرامر درخت مجاورت اغلب به صورت [[زبان ملایم حساس به متن]] توصیف می شود.گمان می رود این کلاس های دستوری برای مدل کردن [[زبان های طبیعی]] کافی باشند، در حالی که همچنین در حالت عمومی تا حد مطلوبی قاعده مند می باشند.<ref name="joshi1985">{{cite book

*[http://mgkit.gforge.inria.fr/ The Metagrammar Toolkit] which provides several tools to edit and compile [[MetaGrammars]] into TAGs. It also include a wide coverage French Metagrammars.

*[http://www.loria.fr/~azim/LLP2/help/fr/index.html LLP2] A [[lexicalized tree adjoining grammar]] parser which provides an easy to use graphical environment (page in French)

[[رده:چارچوب‌های دستور زبانی]]

[[رده:دستور زایشی]]