المحلل اللغوي LL

المحلل يعمل على سلاسل من قواعد السياق الحرقواعد خالية من السياق.

المحلل يتكون من

• وجود مخزن مرحلي للمدخلات صوان (معلوماتية)، يجري سلسلة المدخلات (الذي بنته القاعدة)
• مكدس لتخزين المحطات الطرفية والغير طرفية من القاعدة لتحليلها
• جدول التحليل الذي يقول ما حكم القاعدة (إن وجدت) التي سوف تطبق بإعطاء الرموز في أعلى المكدس الخاص به ورمز المدخلات التالي.

المحلل يطبق الحكم الذي يجده في الجدول عن طريق مطابقة الرمز أعلى المكدس (صف) مع الرمز الحالي في تدفق المدخلات (العمود). عندما يبدأ محلل، المكدس يحتوي بالفعل على رمزين: [ S, $ ] حيث '$' هو محطة طرفية خاصة للإشارة إلى أسفل المكدس ونهاية تدفق المدخلات، و'S' هو رمز البداية للقاعدة. المحلل سوف يحاول إعادة كتابة محتويات هذا المكدس على ما يراه على تدفق المدخلات. ومع ذلك، فإنه يحتفظ فقط في مكدس على ما هو ما زال بحاجة إلى إعادة صياغة.

(لاحظ أن هناك أيضا عمود للمحطة الطرفية الخاصة، الممثلة هنا بـ $، التي تستخدم لتشير إلى نهاية تدفق المدخلات.)

[ (, S, +, F, ), $ ]

[ S, +, F, ), $ ]

[ F, +, F, ), $ ]

[ a, +, F, ), $ ]

[ F, ), $ ]

في هذه الحالة المحلل سوف يقوم بعمل التقرير إلى أنه وافق على سلسلة المدخلات ويكتب القائمة التالية من عدد القواعد إلى تدفق الإخراج:

[ 2, 1, 3, 3 ]

هذا في الواقع هو قائمة من القواعد للاستخلاص أقصى اليسارقواعد خالية من السياق من سلسلة المدخلات، والتي هي كالتالي:

S → ( S + F ) → ( F + F ) → (a + F ) → (a + a)

ما يلي يتبع تنفيذ C++ على أساس جدول محلل LL للغة في المثال التالي:

#include <iostream>
#include <map>
#include <stack>

enum Symbols {
	// the symbols:
	// Terminal symbols:
	TS_L_PARENS,	// (
	TS_R_PARENS,	//)
	TS_A,		// a
	TS_PLUS,	// +
	TS_EOS,		// $, in this case corresponds to '\0'
	TS_INVALID,	// invalid token

	// Non-terminal symbols:
	NTS_S,		// S
	NTS_F
};

/* 
Converts a valid token to the corresponding terminal symbol
*/
enum Symbols lexer(char c)
{
	switch(c)
	{
		case '(':
			return TS_L_PARENS;
			break;

		case ')':
			return TS_R_PARENS;
			break;

		case 'a':
			return TS_A;
			break;

		case '+':
			return TS_PLUS;
			break;

		case '\0':	// this will act as the $ terminal symbol
			return TS_EOS;
			break;

		default:
			return TS_INVALID;
			break;
	}
}

int main(int argc, char **argv)
{
	using namespace std;

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

	map< enum Symbols, map<enum Symbols, int> > table; // LL parser table, maps < non-terminal, terminal> pair to action	
	stack<enum 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;
}

وكما يتبين من المثال أن المحلل اللغوي ينفذ ثلاثة أنواع من الخطوات اعتمادا على ما إذا كان الجزء العلوي من المكدس محطة غير طرفية أو طرفية أو رمز خاص $ :

• إذا كان ما أعلى المكدس هو محطة غير طرفية سوف يبحث في جدول تحليل على أساس هذه المحطة الغير طرفية والرمز على تدفق المدخلات الذي هو حكم القاعدة الذي ينبغي أن يستخدمه لاستبداله مع ما أعلى المكدس. يتم كتابة عدد من القواعد إلى تدفق الإخراج. إذا جدول التحليل يشير إلى أن ليست هناك هذه القاعدة فإن المحلل سوف يفيد أن هناك خطأ ثم يتوقف.
• إذا كان ما في الأعلى محطة طرفية، فإنه يقارنها مع الرمز على تدفق المدخلات، وإذا كانوا متساويين، يتم إزالتهما كليهما و. إذا لم يكونا متساويين فإن المحلل سوف يفيد أن هناك ثمة خطأ ثم يتوقف.
• إذا كان ما في أعلى المكدس $، وعلى تدفق المدخلات هناك أيضا $ فإنالحلل سوف يفيد أنه تم تحليل المدخلات بنجاح، وإلا فإنه سوف يفيد أن هناك خطأ. وفي كلتا الحالتين فإن المحلل سيتوقف.

وتتكرر هذه الخطوات حتى يتوقف المحلل، وبعد ذلك سوف تكون النتيجة إما أن تحليل المدخلات تم ويكتب الاستنتاج أقصى اليسار إلى تدفق الإخراج أو سيفيد أن هناك خطأ حدث.

