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

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

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

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

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

Vijay-Shanker و Weir (در ۱۹۹۴) نشان دادند که گرامرهای نمایه سازی شدهٔ خطی، گرامرهای ترکیبی دسته‌ای، گرامرهای درخت الحاقی، و گرامرهای سر، همه کلاس یکسانی از زبان‌های رشته‌ای را تعریف می‌کنند. تعریف رسمی آن‌ها از گرامرهای ایندکس شدهٔ خطی با تعریف فوقتفاوت دارد.
LIGها (و هم‌ارزهای ضعیف آن‌ها) اکیداً ارزانتر (یعنی زیرمجموعهٔ مناسبی را تولید می‌کنند) از زبان‌هایی است که توسط یک خانواده از هم‌ارزهای ضعیف فرمالیسم شامل:LCFRS, MCTAG, MCFG و گرامرهای مینیمالیست (MGها) تولید می‌شوند. خانوادهٔ آخر را می‌توان همچنین به زمان چندجمله‌ای تجزیه کرد.

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

شکل دیگری از گرامرهای نمایه سازی شده که در ۱۹۹۳ توسط Staudacher معرفی شدند، کلاس گرامرهای نمایه سازی شدهٔ توزیعی (DIها) است. آنچه DIGها را از گرامرهای نمایه سازی شدهٔ Aho متمایز می‌سازد، انتشار ایندکس‌هاست. برخلاف IGهای Aho، که همهٔ پشتهٔ نماد را روی تمام غیرترمینال‌ها در مدت زمان یک عملیات بازنویسی توزیع می‌کند، DIGها پشته را به چند زیرپشته تقسیم می‌کند و زیرپشته‌ها را روی غیرترمینال‌های انتخابی توزیع می‌کند.
طرح کلی برای یک قانون توزیع دودویی از DIG به صورت
X[f₁...fᵢfᵢ₊₁...fₙ] → α Y[f₁...fᵢ] β Z[fᵢ₊₁...fₙ] γ
که α و β و γ رشته‌های ترمینالی دلخواهی هستند. برای یک توزیع رشتهٔ سه‌تایی:
X[f₁...fᵢfᵢ₊₁...fⱼfⱼ₊₁...fₙ] → α Y[f₁...fᵢ] β Z[fᵢ₊₁...fⱼ] γ W[fⱼ₊₁...fₙ] η
و ترتیب برای تعداد بیشتری از غیرترمینال‌ها در دست راست قانون بازنویسی به همین صورت است. به‌طور کلی، اگر m غیرترمینال در سمت راست یک قانون بازنویسی وجود داشته باشد، پشته به m راه تقسیم شده و روی غیرترمینال‌های جدید توزیع می‌شود. توجه کنید که یک مورد خاص وجود دارد که قسمت خالی باشد، که به صورت مؤثر قانون را به یک قانون LIG تبدیل می‌کند؛ بنابراین زبان‌های نمایه سازی شدهٔ توزیعی یک اَبَرمجموعه از زبان‌های نمایه سازی شدهٔ خطی است.