گرامر نمایه‌سازی‌شده

گرامر نمایه‌سازی شده تعمیم گرامر مستقل از متن است که غیرپایانه‌ها با لیستی از پرچم‌ها مجهز شده‌است. زبانی که به وسیلهٔ گرامر نمایه سازی شده تولید می‌شود زبان ایندکس شده نامیده می‌شود.

تعریف

تعریف جدید از Hopcroft و Ullman

گرامر نمایه سازی شده به‌طور رسمی یک ۵تایی G = ⟨N,T,F,P,S تعریف می‌شود به طوریکه:

• N مجموعه‌ای از متغیرها یا نمادهای غیرترمینال
• T مجموعه الفبای نمادهای ترمینال
• F مجموعه نمادهای ایندکس
• S ∈ N نماد شروع
• P مجموعه متناهی از تولیدات

در تولیدات مانند اشتقاق در گرامر نمایه سازی شده، رشتهٔ σ از نمادهای ایندکس به همهٔ نمادهای غیرترمینال A ∈ N متصل می‌شوند که توسط (A)σ مشخص می‌شود. نمادهای ترمینال ممکن است با ایندکس پشته دنبال نشوند. برای نماد پشته σ ∈ F^* و رشتهٔ α ∈ (N ∪ T)^* از نمادهای غیرترمینال و ترمینال، (α)σ نتیجهٔ اتصال (σ) به همهٔ غیرترمینال‌ها در α را مشخص می‌کند. برای مثال اگر α برابر a B C d E باشد به طوریکه a,d ∈ T ترمینال، و B,D,E ∈ N نمادهای غیرترمینال، آنگاه {{.[nowrap|a B[σ] C[σ] d E[σ}} را مشخص می‌کند. با استفاده از این نشانه‌گذاری، هر تولید در P به این فرم می‌باشد:

1. [A[σ] → α[σ،
2. [A[σ] → B[fσ، یا
3. [A[fσ] → α[σ

که A, B ∈ N نمادهای غیرترمینال، f ∈ F ایندکس، σ ∈F رشته از نمادهای ایندکس و (α ∈ (N ∪ T رشته از نمادهای ترمینال و غیرترمینال. بعضی نویسنده‌ها به جای "σ" ".." را برای نماد پشته در قوانین تولید می‌نویسند. قوانین نوع۱٬۲ و۳ به ترتیب به صورت A[..]→α[..], A[..]→B[f..] A[f..]→α[..], خوانده می‌شود.

اشتقاق‌ها مانند اشتقاق در گرامر مستقل از متن می‌باشند جز نماد پشته که به هر نماد غیرترمینال متصل شده‌است. وقتی قاعده تولیدی مانند [A[σ] → B[σ]C[σ به کار رود، نماد پشته A در جفت B و C کپی می‌شود. علاوه براین، قانون ممکن است یک نماد ایندکس را روی پشته بگذارد یا بردارد.

به‌طور رسمی رابطه ⇒ ("اشتقاق مستقیم") روی مجموعه<N[F^*]∪T)^*) از فرم‌های ضروری اینگونه تعریف می‌شود:

1. اگر [A[σ] → α[σ از تولید نوع ۱ باشد، آنگاه β A[φ] γ ⇒ β α[φ] γ با استفاده از تعریف بالا. قوانین سمت چپ ایندکس پشته φ به هرکدام از غیرترمینال‌های سمت راست کپی شده است.
2. اگر [A[σ] → B[fσ از تولید نوع ۲ باشد، آنگاه β A[φ] γ ⇒ β B[fφ] γ که سمت راست ایندکس پشته از سمت چپ پشته φ با وارد کردن f داخلش به دست می‌آید.
3. اگر [A[fσ] → α[σ از تولید نوع ۳ باشد، آنگاه β A[fφ] γ ⇒ β α[φ] γ، با استفادهٔ دوباره از تعریف [α[σ که اولین ایندکس f از سمت چپ پشته خارج می‌شود که به غیرترمینال‌های سمت راست توزیع شده است.

به طور معمول اشتقاق ⇒^* بستار متعدی انعکاسی اشتقاق مستقیم ⇒ تعریف شده است. زبان L(G) = { w ∈ T^*: S ⇒^* w } مجموعه تمام رشته‌های نمادهای ترمینال اشتقاق شده از نماد شروع می‌باشد.

تعریف اصلی توسط Aho

از نظر تاریخی، گرامر ایندکس شده توسط Aho (در ۱۹۶۸) با استفاده از یک فرمالیسم متفاوت معرفی شد. Aho یک گرامر ایندکس شده را یک ۵-تایی (N,T,F,P,S) تعریف کرد به طوریکه:

1. N الفبایی از متغیرها یا نمادهای غیرترمینال
2. T یک الفبای متناهی از نمادهای غیرترمینال
3. F ⊆ 2^{N × (N ∪ T)*} یک مجموعهٔ متناهی که به طور معمول پرچم‌ها خوانده می‌شود (هر پرچم مجموعه‌ای از حاصل‌ضرب‌های ایندکس شده است)
4. P ⊆ N × (NF^* ∪ T)^* مجموعهٔ حاصل‌ضرب‌هاست.
5. S ∈ N نماد شروعی

گرامر نمایه سازی شدهٔ خطی

Gerald Gazdar کلاس دیگری به نام گرامرهای نمایه سازی شدهٔ خطی (LIG) تعریف کرد با این شرط که حداکثر یک غیرترمینال در هر حاصل‌ضرب مخصوص دریافت استک باشد. در حالی که در گرامرهای ایندکس شدهٔ معمولی، تمام غیرترمینال‌ها نسخه‌هایی از استک را دریافت می‌کنند. به صورت رسمی، گرامر ایندکس شدهٔ خطی به طور مشابه با یک گرامر ایندکس شدهٔ معمولی تعریف می‌شود، اما شرط‌های فرم حاصل‌ضرب به صورت زیر اصلاح شده‌اند:

1. A[σ] → α[] B[σ] β[],
2. A[σ] → α[] B[fσ] β[],
3. A[fσ] → α[] B[σ] β[],

که A, B, f, σ, α به صورت فوق استفاده شده‌اند و β ∈ (N ∪ T)^* رشته‌ای از نمادهای ترمینال و غیرترمینال مانند α است. همچنین، رابطهٔ یک‌طرفهٔ ⇒ به صورتی مشابه فوق تعریف شده‌اند. این کلاس جدید از گرامرها یک کلاس اکیداً کوچکتر از زبان‌ها را تعریف می‌کند، که به کلاس‌های با وابستگی کم به متن متعلق هستند.

زبان { www: w ∈ {a,b}^* } توسط یک گرامر ایندکس شده قابل تولید است، ولی توسط یک گرامر نمایه سازی شدهٔ خطی قابل تولید نیست. در حالی که { aⁿ bⁿ cⁿ: n ≥ ۱ } توسط یک گرامر نمایه سازی شدهٔ خطی قابل تولید است.

اگر هم قانون اصلی و هم قانون اصلی حاصل‌ضرب قابل قبول باشند، کلاس زبان به صورت زبان نمایه سازی شده باقی می‌ماند.

مثال

فرض کنید σ نشان‌دهندهٔ مجموعهٔ دلخواهی از نمادهای استک باشد. می‌توانیم گرامری برای زبان L = {aⁿ bⁿ cⁿ | n ≥ ۱ } تعریف کنیم به طوری که:

S[σ]	→	a S[fσ] c
S[σ]	→	T[σ]
T[fσ]	→	T[σ] b
T[]	→	ε

برای به دست آوردن رشتهٔ abc مراحل S[] ⇒ aS[f]c ⇒ aT[f]c ⇒ aT[]bc ⇒ abc را طی می‌کنیم. به صورت مشابه: S[] ⇒ aS[f]c ⇒ aaS[ff]cc ⇒ aaT[ff]cc ⇒ aaT[f]bcc ⇒ aaT[]bbcc ⇒ aabbcc.

قدرت محاسباتی

زبان‌های ایندکس شدهٔ خطی زیرمجموعه‌ای از زبان‌های نمایه سازی شده هستند، بنابراین می‌توانیم تمام LIGها را به صورت IG تعریف کرده و با این کار LIGها را اکیداً کم‌قدرت‌تر از IGها کنیم. تبدیلی از یک LIG به یک IG نسبتاً ساده است. قوانین LIG در حالت کلی، مثل قسمت گذاشتن/برداشتن (Push/Pop) در یک قانون بازنویسی، به صورت $X[\sigma ]\to \alpha Y[\sigma ]\beta$ هستند. نمادهای $\alpha$ و $\beta$ نشان‌دهندهٔ رشته‌هایی از نمادهای ترمینال و/یا غیرترمینال هستند و به خاطر تعریف LIG، هر نماد غیرترمینالی باید یک استک خالی داشته باشد. البته این برعکس تعریف IGهاست: در یک IG، غیرترمینال‌هایی که در استک‌هایشان چیزی گذاشته نمی‌شود یا از آن‌ها چیزی برداشته نمی‌شود، باید دقیقاهمان استک غیرترمینال بازنویسی‌شده باشد؛ بنابراین به نحوی، به غیرترمینال‌هایی در $\alpha$ و $\beta$ احتیاج داریم که علی‌رغم داشتن پشته‌های غیر خالی، طوری از خود رفتار نشان دهند که گویا پشته‌های خالی دارند.

بیایید قانون $X[\sigma ]\to Y[]Z[\sigma f]$ را به عنوان یک مورد مثال فرض کنیم. در تبدیل آن به یک IG، جایگزین $Y[]$ باید چیزی مثل $Y^{\prime }[\sigma ]$ که بدون توجه به مقدار $\sigma$، دقیقاً مشابه $Y[]$ عمل کند. برای رسیدن به این هدف، می‌توانیم یک زوج قانون داشته باشیم که هر $Y^{\prime }[\sigma ]$ را که $\sigma$ تهی نیست می‌گیرد و از پشته نمادها را برمی‌دارد. سپس، وقتی پشته خالی شد، می‌تواند به صورت $Y[]$ بازنویسی شود.

$Y^{\prime }[\sigma f]\to Y^{\prime }[\sigma ]$

$Y^{\prime }[]\to Y[]$

می‌توانیم به صورت کلی این قاعده را به کار ببندیم تا از یک LIG، یک IG را به دست آوریم؛ بنابراین به طور مثال اگر LIG برای زبان $\{a^{n}b^{n}c^{n}d^{m}|n\geq 1,m\geq 1\}$ به صورت زیر باشد:

$S[\sigma ]\to T[\sigma ]V[]$

$V[]\to d~|~dV[]$

$T[\sigma ]\to aT[\sigma f]c~|~U[\sigma ]$

$U[\sigma f]\to bU[\sigma ]$

$U[]\to \epsilon$

قانون ضروری در اینجا یک قانون IG نیست، اما با استفاده از الگوریتم تبدیل بالا، می‌توانیم قوانین جدیدی برای $V^{\prime }$ تعریف کنیم که گرامر را به صورت زیر تغییر می‌دهند:

$S[\sigma ]\to T[\sigma ]V^{\prime }[\sigma ]$

$V^{\prime }[\sigma f]\to V^{\prime }[\sigma ]$

$V^{\prime }[]\to V[]$

$V[]\to d~|~dV[]$

$T[\sigma ]\to aT[\sigma f]c~|~U[\sigma ]$

$U[\sigma f]\to bU[\sigma ]$

$U[]\to \epsilon$

همه قوانین اکنون با تعریف یک IG به این صورت: در آن تمام غیرترمینال‌های در سمت راست یک قانون بازنویسی، نسخه‌ای از نماد بازنویسی شده در پشته را دریافت می‌کنند، مطابقت دارد؛ بنابراین گرامرهای ایندکس شده قادرند تمام زبان‌هایی را که گرامرهای ایندکس شدهٔ خطی وصف می‌کنند را وصف کنند.

ارتباط با روش‌های دیگر

Vijay-Shanker و Weir (در ۱۹۹۴) نشان دادند که گرامرهای نمایه سازی شدهٔ خطی، گرامرهای ترکیبی دسته‌ای، گرامرهای درخت الحاقی، و گرامرهای سر، همه کلاس یکسانی از زبان‌های رشته‌ای را تعریف می‌کنند. تعریف رسمی آن‌ها از گرامرهای ایندکس شدهٔ خطی با تعریف فوقتفاوت دارد.

LIGها (و هم‌ارزهای ضعیف آن‌ها) اکیداً ارزانتر (یعنی زیرمجموعهٔ مناسبی را تولید می‌کنند) از زبان‌هایی است که توسط یک خانواده از هم‌ارزهای ضعیف فرمالیسم شامل:LCFRS, MCTAG, MCFG و گرامرهای مینیمالیست (MGها) تولید می‌شوند. خانوادهٔ آخر را می‌توان همچنین به زمان چندجمله‌ای تجزیه کرد.

گرامرهای نمایه سازی شدهٔ توزیعی

شکل دیگری از گرامرهای نمایه سازی شده که در ۱۹۹۳ توسط Staudacher معرفی شدند، کلاس گرامرهای نمایه سازی شدهٔ توزیعی (DIها) است. آنچه DIGها را از گرامرهای نمایه سازی شدهٔ Aho متمایز می‌سازد، انتشار ایندکس‌هاست. برخلاف IGهای Aho، که همهٔ پشتهٔ نماد را روی تمام غیرترمینال‌ها در مدت زمان یک عملیات بازنویسی توزیع می‌کند، DIGها پشته را به چند زیرپشته تقسیم می‌کند و زیرپشته‌ها را روی غیرترمینال‌های انتخابی توزیع می‌کند.

طرح کلی برای یک قانون توزیع دودویی از DIG به صورت

X[f₁...f_if_i+1...f_n] → α Y[f₁...f_i] β Z[f_i+1...f_n] γ

که α و β و γ رشته‌های ترمینالی دلخواهی هستند. برای یک توزیع رشتهٔ سه‌تایی:

X[f₁...f_if_i+1...f_jf_j+1...f_n] → α Y[f₁...f_i] β Z[f_i+1...f_j] γ W[f_j+1...f_n] η

و ترتیب برای تعداد بیشتری از غیرترمینال‌ها در دست راست قانون بازنویسی به همین صورت است. به‌طور کلی، اگر m غیرترمینال در سمت راست یک قانون بازنویسی وجود داشته باشد، پشته به m راه تقسیم شده و روی غیرترمینال‌های جدید توزیع می‌شود. توجه کنید که یک مورد خاص وجود دارد که قسمت خالی باشد، که به صورت مؤثر قانون را به یک قانون LIG تبدیل می‌کند؛ بنابراین زبان‌های نمایه سازی شدهٔ توزیعی یک اَبَرمجموعه از زبان‌های نمایه سازی شدهٔ خطی است.