LL grammar
رسمی زبان کے نظریہ میں، ایل ایل گرائمر ایک سیاق و سباق سے پاک گرائمر ہے جسے ایل ایل پارسر کے ذریعے تجزیہ کیا جا سکتا ہے، جو ان پٹ کو بائیں سے دائیں طرف تجزیہ کرتا ہے، اور جملے کی بائیں طرف مشتق کی تعمیر کرتا ہے (اس لیے ایل ایل، ایل آر پارسر کے مقابلے میں جو دائیں طرف مشتق کی تعمیر کرتا ہے)۔ جس زبان میں ایل ایل گرائمر ہو اسے ایل ایل زبان کہا جاتا ہے۔ یہ بالترتیب تعیناتی سیاق و سباق سے پاک گرامر (ڈی سی ایف جی) اور تعیناتی سیاق و سباق سے پاک زبانوں (ڈی سی ایف ایل) کے ذیلی مجموعے بناتے ہیں۔ ایک کا کہنا ہے کہ دی گئی گرامر یا زبان "ایل ایل گرامر/زبان ہے" یا صرف "ایل ایل ہے" اس بات کی نشاندہی کرنے کے لیے کہ یہ اس کلاس میں ہے۔ ایل ایل پارسر ٹیبل پر مبنی پارسر ہوتے ہیں، جو ایل آر پارسر کی طرح ہوتے ہیں۔ ایل ایل گرائمرز کو متبادل طور پر ان کے طور پر واضح کیا جا سکتا ہے جنہیں پیش گوئی کرنے والے تجزیہ کار کے ذریعے تجزیہ کیا جا سکتا ہے-بیک ٹریکنگ کے بغیر ایک تکراری نزول تجزیہ کار-اور یہ آسانی سے ہاتھ سے لکھے جا سکتے ہیں۔ یہ مضمون ایل ایل گرائمرز کی رسمی خصوصیات کے بارے میں ہے۔ تجزیہ کے لیے، ایل ایل پارسر یا ریکرسو ڈیسنٹ پارسر دیکھیں۔ رسمی تعریف ایک قدرتی نمبر کو دیکھتے ہوئے، ایک سیاق و سباق سے پاک گرائمر ایک ایل ایل (کے) گرائمر ہے اگر علامتوں تک کی لمبائی کے ہر ٹرمینل علامت کے سٹرنگ کے لیے، ہر غیر ٹرمینل علامت کے لیے، اور ہر ٹرمینل علامت کے سٹرنگ کے لیے، زیادہ سے زیادہ ایک پروڈکشن رول ہوتا ہے جیسے کہ کچھ ٹرمینل علامت کے سٹرنگ کے لیے، سٹرنگ کو اسٹارٹ علامت سے اخذ کیا جا سکتا ہے، پہلے اصول کو لاگو کرنے کے بعد سے اخذ کیا جا سکتا ہے، اور اتفاق کی پہلی علامت۔ ایک متبادل، لیکن مساوی، رسمی تعریف درج ذیل ہے: ایک ایل ایل (کے) گرائمر ہے اگر، صوابدیدی مشتقات کے لیے جب کی پہلی علامتیں ان سے متفق ہوں، تو۔ غیر رسمی طور پر، جب کسی پارسر نے اپنے بائیں طرف کے نان ٹرمینل کے ساتھ اخذ کیا ہے اور پہلے ہی ان پٹ سے استعمال کیا ہے، تو اسے دیکھ کر اور موجودہ ان پٹ کی اگلی علامتوں پر جھانک کر، پارسر یقینی طور پر پروڈکشن رول کی شناخت کر سکتا ہے۔ جب ماضی کے ان پٹ پر غور کیے بغیر بھی اصول کی شناخت ممکن ہو تو گرائمر کو مضبوط ایل ایل (کے) گرائمر کہا جاتا ہے۔ مضبوط ایل ایل (کے) گرائمر کی رسمی تعریف میں، کے لیے عالمگیر مقداری کو خارج کر دیا جاتا ہے، اور اس کے لیے "کچھ کے لیے" مقداری میں شامل کیا جاتا ہے۔ ہر ایل ایل (کے) گرائمر کے لیے ساختی طور پر مساوی مضبوط ایل ایل (کے) گرائمر بنایا جا سکتا ہے۔ ایل ایل (کے) زبانوں کی کلاس سیٹوں کی سختی سے بڑھتی ہوئی ترتیب تشکیل دیتی ہے: ایل ایل (0) ایل ایل (1) ایل ایل (2)۔ یہ فیصلہ کرنے کے قابل ہے کہ آیا دیا ہوا گرائمر G، LL (k) ہے، لیکن یہ فیصلہ کرنے کے قابل نہیں ہے کہ آیا ایک من مانی گرائمر کسی k کے لیے LL (k) ہے۔ یہ بھی فیصلہ کرنے کے قابل ہے کہ آیا دیا ہوا LR (k) گرائمر بھی کسی m کے لیے LL (m) گرائمر ہے۔ ہر LL (k) گرائمر بھی ایک LR (k) گرائمر ہے۔ ایک ε-فری ایل ایل (1) گرائمر بھی ایک ایس ایل آر (1) گرائمر ہے۔ خالی اور غیر خالی دونوں مشتقات والی علامتوں کے ساتھ ایل ایل (1) گرائمر بھی ایک ایل اے ایل آر (1) گرائمر ہے۔ ایک ایل ایل (1) گرائمر جس میں صرف خالی مشتق علامات ہوں وہ ایل اے ایل آر (1) ہو بھی سکتا ہے اور نہیں بھی۔ ایل ایل گرائمر میں لیفٹ ریکرشن پر مشتمل اصول نہیں ہو سکتے۔ ہر ایل ایل (کے) گرائمر جو ε-فری ہے اسے گریباچ نارمل فارم میں مساوی ایل ایل (کے) گرائمر میں تبدیل کیا جا سکتا ہے (جس کی تعریف کے مطابق لیفٹ ریکرشن کے ساتھ قواعد نہیں ہیں)۔ باقاعدہ صورت ایک ٹرمینل حروف تہجی ہونے دیں۔ کی تقسیم کو باقاعدہ تقسیم کہا جاتا ہے اگر ہر زبان کے لیے باقاعدہ ہو۔ ایک سیاق و سباق سے پاک گرائمر بننے دیں اور اس کی باقاعدہ تقسیم ہونے دیں۔ ہم کہتے ہیں کہ یہ ایک ایل ایل () گرائمر ہے اگر، صوابدیدی مشتقات کے لیے اس طرح کہ یہ اس کی پیروی کرتا ہے۔ اگر کوئی باقاعدہ تقسیم موجود ہو کہ G، LL () ہے تو گرائمر G کو LL-ریگولر (LLR) کہا جاتا ہے۔ کوئی زبان ایل ایل ریگولیٹر ہوتی ہے اگر وہ ایل ایل ریگولیٹر گرائمر سے تیار کی جاتی ہے۔ ایل ایل آر گرائمر غیر واضح ہوتے ہیں اور لیفٹ ریکرسو نہیں ہو سکتے۔ ہر ایل ایل (کے) گرائمر ایل ایل آر ہے۔ ہر ایل ایل (کے) گرائمر تعیناتی ہے، لیکن ایک ایل ایل آر گرائمر موجود ہے جو تعیناتی نہیں ہے۔ لہذا ایل ایل آر گرائمر کی کلاس ہر کے کے لیے ایل ایل (کے) کے اتحاد سے سختی سے بڑی ہوتی ہے۔ یہ فیصلہ کن ہے کہ، باقاعدہ تقسیم کو دیکھتے ہوئے، دیا گیا گرائمر ایل ایل () ہے یا نہیں۔ تاہم، یہ فیصلہ کن نہیں ہے کہ آیا صوابدیدی گرائمر جی ایل ایل آر ہے۔ یہ اس حقیقت کی وجہ سے ہے کہ یہ فیصلہ کرنا کہ آیا گرامر G ایک باقاعدہ زبان پیدا کرتا ہے، جو G کے لیے باقاعدہ پارٹیشن تلاش کرنے کے لیے ضروری ہوگی، پوسٹ خط و کتابت کے مسئلے تک کم کیا جا سکتا ہے۔ ہر ایل ایل آر گرائمر ایل آر ریگولیٹر (ایل آر آر، ایل آر (کے) گرائمر کے مساوی) ہوتا ہے، لیکن ایک ایل آر (1) گرائمر موجود ہے جو ایل ایل آر نہیں ہے۔ تاریخی طور پر، ایل ایل آر گرائمرز نے ایل آر آر گرائمرز کی ایجاد کی پیروی کی۔ باقاعدہ تقسیم کو دیکھتے ہوئے ایک مور مشین دائیں سے بائیں طرف تجزیہ کو منتقل کرنے کے لیے بنائی جا سکتی ہے، جو باقاعدہ پیداوار کی مثالوں کی نشاندہی کرتی ہے۔ ایک بار ایسا کرنے کے بعد، ایل ایل (1) پارسر لکیری وقت میں ٹرانسڈیوسڈ ان پٹ کو سنبھالنے کے لیے کافی ہے۔ اس طرح، ایل ایل آر تجزیہ کار ایل ایل (کے) تجزیہ کاروں سے سختی سے بڑے گرائمر کی ایک کلاس کو سنبھال سکتے ہیں جبکہ یکساں طور پر موثر ہوتے ہیں۔ اس کے باوجود ایل ایل آر کے نظریہ کا کوئی بڑا اطلاق نہیں ہے۔ ایک ممکنہ اور انتہائی قابل فہم وجہ یہ ہے کہ اگرچہ ایل ایل (کے) اور ایل آر (کے) تجزیہ کاروں کے لیے جنریٹو الگورتھم موجود ہیں، لیکن ایل ایل آر/ایل آر آر تجزیہ کار تیار کرنے کا مسئلہ ناقابل فیصلہ ہے جب تک کہ کسی نے باقاعدہ تقسیم کو پہلے سے تعمیر نہ کیا ہو۔ لیکن یہاں تک کہ گرائمر کو دیکھتے ہوئے ایک مناسب باقاعدہ پارٹیشن بنانے کا مسئلہ بھی ناقابل فیصلہ ہے۔ سادہ تعیناتی زبانیں سیاق و سباق سے پاک گرائمر کو سادہ تعیناتی، یا صرف سادہ کہا جاتا ہے، اگر یہ گریباچ عام شکل میں ہو (یعنی۔ ہر اصول کی شکل ہوتی ہے)، اور ایک ہی نان ٹرمینل کے لیے مختلف دائیں ہاتھ کے اطراف ہمیشہ مختلف ٹرمینلز سے شروع ہوتے ہیں۔ تاروں کے ایک سیٹ کو سادہ تعیناتی، یا صرف سادہ زبان کہا جاتا ہے، اگر اس میں سادہ تعیناتی گرائمر ہو۔ گریباخ عام شکل میں ε-فری LL (1) گرائمر رکھنے والی زبانوں کی کلاس سادہ تعیناتی زبانوں کی کلاس کے برابر ہے۔ اس زبان کی کلاس میں باقاعدہ سیٹ شامل ہیں جن میں ε نہیں ہے۔ مساوات اس کے لیے فیصلہ کن ہے، جبکہ شمولیت نہیں ہے۔ ایپلی کیشنز ایل ایل گرائمرز، خاص طور پر ایل ایل (1) گرائمرز، بہت عملی دلچسپی کے حامل ہیں، کیونکہ ان کا تجزیہ کرنا آسان ہے، یا تو ایل ایل پارسرز کے ذریعے یا ریکرسو ڈیسنٹ پارسرز کے ذریعے، اور اسی وجہ سے ایل ایل (1) ہونے کے لیے ڈیزائن کیے گئے ہیں۔ k کی اعلی قیمت والے گرائمرز پر مبنی زبانوں کو روایتی طور پر تجزیہ کرنا مشکل سمجھا جاتا ہے، حالانکہ اب یہ کم درست ہے کیونکہ LL (k) گرائمرز کی حمایت کرنے والے پارسر جنریٹرز کی دستیابی اور وسیع پیمانے پر استعمال صوابدیدی k کے لیے ہے۔ LL (k) اور LL (*) پارسرز کی فہرست کے لیے پارسر جنریٹرز کا موازنہ بھی دیکھیں۔ مزید پڑھنے کے لیے رسمی زبانیں