Shift-reduce parser
شفٹ-ریڈوس پارسر کمپیوٹر زبانوں اور دیگر اشاروں کے لیے موثر، ٹیبل سے چلنے والے باٹم اپ پارسنگ طریقوں کی ایک کلاس ہے جس کی رسمی طور پر گرامر کے ذریعے وضاحت کی جاتی ہے۔ تجزیہ کرنے کے طریقے جو عام طور پر پروگرامنگ زبانوں کو تجزیہ کرنے کے لیے استعمال ہوتے ہیں، ایل آر تجزیہ اور اس کی تغیرات، شفٹ کم کرنے کے طریقے ہیں۔ ایل آر تجزیہ کی ایجاد سے پہلے استعمال ہونے والے ترجیحی تجزیہ کار بھی شفٹ کم کرنے کے طریقے ہیں۔ تمام شفٹ-کم تجزیہ کاروں کے اسی طرح کے بیرونی اثرات ہوتے ہیں، انکریمنٹل آرڈر میں جس میں وہ پارس ٹری بناتے ہیں یا مخصوص آؤٹ پٹ ایکشنز کو کال کرتے ہیں۔ جائزہ شفٹ کم کرنے والا تجزیہ کار بغیر بیک اپ لیے متن کے اوپر ایک فارورڈ پاس میں ان پٹ متن کو اسکین اور تجزیہ کرتا ہے۔ تجزیہ کار تجزیہ کے درخت کو بغیر اندازہ لگائے یا پیچھے ہٹائے، نیچے سے اوپر، اور بائیں سے دائیں بڑھاتا ہے۔ اس پاس کے ہر پوائنٹ پر، پارسر نے ان پٹ ٹیکسٹ کے سبٹریز یا فقروں کی ایک فہرست جمع کی ہے جو پہلے ہی تجزیہ کیے جا چکے ہیں۔ وہ سبٹریز ابھی تک ایک ساتھ نہیں جڑے ہیں کیونکہ پارسر ابھی تک نحو پیٹرن کے دائیں سرے تک نہیں پہنچا ہے جو انہیں یکجا کرے گا۔ سٹرنگ A = B + C * 2 پر غور کریں۔ مثال میں مرحلہ 7 پر، صرف "A = B +" کو تجزیہ کیا گیا ہے۔ پارس کے درخت کا صرف سایہ دار نچلا بائیں کونہ موجود ہے۔ 8 اور اس سے اوپر کے نمبر والے پارس ٹری نوڈس میں سے کوئی بھی ابھی موجود نہیں ہے۔ نوڈس 1، 2، 6، اور 7 الگ تھلگ ذیلی درختوں کی جڑیں ہیں جو تمام آئٹمز کا احاطہ کرتی ہیں۔ نوڈ 1 متغیر A ہے، نوڈ 2 حد بندی = ہے، نوڈ 6 خلاصہ B ہے، اور نوڈ 7 آپریٹر + ہے۔ یہ چار جڑ نوڈس عارضی طور پر ایک پارس اسٹیک میں رکھے جاتے ہیں۔ ان پٹ اسٹریم کا بقیہ غیر تجزیہ شدہ حصہ "C * 2" ہے۔ شفٹ کم کرنے والا تجزیہ کار شفٹ اقدامات اور کم کرنے والے اقدامات کے کچھ امتزاج سے کام کرتا ہے، اسی لیے اس کا نام رکھا گیا ہے۔ ایک شفٹ مرحلہ ان پٹ اسٹریم میں ایک علامت کے ذریعے آگے بڑھتا ہے۔ وہ منتقل شدہ علامت ایک نیا سنگل نوڈ پارس ٹری بن جاتا ہے۔ ایک کم قدم کچھ حالیہ پارس درختوں پر ایک مکمل گرائمر اصول کا اطلاق کرتا ہے، انہیں جڑ کی نئی علامت کے ساتھ ایک درخت کے طور پر جوڑتا ہے۔ پارسر ان مراحل کے ساتھ جاری رہتا ہے جب تک کہ تمام ان پٹ کا استعمال نہ ہو جائے اور تمام پارس ٹری کو ایک ہی ٹری میں تبدیل کر دیا جائے جو ایک مکمل قانونی ان پٹ کی نمائندگی کرتا ہے۔ ٹری بلڈنگ کے اقدامات ہر پارس مرحلے پر، پورے ان پٹ متن کو پارس اسٹیک، موجودہ لک ہیڈ علامت، اور باقی غیر سکین شدہ متن میں تقسیم کیا جاتا ہے۔ پارسر کے اگلے عمل کا تعین سب سے دائیں اسٹیک کی علامت اور لک ہیڈ کی علامت سے ہوتا ہے۔ عمل کو ایک میز سے پڑھا جاتا ہے جس میں اسٹیک اور لک ہیڈ علامتوں کے تمام نحو طور پر درست امتزاج ہوتے ہیں۔ ایک آسان مثال کے لیے دیکھیں۔ گرامر ان پٹ زبان کے لیے نمونوں یا نحو کے اصولوں کا مجموعہ ہے۔ یہ زبان کے تمام اصولوں کا احاطہ نہیں کرتا، جیسے کہ اعداد کا سائز، یا پورے پروگرام کے تناظر میں ناموں اور ان کی تعریفوں کا مستقل استعمال۔ شفٹ-کم تجزیہ کار سیاق و سباق سے پاک گرائمر کا استعمال کرتے ہیں جو صرف علامتوں کے مقامی نمونوں سے متعلق ہے۔ جاوا یا سی زبان کے ایک چھوٹے سے ذیلی سیٹ کے طور پر ایک مثال گرائمر جو A = B + C * 2 سے مماثل ہونے کے قابل ہے یہ ہو سکتا ہے: تفویض کریں | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | یہاں ان میں کسی بھی عدد مستقل کے لیے = + * اور انٹ، اور کسی بھی شناخت کنندہ کے نام کے لیے آئی ڈی شامل ہیں۔ گرائمر کو اس بات کی پرواہ نہیں ہے کہ انٹی ویلیوز یا آئی ڈی اسپیلنگ کیا ہیں، اور نہ ہی اسے خالی جگہوں یا لائن بریکس کی پرواہ ہے۔ گرامر ان آخری علامتوں کا استعمال کرتا ہے لیکن ان کی وضاحت نہیں کرتا ہے۔ وہ ہمیشہ پارس کے درخت کے نچلے جھاڑی والے سرے پر ہوتے ہیں۔ سمز جیسی بڑے حروف والی اصطلاحات غیر آخری علامتیں ہیں۔ یہ زبان میں تصورات یا نمونوں کے نام ہیں۔ ان کی وضاحت گرائمر میں کی جاتی ہے اور وہ خود کبھی ان پٹ اسٹریم میں نہیں آتے۔ وہ ہمیشہ پارس کے درخت کے نچلے حصے سے اوپر ہوتے ہیں۔ وہ صرف پارسر کے کچھ گرامر کے اصول کو لاگو کرنے کے نتیجے میں ہوتے ہیں۔ کچھ نان ٹرمینلز کی تعریف دو یا زیادہ اصولوں کے ساتھ کی جاتی ہے۔ یہ متبادل نمونے ہیں۔ قواعد خود کا حوالہ دے سکتے ہیں۔ یہ گرائمر بار بار ریاضی چلانے والوں کو سنبھالنے کے لیے تکراری اصولوں کا استعمال کرتا ہے۔ مکمل زبانوں کے لیے گرامر فہرستوں، قوسین والے تاثرات اور گھڑے ہوئے بیانات کو سنبھالنے کے لیے تکراری اصولوں کا استعمال کرتے ہیں۔ کسی بھی کمپیوٹر زبان کو کئی مختلف گرائمرز کے ذریعے بیان کیا جا سکتا ہے۔ شفٹ کم تجزیہ کار کے لیے گرائمر خود غیر واضح ہونا چاہیے، یا ٹائی بریکنگ ترجیحی اصولوں کے ذریعے بڑھایا جانا چاہیے۔ اس کا مطلب یہ ہے کہ زبان کی دی گئی قانونی مثال پر گرائمر کو لاگو کرنے کا صرف ایک ہی صحیح طریقہ ہے، جس کے نتیجے میں ایک منفرد پارس ٹری اور اس مثال کے لیے شفٹ/کم کرنے کے اقدامات کا ایک منفرد سلسلہ ہوتا ہے۔ ٹیبل سے چلنے والے پارسر کے پاس گرائمر کے بارے میں اپنا تمام علم ہوتا ہے جسے غیر متغیر ڈیٹا میں انکوڈ کیا جاتا ہے جسے پارسر ٹیبل کہتے ہیں۔ پارسر کا پروگرام کوڈ ایک سادہ عام لوپ ہے جو بہت سے گرامر اور زبانوں پر بغیر کسی تبدیلی کے لاگو ہوتا ہے۔ ترجیح کے طریقوں کے لیے میزوں کو ہاتھ سے تیار کیا جا سکتا ہے۔ ایل آر طریقوں کے لیے، پیچیدہ میزیں میکانکی طور پر بیسن جیسے کچھ پارسر جنریٹر ٹول کے ذریعے گرائمر سے حاصل کی جاتی ہیں۔ پارسر ٹیبل عام طور پر گرائمر سے بہت بڑے ہوتے ہیں۔ دوسرے پارسرز میں جو ٹیبل پر مبنی نہیں ہیں، جیسے کہ ریکرسو ڈیسنٹ، ہر زبان کی ساخت کو ایک مختلف سبروٹین کے ذریعے تجزیہ کیا جاتا ہے، جو اس ایک ساخت کے نحو کے لیے مخصوص ہوتا ہے۔ پارسر ایکشن شفٹ کم کرنے والا پارسر موثر ہے کیونکہ اس میں کوئی بیک اپ شامل نہیں ہوتا ہے۔ اس پر عمل درآمد کا کل وقت ان پٹ کی لمبائی اور مکمل پارس ٹری کے سائز کے ساتھ لکیری پیمانے پر ہوتا ہے۔ دیگر پارسر طریقے جو بیک ٹریک کرتے ہیں جب وہ بری طرح اندازہ لگاتے ہیں تو اس میں تیزی سے وقت لگ سکتا ہے۔ اندازہ لگانے سے بچنے کے لیے، شفٹ-ریڈیوز پارسر اکثر پہلے سے اسکین شدہ علامتوں کے ساتھ کیا کرنا ہے اس کا فیصلہ کرنے سے پہلے اگلی اسکین شدہ علامت پر آگے (بائیں سے دائیں متن میں دائیں طرف) دیکھتا ہے۔ لیکسیکل اسکینر ایک علامت کو باقی پارسر سے آگے کام کرتا ہے۔ نظر کی علامت کو تجزیہ کے ہر فیصلے کے لیے 'دائیں ہاتھ کا سیاق و سباق' بھی کہا جاتا ہے۔ (شاذ و نادر ہی، دو یا زیادہ لک ہیڈ علامتوں کا استعمال کیا جا سکتا ہے، حالانکہ زیادہ تر عملی گرائمرز کو ایک لک ہیڈ علامت استعمال کرنے کے لیے ڈیزائن کیا جا سکتا ہے۔) ایک شفٹ-کم تجزیہ کار اس وقت تک انتظار کرتا ہے جب تک کہ وہ مشترکہ تعمیر کا عہد کرنے سے پہلے کسی تعمیر کے تمام حصوں کو اسکین اور تجزیہ نہ کر لے۔ پارسر پھر مزید انتظار کرنے کے بجائے امتزاج پر فوری طور پر عمل کرتا ہے۔ مندرجہ بالا پارس ٹری کی مثال میں، فقرہ B کم ہو کر ویلیو ہو جاتا ہے اور پھر 3 سے 6 مراحل میں پروڈکٹس اور سمز ہو جاتا ہے جیسے ہی + نظر آتا ہے، بجائے اس کے کہ پارس ٹری کے ان حصوں کو منظم کرنے کے لیے مزید انتظار کیا جائے۔ B کو سنبھالنے کے فیصلے صرف اس بات پر مبنی ہوتے ہیں جو پارسر اور اسکینر پہلے ہی دیکھ چکے ہیں، ان چیزوں پر غور کیے بغیر جو بہت بعد میں دائیں طرف دکھائی دیتی ہیں۔ کمی حال ہی میں تجزیہ شدہ چیزوں کو دوبارہ منظم کرتی ہے، یعنی وہ جو فوری طور پر لک ہیڈ علامت کے بائیں طرف ہیں۔ لہذا پہلے سے تجزیہ شدہ چیزوں کی فہرست اسٹیک کی طرح کام کرتی ہے۔ یہ پارس اسٹیک دائیں طرف بڑھتا ہے۔ اسٹیک کا بیس یا نیچے بائیں طرف ہوتا ہے اور اس میں بائیں طرف کا سب سے قدیم پارس ٹکڑا ہوتا ہے۔ ہر تخفیف کا مرحلہ صرف دائیں طرف کے تازہ ترین تجزیہ کے ٹکڑوں پر کام کرتا ہے۔ (یہ جمع شدہ پارس اسٹیک اوپر سے نیچے تجزیہ کاروں کے ذریعہ استعمال ہونے والے پیش گوئی کرنے والے، بائیں طرف بڑھتے ہوئے پارس اسٹیک کے بالکل برعکس ہے۔) جب کوئی گرائمر رول جیسے پروڈکٹس پروڈکٹس * ویلیو کا اطلاق ہوتا ہے، تو اسٹیک ٹاپ میں پارس ٹری ہوتے ہیں۔ "پروڈکٹس * ویلیو"۔ اصول کے دائیں ہاتھ کی اس مثال کو ہینڈل کہا جاتا ہے۔ کم کرنے والا مرحلہ ہینڈل "پروڈکٹس * ویلیو" کو بائیں ہاتھ کی طرف غیر ٹرمینل سے بدل دیتا ہے، اس صورت میں ایک بڑی مصنوعات۔ اگر تجزیہ کار مکمل پارس ٹری بناتا ہے، تو اندرونی مصنوعات کے لیے تین ٹری، *، اور ویلیو کو بڑی مصنوعات کے لیے ایک نئے ٹری روٹ کے ذریعے جوڑا جاتا ہے۔ بصورت دیگر، اندرونی پروڈکٹس اور ویلیو سے بامعنی تفصیلات کچھ بعد میں مرتب کرنے والے پاس میں آؤٹ پٹ ہوتی ہیں، یا مشترکہ ہوتی ہیں اور مصنوعات کی نئی علامت میں محفوظ ہوتی ہیں۔ پارسر پارس اسٹیک کے اوپری حصے پر تب تک کٹوتیوں کا اطلاق کرتا رہتا ہے جب تک کہ اسے وہاں گرامر کے اصولوں کی نئی مکمل مثالیں ملتی رہیں۔ جب مزید قواعد کا اطلاق نہیں کیا جا سکتا، تب تجزیہ کار لک ہیڈ علامت کو پارس اسٹیک پر منتقل کرتا ہے، ایک نئی لک ہیڈ علامت کو اسکین کرتا ہے، اور دوبارہ کوشش کرتا ہے۔ شفٹ-ریڈیس پارسرز کی اقسام پارسر ٹیبلز دکھاتے ہیں کہ سب سے اوپر پارس اسٹیک علامتوں اور لک ہیڈ علامت کے ہر قانونی امتزاج کے لیے آگے کیا کرنا ہے۔ وہ اگلا عمل منفرد ہونا چاہیے ؛ یا تو شفٹ، یا کم، لیکن دونوں نہیں۔ (اس سے گرائمر پر کچھ مزید حدود ظاہر ہوتی ہیں، جو غیر واضح ہونے سے بالاتر ہیں۔) ٹیبل کی تفصیلات مختلف قسم کے شفٹ کم تجزیہ کاروں کے درمیان بہت مختلف ہوتی ہیں۔ ترجیحی تجزیہ کاروں میں، ہینڈلز کا دایاں سرے کو اولین اسٹیک علامتوں کی ترجیحی سطح یا گرائمر کی جکڑن کا موازنہ لک ہیڈ علامت سے کرکے پایا جاتا ہے۔ مندرجہ بالا مثال میں، انٹی اور آئی ڈی کا تعلق بیان ڈیلیمیٹر کے مقابلے میں اندرونی گرائمر کی سطح سے ہے۔ لہذا انٹی اور آئی ڈی دونوں کو اس سے زیادہ ترجیح سمجھا جاتا ہے ؛ اور جب بھی اس کے بعد آتا ہے تو اسے کسی اور چیز تک کم کر دیا جانا چاہیے۔ ترجیحی تجزیہ کاروں کی مختلف قسمیں ہیں، جن میں سے ہر ایک کے ہینڈل کے بائیں سرے کو تلاش کرنے اور لاگو کرنے کے لیے صحیح اصول کا انتخاب کرنے کے مختلف طریقے ہیں: آپریٹر-پریسینڈینس تجزیہ کار، ایک بہت ہی آسان عددی طریقہ ہے جو تاثرات کے لیے کام کرتا ہے لیکن عمومی پروگرام نحو کے لیے نہیں۔ سادہ ترجیحی تجزیہ کار، دائیں اور بائیں سروں کو تلاش کرنے کے لیے ایک بڑی MxN ٹیبل کا استعمال کرتا ہے۔ پی ایل 360 میں استعمال ہوتا ہے۔ عام پروگرامنگ زبانوں کو ہینڈل نہیں کرتا ہے۔ کمزور ترجیحی تجزیہ کار، ترجیحی جدول کا استعمال صرف ہینڈلز کے دائیں سروں کو تلاش کرنے کے لیے کرتا ہے۔ سادہ ترجیح سے زیادہ گرائمر کو سنبھالتا ہے۔ توسیعی ترجیحی تجزیہ کار۔ مکسڈ اسٹریٹجی پریسیڈینس پارسر، جو ایکس پی ایل کے اصل ورژن میں استعمال ہوتا ہے۔ "ڈبلز" کو بڑھاتا ہے، جو کسی بھی ترجیحی شناخت کنندہ میں موروثی ہے، "ٹرپل" کو شامل کرنے کے لیے۔ ایس ایل آر سے کم طاقتور۔ عام طور پر بہت بڑی میزیں ہوتی ہیں یہاں تک کہ نسبتا چھوٹی زبانوں کے لیے بھی جیسے کہ خود ایکس پی ایل بہت زیادہ "ٹرپل" کی وجہ سے جو ترجیحی طریقوں کے ذریعے عائد کردہ حدود سے باہر گرائمر کو پہچاننے کے لیے ضروری ہیں۔ ترجیحی تجزیہ کار ان گرائمرز میں محدود ہوتے ہیں جنہیں وہ سنبھال سکتے ہیں۔ فیصلے کرتے وقت وہ زیادہ تر پارس اسٹیک کو نظر انداز کر دیتے ہیں۔ وہ صرف اعلی ترین علامتوں کے ناموں پر غور کرتے ہیں، نہ کہ اس کے مکمل سیاق و سباق پر کہ وہ علامتیں اب گرامر میں کہاں ظاہر ہو رہی ہیں۔ ترجیح کے لیے ضروری ہے کہ ایک جیسی نظر آنے والی علامتوں کے امتزاج کو تجزیہ کیا جائے اور پورے گرائمر میں یکساں طریقوں سے استعمال کیا جائے تاہم وہ امتزاج سیاق و سباق سے قطع نظر ہوتے ہیں۔ ایل آر تجزیہ کار شفٹ کم تجزیہ کی ایک زیادہ لچکدار شکل ہیں، جو بہت سے اور گرائمرز کو سنبھالتے ہیں۔ ایل آر پارسر پروسیسنگ ایل آر پارسر ایک ریاستی مشین کی طرح کام کرتے ہیں، جو ہر شفٹ کے لیے ریاستی منتقلی انجام دیتے ہیں یا عمل کو کم کرتے ہیں۔ یہ ایک اسٹیک کا استعمال کرتے ہیں جہاں موجودہ حالت کو شفٹ ایکشن کے ذریعے (نیچے) دھکیل دیا جاتا ہے۔ اس اسٹیک کو پھر کم کارروائیوں کے ذریعے پاپ (اپ) کیا جاتا ہے۔ یہ طریقہ کار ایل آر پارسر کو تمام تعیناتی سیاق و سباق سے پاک گرائمرز کو سنبھالنے کی اجازت دیتا ہے، جو ترجیحی گرائمرز کا ایک سپر سیٹ ہے۔ ایل آر تجزیہ کار مکمل طور پر کینونکل ایل آر تجزیہ کار کے ذریعے نافذ کیا جاتا ہے۔ لک-ہیڈ ایل آر اور سمپل ایل آر پارسر اس کی آسان شکلوں کو لاگو کرتے ہیں جن سے میموری کی ضروریات میں نمایاں کمی واقع ہوتی ہے۔ حالیہ تحقیق نے ان طریقوں کی نشاندہی کی ہے جن کے ذریعے کینونکل ایل آر پارسرز کو نوتھ کے ٹیبل بلڈنگ الگورتھم پر ٹیبل کی ڈرامائی طور پر کم ضروریات کے ساتھ نافذ کیا جا سکتا ہے۔ چاہے ایل آر ہو، ایل اے ایل آر ہو یا ایس ایل آر، بنیادی ریاستی مشین ایک جیسی ہوتی ہے۔ صرف ٹیبل مختلف ہوتے ہیں، اور یہ ٹیبل تقریبا ہمیشہ میکانکی طور پر تیار کیے جاتے ہیں۔ مزید برآں، ان ٹیبلز کو عام طور پر اس طرح لاگو کیا جاتا ہے کہ ریڈکس کے نتیجے میں کال کو ایک بند سبروٹین میں منتقل کیا جاتا ہے جو ریاستی مشین سے باہر ہے اور جو ایک ایسا فنکشن انجام دیتا ہے جو گرامر کے اصول کے الفاظ سے ظاہر ہوتا ہے جسے ریڈک ایڈ کیا جا رہا ہے۔ لہذا، تجزیہ کار کو ایک غیر متغیر ریاستی مشین کے حصے، اور ایک متغیر سیمنٹکس حصے میں تقسیم کیا جاتا ہے۔ یہ بنیادی فرق اعلی معیار کے تجزیہ کاروں کی ترقی کی حوصلہ افزائی کرتا ہے جو غیر معمولی طور پر قابل اعتماد ہیں۔ ایک مخصوص اسٹیک اسٹیٹ اور لک ہیڈ علامت کو دیکھتے ہوئے، قطعی طور پر چار ممکنہ اقدامات ہیں، غلطی، شفٹ، ریڈک، اور اسٹاپ (اس کے بعد ترتیبات کے طور پر کہا جاتا ہے)۔ کسی ترتیب میں ایک ڈاٹ کی موجودگی موجودہ لک ہیڈ پوزیشن کی نمائندگی کرتی ہے، جس میں لک ہیڈ کی علامت ڈاٹ کے دائیں طرف دکھائی جاتی ہے (اور جو ہمیشہ ایک ٹرمینل علامت سے مطابقت رکھتی ہے)، اور موجودہ اسٹیک کی حالت ڈاٹ کے بائیں طرف ہوتی ہے (اور جو عام طور پر ایک نان ٹرمینل علامت سے مطابقت رکھتی ہے)۔ عملی وجوہات کی بناء پر، بشمول اعلی کارکردگی، ٹیبلز کو عام طور پر دو بٹ علامتوں کی کسی حد تک بڑی، معاون صف کے ذریعہ بڑھایا جاتا ہے، واضح طور پر بائٹ پر مبنی مشینوں پر موثر رسائی کے لیے چار دو بٹ علامتوں، ایک بائٹ میں کمپریس کیا جاتا ہے، اکثر اس طرح انکوڈ کیا جاتا ہے: 00b غلطی کی نمائندگی کرتا ہے 01b کی نمائندگی کرتا ہے شفٹ 10b کی نمائندگی کرتا ہے ریڈک 11b اسٹاپ کی نمائندگی کرتا ہے (اسٹاپ شفٹ کا ایک خاص معاملہ ہے)۔ پوری صف میں عام طور پر زیادہ تر ایرر کنفیگریشن، شفٹ اور ریڈکس کنفیگریشن کی گرامر سے متعین تعداد، اور ایک اسٹاپ کنفیگریشن شامل ہوتی ہے۔ پروگرامنگ سسٹمز میں جو کواٹرنیری عددی نظام (بیس 4، دو بٹس فی کواٹرنیری ہندسوں) میں اقدار کی وضاحت کی حمایت کرتے ہیں، جیسے کہ ایکس پی ایل، ان کو کوڈ کیا جاتا ہے، مثال کے طور پر: "(2). 0" غلطی کی نمائندگی کرتا ہے "(2). 1" شفٹ کی نمائندگی کرتا ہے "(2). 2" ریڈکس کی نمائندگی کرتا ہے "(2). 3" اسٹاپ کی نمائندگی کرتا ہے اور ریڈکس ٹیبلز کو صف سے الگ لاگو کیا جاتا ہے۔ معاون صف کو صرف موجودہ حالت اور نظر کی علامت کے لیے "جانچ" کیا جاتا ہے۔ (معاون) صف "مکمل" ہے، جبکہ (شفٹ اور کم) ٹیبلز درحقیقت بہت "کم" ہو سکتی ہیں، اور ان شفٹ اور ریڈکس ٹیبلز (ایرر اور اسٹاپ کو کسی ٹیبل کی ضرورت نہیں ہے) کے زیادہ سے زیادہ "سڑنے" کے ذریعے اہم استعداد حاصل کی جا سکتی ہے۔ شفٹ-ریڈیوز پارسر کی بنیادی تعریف سے شفٹ اور ریڈیوز کی ترتیبات واضح ہیں۔ اسٹاپ، پھر، ایک ترتیب کی نمائندگی کرتا ہے جہاں اسٹیک کے اوپری حصے میں ریاست اور لک ہیڈ ٹرمینل کی علامت موضوع کے گرائمر کے اندر ہوتی ہے، اور پروگرام کے اختتام کی نمائندگی کرتی ہے: حتمی سے آگے منتقل کرنا ناممکن ہے تاکہ پہنچ سکے، تصوراتی طور پر δ <پروگرام> δ> غلطی، پھر، ایک ترتیب کی نمائندگی کرتی ہے جہاں اسٹیک کے اوپری حصے میں ریاست، اور لک ہیڈ ٹرمینل علامت موضوع کے گرائمر کے اندر نہیں ہے۔ یہ غلطی کی بازیابی کے طریقہ کار کو، شاید، اس کی سب سے آسان شکل میں، لک ہیڈ ٹرمینل علامت کو ضائع کرنے اور اگلی ٹرمینل علامت کو پڑھنے کا موقع پیش کرتا ہے، لیکن بہت سے دوسرے پروگرام شدہ اقدامات ممکن ہیں، بشمول اسٹیک کو تراشنا، یا لک ہیڈ ٹرمینل علامت کو رد کرنا اور اسٹیک کو تراشنا (اور ایک پیتھولوجیکل معاملے میں، عام طور پر حاصل کرنا ممکن ہے جہاں <پروگرام> صرف ایک "کالعدم بیان" پر مشتمل ہوتا ہے)۔ زیادہ تر معاملات میں، اسٹیک کو جان بوجھ کر پہلے سے لوڈ کیا جاتا ہے، یعنی شروع کیا جاتا ہے، ڈی ڈی کے ساتھ جس کے تحت ابتدائی ڈی ڈی کو پہلے ہی پہچانا جا چکا ہے۔ یہ، پھر، پروگرام کے آغاز کی نمائندگی کرتا ہے، اور اس طرح، ایک علیحدہ START ترتیب رکھنے سے بچتا ہے، جو کہ تصوراتی طور پر ایک خاص فرضی-ٹرمینل علامت ہے جسے میکانکی طور پر گرائمر میں شامل کیا جاتا ہے، جس طرح <پروگرام> ایک خاص فرضی-غیر ٹرمینل علامت ہے جسے میکانکی طور پر گرائمر میں شامل کیا جاتا ہے (اگر پروگرامر واضح طور پر گرائمر میں <پروگرام> کو شامل نہیں کرتا ہے، تو <پروگرام> خود بخود پروگرامر کی طرف سے گرائمر میں شامل ہو جائے گا)۔ واضح طور پر، اس طرح کے پارسر میں بالکل ایک (مضمر) اسٹارٹ کنفیگریشن اور ایک (واضح) اسٹاپ کنفیگریشن ہوتی ہے، لیکن یہ کر سکتا ہے، اور عام طور پر اس میں سینکڑوں شفٹ اور ریڈکس کنفیگریشن، اور شاید ہزاروں ایرر کنفیگریشن ہوتی ہیں۔ حوالہ جات پارسنگ الگورتھم