تجزیه‌کننده ال‌ال

در علوم کامپیوتر، تجزیه‌کنندهٔ ال‌ال یک پارسر بالا به پایین برای یک زیرمجموعه از گرامرهای مستقل از متن است. این پارسر ورودی را از چپ به راست و بر اساس چپ ترین اشتقاق جملات می‌خواند. (از این رو 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’, ‘+’, ‘F’, ‘)’ را در پشته قرار می‌دهیم، عدد ۲ را در خروجی چاپ می‌کند. بنابراین پشته در این مرحله بدین صورت است:
[ (, S, +, F,), $ ]
در گام دوم پارسر ‘(’ را یه دلیل مطابقت از روی پشته و اول ورودی حذف می‌کند. حال پشته اینگونه است:
[ S, +, F,), $ ]
حال پارسر ‘a’ را به عنوان ورودی و عنصر روی پشته ‘S’ دارد. با توجه به جدول پارس قاعده شماره یک را به جای عنصر روی پشته بازنویسی می‌کند. عدد ۱ را در خروجی چاپ می‌کند. پشته به این صورت دیده می‌شود:
[ F, +, F,), $ ]
اکنون پارسر ورودی ‘a’ و عنصر روی پشته ‘F’ است. با توجه به جدول پارس در این مرحله شماره سه به عنوان قاعده مطابقت یافته انتخاب شده و جایگزین عنصر بالای پشته می‌شود. عدد ۳ را در خروجی چاپ می‌کند. اکنون پشته اینگونه است:
[ a, +, F,), $ ]
در ۲ گام بعدی پارسر ‘’, ‘’ را از ورودی خوانده، با عناصر بالای پشته مطابقت می‌دهد و آنها را حذف می‌کند. نتیجه کار این خواهد شد:
[ F,), $ ]
در ۳ گام بعدی کار بدین صورت ادامه می‌یابد که پارسر ‘F’ را از روی پشته با ‘a’ جایگزین می‌کند، شماره ۳ را بر روی خروجی چاپ می‌کند و ‘a’, ‘)’ را از روی ورودی و پشته حذف می‌کند. بنابراین پارسر با ‘$’ در پشته و ورودی مواجه می‌شود و به کارش پایان می‌دهد.

در این حال پارسر پیغام "رشته تایید شد" را گزارش می‌دهد و شماره قواعد زیر را چاپ می‌کند:
[ 2, 1, 3, 3 ]
در حقیقت این شماره قواعد چپ‌ترین اشتقاق رشته ورودی است:
S → (S + F) → (F + F) → (a + F) → (a + a)

پیاده‌سازی پارسر در C++

کد زیر پیاده‌سازی مثال مطرح شده در زبان C++ است:
int main(int argc, char **argv){
using namespace std;

if (argc <2)
{
cout <<"usage:\n\tll '(a+a)'" <<endl;
return 0;
}

// LL parser table, maps <non-terminal, terminal> pair to action
map<Symbols, map<Symbols, int>> table;
stack<Symbols>ss;// symbol stack
char *p;// input buffer

// initialize the symbols stack
ss.push(TS_EOS);// terminal, $
ss.push(NTS_S);// non-terminal, S

// initialize the symbol stream cursor
p = &argv[1][0];

// setup the parsing table
table[NTS_S][TS_L_PARENS] = 2;
        table[NTS_S][TS_A] = 1;
table[NTS_F][TS_A] = 3;

while(ss.size()> 0)
{
if(lexer(*p) == ss.top())
{
cout <<"Matched symbols: " <<lexer(*p) <<endl;
p++;
ss.pop();
}
else
{
cout <<"Rule " <<table[ss.top()][lexer(*p)] <<endl;
switch(table[ss.top()][lexer(*p)])
{
case 1:// 1. S → F
ss.pop();
ss.push(NTS_F);// F
break;

        case 2:// 2. S → (S + F)
ss.pop();
ss.push(TS_R_PARENS);//)
ss.push(NTS_F);// F
ss.push(TS_PLUS);// +
ss.push(NTS_S);// S
ss.push(TS_L_PARENS);// (break;

        case 3:// 3. F → a
ss.pop();
ss.push(TS_A);// a
break;

default:
cout <<"parsing table defaulted" <<endl;
return 0;
break;
}
}
}

cout <<"finished parsing" <<endl;

return 0;}

پیاده‌سازی پارسر در Python

