Left recursion
کمپیوٹر سائنس کے رسمی زبان کے نظریہ میں، لیفٹ ریکرشن ریکرشن کا ایک خاص معاملہ ہے جہاں ایک سٹرنگ کو کسی زبان کے حصے کے طور پر اس حقیقت سے پہچانا جاتا ہے کہ وہ اسی زبان (بائیں طرف) اور لاحقہ (دائیں طرف) سے ایک سٹرنگ میں تحلیل ہو جاتی ہے۔ مثال کے طور پر، ایک مجموعہ کے طور پر پہچانا جا سکتا ہے کیونکہ اسے ایک مجموعہ، اور ایک مناسب لاحقہ میں بھی تقسیم کیا جا سکتا ہے۔ سیاق و سباق سے پاک گرائمر کے لحاظ سے، ایک نان ٹرمینل لیفٹ ریکرسو ہوتا ہے اگر اس کی کسی پروڈکشن میں سب سے بائیں طرف کی علامت خود ہو (براہ راست بائیں ریکرسن کی صورت میں) یا متبادل کے کچھ سلسلے کے ذریعے خود کو بنایا جا سکتا ہے (بالواسطہ بائیں ریکرسن کی صورت میں)۔ غیر تکنیکی تعارف رسمی زبان کا نظریہ بہت مشکل ہو سکتا ہے۔ آئیے صرف مسئلہ کو ظاہر کرنے کے لیے ایک بہت ہی آسان مثال سے شروعات کرتے ہیں۔ اگر ہم ایک سابق ڈچ بینک، وی ایس بی بینک کے نام پر نظر ڈالیں تو آپ کو کچھ عجیب نظر آئے گا۔ آپ کے خیال میں بی کا مطلب کیا ہے؟ بینک۔ دوبارہ وہی لفظ۔ اس نام کے کتنے بینک ہیں؟ آئیے نام کو حصوں میں کاٹتے ہیں: وی ایس بی بینک: وی = ویرنیگڈے (یونائیٹڈ) ایس = سپار بینک (سیونگ بینک) بی = بینک بینک۔ اختتامی: وی ایس بی بینک = ویرنیگڈے سپاربینک بینک۔ اب آپ دیکھتے ہیں کہ لیفٹ ریکرسو نام کا مخفف کیا ہے۔ اس مضمون کا بقیہ حصہ مثالوں کا استعمال نہیں کر رہا ہے، بلکہ علامتوں کی شکلوں میں خلاصہ کر رہا ہے۔ تعریف ایک گرائمر بائیں بار بار آتا ہے اگر اور صرف اس صورت میں جب کوئی غیر ٹرمینل علامت موجود ہو جو خود کو بائیں طرف کی علامت کے طور پر ایک جذباتی شکل میں حاصل کر سکتی ہے۔ علامتی طور پر، جہاں ایک یا زیادہ متبادل بنانے کے عمل کی نشاندہی کرتا ہے، اور ٹرمینل اور نان ٹرمینل علامتوں کی کوئی ترتیب ہے۔ براہ راست بائیں ریکرشن براہ راست بائیں ریکرشن اس وقت ہوتا ہے جب تعریف کو صرف ایک متبادل سے مطمئن کیا جا سکتا ہے۔ اس کے لیے فارم کا ایک قاعدہ درکار ہوتا ہے جہاں نان ٹرمینلز اور ٹرمینلز کی ترتیب ہوتی ہے۔ مثال کے طور پر، قاعدہ براہ راست لیفٹ ریکرسو ہے۔ اس قاعدے کے لیے بائیں سے دائیں ریکرسو ڈیسنٹ پارسر کالعدم ایکسپریشن () {ایکسپریشن () ؛ میچ ('+') ؛ ٹرم () ؛} کی طرح نظر آسکتا ہے اور اس طرح کے کوڈ پر عمل درآمد ہونے پر یہ لامحدود ریکرسن میں آ جائے گا۔ بالواسطہ بائیں بازیافت بالواسطہ بائیں بازیافت اس وقت ہوتی ہے جب بائیں بازیافت کی تعریف کئی متبادلات کے ذریعے مطمئن ہوتی ہے۔ اس میں پیٹرن کی پیروی کرنے والے اصولوں کا ایک مجموعہ شامل ہوتا ہے جہاں ایسے سلسلے ہوتے ہیں جو ہر ایک خالی تار حاصل کر سکتے ہیں، جبکہ ٹرمینل اور نان ٹرمینل علامتوں کا کوئی بھی سلسلہ بالکل بھی ہو سکتا ہے۔ نوٹ کریں کہ یہ ترتیبات خالی ہو سکتے ہیں۔ اس کے بعد مشتق اپنی آخری جذباتی شکل میں بائیں طرف کے طور پر دیتا ہے۔ لیفٹ ریکرشن کو ہٹانا اکثر پارسرز کے لیے مسائل کا باعث بنتا ہے، یا تو اس وجہ سے کہ یہ انہیں لامحدود ریکرشن کی طرف لے جاتا ہے (جیسا کہ زیادہ تر ٹاپ ڈاؤن پارسرز کے معاملے میں) یا اس وجہ سے کہ وہ عام شکل میں اصولوں کی توقع کرتے ہیں جو اس کی ممانعت کرتے ہیں (جیسا کہ بہت سے باٹم اپ پارسرز کے معاملے میں)۔ لہذا، بائیں بازیافت کو ختم کرنے کے لیے اکثر گرائمر پر پہلے سے عمل کیا جاتا ہے۔ براہ راست بائیں بازیافت کو ہٹانا براہ راست بائیں بازیافت کو ہٹانے کے لیے عمومی الگورتھم مندرجہ ذیل ہے۔ اس طریقہ کار میں کئی اصلاحات کی گئی ہیں۔ لیفٹ ریکرسو نان ٹرمینل کے لیے، فارم کے کسی بھی اصول کو رد کریں اور ان پر غور کریں جو باقی ہیں: جہاں: ہر ایک نان ٹرمینلز اور ٹرمینلز کا ایک نان ایمپٹی تسلسل ہے، اور ہر ایک نان ٹرمینلز اور ٹرمینلز کا ایک سلسلہ ہے جو اس سے شروع نہیں ہوتا ہے۔ ان کو پروڈکشن کے دو سیٹوں سے تبدیل کریں، ایک سیٹ کے لیے: اور دوسرا سیٹ تازہ نان ٹرمینل کے لیے (جسے اکثر "دم" یا "آرام" کہا جاتا ہے): اس عمل کو اس وقت تک دہرائیں جب تک کہ کوئی براہ راست بائیں بازیافت باقی نہ رہے۔ ایک مثال کے طور پر، قاعدہ سیٹ پر غور کریں یہ بائیں بازیافت سے بچنے کے لیے دوبارہ لکھا جا سکتا ہے جیسا کہ تمام بائیں بازیافت کو ہٹانا نان ٹرمینلز پر ٹپوولوجیکل ترتیب قائم کرنے سے، مندرجہ بالا عمل کو بالواسطہ بائیں بازیافت کو ختم کرنے کے لیے بھی بڑھایا جا سکتا ہے: ان پٹ ایک گرائمر: نان ٹرمینلز کا ایک مجموعہ اور ان کی پیداوار آؤٹ پٹ ایک ترمیم شدہ گرائمر جو ایک ہی زبان پیدا کرتا ہے لیکن بغیر بائیں بازیافت کے ہر نان ٹرمینل کے لیے: اس وقت تک دہرائیں جب تک کہ تکرار گرائمر کو تبدیل نہ کر دے: ہر اصول کے لیے، ٹرمینلز اور نان ٹرمینلز کی ترتیب ہونے کے ناطے: اگر نان ٹرمینل سے شروع ہوتا ہے اور: تو اس کے لیڈنگ کے بغیر رہیں۔ اصول کو ہٹا دیں۔ ہر اصول کے لیے: اصول شامل کریں۔ جیسا کہ اوپر بیان کیا گیا ہے اس کے لیے براہ راست بائیں ریکرشن کو ہٹا دیں۔ نوٹ کریں کہ یہ الگورتھم نان ٹرمینل آرڈرنگ کے لیے انتہائی حساس ہے۔ اصلاح اکثر اس ترتیب کو اچھی طرح سے منتخب کرنے پر مرکوز ہوتی ہے۔ نقصانات اگرچہ مذکورہ بالا تبدیلیاں گرامر سے پیدا ہونے والی زبان کو محفوظ رکھتی ہیں، لیکن وہ پارس کے درختوں کو تبدیل کر سکتی ہیں جو تاروں کی پہچان کے گواہ ہیں۔ مناسب حساب کتاب کے ساتھ، ٹری ری رائٹنگ اصل کو بازیافت کر سکتی ہے، لیکن اگر اس مرحلے کو چھوڑ دیا جائے تو، اختلافات پارس کے الفاظ کو تبدیل کر سکتے ہیں۔ ایسوسی ایٹیویٹی خاص طور پر کمزور ہے ؛ بائیں ایسوسی ایٹیو آپریٹرز عام طور پر نئے گرامر کے تحت دائیں ایسوسی ایٹیو جیسے انتظامات میں ظاہر ہوتے ہیں۔ مثال کے طور پر، اس گرائمر سے شروع کرتے ہوئے: لیفٹ ریکرشن کو ہٹانے کے لیے معیاری تبدیلیوں سے درج ذیل نتائج برآمد ہوتے ہیں: ایل اے ایل آر پارسر میں پہلے گرائمر کے ساتھ سٹرنگ "1-2-3" کو پارس کرنے (جو لیفٹ ریکرسو گرامر کو سنبھال سکتا ہے) کے نتیجے میں پارس ٹری ہوتا: یہ پارس ٹری بائیں طرف کی اصطلاحات کو گروپ کرتا ہے، جس سے صحیح سیمنٹکس (1-2)-3 ملتا ہے۔ دوسرے گرائمر کے ساتھ تجزیہ کرنے سے پتہ چلتا ہے کہ جس کی صحیح تشریح کی گئی ہے، اس کی معنی 1 + (-2 + (-3)) ہے، وہ بھی درست ہے، لیکن ان پٹ کے لیے کم وفادار ہے اور کچھ آپریٹرز کے لیے اس پر عمل درآمد کرنا بہت مشکل ہے۔ غور کریں کہ کس طرح دائیں طرف کی اصطلاحات درخت میں گہری نظر آتی ہیں، جس طرح دائیں بار بار آنے والا گرائمر انہیں 1-(2-3) کے لیے ترتیب دیتا ہے۔ ایک رسمی گرائمر جس میں لیفٹ ریکرشن ہوتا ہے اسے ایل ایل (کے)-پارسر یا دیگر سادہ ریکرسو نزول پارسر کے ذریعے تجزیہ نہیں کیا جا سکتا جب تک کہ اسے کمزور مساوی دائیں-ریکرسو شکل میں تبدیل نہ کیا جائے۔ اس کے برعکس، ایل اے ایل آر تجزیہ کاروں کے لیے لیفٹ ریکرشن کو ترجیح دی جاتی ہے کیونکہ اس کے نتیجے میں دائیں ریکرشن کے مقابلے اسٹیک کا استعمال کم ہوتا ہے۔ تاہم، زیادہ نفیس ٹاپ ڈاؤن پارسرز کٹوتی کے استعمال سے عمومی سیاق و سباق سے پاک گرائمرز کو نافذ کر سکتے ہیں۔ 2006 میں، فراسٹ اور حافظ نے ایک الگورتھم بیان کیا جس میں مبہم گرائمرز کو براہ راست لیفٹ ریکرسو پروڈکشن قوانین کے ساتھ ایڈجسٹ کیا گیا ہے۔ اس الگورتھم کو ایک مکمل تجزیہ الگورتھم تک بڑھایا گیا تھا تاکہ کثیر الجہتی وقت میں بالواسطہ کے ساتھ ساتھ براہ راست بائیں بازیافت کو ایڈجسٹ کیا جا سکے، اور 2007 میں فراسٹ، حافظ اور کالاگان کے ذریعہ انتہائی مبہم گرائمرز کے لیے تجزیہ کے درختوں کی ممکنہ طور پر تیز رفتار تعداد کی کمپیکٹ کثیر الجہتی سائز کی نمائندگی پیدا کی جا سکے۔ اس کے بعد مصنفین نے الگورتھم کو ہاسکل پروگرامنگ زبان میں لکھے گئے پارسر کمبینٹرز کے ایک سیٹ کے طور پر نافذ کیا۔ ٹیل ریکرشن حوالہ جات بیرونی لنکس LALR کے لیے عملی غور (1) گرامر کنٹرول فلو رسمی زبانیں پارسنگ ریکرشن