گرامر نمایه‌سازی‌شده کیست؟ توضیح بده.
گرامر نمایه‌سازی شده تعمیم گرامر مستقل از متن است که غیرپایانه‌ها با لیستی از پرچم‌ها مجهز شده‌است. زبانی که به وسیلهٔ گرامر نمایه سازی شده تولید می‌شود زبان ایندکس شده نامیده می‌شود.تعریف.تعریف جدید از Hopcroft و Ullman.گرامر نمایه سازی شده به‌طور رسمی یک ۵تایی "G" = ⟨"N","T","F","P","S" تعریف می‌شود به طوریکه:در تولیدات مانند اشتقاق در گرامر نمایه سازی شده، رشتهٔ σ از نمادهای ایندکس به همهٔ نمادهای غیرترمینال "A" ∈ "N" متصل می‌شوند که توسط (A")σ" مشخص می‌شود. نمادهای ترمینال ممکن است با ایندکس پشته دنبال نشوند. برای نماد پشتهσ ∈ "F"* و رشتهٔ α ∈ ("N" ∪ "T")* از نمادهای غیرترمینال و ترمینال، (α)σ نتیجهٔ اتصال (σ) به همهٔ غیرترمینال‌ها در α را مشخص می‌کند. برای مثال اگر α برابر باشد به طوریکه "a","d" ∈ "T" ترمینال، و "B","D","E" ∈ "N" نمادهای غیرترمینال، آنگاه را مشخص می‌کند. با استفاده از این نشانه‌گذاری، هر تولید در "P" به این فرم می‌باشد:که A, B ∈ N نمادهای غیرترمینال، f ∈ F ایندکس، σ ∈F رشته از نمادهای ایندکس و (α ∈ (N ∪ T رشته از نمادهای ترمینال و غیرترمینال. بعضی نویسنده‌ها به جای "σ" ".." را برای نماد پشته در قوانین تولید می‌نویسند. قوانین نوع۱٬۲ و۳ به ترتیب به صورت A[..]→α[..], A[..]→B[f..] A[f..]→α[..], خوانده می‌شود.اشتقاق‌ها مانند اشتقاق در گرامر مستقل از متن می‌باشند جز نماد پشته که به هر نماد غیرترمینال متصل شده‌است. وقتی قاعده تولیدی مانند [A[σ] → B[σ]C[σ به کار رود، نماد پشته "A" در جفت "B" و "C" کپی می‌شود. علاوه براین، قانون ممکن است یک نماد ایندکس را روی پشته بگذارد یا بردارد.به‌طور رسمی رابطه ⇒ ("اشتقاق مستقیم") روی مجموعه&lt;"N"["F"*]∪"T")*") از فرم‌های ضروری اینگونه تعریف می‌شود:به طور معمول اشتقاق ⇒* بستار متعدی انعکاسی اشتقاق مستقیم ⇒ تعریف شده است. زبان "L"("G") = { w ∈ "T"*: "S" ⇒* w } مجموعه تمام رشته‌های نمادهای ترمینال اشتقاق شده از نماد شروع می‌باشد.تعریف اصلی توسط Aho.از نظر تاریخی، گرامر ایندکس شده توسط Aho (در ۱۹۶۸) با استفاده از یک فرمالیسم متفاوت معرفی شد. Aho یک گرامر ایندکس شده را یک ۵-تایی ("N","T","F","P","S") تعریف کرد به طوریکه:گرامر نمایه سازی شدهٔ خطی.Gerald Gazdar کلاس دیگری به نام گرامرهای نمایه سازی شدهٔ خطی (LIG) تعریف کرد با این شرط که حداکثر یک غیرترمینال در هر حاصل‌ضرب مخصوص دریافت استک باشد. در حالی که در گرامرهای ایندکس شدهٔ معمولی، تمام غیرترمینال‌ها نسخه‌هایی از استک را دریافت می‌کنند.به صورت رسمی، گرامر ایندکس شدهٔ خطی به طور مشابه با یک گرامر ایندکس شدهٔ معمولی تعریف می‌شود، اما شرط‌های فرم حاصل‌ضرب به صورت زیر اصلاح شده‌اند:که "A", "B", "f", σ, α به صورت فوق استفاده شده‌اند و β ∈ ("N" ∪ "T")* رشته‌ای از نمادهای ترمینال و غیرترمینال مانند α است. همچنین، رابطهٔ یک‌طرفهٔ ⇒ به صورتی مشابه فوق تعریف شده‌اند. این کلاس جدید از گرامرها یک کلاس اکیداً کوچکتر از زبان‌ها را تعریف می‌کند، که به کلاس‌های با وابستگی کم به متن متعلق هستند.زبان { "www": "w" ∈ {"a","b"}* } توسط یک گرامر ایندکس شده قابل تولید است، ولی توسط یک گرامر نمایه سازی شدهٔ خطی قابل تولید نیست. در حالی که { "a""n" "b""n" "c""n": n ≥ ۱ } توسط یک گرامر نمایه سازی شدهٔ خطی قابل تولید است.اگر هم قانون اصلی و هم قانون اصلی حاصل‌ضرب قابل قبول باشند، کلاس زبان به صورت زبان نمایه سازی شده باقی می‌ماند.مثال.فرض کنید σ نشان‌دهندهٔ مجموعهٔ دلخواهی از نمادهای استک باشد. می‌توانیم گرامری برای زبان "L" = {"a""n" "b""n" "c""n" | "n" ≥ ۱ } تعریف کنیم به طوری که:برای به دست آوردن رشتهٔ "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) در یک قانون بازنویسی، به صورت formula_1 هستند. نمادهای formula_2 و formula_3 نشان‌دهندهٔ رشته‌هایی از نمادهای ترمینال و/یا غیرترمینال هستند و به خاطر تعریف LIG، هر نماد غیرترمینالی باید یک استک خالی داشته باشد. البته این برعکس تعریف IGهاست: در یک IG، غیرترمینال‌هایی که در استک‌هایشان چیزی گذاشته نمی‌شود یا از آن‌ها چیزی برداشته نمی‌شود، باید دقیقاهمان استک غیرترمینال بازنویسی‌شده باشد؛ بنابراین به نحوی، به غیرترمینال‌هایی در formula_2 و formula_3 احتیاج داریم که علی‌رغم داشتن پشته‌های غیر خالی، طوری از خود رفتار نشان دهند که گویا پشته‌های خالی دارند.بیایید قانون formula_6 را به عنوان یک مورد مثال فرض کنیم. در تبدیل آن به یک IG، جایگزین formula_7 باید چیزی مثل formula_8 که بدون توجه به مقدار formula_9، دقیقاً مشابه formula_7 عمل کند. برای رسیدن به این هدف، می‌توانیم یک زوج قانون داشته باشیم که هر formula_8 را که formula_9 تهی نیست می‌گیرد و از پشته نمادها را برمی‌دارد. سپس، وقتی پشته خالی شد، می‌تواند به صورت formula_7 بازنویسی شود.formula_14formula_15می‌توانیم به صورت کلی این قاعده را به کار ببندیم تا از یک LIG، یک IG را به دست آوریم؛ بنابراین به طور مثال اگر LIG برای زبان formula_16 به صورت زیر باشد:formula_17formula_18formula_19formula_20formula_21قانون ضروری در اینجا یک قانون IG نیست، اما با استفاده از الگوریتم تبدیل بالا، می‌توانیم قوانین جدیدی برای formula_22 تعریف کنیم که گرامر را به صورت زیر تغییر می‌دهند:formula_23formula_24formula_25formula_18formula_19formula_20formula_21همه قوانین اکنون با تعریف یک IG به این صورت: در آن تمام غیرترمینال‌های در سمت راست یک قانون بازنویسی، نسخه‌ای از نماد بازنویسی شده در پشته را دریافت می‌کنند، مطابقت دارد؛ بنابراین گرامرهای ایندکس شده قادرند تمام زبان‌هایی را که گرامرهای ایندکس شدهٔ خطی وصف می‌کنند را وصف کنند.ارتباط با روش‌های دیگر.Vijay-Shanker و Weir (در ۱۹۹۴) نشان دادند که گرامرهای نمایه سازی شدهٔ خطی، گرامرهای ترکیبی دسته‌ای، گرامرهای درخت الحاقی، و گرامرهای سر، همه کلاس یکسانی از زبان‌های رشته‌ای را تعریف می‌کنند. تعریف رسمی آن‌ها از گرامرهای ایندکس شدهٔ خطی با تعریف فوقتفاوت دارد.LIGها (و هم‌ارزهای ضعیف آن‌ها) اکیداً ارزانتر (یعنی زیرمجموعهٔ مناسبی را تولید می‌کنند) از زبان‌هایی است که توسط یک خانواده از هم‌ارزهای ضعیف فرمالیسم شامل:LCFRS, MCTAG, MCFG و گرامرهای مینیمالیست (MGها) تولید می‌شوند. خانوادهٔ آخر را می‌توان همچنین به زمان چندجمله‌ای تجزیه کرد.گرامرهای نمایه سازی شدهٔ توزیعی.شکل دیگری از گرامرهای نمایه سازی شده که در ۱۹۹۳ توسط Staudacher معرفی شدند، کلاس گرامرهای نمایه سازی شدهٔ توزیعی (DIها) است. آنچه DIGها را از گرامرهای نمایه سازی شدهٔ Aho متمایز می‌سازد، انتشار ایندکس‌هاست. برخلاف IGهای Aho، که همهٔ پشتهٔ نماد را روی تمام غیرترمینال‌ها در مدت زمان یک عملیات بازنویسی توزیع می‌کند، DIGها پشته را به چند زیرپشته تقسیم می‌کند و زیرپشته‌ها را روی غیرترمینال‌های انتخابی توزیع می‌کند.طرح کلی برای یک قانون توزیع دودویی از DIG به صورت"X"["f"1..."f""i""f""i"+1..."f""n"] → α "Y"[f1..."f""i"] β "Z"["f""i"+1..."f""n"] γکه α و β و γ رشته‌های ترمینالی دلخواهی هستند. برای یک توزیع رشتهٔ سه‌تایی:"X"["f"1..."f""i""f""i"+1..."f""j""f""j"+1..."f""n"] → α "Y"[f1..."f""i"] β "Z"["f""i"+1..."f""j"] γ "W"["f""j"+1..."f""n"] ηو ترتیب برای تعداد بیشتری از غیرترمینال‌ها در دست راست قانون بازنویسی به همین صورت است. به‌طور کلی، اگر m غیرترمینال در سمت راست یک قانون بازنویسی وجود داشته باشد، پشته به m راه تقسیم شده و روی غیرترمینال‌های جدید توزیع می‌شود. توجه کنید که یک مورد خاص وجود دارد که قسمت خالی باشد، که به صورت مؤثر قانون را به یک قانون LIG تبدیل می‌کند؛ بنابراین زبان‌های نمایه سازی شدهٔ توزیعی یک اَبَرمجموعه از زبان‌های نمایه سازی شدهٔ خطی است.