موضوع مقاله: گرامر نمایه‌سازی‌شده | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # گرامر نمایه‌سازی‌شده | مقدمه: گرامر نمایه‌سازی شده تعمیم گرامر مستقل از متن است که غیرپایانه‌ها با لیستی از پرچم‌ها مجهز شده‌است. | ## بخش 1: گرامر نمایه‌سازی‌شده | زبانی که به وسیلهٔ گرامر نمایه سازی شده تولید می‌شود زبان ایندکس شده نامیده می‌شود. تعریف تعریف جدید از Hopcroft و Ullman گرامر نمایه سازی شده به‌طور رسمی یک ۵تایی G = ⟨N,T,F,P,S تعریف می‌شود به طوریکه: N مجموعه‌ای از متغیرها یا نمادهای غیرترمینال T مجموعه الفبای نمادهای ترمینال F مجموعه نمادهای ایندکس S ∈ N نماد شروع P مجموعه متناهی از تولیدات در تولیدات مانند اشتقاق در گرامر نمایه سازی شده، رشتهٔ σ از نمادهای ایندکس به همهٔ نمادهای غیرترمینال A ∈ N متصل می‌شوند که توسط (A)σ مشخص می‌شود. برای نماد پشته σ ∈ F* و رشتهٔ α ∈ (N ∪ T)* از نمادهای غیرترمینال و ترمینال، (α)σ نتیجهٔ اتصال (σ) به همهٔ غیرترمینال‌ها در α را مشخص می‌کند. با استفاده از این نشانه‌گذاری، هر تولید در P به این فرم می‌باشد: [A[σ] → α[σ، [A[σ] → B[fσ، یا [A[fσ] → α[σ که A, B ∈ N نمادهای غیرترمینال، f ∈ F ایندکس، σ ∈F رشته از نمادهای ایندکس و (α ∈ (N ∪ T رشته از نمادهای ترمینال و غیرترمینال. اشتقاق‌ها مانند اشتقاق در گرامر مستقل از متن می‌باشند جز نماد پشته که به هر نماد غیرترمینال متصل شده‌است. وقتی قاعده تولیدی مانند [A[σ] → B[σ]C[σ به کار رود، نماد پشته A در جفت B و C کپی می‌شود. به‌طور رسمی رابطه ⇒ ("اشتقاق مستقیم") روی مجموعه<N[F*]∪T)*) از فرم‌های ضروری اینگونه تعریف می‌شود: اگر [A[σ] → α[σ از تولید نوع ۱ باشد، آنگاه β A[φ] γ ⇒ β α[φ] γ با استفاده از تعریف بالا. اگر [A[σ] → B[fσ از تولید نوع ۲ باشد، آنگاه β A[φ] γ ⇒ β B[fφ] γ که سمت راست ایندکس پشته از سمت چپ پشته φ با وارد کردن f داخلش به دست می‌آید. اگر [A[fσ] → α[σ از تولید نوع ۳ باشد، آنگاه β A[fφ] γ ⇒ β α[φ] γ، با استفادهٔ دوباره از تعریف [α[σ که اولین ایندکس f از سمت چپ پشته خارج می‌شود که به غیرترمینال‌های سمت راست توزیع شده است. زبان L(G) = { w ∈ T*: S ⇒* w } مجموعه تمام رشته‌های نمادهای ترمینال اشتقاق شده از نماد شروع می‌باشد. | ## بخش 2: گرامر نمایه‌سازی‌شده | تعریف اصلی توسط Aho از نظر تاریخی، گرامر ایندکس شده توسط Aho (در ۱۹۶۸) با استفاده از یک فرمالیسم متفاوت معرفی شد. Aho یک گرامر ایندکس شده را یک ۵-تایی (N,T,F,P,S) تعریف کرد به طوریکه: N الفبایی از متغیرها یا نمادهای غیرترمینال T یک الفبای متناهی از نمادهای غیرترمینال F ⊆ 2N × (N ∪ T)* یک مجموعهٔ متناهی که به طور معمول پرچم‌ها خوانده می‌شود (هر پرچم مجموعه‌ای از حاصل‌ضرب‌های ایندکس شده است) P ⊆ N × (NF* ∪ T)* مجموعهٔ حاصل‌ضرب‌هاست. در حالی که در گرامرهای ایندکس شدهٔ معمولی، تمام غیرترمینال‌ها نسخه‌هایی از استک را دریافت می‌کنند. به صورت رسمی، گرامر ایندکس شدهٔ خطی به طور مشابه با یک گرامر ایندکس شدهٔ معمولی تعریف می‌شود، اما شرط‌های فرم حاصل‌ضرب به صورت زیر اصلاح شده‌اند: A[σ] → α B[σ] β , A[σ] → α B[fσ] β , A[fσ] → α B[σ] β , که A, B, f, σ, α به صورت فوق استفاده شده‌اند و β ∈ (N ∪ T)* رشته‌ای از نمادهای ترمینال و غیرترمینال مانند α است. این کلاس جدید از گرامرها یک کلاس اکیداً کوچکتر از زبان‌ها را تعریف می‌کند، که به کلاس‌های با وابستگی کم به متن متعلق هستند. زبان { www: w ∈ {a,b}* } توسط یک گرامر ایندکس شده قابل تولید است، ولی توسط یک گرامر نمایه سازی شدهٔ خطی قابل تولید نیست. اگر هم قانون اصلی و هم قانون اصلی حاصل‌ضرب قابل قبول باشند، کلاس زبان به صورت زبان نمایه سازی شده باقی می‌ماند. قدرت محاسباتی زبان‌های ایندکس شدهٔ خطی زیرمجموعه‌ای از زبان‌های نمایه سازی شده هستند، بنابراین می‌توانیم تمام LIGها را به صورت IG تعریف کرده و با این کار LIGها را اکیداً کم‌قدرت‌تر از IGها کنیم. نمادهای و نشان‌دهندهٔ رشته‌هایی از نمادهای ترمینال و/یا غیرترمینال هستند و به خاطر تعریف LIG، هر نماد غیرترمینالی باید یک استک خالی داشته باشد. البته این برعکس تعریف IGهاست: در یک IG، غیرترمینال‌هایی که در استک‌هایشان چیزی گذاشته نمی‌شود یا از آن‌ها چیزی برداشته نمی‌شود، باید دقیقاهمان استک غیرترمینال بازنویسی‌شده باشد؛ بنابراین به نحوی، به غیرترمینال‌هایی در و احتیاج داریم که علی‌رغم داشتن پشته‌های غیر خالی، طوری از خود رفتار نشان دهند که گویا پشته‌های خالی دارند. | ## بخش 3: گرامر نمایه‌سازی‌شده | در تبدیل آن به یک IG، جایگزین باید چیزی مثل که بدون توجه به مقدار ، دقیقاً مشابه عمل کند. برای رسیدن به این هدف، می‌توانیم یک زوج قانون داشته باشیم که هر را که تهی نیست می‌گیرد و از پشته نمادها را برمی‌دارد. می‌توانیم به صورت کلی این قاعده را به کار ببندیم تا از یک LIG، یک IG را به دست آوریم؛ بنابراین به طور مثال اگر LIG برای زبان به صورت زیر باشد: قانون ضروری در اینجا یک قانون IG نیست، اما با استفاده از الگوریتم تبدیل بالا، می‌توانیم قوانین جدیدی برای تعریف کنیم که گرامر را به صورت زیر تغییر می‌دهند: همه قوانین اکنون با تعریف یک IG به این صورت: در آن تمام غیرترمینال‌های در سمت راست یک قانون بازنویسی، نسخه‌ای از نماد بازنویسی شده در پشته را دریافت می‌کنند، مطابقت دارد؛ بنابراین گرامرهای ایندکس شده قادرند تمام زبان‌هایی را که گرامرهای ایندکس شدهٔ خطی وصف می‌کنند را وصف کنند. ارتباط با روش‌های دیگر Vijay-Shanker و Weir (در ۱۹۹۴) نشان دادند که گرامرهای نمایه سازی شدهٔ خطی، گرامرهای ترکیبی دسته‌ای، گرامرهای درخت الحاقی، و گرامرهای سر، همه کلاس یکسانی از زبان‌های رشته‌ای را تعریف می‌کنند. گرامرهای نمایه سازی شدهٔ توزیعی شکل دیگری از گرامرهای نمایه سازی شده که در ۱۹۹۳ توسط Staudacher معرفی شدند، کلاس گرامرهای نمایه سازی شدهٔ توزیعی (DIها) است. آنچه DIGها را از گرامرهای نمایه سازی شدهٔ Aho متمایز می‌سازد، انتشار ایندکس‌هاست. برخلاف IGهای Aho، که همهٔ پشتهٔ نماد را روی تمام غیرترمینال‌ها در مدت زمان یک عملیات بازنویسی توزیع می‌کند، DIGها پشته را به چند زیرپشته تقسیم می‌کند و زیرپشته‌ها را روی غیرترمینال‌های انتخابی توزیع می‌کند. به‌طور کلی، اگر m غیرترمینال در سمت راست یک قانون بازنویسی وجود داشته باشد، پشته به m راه تقسیم شده و روی غیرترمینال‌های جدید توزیع می‌شود. | ## جمع‌بندی | توجه کنید که یک مورد خاص وجود دارد که قسمت خالی باشد، که به صورت مؤثر قانون را به یک قانون LIG تبدیل می‌کند؛ بنابراین زبان‌های نمایه سازی شدهٔ توزیعی یک اَبَرمجموعه از زبان‌های نمایه سازی شدهٔ خطی است.