# All constants are indexed from 0Term = 0Rule = 1# TerminalsT_LPAR = 0T_RPAR = 1T_A = 2T_PLUS = 3T_END = 4T_INVALID = 5# Non-terminalsN_S = 0N_F = 1# parse tabletable = [[1, -1, 0, -1, -1, -1],
         [-1, -1, 2, -1, -1, -1]]rules = [[(Rule,N_F)],
         [(Term,T_LPAR), (Rule,N_S), (Term,T_PLUS), (Rule,N_F), (Term,T_RPAR)],
         [(Term,T_A)]]stack = [(Term,T_END), (Rule,N_S)]def lexicalAnalysis(inputstring):
    print('Lexical analysis')
    tokens = []
    cdict = {'+': T_PLUS, '(': T_LPAR, ')': T_RPAR, 'a': T_A}
    for c in inputstring:
        tokens.append(cdict.get(c, T_INVALID))
    tokens.append(T_END)
    print(tokens)
    return tokensdef syntacticAnalysis(tokens):
    print('Syntactic analysis')
    position = 0
    while len(stack)> 0:
        (stype, svalue) = stack.pop()
        token = tokens[position]
        if stype == Term:
            if svalue == token:
                position += 1
                print('pop', svalue)
                if token == T_END:
                    print('input accepted')
            else:
                print('bad term on input:', token)
                break
        elif stype == Rule:
            print('svalue', svalue, 'token', token)
            rule = table[svalue][token]
            print('rule', rule)
            for r in reversed(rules[rule]):
                stack.append(r)
        print('stack', stack)inputstring = '(a+a)'syntacticAnalysis(lexicalAnalysis(inputstring))

ساخت جدول پارس پارسر LL(k)

تا اواسط دهه ۱۹۹۰ میلادی از آنجایی که حالت بد 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)

دو نوع مغایرت در LL(1) وجود دارد:

مغایرت First/First

مجموعه First دو گرامر متفاوت برای یک غیر پایانه متفاوت باشد. به عنوان مثال حالت زیر را در نظر بگیرید:
S -> E | E 'a'
E -> 'b' | ε

حالت خاص: بازگشتی چپ

بازگشتی چپ باعث به وجود آمدن یک مغایرت First/First در LL(1)می‌شود.
E -> E '+' term | alt1 | alt2

مغایرت First/Follow

مجموعه First و Follow یک گرامر هم پوشانی داشته باشند. یک رشته خالی در مجموعه First باعث ایجاد ابهام در انتخاب قاعده می‌شود. به عنوان مثال:
S -> A 'a' 'b'
A -> 'a' | ε

فاکتور گیری چپ

یک فاکتورگیری معمول "Factored Out" است.
A -> X | X Y Z
تبدیل می‌شود به
A -> X B
B -> Y Z | ε
می‌تواند هنگامی که دو قاعده مجزا با یک نماد شروع می‌شوند مثل مغایرت First/First استفاده شود.

مثال دیگر (کمی پیچیده تر) استفاده از مغایرت First/First بالاست:
S ->E | E 'a'
E -> 'b' | ε
تبدیل می‌شود به
S -> 'b' | ε | 'b' 'a' | 'a'
حال با فاکتورگیری چپ
S -> 'b' E | E
E -> 'a' | ε

جانشینی

جانشین کردن یک قاعده در قاعده دیگر به منظور حذف بازگشتی غیرمستقیم یا مغایرت First/Follow. نکته: جانشینی ممکن است باعث به وجود آمدن مغایرت First/First شود.

حذف بازگشتی چپ

یک مثال ساده برای حذف بازگشتی چپ: مثال زیر برای غیرپایانه E بازگشتی چپ دارد.
E -> E '+' T
  -> T
در رابطه Tها به وسیله ‘+’ از یکدیگر جدا می‌شوند. عبارت منظم آن T (+ T)* است. پس می‌توان آن را به صورت زیر بازنویسی کرد:
E -> T Z
Z -> '+' T Z
  -> ε
حال هیچ مغایرت یا بازگشتی چپی در هیج یک از قواعد وجود ندارد.

با این حال همه گرامرهای مستقل از متن گرامر معادل LL(k) ندارند، مثل:
S -> A | B
A -> 'a' A 'b' | ε
B -> 'a' B 'b' 'b' | ε
این مورد نشان می‌دهد که هیچ گرامر LL(k)ی وجود ندارد که بتواند رشته‌های تولید شده توسط زبان گرامر فوق را بپذیرد.