موضوع مقاله: تجزیه‌کننده ال‌ال | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # تجزیه‌کننده ال‌ال | مقدمه: در علوم کامپیوتر، تجزیه‌کنندهٔ ال‌ال یک پارسر بالا به پایین برای یک زیرمجموعه از گرامرهای مستقل از متن است. | ## بخش 1: تجزیه‌کننده ال‌ال | (از این رو LL با LR مقایسه می‌شود) به مجموعه گرامرهایی که به وسیله این روش قابل پارس هستند، گرامرهای LL می‌گویند. پارسر LL را در صورتی که از k توکن در هنگام پارس جملات استفاده کنیم پارسر LL(k) گوییم. اگر چنین پارسری برای گرامری خاص وجود داشت که می‌توانست جملات این گرامر را بدون بازگشت به عقب پارس کند آنگاه گرامر را گرامر LL(k) می‌گوییم. اگر مقدار k به یک مقدار متناهی مقید نشده باشد پارسر LL(k) را پارسر LL(*) نیز می‌گویند اما می‌تواند با شناسایی توکن‌های دنباله رو متعلق به یک زبان منظم تصمیم بگیرد. (به عنوان مثال با استفاده از DFA) از منافع بزرگ گرامرهای LL مخصوصاً LL(1) این است که ساخت پارسر آن‌ها بسیار ساده بوده و به همین دلیل زبان‌های کامپیوتری زیادی به صورت LL(1) طراحی شده‌اند. گرامر LL همچنین به عنوان یک گرامر پیشگوی دقیق که می‌تواند به آسانی با دست نوشته شود نیز شناخته می‌شود. (ساخته شده از گرامر) پشته برای ذخیره کردن پایانه‌ها و غیرپایانه‌هایی که تا کنون از گرامر پارس شده‌اند. یک جدول پارس که مشخص می‌کند با توجه به ورودی و نماد روی پشته کدام گرامر قبول شود. پارسر قواعد به دست آمد جدول پارس از طریق تطابق نماد روی پشته به عنوان سطر و با عنصر روی ورودی به عنوان ستون را تأیید می‌کند. در ابتدای کار پارسر دو نماد زیر را شامل می‌شود: [ S, $ ] از نماد ‘$’ برای نشان دادن پایان پشته و جریان ورودی و از ‘S’ برای نشان دادن گرامر شروع استفاده می‌شود. F → a رشته ورودی نیز بدین صورت است: (a + a) جدول پارس برای گرامر بالا به صورت زیر است: (برای ساخت جدول پارس همه پایانه‌ها را به عنوان ستون و غیر پایانه‌ها را به عنوان سطر در نظر می‌گیریم. برای مثال ‘(’ و ‘S’ شماره ۲ را قرار می‌دهیم.) a + $ S 2 - 1 - - F - - 3 - - (نکته: همچنین یک ستون را به پایانه‌های خاص اختصاص می‌دهیم، در این مثال ‘$’ را می‌توان برشمرد.) روند پارس در هر مرحله پارسر نماد موجود بعدی در رشته ورودی و عنصر بالای پشته را می‌خواند. اگر عنصر خوانده شده از ورودی و بالای پشته یکسان بودند آن‌ها را رها کرده و در صورت یکسان نبودن نماد خوانده شده از ورودی را بر بالای پشته قرار می‌دهد. | ## بخش 2: تجزیه‌کننده ال‌ال | پارسر ‘S’ را از پشته برداشته و ‘(’, ‘S’, ‘+’, ‘F’, ‘)’ را در پشته قرار می‌دهیم، عدد ۲ را در خروجی چاپ می‌کند. بنابراین پشته در این مرحله بدین صورت است: [ (, S, +, F,), $ ] در گام دوم پارسر ‘(’ را یه دلیل مطابقت از روی پشته و اول ورودی حذف می‌کند. حال پشته اینگونه است: [ S, +, F,), $ ] حال پارسر ‘a’ را به عنوان ورودی و عنصر روی پشته ‘S’ دارد. پشته به این صورت دیده می‌شود: [ F, +, F,), $ ] اکنون پارسر ورودی ‘a’ و عنصر روی پشته ‘F’ است. با توجه به جدول پارس در این مرحله شماره سه به عنوان قاعده مطابقت یافته انتخاب شده و جایگزین عنصر بالای پشته می‌شود. اکنون پشته اینگونه است: [ a, +, F,), $ ] در ۲ گام بعدی پارسر ‘’, ‘’ را از ورودی خوانده، با عناصر بالای پشته مطابقت می‌دهد و آنها را حذف می‌کند. نتیجه کار این خواهد شد: [ F,), $ ] در ۳ گام بعدی کار بدین صورت ادامه می‌یابد که پارسر ‘F’ را از روی پشته با ‘a’ جایگزین می‌کند، شماره ۳ را بر روی خروجی چاپ می‌کند و ‘a’, ‘)’ را از روی ورودی و پشته حذف می‌کند. اگر در جدول با عنصر مورد نظر مقداری تعریف نشده بود یک خطا گزارش کرده و از ادامه پارس صرف نظر می‌کنیم. در صورتی که دو عنصر یکسان بودند هر دو حذف می‌شوند، در غیر این صورت خطا گزارش شده و ادامه کار متوقف می‌شود. اگر در بالای پشته و ورودی ‘$’ قرار داشت موفقیت پارس را گزارش می‌دهد، در هر حالتی غیر از این مورد خطا گزارش شده و ادامه کار متوقف می‌شود. این گام‌ها تا توقف پارس تکرار می‌شوند، سپس بلافاصله پیغام موفقیت به همراه چپ‌ترین اشتقاق چاپ شده یا پیغام خطا را نمایش می‌دهد. ساخت جدول پارس پارسر LL(1) به منظور پر کردن جدول پارس باید تعیین کرد در صورت مشاهده غیرپایانه A در بالای پشته و a در جریان ورودی کدام گرامر می‌بایست انتخاب شود. به عنوان مثال در عبارت A → w خیلی راحت می‌توان گفت w حداقل یک رشته است که با a شروع شده‌است. | ## بخش 3: تجزیه‌کننده ال‌ال | برای رسیدن به این هدف مجموعه First(w) را با نماد Fi(w) به صورت مجموعه پایانه‌هایی که در ابتدای رشته w یا ε در صورتی که رشته خالی در w وجود داشته باشد تعریف می‌شود. به این دلیل که دست راست w ممکن است در یک قاعده بی‌نهایت رشته خالی به دام بیفتد بنابراین پارسر باید از قاعده A → w در صورتی که ε عضو Fi(w) و عنصری در ورودی است که می‌تواند به دنبال A بیاید استفاده کند. بنابرین به تعریف مجموعه Follow نیاز است که در اینجا Fo(A) نوشته می‌شود و به مجموعه‌ای از پایانه‌ها همچون a اطلاق می‌شود که در قاعده به صورت αAaβ وجود دارد و می‌تواند از نماد شروع اشتقاق شود. فرض کنید منظور از T[A, a] منظور خانه‌ای از جدول است که با غیرپایانه A و پایانه a به دست می‌آید. اگر در هر خانه از جدول حداکثر یک قاعده قرار بگیرد پارسر همیشه می‌توان بفمد کدام قاعده را انخاب کرده و رشته را بدون عقب‌گرد پیمایش کند. ساخت جدول پارس پارسر LL(k) تا اواسط دهه ۱۹۹۰ میلادی از آنجایی که حالت بد LL(k) تابع نمایی از درجه k است باور عام بر این بود که پارسر LL(k) (برای k بزرگتر از ۱) غیرعملی است. مغایرت همان گونه که در مقدمه گفته شد پارسر LL(1) گرامرهای LL(1) را شناسایی می‌کند که قسمتی از گرامرهای مستقل از متن را تشکیل می‌دهند. زبان LL(1) یک زیر مجموعه از زبان‌های LR(1) است که LR(1) نیز خود زیر مجموعه از زبان‌های مستقل از متن است. برای این که یک گرامر مستقل از متن LL(1) باشد باید برخی مغایرت‌ها وجود نداشته باشند که در این جا توضیح خواهیم داد. First(A) مجموعه تمام پایانه‌هایی است که می‌توانند در ابتدای تمام رشته‌هایی که از A اشتقاق می‌شوند قرار دارند. حذف بازگشتی چپ یک مثال ساده برای حذف بازگشتی چپ: مثال زیر برای غیرپایانه E بازگشتی چپ دارد. پس می‌توان آن را به صورت زیر بازنویسی کرد: E -> T Z Z -> '+' T Z -> ε حال هیچ مغایرت یا بازگشتی چپی در هیج یک از قواعد وجود ندارد. | ## جمع‌بندی | با این حال همه گرامرهای مستقل از متن گرامر معادل LL(k) ندارند، مثل: S -> A | B A -> 'a' A 'b' | ε B -> 'a' B 'b' 'b' | ε این مورد نشان می‌دهد که هیچ گرامر LL(k)ی وجود ندارد که بتواند رشته‌های تولید شده توسط زبان گرامر فوق را بپذیرد.