من أجل ملء جدول التحليل، يجب علينا ان نقرر القاعدة التي يجب أن يختارها المحلل إذا رأى المحطة الغير طرفية A أعى المكدس من ورمزa على تدفق المدخلات. فمن السهل أن نرى أن هذه القاعدة ينبغي أن تكون على شكل A → w واللغة الموافقة ل w يجب أن يكون لديها على الأقل سلسلة واحدة تبدءا من a لهذا الغرض نحدد أول مجموعة من 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 يتم تعريفها على النحو التالي: o Fi(a w') = { a } for every terminal a لكل محطة طرفية o Fi(A w') = Fi(A) for every nonterminal A with ε not in Fi(A) لكل محطة طرفية a مع ε ليست في o Fi(A w') = Fi(A) \ { ε } ∪ Fi(w') for every nonterminal A with ε in Fi(A) لكل محطة غير طرفية aمع ε في o Fi(ε) = { ε }

3. أضف Fi(wi) إلى Fi(Ai) لكل قاعدة Ai → wi 4. كرر الخطوات 2 و3 حتى كافة مجموعات Fi تبقى متساوية.

وللأسف، فإن المجموعات الأولى ليست كافية لحساب جدول التحليل، لأن الجزء اليمين w من القاعدة قد يكتب أخيراً لسلسلة فارغة. لذلك فإن المحلل ينبغي أن يستخدم القاعدة A → w إذا ε في Fi(w) وترا على تدفق الإدخال الرمز الذي يمكن أن يتبع a ولذلك نحن بحاجة أيضا المجموعة التابعة لـ A، تكتب هنا Fo(A)، التي تعرف على أنها مجموعة من المحطات الطرفية a ومن هذا القبيل هناك سلسلة من الرموز αAaβ التي يمكن استخلاصها من رمز البداية. ويمكن أن يتم احتساب المجموعات التابعة للمحطات الغير طرفية في القواعد على النحو التالي:

1. نبدأ كل Fo(Ai) مع المجموعة الفارغة

2. إذا كان هناك قاعدة للنموذج Aj → wAiw'، إذا

* إذا كانت المحطة الطرفية a في Fi(w')، قم بإضافة a إلى Fo(Ai)
* إذا كانت ε في Fi(w')، قم بإضافة a إلى Fo(Ai)

3. كرر الخطوة 2 حتى كل مجموعات Fo تبقى متساوية.

الآن يمكن أن نحدد بالضبط أي القواعد التي سوف ترد في جدول التحليل. إذا T[A, a] تشير إلى الدخول في الجدول لمحطة غير طرفية A وطرفية a، إذا

T[A،a]يحتوي على مادة A → w إذا وفقط إذا كانت a في Fi(w) أو ε في Fi(w) وFo(A) إذا كان الجدول يحتوي على قاعدة واحدة على أكثر في كل خلية من خلاياه، إذا المحلل سوف يعرف دائما أي قاعدة يجب أن يستخدمها وبالتالي يمكن تحليل السلاسل بدون تراجع. في هذه الحالة على وجه التحديد القاعدة تسمى قاعدة LL(1).

حتى منتصف التسعينات، وكان يعتقد على نطاق واسع أن LL(k) تحليل لـ (k > 1) كان غير عملياً [citation needed]، إذ أن جدول التحليل سيكون حجمه هائل في k في أسوأ الأحوال. وهذا المفهوم تغيير تدريجيا بعد إصدار PCCTS في حوالي عام 1992، عندما اتضح أنه يمكن تحليل العديد من لغات البرمجة بكفاءة من خلال المحلل LL(k) من دون التسبب في أعمال أسوأ الحالات للمحلل اللغوي. وعلاوة على ذلك، في بعض حالات تحليل LL مجدية حتى مع الاستباق غير المحدود. على النقيض من ذلك، مولدات المحلل التقليدي، مثل yacc يستخدم جدول تحليل LALR(1) لبناء محلل LR المقيد مع استباق رمز ثابت واحد.

كما هو موضح في المقدمة، محللات(1) LL تتعرف على اللغات ذات قواعد (1) LL، والتي هي حالة خاصة من قواعد السياق الحر (CFG's)؛ محللات (1) LL لا يمكن أن تتعرف على كل لغات السياق الحر. لغات (1) LLهي بالضبط تلك التي يتم التعرف عليها بتأكيدية التشغيل الذاتي التنازلى deterministic pushdown automata الذي يقتصر على حالة واحدة.[2] من أجل CFG أن تكون قاعدة (1) LL، يجب أن لا تنشأ تعارضات معينة، التي وصفناها في هذا القسم.

لتكونA محطة غير طرفية. أولاً A (تعرف لتكون) مجموعة من المحطات الطرفية التي يمكن أن تظهر في المركز الأول لأي سلسلة مستمدة من A. يتبع (A) الاتحاد الفوقي أولاً (B) حيث B هي أي محطة غير طرفية التي تليA مباشرة في الجانب الأيمن من قاعدة الإنتاج.

S -> A 'a' 'b'
A -> 'a' | epsilon

E -> E '+' term | alt1 | alt2

A -> X | X Y Z

A -> X B
B -> Y Z | ε

E -> E '+' T
-> T

E -> T Z
Z -> '+' T Z
-> ε

S -> A | B
A -> 'a' A 'b' | ε
B -> 'a' B 'b' 'b' | ε

• Comparison of parser generators
• Parse tree
• Top-down parsing
• Bottom-up parsing

• An easy explanation of First and Follow Sets (an attempt to explain the process of creating first and follow sets in a more straightforward way)
• A tutorial on implementing LL(1) parsers in C#
• Parsing Simulator This simulator is used to generate parsing tables LL1 and to resolve the exercises of the book.
• LL(1) DSL PEG parser (toolkit framework)

• بوابة تقانة المعلومات
• بوابة علم الحاسوب