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

در علم کامپیوتر نظری و تئوری زبان رسمی، یک گِرامر درخت منظم، گرامر صوری است که مجموعه‌ای از درختان جهت دار یا جملات ( 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₁∈ T_Σ(N می‌تواند در یک مرحله اشتقاق شود به درخت (t₁∈ T_Σ(N اگر وجود داشته باشد : متن S و انتقال A→t) ∈ P) به طوری که

[t₁ = S[A و
[t₂ = S[t.

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

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

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

مثال‌ها

Example derivation tree from G₁ in linear (upper left table) and graphical (main picture) notation

فرض کنید G₁ = (N₁,Σ₁) , Z₁ , P₁ که در آن

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

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

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

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

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

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

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

به عنوان مثال دیگر ، فرض کنید (G₂ = (N₁,Σ₁, BList1 , P₁ ∪ P₂ با استفاده از مجموعه‌ای از غیر پایانی‌ها و الفبای بالا ، گسترش تولیدات P₂ , متشکل از تولیدات زیر است :

(BList1 → cons(true,BList
(BList1 → cons(false,BList1

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

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

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

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

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

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

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

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