تجزیه‌کننده ال‌ال
در علوم کامپیوتر، تجزیه‌کنندهٔ ال‌ال یک پارسر بالا به پایین برای یک زیرمجموعه از گرامرهای مستقل از متن است. این پارسر ورودی را از چپ به راست و بر اساس چپ ترین اشتقاق جملات می‌خواند. (از این رو LL با LR مقایسه می‌شود) به مجموعه گرامرهایی که به وسیله این روش قابل پارس هستند، گرامرهای LL می‌گویند.
پارسر LL را در صورتی که از k توکن در هنگام پارس جملات استفاده کنیم پارسر LL(k) گوییم. اگر چنین پارسری برای گرامری خاص وجود داشت که می‌توانست جملات این گرامر را بدون بازگشت به عقب پارس کند آنگاه گرامر را گرامر LL(k) می‌گوییم. همچنین زبانی که یک گرامر LL(k) دارد به عنوان زبان LL(k) شناخته می‌شود. زبان‌های LL(k+n) وجود دارند که LL(k) نیستند. به عنوان نتیجه می‌توان گفت که همه زبان‌های مستقل از متن LL(k) نیستند. اگر مقدار k به یک مقدار متناهی مقید نشده باشد پارسر LL(k) را پارسر LL(*) نیز می‌گویند اما می‌تواند با شناسایی توکن‌های دنباله رو متعلق به یک زبان منظم تصمیم بگیرد. (به عنوان مثال با استفاده از DFA)
از منافع بزرگ گرامرهای LL مخصوصاً LL(1) این است که ساخت پارسر آن‌ها بسیار ساده بوده و به همین دلیل زبان‌های کامپیوتری زیادی به صورت LL(1) طراحی شده‌اند. پارسرهای LL همچون پارسر LR براساس جدول پارس کار می‌کنند. گرامر LL همچنین به عنوان یک گرامر پیشگوی دقیق که می‌تواند به آسانی با دست نوشته شود نیز شناخته می‌شود. این مقاله دربارهٔ جداول پارس، برخی خواص رسمی و پارس پیشگویانه است.
پارسر تنها بر روی رشته‌های زبان‌های مستقل از متن خاصی کار می‌کند.
پارسر از موارد زیر تشکیل شده‌است:
پارسر قواعد به دست آمد جدول پارس از طریق تطابق نماد روی پشته به عنوان سطر و با عنصر روی ورودی به عنوان ستون را تأیید می‌کند.
در ابتدای کار پارسر دو نماد زیر را شامل می‌شود: از نماد ‘$’ برای نشان دادن پایان پشته و جریان ورودی و از ‘S’ برای نشان دادن گرامر شروع استفاده می‌شود. پارسر با توجه به محتویات پشته سعی در بازنویسی رشته ورودی دارد.
برای بررسی روش کار ابتدا گرامر ساده زیر را در نظر بگیرید رشته ورودی نیز بدین صورت است:
جدول پارس برای گرامر بالا به صورت زیر است: (برای ساخت جدول پارس همه پایانه‌ها را به عنوان ستون و غیر پایانه‌ها را به عنوان سطر در نظر می‌گیریم. سپس شماره عبارت را در خانه حاصل از سطر و ستون قرار می‌دهیم. برای مثال ‘(’ و ‘S’ شماره ۲ را قرار می‌دهیم.)
در هر مرحله پارسر نماد موجود بعدی در رشته ورودی و عنصر بالای پشته را می‌خواند. اگر عنصر خوانده شده از ورودی و بالای پشته یکسان بودند آن‌ها را رها کرده و در صورت یکسان نبودن نماد خوانده شده از ورودی را بر بالای پشته قرار می‌دهد. پس، در گام اول پارسر عنصر اول ورودی ‘(’ و عنصر بالای پشته ‘S’ را می‌خواند. در جدول پارس با توجه به ستون ‘(’ و سطر ‘S’ به قاعده شماره ۲ می‌رسد. بنابراین پارسر قاعده شماره ۲ را به جای عنصر بالای پشته قرار می‌دهد. پارسر ‘S’ را از پشته برداشته و ‘(’, ‘S’, ‘+’, ‘F’, ‘)’ را در پشته قرار می‌دهیم، عدد ۲ را در خروجی چاپ می‌کند. بنابراین پشته در این مرحله بدین صورت است:
در گام دوم پارسر ‘(’ را یه دلیل مطابقت از روی پشته و اول ورودی حذف می‌کند. حال پشته اینگونه است:
حال پارسر ‘a’ را به عنوان ورودی و عنصر روی پشته ‘S’ دارد. با توجه به جدول پارس قاعده شماره یک را به جای عنصر روی پشته بازنویسی می‌کند. عدد ۱ را در خروجی چاپ می‌کند. پشته به این صورت دیده می‌شود:
اکنون پارسر ورودی ‘a’ و عنصر روی پشته ‘F’ است. با توجه به جدول پارس در این مرحله شماره سه به عنوان قاعده مطابقت یافته انتخاب شده و جایگزین عنصر بالای پشته می‌شود. عدد ۳ را در خروجی چاپ می‌کند. اکنون پشته اینگونه است:
در ۲ گام بعدی پارسر ‘’, ‘’ را از ورودی خوانده، با عناصر بالای پشته مطابقت می‌دهد و آنها را حذف می‌کند. نتیجه کار این خواهد شد:
در ۳ گام بعدی کار بدین صورت ادامه می‌یابد که پارسر ‘F’ را از روی پشته با ‘a’ جایگزین می‌کند، شماره ۳ را بر روی خروجی چاپ می‌کند و ‘a’, ‘)’ را از روی ورودی و پشته حذف می‌کند. بنابراین پارسر با ‘$’ در پشته و ورودی مواجه می‌شود و به کارش پایان می‌دهد. در این حال پارسر پیغام "رشته تایید شد" را گزارش می‌دهد و شماره قواعد زیر را چاپ می‌کند:
در حقیقت این شماره قواعد چپ‌ترین اشتقاق رشته ورودی است: کد زیر پیاده‌سازی مثال مطرح شده در زبان C++ است: int main(int argc, char **argv)Term = 0 Rule = 1 T_LPAR = 0 T_RPAR = 1 T_A = 2 T_PLUS = 3 T_END = 4 T_INVALID = 5 N_S = 0 N_F = 1 table = 1, -1, 0, -1, -1, -1],
rules = (Rule,N_F)],
stack = [(Term,T_END), (Rule,N_S)]
def lexicalAnalysis(inputstring):
def syntacticAnalysis(tokens):
inputstring = '(a+a)' syntacticAnalysis(lexicalAnalysis(inputstring))
همانگونه که در مثال قابل مشاهده است پارسر سه نوع عملیات با توجه به بالای پشته پایانه، غیر پایانه یا نماد ‘$’ باشد انجام می‌دهد: این گام‌ها تا توقف پارس تکرار می‌شوند، سپس بلافاصله پیغام موفقیت به همراه چپ‌ترین اشتقاق چاپ شده یا پیغام خطا را نمایش می‌دهد.
به منظور پر کردن جدول پارس باید تعیین کرد در صورت مشاهده غیرپایانه A در بالای پشته و a در جریان ورودی کدام گرامر می‌بایست انتخاب شود. به عنوان مثال در عبارت A → w خیلی راحت می‌توان گفت w حداقل یک رشته است که با a شروع شده‌است. برای رسیدن به این هدف مجموعه First(w) را با نماد Fi(w) به صورت مجموعه پایانه‌هایی که در ابتدای رشته w یا ε در صورتی که رشته خالی در w وجود داشته باشد تعریف می‌شود. برای گرامری به صورت A1 → w1, ... , An → wn مجموعه Fi(wi) و Fi(Ai) با هر قاعده‌ای به صورت زیر هستند: متأسفانه مجموعه Firstها به تنهایی برای محاسبه جدول پارس کافی نیست. به این دلیل که دست راست w ممکن است در یک قاعده بی‌نهایت رشته خالی به دام بیفتد بنابراین پارسر باید از قاعده A → w در صورتی که ε عضو Fi(w) و عنصری در ورودی است که می‌تواند به دنبال A بیاید استفاده کند. بنابرین به تعریف مجموعه Follow نیاز است که در اینجا Fo(A) نوشته می‌شود و به مجموعه‌ای از پایانه‌ها همچون a اطلاق می‌شود که در قاعده به صورت αAaβ وجود دارد و می‌تواند از نماد شروع اشتقاق شود. محاسبه مجموعه Follow برای غیرپایانه‌ها به صورت زیر ادامه می‌یابد: حال می‌توان دقیق مشخص کرد کدام قاعده در جدول پارس قرار خواهد گرفت. فرض کنید منظور از T[A, a] منظور خانه‌ای از جدول است که با غیرپایانه A و پایانه a به دست می‌آید. T[A, a] شامل قاعده A → w می‌شود اگر و تنها اگر a در مجموعه Fi(w) باشد یا ε در Fi(w) و a در Fo(A) باشد. اگر در هر خانه از جدول حداکثر یک قاعده قرار بگیرد پارسر همیشه می‌توان بفمد کدام قاعده را انخاب کرده و رشته را بدون عقب‌گرد پیمایش کند. دقیقاً به همین دلیل است که به این گرامر، گرامر LL(1) گفته می‌شود.
تا اواسط دهه ۱۹۹۰ میلادی از آنجایی که حالت بد LL(k) تابع نمایی از درجه k است باور عام بر این بود که پارسر LL(k) (برای k بزرگتر از ۱) غیرعملی است. این باور رفته رفته بعد از انتشار Purdue Compiler Construction Tool Set در ۱۹۹۲ و اثبات این موضوع که بسیاری از زبان‌های برنامه‌نویسی بدون اینکه از حالات بد اثر بپذیرند با LL(k) قابل پارس هستند تغییر کرد. علاوه بر این در بعضی موارد خاص پارس LL با بی‌نهایت lookahead امکان‌پذیر است. در مقابل مولد پارسرهای قدیمی مثل yacc از جدول پارس LALR(1) برای ساخت نسخه محدود شده از LR(1) با یک توکن lookahead استفاده می‌کند.
همان گونه که در مقدمه گفته شد پارسر LL(1) گرامرهای LL(1) را شناسایی می‌کند که قسمتی از گرامرهای مستقل از متن را تشکیل می‌دهند. بنابراین پارسر LL(1) قادر به شناسایی تمام گرامرهای مستقل از متن نیست. زبان LL(1) یک زیر مجموعه از زبان‌های LR(1) است که LR(1) نیز خود زیر مجموعه از زبان‌های مستقل از متن است. برای این که یک گرامر مستقل از متن LL(1) باشد باید برخی مغایرت‌ها وجود نداشته باشند که در این جا توضیح خواهیم داد.
A یک غیرپایانه است. First(A) مجموعه تمام پایانه‌هایی است که می‌توانند در ابتدای تمام رشته‌هایی که از A اشتقاق می‌شوند قرار دارند. Follow(A) اجتماع تمام First(B) هاست که B هر غیرپایانه ایست که بلافاصله بعد از A در سمت راست قواعد تولید دیده می‌شود.
دو نوع مغایرت در LL(1) وجود دارد:
مجموعه First دو گرامر متفاوت برای یک غیر پایانه متفاوت باشد. به عنوان مثال حالت زیر را در نظر بگیرید: بازگشتی چپ باعث به وجود آمدن یک مغایرت First/First در LL(1)می‌شود. مجموعه First و Follow یک گرامر هم پوشانی داشته باشند. یک رشته خالی در مجموعه First باعث ایجاد ابهام در انتخاب قاعده می‌شود. به عنوان مثال: یک فاکتورگیری معمول "Factored Out" است.
تبدیل می‌شود به
می‌تواند هنگامی که دو قاعده مجزا با یک نماد شروع می‌شوند مثل مغایرت First/First استفاده شود. مثال دیگر (کمی پیچیده تر) استفاده از مغایرت First/First بالاست:
تبدیل می‌شود به
حال با فاکتورگیری چپ جانشین کردن یک قاعده در قاعده دیگر به منظور حذف بازگشتی غیرمستقیم یا مغایرت First/Follow. نکته: جانشینی ممکن است باعث به وجود آمدن مغایرت First/First شود.
یک مثال ساده برای حذف بازگشتی چپ: مثال زیر برای غیرپایانه E بازگشتی چپ دارد.
در رابطه Tها به وسیله ‘+’ از یکدیگر جدا می‌شوند. عبارت منظم آن T (+ T)* است. پس می‌توان آن را به صورت زیر بازنویسی کرد:
حال هیچ مغایرت یا بازگشتی چپی در هیج یک از قواعد وجود ندارد. با این حال همه گرامرهای مستقل از متن گرامر معادل LL(k) ندارند، مثل:
این مورد نشان می‌دهد که هیچ گرامر LL(k)ی وجود ندارد که بتواند رشته‌های تولید شده توسط زبان گرامر فوق را بپذیرد.