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

پارسر تنها بر روی رشته‌های زبان‌های مستقل از متن خاصی کار می‌کند.

پارسر از موارد زیر تشکیل شده‌است:

• بافر ورودی برای نگهداری رشته ورودی. (ساخته شده از گرامر)
• پشته برای ذخیره کردن پایانه‌ها و غیرپایانه‌هایی که تا کنون از گرامر پارس شده‌اند.
• یک جدول پارس که مشخص می‌کند با توجه به ورودی و نماد روی پشته کدام گرامر قبول شود.

پارسر قواعد به دست آمد جدول پارس از طریق تطابق نماد روی پشته به عنوان سطر و با عنصر روی ورودی به عنوان ستون را تأیید می‌کند.

در ابتدای کار پارسر دو نماد زیر را شامل می‌شود:

[ S, $ ]

از نماد ‘$’ برای نشان دادن پایان پشته و جریان ورودی و از ‘S’ برای نشان دادن گرامر شروع استفاده می‌شود. پارسر با توجه به محتویات پشته سعی در بازنویسی رشته ورودی دارد.

شروع

برای بررسی روش کار ابتدا گرامر ساده زیر را در نظر بگیرید

1. S → F
2. S → (S + F)
3. F → a

رشته ورودی نیز بدین صورت است:

(a + a)

جدول پارس برای گرامر بالا به صورت زیر است: (برای ساخت جدول پارس همه پایانه‌ها را به عنوان ستون و غیر پایانه‌ها را به عنوان سطر در نظر می‌گیریم. سپس شماره عبارت را در خانه حاصل از سطر و ستون قرار می‌دهیم. برای مثال ‘(’ و ‘S’ شماره ۲ را قرار می‌دهیم.)

(نکته: همچنین یک ستون را به پایانه‌های خاص اختصاص می‌دهیم، در این مثال ‘$’ را می‌توان برشمرد.)

روند پارس

در هر مرحله پارسر نماد موجود بعدی در رشته ورودی و عنصر بالای پشته را می‌خواند. اگر عنصر خوانده شده از ورودی و بالای پشته یکسان بودند آن‌ها را رها کرده و در صورت یکسان نبودن نماد خوانده شده از ورودی را بر بالای پشته قرار می‌دهد.
پس، در گام اول پارسر عنصر اول ورودی ‘(’ و عنصر بالای پشته ‘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 0

Term = 0
Rule = 1
# Terminals
T_LPAR = 0
T_RPAR = 1
T_A = 2
T_PLUS = 3
T_END = 4
T_INVALID = 5
# Non-terminals
N_S = 0
N_F = 1
# parse table
table = [[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 tokens

def 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))

همانگونه که در مثال قابل مشاهده است پارسر سه نوع عملیات با توجه به بالای پشته پایانه، غیر پایانه یا نماد ‘$’ باشد انجام می‌دهد:

• اگر عنصر بالای پشته یک غیر پایانه باشد در جدول پارس با توجه این غیرپایانه و عنصر ورودی به دنبال گرامری جهت جایگزین کردن آن در بالای پشته می‌گردد. شماره گرامر را در خروجی چاپ می‌کند. اگر در جدول با عنصر مورد نظر مقداری تعریف نشده بود یک خطا گزارش کرده و از ادامه پارس صرف نظر می‌کنیم.
• اگر عنصر بالای پشته پایانه باشد مطابقت آن را با عنصر ورودی بررسی می‌کند. در صورتی که دو عنصر یکسان بودند هر دو حذف می‌شوند، در غیر این صورت خطا گزارش شده و ادامه کار متوقف می‌شود.
• اگر در بالای پشته و ورودی ‘$’ قرار داشت موفقیت پارس را گزارش می‌دهد، در هر حالتی غیر از این مورد خطا گزارش شده و ادامه کار متوقف می‌شود.
  

این گام‌ها تا توقف پارس تکرار می‌شوند، سپس بلافاصله پیغام موفقیت به همراه چپ‌ترین اشتقاق چاپ شده یا پیغام خطا را نمایش می‌دهد.

به منظور پر کردن جدول پارس باید تعیین کرد در صورت مشاهده غیرپایانه A در بالای پشته و a در جریان ورودی کدام گرامر می‌بایست انتخاب شود. به عنوان مثال در عبارت A → w خیلی راحت می‌توان گفت w حداقل یک رشته است که با a شروع شده‌است. برای رسیدن به این هدف مجموعه First(w) را با نماد Fi(w) به صورت مجموعه پایانه‌هایی که در ابتدای رشته w یا ε در صورتی که رشته خالی در w وجود داشته باشد تعریف می‌شود. برای گرامری به صورت A1 → w1, ... , An → wn مجموعه Fi(wi) و Fi(Ai) با هر قاعده‌ای به صورت زیر هستند:

1. همه Fi(wi) و Fi(Ai) را به تهی مقدار دهی اولیه می‌شوند.
2. افزودن Fi(wi) به Fi(Ai) هرگاه رابطه Ai → wi وجود داشته باشد و Fi به صورت زیر باشد:
   1. برای هر پایانه a: Fi(a w') = { a }
   2. برای هر غیرپایانه که Fi(Ai) آن شامل ε نیست: Fi(A w') = Fi(A)
   3. برای هر غیرپایانه که Fi(Ai) آن شامل ε است: Fi(A w') = Fi(A) \ { ε } ∪ Fi(w')
   4. Fi(ε) = { ε }
3. افزودن Fi(wi) به Fi(Ai) برای هر Ai → wi
4. تکرار گام‌های ۲ و ۳ تا تمام Fiها دیگر تغییر نکنند.
   

متأسفانه مجموعه Firstها به تنهایی برای محاسبه جدول پارس کافی نیست. به این دلیل که دست راست w ممکن است در یک قاعده بی‌نهایت رشته خالی به دام بیفتد بنابراین پارسر باید از قاعده A → w در صورتی که ε عضو Fi(w) و عنصری در ورودی است که می‌تواند به دنبال A بیاید استفاده کند. بنابرین به تعریف مجموعه Follow نیاز است که در اینجا Fo(A) نوشته می‌شود و به مجموعه‌ای از پایانه‌ها همچون a اطلاق می‌شود که در قاعده به صورت αAaβ وجود دارد و می‌تواند از نماد شروع اشتقاق شود. محاسبه مجموعه Follow برای غیرپایانه‌ها به صورت زیر ادامه می‌یابد:

1. همه Fo(Ai) را با تهی مقدار دهی اولیه می‌کند.
2. اگر قاعده به صورت Aj → wAiw’ وجود داشت آنگاه:
   1. اگر پایانه a در Fi(w') وجود داشت آن را به Fo(Ai) اضافه می‌کند.
   2. اگر ε در Fi(w') وجود داشت آنگاه Fo(Aj) را به Fo(Ai) اضافه می‌کند.
3. اگر طول رشته w’ صفر باشد آنگاه Fo(Aj) را به Fo(Ai) اضافه می‌کند.
4. گام ۲ تا زمانی که دیگر هیچ یک از مجموعه‌های Fo تغییر نکند انجام می‌شود.
   

حال می‌توان دقیق مشخص کرد کدام قاعده در جدول پارس قرار خواهد گرفت. فرض کنید منظور از 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)

دو نوع مغایرت در 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' | ε

راه حل مغایرات LL(1)

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

یک فاکتورگیری معمول "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)ی وجود ندارد که بتواند رشته‌های تولید شده توسط زبان گرامر فوق را بپذیرد.