در مورد گرامر درخت منظم توضیح بده.
در علم کامپیوتر نظری و تئوری زبان رسمی، یک گِرامر درخت منظم،گرامر صوری است که مجموعه‌ای از درختان جهت دار یا جملات ( terms ) را توصیف می‌کند.گرامر کلمه منظم می‌تواند به عنوان یک نوع خاص از گرامر درخت منظم که مجموعه‌ای از درختان تک مسیر را توصیف می‌کند بیان شود.تعریف.گرامر درخت منظم توسط چندتایی("G" = ("N", Σ, "Z", "P"که در آن("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") به طوری کهدر اینجا یک بافت ( متن ) به معنی یک درخت با دقیقاً یک حفره در آن است و ["S"["t" نشان دهندهٔ نتیجهٔ پر کردن درخت T با حفره‌ای از S است .زبان درخت تولید شده توسط T زبان { "L"("G") = { "t" ∈ "T"Σ | "Z" ⇒"G"* "t" است.در اینجا "T"Σ نشان دهندهٔ مجموعه‌ای از تمام درختان تشکیل شده از نمادهای Σ , درحالیکه ⇒"G"* نشان دهندهٔ عملیات پی در پی از ⇒"G" است.مثال‌ها.فرض کنید "G"1 = ("N"1,Σ1) , "Z"1 , "P"1 که در آنمثالی از اشتقاق گرامر "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 مرتبط است با اظهارات نوع داده جبری . 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 , متشکل از تولیدات زیر است :زبان "(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 یک زیرکلاس از زبان درخت دودویی منظم را به کلمات تو در تو و زبان‌های پشته‌ای مشخصه ارتباط دادند .زبان‌های درخت منظم همچنین شامل زبان‌های به رسمیت شناخته شدهٔ درخت‌های پایین به بالا و درخت‌های غیرقطعی بالا به پایین هستند .گرامرهای درخت منظم کلیتی از گرامرهای کلمه منظم هستند .