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

در علم کامپیوتر نظری و تئوری زبان رسمی، یک گرامر درخت منظم،
گرامر صوری است که مجموعه‌ای از درختان جهت دار یا جملات ( 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 = SA و
t 2 = St.
در اینجا یک بافت ( متن ) به معنی یک درخت با دقیقا یک حفره در آن است و St نشان دهنده نتیجه پر کردن درخت T با حفره‌ای از S است .
زبان درخت تولید شده توسط T زبان { L(G) = { t ∈ T  | Z ⇒ G* t است.
در اینجا T  نشان دهنده مجموعه‌ای از تمام درختان تشکیل شده از نمادهای  , درحالیکه ⇒ G* نشان دهنده عملیات پی در پی از ⇒ G است.
مثال‌ها
Example derivation tree from G 1 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 مرتبط است با اظهارات نوع داده جبری .
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 یک زیرکلاس از زبان درخت دودویی منظم را به کلمات تو در تو و زبان‌های پشته‌ای مشخصه ارتباط دادند .
زبان‌های درخت منظم همچنین شامل زبان‌های به رسمیت شناخته شده درخت‌های پایین به بالا و درخت‌های غیرقطعی بالا به پایین هستند .
گرامرهای درخت منظم کلیتی از گرامرهای کلمه منظم هستند .