گرامر درخت منظم

در علم کامپیوتر نظری و تئوری زبان رسمی، یک گِرامر درخت منظم،
گرامر صوری است که مجموعه‌ای از درختان جهت دار یا جملات ( **terms** ) را توصیف می‌کند.
گرامر کلمه منظم می‌تواند به عنوان یک نوع خاص از **گرامر درخت منظم** که مجموعه‌ای از درختان تک مسیر را توصیف می‌کند بیان شود.

## تعریف

گرامر درخت منظم توسط چندتایی

(*G* = (*N*, Σ, *Z*, *P*

که در آن
* *N* مجموعه‌ای از غیرپایانه‌ها
* Σ الفبای رتبه‌ای مجزا شده از N 
* *Z* یک غیرپایانه شروع است به طوریکه *Z* ∈ *N* و
* *P* مجموعه‌ای از انتقالات به فرم *A* → *t* که *A* ∈ *N* و (*t* ∈ *T*Σ(*N* به صورتی که

(*T*Σ(*N* جبر واژه همراه است، یعنی مجموعه‌ای از تمام درختان تشکیل شده از نمادها در Σ ∪ *N* با توجه به arities خود که در آن غیر پایانه‌ها nullary در نظر گرفته می‌شود.

## اشتقاق از درختان

دستور زبان G به‌طور ضمنی مجموعه‌ای از درختان تعرف می‌شود : هر درختی که می‌تواند از Z با استفاده از مجموعهٔ قوانین P مشتق شود ، گفته می‌شود که توسط G توصیف شده‌است .

این مجموعه از درختان به عنوان زبان G شناخته می‌شوند . به‌طور رسمی تر ، رابطهٔ  ⇒*G*  روی مجموعهٔ (*T*Σ(*N*  به صورت زیر تعرف می‌شود :

درخت   (*t*1∈ *T*Σ(*N*   می‌تواند در یک مرحله اشتقاق شود به درخت   (*t*1∈ *T*Σ(*N*   اگر وجود داشته باشد :  متن S و انتقال   *A*→*t*) ∈ *P*)   به طوری که
* [*t*1 = *S*[*A* و
* [*t*2 = *S*[*t*.

در اینجا یک بافت ( متن ) به معنی یک درخت با دقیقاً یک حفره در آن است و  [*S*[*t*  نشان دهندهٔ نتیجهٔ پر کردن درخت T با حفره‌ای از S است .

زبان درخت تولید شده توسط T زبان   { *L*(*G*) = { *t* ∈ *T*Σ | *Z* ⇒*G** *t*   است.

در اینجا  *T*Σ  نشان دهندهٔ مجموعه‌ای از تمام درختان تشکیل شده از نمادهای Σ  ,  درحالیکه   ⇒*G**   نشان دهندهٔ عملیات  پی در پی از  ⇒*G*  است.

## مثال‌ها

[upright=2.5|بندانگشتی|Example [derivation tree from G1 in linear (upper left table) and graphical (main picture) notation]]

فرض کنید  *G*1 = (*N*1,Σ1)  , *Z*1  , *P*1   که در آن
* {*N*1 = {*Bool*, *BList* مجموعه‌ای از غیرپایانه‌های ماست.
* {*N*1 = {*Bool*, *BList* الفبای رتبه بندی شدهٔ ماست که arities توسط استدلال‌های ساختگی نشان داده شده (یعنی منفی نماد arity 2 است)
* *Z*1 = *BList* غیرپایانه آغازین است و
* مجموعهٔ *P*1 شامل موارد زیر می‌شود:
* *Bool* → *false*
* *Bool* → *true*
* *BList* → *nil*
* (*BList* → *cons*(*Bool*,*BList*

مثالی از اشتقاق گرامر *G*1  :

*BList*
⇒ *cons*(*Bool*,*BList*)
⇒ *cons*(*false*,*cons*(*Bool*,*BList*))
⇒ *cons*(*false*,*cons*(*true*,*nil*))

تصویر نشان می‌دهد که درخت اشتقاق مربوطه ، آن درخت از درختان (تصویر اصلی) است ، در حالیکه یک درخت اشتقاق در گرامر کلمه یک درخت از رشته (جدول بالا سمت چپ) است .

زبان درخت تولید شده توسط  *G*1  مجموعه‌ای از تمام لیست‌های متناهی از مقادیر بولی است ، که  (*L*(*G*1  برابر با  *T*Σ1 شده‌است.
گرامر  *G*1  مرتبط است با اظهارات نوع داده جبری .


```ocaml
datatype Bool
    = false
    | true
  datatype BList
    = nil
    | cons of Bool * BList
```


در زبان برنامه نویسی استاندارد ML : هر عضو از  *(L*(*G*1  مرتبط است با مقدار استاندارد ML از نوع دادهٔ  BList .

به عنوان مثال دیگر ، فرض کنید  (*G*2 = (*N*1,Σ1, *BList1* , *P*1 ∪ *P*2
با استفاده از مجموعه‌ای از غیر پایانی‌ها و الفبای بالا ، گسترش تولیدات *P*2 , متشکل از تولیدات زیر است :
* (*BList1* → *cons*(*true*,*BList*
* (*BList1* → *cons*(*false*,*BList1*

زبان  *(L*(*G*2  مجموعه‌ای از تمام لیست‌های متناهی از مقادیر بولی است که حداقل یکبار شامل مقدار «درست» ( true ) می‌باشند .
مجموعهٔ (*L*(*G*2 هیچ همتای نوع داده‌ای نه در استاندارد ML و نه در هیج زبان تابعی دیگر ندارد . این یک زیرمجموعه مناسب از
(*L*(*G*1 است . ترم مثال بالا نیز در  (*L*(*G*2 است ، همانطور که اشتقاقزیر نشان می‌دهد :

*BList1*
⇒ *cons*(*false*,*BList1*)
⇒ *cons*(*false*,*cons*(*true*,*BList*))
⇒ *cons*(*false*,*cons*(*true*,*nil*)).

## ویژگی‌های زبان

اگر  *L*1  و *L*2  هر دو زبان درخت منظم باشند ، مجموعهٔ درخت *L*1 ∩ *L*2 و *L*1 ∪ *L*2 و *L*1 \ *L*2  نیز درخت زبان منظم هستند ؛  و می‌توان نتیجه گرفت که آیا *L*1 ⊆ *L*2 یا *L*1 = *L*2 هست یا نه .

## مشخصات جایگزین و ارتباط با دیگر زبان‌های رسمی

Rajeev Alur و Parthasarathy Madhusudan  یک زیرکلاس از زبان درخت دودویی منظم را به کلمات تو در تو و زبان‌های پشته‌ای مشخصه ارتباط دادند .

زبان‌های درخت منظم همچنین شامل زبان‌های به رسمیت شناخته شدهٔ درخت‌های پایین به بالا و درخت‌های غیرقطعی بالا به پایین هستند .

گرامرهای درخت منظم کلیتی از گرامرهای کلمه منظم هستند .

## منابع

* [//en.wikipedia.org/w/index.php?title=Useless_rules&oldid=620871818 ویکی‌پدیای انگلیسی]
* [//en.wikipedia.org/w/index.php?title=Regular_tree_grammar&oldid=624268966 مقاله گرامر درخت منظم]

رده:زبان‌های صوری
رده:قاعده‌ها
رده:ویکی‌سازی رباتیک