Shift-reduce parser
একটি শিফট-রিডিউস পার্সার হল কম্পিউটার ভাষা এবং ব্যাকরণ দ্বারা আনুষ্ঠানিকভাবে সংজ্ঞায়িত অন্যান্য স্বরলিপির জন্য দক্ষ, টেবিল-চালিত বটম-আপ পার্সিং পদ্ধতির একটি শ্রেণী। প্রোগ্রামিং ভাষাগুলি, এলআর পার্সিং এবং এর বৈচিত্র্যগুলি পার্স করার জন্য সর্বাধিক ব্যবহৃত পার্সিং পদ্ধতিগুলি হল স্থানান্তর-হ্রাস পদ্ধতি। এলআর পার্সিং আবিষ্কারের আগে ব্যবহৃত অগ্রাধিকার পার্সারগুলিও স্থানান্তর-হ্রাস পদ্ধতি। সমস্ত স্থানান্তর-হ্রাস পার্সারের অনুরূপ বাহ্যিক প্রভাব রয়েছে, ক্রমবর্ধমান ক্রমে যেখানে তারা একটি পার্স ট্রি তৈরি করে বা নির্দিষ্ট আউটপুট ক্রিয়া কল করে। একটি শিফট-রিডিউস পার্সার ব্যাক আপ না করে পাঠ্যের উপর একটি ফরোয়ার্ড পাসে ইনপুট পাঠ্যটি স্ক্যান এবং পার্স করে। পার্সার অনুমান বা ব্যাকট্র্যাকিং ছাড়াই ক্রমবর্ধমানভাবে, নীচে উপরে এবং বাম থেকে ডানদিকে পার্স ট্রি তৈরি করে। এই পাসের প্রতিটি বিন্দুতে, পার্সার ইনপুট পাঠ্যের সাবট্রি বা বাক্যাংশের একটি তালিকা সংগ্রহ করেছে যা ইতিমধ্যে পার্স করা হয়েছে। এই সাবট্রিগুলি এখনও একসঙ্গে যুক্ত হয়নি কারণ পার্সার এখনও সিনট্যাক্স প্যাটার্নের ডান প্রান্তে পৌঁছায়নি যা তাদের একত্রিত করবে। A = B + C * 2 স্ট্রিংটি বিবেচনা করুন। উদাহরণের 7ম ধাপে, শুধুমাত্র "এ = বি +" বিশ্লেষণ করা হয়েছে। পার্স গাছের কেবল ছায়াযুক্ত নীচের-বাম কোণটি বিদ্যমান। 8 এবং তার উপরে সংখ্যাযুক্ত পার্স ট্রি নোডগুলির কোনওটিই এখনও বিদ্যমান নেই। নোড 1,2,6 এবং 7 হল সমস্ত আইটেম 1.7-কে আচ্ছাদনকারী বিচ্ছিন্ন সাবট্রির মূল। নোড 1 হল পরিবর্তনশীল এ, নোড 2 হল ডিলিমিটার =, নোড 6 হল যোগফল বি, এবং নোড 7 হল অপারেটর +। এই চারটি মূল নোড সাময়িকভাবে একটি পার্স স্ট্যাকে রাখা হয়। ইনপুট স্ট্রিমের অবশিষ্ট পার্স করা অংশটি হল "সি * 2"। একটি শিফট-রিডিউস পার্সার শিফট ধাপ এবং রিডিউস ধাপের সংমিশ্রণে কাজ করে, তাই এই নাম। একটি স্থানান্তর ধাপ একটি প্রতীক দ্বারা ইনপুট প্রবাহে অগ্রসর হয়। সেই স্থানান্তরিত প্রতীকটি একটি নতুন একক-নোড পার্স ট্রি হয়ে ওঠে। একটি হ্রাস পদক্ষেপ সাম্প্রতিক কিছু পার্স গাছের জন্য একটি সম্পূর্ণ ব্যাকরণের নিয়ম প্রয়োগ করে, একটি নতুন মূল প্রতীক সহ একটি গাছ হিসাবে তাদের একত্রিত করে। পার্সার এই পদক্ষেপগুলি অব্যাহত রাখে যতক্ষণ না সমস্ত ইনপুট গ্রাস করা হয় এবং সমস্ত পার্স গাছগুলি একটি সম্পূর্ণ আইনি ইনপুটের প্রতিনিধিত্বকারী একক গাছে পরিণত হয়। বৃক্ষ নির্মাণের পদক্ষেপগুলি প্রতিটি পার্স ধাপে, সম্পূর্ণ ইনপুট পাঠ্যটি পার্স স্ট্যাক, বর্তমান লুকহেড প্রতীক এবং অবশিষ্ট আনস্ক্যান করা পাঠ্যে বিভক্ত করা হয়। পার্সারের পরবর্তী ক্রিয়াটি ডানদিকের স্ট্যাক প্রতীক (গুলি) এবং লুকহেড প্রতীক দ্বারা নির্ধারিত হয়। ক্রিয়াটি একটি টেবিল থেকে পড়া হয় যেখানে স্ট্যাক এবং লুকহেড প্রতীকগুলির সমস্ত সিনট্যাক্টিকভাবে বৈধ সংমিশ্রণ রয়েছে। একটি সহজ উদাহরণ দেখুন। ব্যাকরণ হল ইনপুট ভাষার জন্য প্যাটার্ন বা সিনট্যাক্স নিয়মের সেট। এটি সমস্ত ভাষার নিয়মকে অন্তর্ভুক্ত করে না, যেমন সংখ্যার আকার, বা পুরো প্রোগ্রামের প্রসঙ্গে নাম এবং তাদের সংজ্ঞাগুলির সামঞ্জস্যপূর্ণ ব্যবহার। স্থানান্তর-হ্রাস পার্সারগুলি একটি প্রসঙ্গ-মুক্ত ব্যাকরণ ব্যবহার করে যা কেবল প্রতীকগুলির স্থানীয় নিদর্শনগুলির সাথে সম্পর্কিত। জাভা বা সি ভাষার একটি ক্ষুদ্র উপসেট হিসাবে ব্যাকরণের একটি উদাহরণ যা এ = বি + সি * 2 এর সাথে মেলেঃ অ্যাসাইন-এ-আই. ডি = সামস-এ-সামস-এ-সামস-এ-সামস-এ-সামস-এ-সামস-এ-সামস-এ-সামস-এ-সামস-এ-সামস-এ-সামস-এ-সামস-এ-সামস-এ-সামস-এ-সামস-এ-সামস-এ-এ-সামস-এ-এ-সামস-এ-এ-সামস-এ-এ-সামস-এ-এ-এ-এ-এ-এ-এ-এ-এ-এ-এ-এ-এ-এ-এ-এ-এ-এ-এ-এ-এ-এ-এ-এ-এ-এ-এ-এ-এ - এখানে যে কোনও পূর্ণসংখ্যা ধ্রুবকের জন্য = + * এবং পূর্ণসংখ্যা এবং যে কোনও শনাক্তকারী নামের জন্য আইডি অন্তর্ভুক্ত রয়েছে। ব্যাকরণ ইন্ট মান বা আইডি বানানগুলি কী তা নিয়ে চিন্তা করে না, বা এটি ফাঁকা বা লাইন বিরতির বিষয়েও চিন্তা করে না। ব্যাকরণ এই চূড়ান্ত প্রতীকগুলি ব্যবহার করে তবে সেগুলিকে সংজ্ঞায়িত করে না। এগুলি সর্বদা পার্স গাছের নিচের ঝোপঝাড়ের প্রান্তে থাকে। সুমের মতো মূলধনযুক্ত পদগুলি অ-প্রান্তিক প্রতীক। এগুলি ভাষার ধারণা বা নিদর্শনগুলির নাম। এগুলি ব্যাকরণে সংজ্ঞায়িত করা হয় এবং কখনও ইনপুট প্রবাহে ঘটে না। এগুলি সর্বদা পার্স গাছের তলদেশের উপরে থাকে। এগুলি কেবল কিছু ব্যাকরণের নিয়ম প্রয়োগকারী পার্সারের ফলস্বরূপ ঘটে। কিছু নন-টার্মিনালকে দুই বা ততোধিক নিয়ম দিয়ে সংজ্ঞায়িত করা হয়; এগুলি হল বিকল্প প্যাটার্ন। নিয়মগুলি নিজেদের দিকে ফিরে যেতে পারে। এই ব্যাকরণ পুনরাবৃত্ত গণিত অপারেটরদের পরিচালনা করার জন্য পুনরাবৃত্তিমূলক নিয়ম ব্যবহার করে। সম্পূর্ণ ভাষার জন্য ব্যাকরণগুলি তালিকা, বন্ধনীযুক্ত অভিব্যক্তি এবং নেস্টেড বিবৃতি পরিচালনা করতে পুনরাবৃত্তিমূলক নিয়ম ব্যবহার করে। যে কোনও কম্পিউটার ভাষা বিভিন্ন ব্যাকরণ দ্বারা বর্ণনা করা যেতে পারে। একটি শিফট-রিডিউস পার্সারের ব্যাকরণ অবশ্যই দ্ব্যর্থহীন হতে হবে, অথবা টাই-ব্রেকিং অগ্রাধিকার নিয়ম দ্বারা বর্ধিত হতে হবে। এর অর্থ হল ভাষার প্রদত্ত আইনি উদাহরণে ব্যাকরণ প্রয়োগ করার একমাত্র সঠিক উপায় রয়েছে, যার ফলে একটি অনন্য পার্স ট্রি এবং সেই উদাহরণের জন্য স্থানান্তর/হ্রাস ক্রিয়াগুলির একটি অনন্য ক্রম তৈরি হয়। একটি টেবিল-চালিত পার্সারের ব্যাকরণ সম্পর্কে তার সমস্ত জ্ঞান থাকে যা পার্সার টেবিল নামে অপরিবর্তনীয় ডেটাতে এনকোড করা থাকে। পার্সারের প্রোগ্রাম কোড হল একটি সাধারণ জেনেরিক লুপ যা অনেক ব্যাকরণ এবং ভাষায় অপরিবর্তিতভাবে প্রযোজ্য। অগ্রাধিকার পদ্ধতির জন্য টেবিলগুলি হাতে তৈরি করা যেতে পারে। এলআর পদ্ধতির জন্য, জটিল টেবিলগুলি বাইসনের মতো কিছু পার্সার জেনারেটর সরঞ্জাম দ্বারা যান্ত্রিকভাবে একটি ব্যাকরণ থেকে উদ্ভূত হয়। পার্সার টেবিলগুলি সাধারণত ব্যাকরণের চেয়ে অনেক বড় হয়। টেবিল-চালিত নয় এমন অন্যান্য পার্সারগুলিতে, যেমন পুনরাবৃত্তিমূলক বংশোদ্ভূত, প্রতিটি ভাষা গঠন একটি ভিন্ন সাবরুটিন দ্বারা পার্স করা হয়, যা সেই একটি গঠনের বাক্যবিন্যাসের জন্য বিশেষায়িত। পার্সার ক্রিয়া স্থানান্তর-হ্রাস পার্সার কার্যকরী কারণ এতে কোনও ব্যাক আপ জড়িত থাকে না। এর মোট এক্সিকিউশন সময় ইনপুটের দৈর্ঘ্য এবং সম্পূর্ণ পার্স গাছের আকারের সাথে রৈখিকভাবে স্কেল করে। ব্যাকট্র্যাক করা অন্যান্য পার্সার পদ্ধতিগুলি খারাপভাবে অনুমান করতে এক্সপোনেনশিয়াল সময় নিতে পারে। অনুমান এড়ানোর জন্য, শিফট-রিডিউস পার্সার প্রায়শই পূর্বের স্ক্যান করা চিহ্নগুলির সাথে কী করতে হবে তা সিদ্ধান্ত নেওয়ার আগে পরবর্তী স্ক্যান করা প্রতীকটির দিকে (বাম-থেকে-ডান পাঠ্যের ডানদিকে) তাকায়। লেক্সিকাল স্ক্যানার বাকি পার্সারের আগে একটি প্রতীক কাজ করে। লুকহেড প্রতীকটিকে প্রতিটি পার্সিং সিদ্ধান্তের জন্য 'ডান হাতের প্রসঙ্গ' বলা হয়। (কদাচিৎ, দুই বা ততোধিক চেহারা চিহ্ন ব্যবহার করা যেতে পারে, যদিও বেশিরভাগ ব্যবহারিক ব্যাকরণ একটি চেহারা চিহ্ন ব্যবহার করার জন্য ডিজাইন করা যেতে পারে।) একটি শিফট-রিডিউস পার্সার অপেক্ষা করে যতক্ষণ না এটি কোনও নির্মাণের সমস্ত অংশ স্ক্যান এবং পার্স করে সংযুক্ত গঠনটি কী তা প্রতিশ্রুতিবদ্ধ করার আগে। পার্সার তারপর আর অপেক্ষা করার পরিবর্তে সংমিশ্রণে অবিলম্বে কাজ করে। উপরের পার্স ট্রি-র উদাহরণে, পার্স ট্রি-র সেই অংশগুলিকে সংগঠিত করার জন্য আর অপেক্ষা করার পরিবর্তে, 'বি' বাক্যাংশটি 'ভ্যালু'-তে এবং তারপর '+' লুকহেডে দেখা যাওয়ার সাথে সাথে 3-6 ধাপে 'প্রোডাক্টস অ্যান্ড সামস'-এ হ্রাস পায়। 'বি'-কে কীভাবে পরিচালনা করতে হবে তার সিদ্ধান্তগুলি কেবল পার্সার এবং স্ক্যানার ইতিমধ্যে যা দেখেছে তার উপর ভিত্তি করে, ডানদিকে অনেক পরে প্রদর্শিত জিনিসগুলি বিবেচনা না করে। হ্রাসগুলি সাম্প্রতিকতম পার্স করা জিনিসগুলিকে পুনর্গঠন করে, অর্থাৎ লুকহেড প্রতীকের অবিলম্বে বাম দিকে। সুতরাং ইতিমধ্যেই বিশ্লেষণ করা জিনিসগুলির তালিকা একটি স্ট্যাকের মতো কাজ করে। এই পার্স স্ট্যাক ডানদিকে বৃদ্ধি পায়। স্ট্যাকের বেস বা নীচে বাম দিকে থাকে এবং বামতম, প্রাচীনতম পার্স খণ্ডটি ধরে রাখে। প্রতিটি হ্রাস পদক্ষেপ শুধুমাত্র ডানদিকের, নতুনতম পার্স খণ্ডগুলিতে কাজ করে। (এই সঞ্চিত পার্স স্ট্যাকটি টপ-ডাউন পার্সার দ্বারা ব্যবহৃত ভবিষ্যদ্বাণীমূলক, বাম দিকে ক্রমবর্ধমান পার্স স্ট্যাকের থেকে খুব আলাদা।) যখন ব্যাকরণের নিয়ম যেমন প্রোডাক্টস * প্রোডাক্টস * ভ্যালু প্রয়োগ করা হয়, তখন স্ট্যাক টপ পার্স ট্রি ধরে রাখে। "প্রোডাক্টস * ভ্যালু"। নিয়মের ডান দিকের এই উদাহরণটিকে হ্যান্ডেল বলা হয়। হ্রাস পদক্ষেপটি "পণ্য * মূল্য" হ্যান্ডেলটিকে বাম দিকের নন-টার্মিনাল দ্বারা প্রতিস্থাপন করে, এই ক্ষেত্রে একটি বড় পণ্য। যদি পার্সার সম্পূর্ণ পার্স ট্রি তৈরি করে, তবে অভ্যন্তরীণ পণ্যের জন্য তিনটি গাছ, *, এবং মান বৃহত্তর পণ্যের জন্য একটি নতুন গাছের মূল দ্বারা মিলিত হয়। অন্যথায়, অভ্যন্তরীণ পণ্য এবং মূল্য থেকে শব্দার্থগত বিবরণগুলি পরবর্তী কিছু সংকলক পাসের আউটপুট হয়, অথবা নতুন পণ্য প্রতীকে একত্রিত এবং সংরক্ষণ করা হয়। পার্সার পার্স স্ট্যাকের শীর্ষে হ্রাস প্রয়োগ করতে থাকে যতক্ষণ না এটি সেখানে ব্যাকরণের নিয়মের নতুন সম্পূর্ণ উদাহরণ খুঁজে পেতে থাকে। যখন আর কোনও নিয়ম প্রয়োগ করা যায় না, তখন পার্সার লুকহেড প্রতীকটি পার্স স্ট্যাকে স্থানান্তরিত করে, একটি নতুন লুকহেড প্রতীক স্ক্যান করে এবং আবার চেষ্টা করে। স্থানান্তর-হ্রাস পার্সারের প্রকারগুলি পার্সার টেবিলগুলি দেখায় যে শীর্ষস্থানীয় পার্স স্ট্যাক প্রতীক এবং লুকহেড প্রতীকের প্রতিটি আইনি সংমিশ্রণের জন্য পরবর্তী কী করতে হবে। সেই পরবর্তী পদক্ষেপটি অবশ্যই অনন্য হতে হবে; হয় স্থানান্তর, অথবা হ্রাস, কিন্তু উভয়ই নয়। (এটি ব্যাকরণের উপর আরও কিছু সীমাবদ্ধতা বোঝায়, যা দ্ব্যর্থহীন নয়।) বিভিন্ন ধরনের স্থানান্তর-হ্রাস পার্সারের মধ্যে টেবিলের বিশদ বিবরণ ব্যাপকভাবে পরিবর্তিত হয়। অগ্রাধিকার পার্সারগুলিতে, হ্যান্ডেলগুলির ডান প্রান্তটি লুকহেড প্রতীকের সাথে শীর্ষ স্ট্যাক প্রতীকগুলির অগ্রাধিকার স্তর বা ব্যাকরণের আঁটসাঁটতার তুলনা করে পাওয়া যায়। উপরের উদাহরণে, ইন্টি এবং আইডি বিবৃতি ডিলিমিটারের তুলনায় অভ্যন্তরীণ ব্যাকরণ স্তরের অন্তর্গত। সুতরাং ইন্ট এবং আইডি উভয়কেই এর চেয়ে উচ্চতর অগ্রাধিকার হিসাবে বিবেচনা করা হয় এবং যখনই অনুসরণ করা হয় তখন অন্য কিছুতে হ্রাস করা উচিত। বিভিন্ন ধরনের অগ্রাধিকার পার্সার রয়েছে, যার প্রত্যেকটিতে হ্যান্ডেলের বাম প্রান্তটি খুঁজে বের করার এবং প্রয়োগ করার জন্য সঠিক নিয়মটি বেছে নেওয়ার বিভিন্ন উপায় রয়েছেঃ অপারেটর-পূর্ববর্তী পার্সার, একটি খুব সহজ সংখ্যাসূচক পদ্ধতি যা এক্সপ্রেশনগুলির জন্য কাজ করে তবে সাধারণ প্রোগ্রাম সিনট্যাক্সের জন্য নয়। সহজ অগ্রাধিকার পার্সার, ডান এবং বাম প্রান্ত খুঁজে পেতে একটি বড় এমএক্সএন টেবিল ব্যবহার করে। পিএল360-এ ব্যবহৃত। সাধারণ প্রোগ্রামিং ভাষাগুলি পরিচালনা করে না। দুর্বল অগ্রাধিকার পার্সার, শুধুমাত্র হ্যান্ডেলের ডান প্রান্ত খুঁজে বের করার জন্য অগ্রাধিকার টেবিল ব্যবহার করে। সহজ অগ্রগতির চেয়ে বেশি ব্যাকরণ পরিচালনা করে। বর্ধিত অগ্রাধিকার পার্সার। মিক্সড স্ট্র্যাটেজি প্রিডেন্স পার্সার, এক্সপিএল-এর মূল সংস্করণ দ্বারা ব্যবহৃত। "ট্রিপল" অন্তর্ভুক্ত করার জন্য যে কোনও অগ্রাধিকার শনাক্তকারীতে অন্তর্নিহিত "ডাবলস" প্রসারিত করে। এসএলআর-এর চেয়ে কম শক্তিশালী। সাধারণত তুলনামূলকভাবে ছোট ভাষাগুলির জন্যও খুব বড় টেবিল থাকে যেমন এক্সপিএল নিজেই অনেকগুলি "ট্রিপল"-এর কারণে যা অগ্রাধিকার পদ্ধতি দ্বারা আরোপিত সীমার বাইরে ব্যাকরণগুলি সনাক্ত করতে প্রয়োজন। অগ্রাধিকার পার্সারগুলি ব্যাকরণের মধ্যে সীমাবদ্ধ যা তারা পরিচালনা করতে পারে। সিদ্ধান্ত নেওয়ার সময় তারা বেশিরভাগ পার্স স্ট্যাককে উপেক্ষা করে। তারা কেবল শীর্ষস্থানীয় প্রতীকগুলির নাম বিবেচনা করে, ব্যাকরণে সেই প্রতীকগুলি এখন কোথায় উপস্থিত হচ্ছে তার সম্পূর্ণ প্রসঙ্গ নয়। অগ্রগতির জন্য প্রয়োজন যে অনুরূপ-চেহারার প্রতীক সংমিশ্রণগুলি অবশ্যই বিশ্লেষণ করা উচিত এবং ব্যাকরণ জুড়ে অভিন্ন উপায়ে ব্যবহার করা উচিত তবে প্রসঙ্গ নির্বিশেষে এই সংমিশ্রণগুলি ঘটে। এলআর পার্সার হল স্থানান্তর-হ্রাস পার্সিং-এর আরও নমনীয় রূপ, যা আরও অনেক ব্যাকরণ পরিচালনা করে। এলআর পার্সার প্রসেসিং এলআর পার্সারগুলি একটি স্টেট মেশিনের মতো কাজ করে, প্রতিটি শিফটের জন্য একটি স্টেট ট্রানজিশন সম্পাদন করে বা ক্রিয়া হ্রাস করে। এগুলি একটি স্ট্যাক নিয়োগ করে যেখানে বর্তমান অবস্থাটি স্থানান্তর ক্রিয়া দ্বারা ধাক্কা দেওয়া হয় (নিচে)। এই স্ট্যাকটি তারপর হ্রাস ক্রিয়া দ্বারা পপ (আপ) করা হয়। এই প্রক্রিয়াটি এলআর পার্সারকে সমস্ত নির্ধারক প্রসঙ্গ-মুক্ত ব্যাকরণ পরিচালনা করতে দেয়, যা অগ্রাধিকার ব্যাকরণের একটি সুপারসেট। এলআর পার্সার সম্পূর্ণরূপে ক্যানোনিকাল এলআর পার্সার দ্বারা প্রয়োগ করা হয়। লুক-অ্যাহেড এলআর এবং সিম্পল এলআর পার্সারগুলি এর সরলীকৃত রূপগুলি প্রয়োগ করে যা মেমরির প্রয়োজনীয়তা উল্লেখযোগ্যভাবে হ্রাস করেছে। সাম্প্রতিক গবেষণায় এমন পদ্ধতিগুলি চিহ্নিত করা হয়েছে যার মাধ্যমে নুথের টেবিল-বিল্ডিং অ্যালগরিদমের তুলনায় নাটকীয়ভাবে টেবিলের প্রয়োজনীয়তা হ্রাস করে ক্যানোনিকাল এলআর পার্সারগুলি প্রয়োগ করা যেতে পারে। এলআর, এলএএলআর বা এসএলআর যাই হোক না কেন, বেসিক স্টেট মেশিন একই; শুধুমাত্র টেবিলগুলি আলাদা, এবং এই টেবিলগুলি প্রায় সবসময় যান্ত্রিকভাবে তৈরি করা হয়। উপরন্তু, এই টেবিলগুলি সাধারণত এমনভাবে প্রয়োগ করা হয় যাতে একটি রিডিউস একটি কল থেকে একটি ক্লোজড সাবরুটিনে পরিণত হয় যা স্টেট মেশিনের বাইরের অংশ এবং যা এমন একটি ফাংশন সম্পাদন করে যা ব্যাকরণ নিয়মের শব্দার্থবিদ্যা দ্বারা বোঝানো হয় যা রিডিউসএড হচ্ছে। অতএব, পার্সারটি একটি অপরিবর্তনীয় অবস্থা মেশিনের অংশে এবং একটি বৈকল্পিক শব্দার্থিক অংশে বিভক্ত করা হয়। এই মৌলিক পার্থক্য উচ্চ মানের পার্সারের বিকাশকে উৎসাহিত করে যা ব্যতিক্রমীভাবে নির্ভরযোগ্য। একটি নির্দিষ্ট স্ট্যাক অবস্থা এবং লুকহেড প্রতীক দেওয়া হলে, সুনির্দিষ্টভাবে চারটি সম্ভাব্য ক্রিয়া রয়েছে, ত্রুটি, স্থানান্তর, হ্রাস এবং বন্ধ (এরপরে কনফিগারেশন হিসাবে উল্লেখ করা হয়েছে)। একটি বিন্যাসে একটি বিন্দুর উপস্থিতি বর্তমান চেহারাটির অবস্থানকে উপস্থাপন করে, যেখানে বিন্দুটির ডানদিকে লুকহেড প্রতীক দেখানো হয় (এবং যা সর্বদা একটি টার্মিনাল প্রতীকের সাথে মিলে যায়), এবং বিন্দুটির বামদিকে বর্তমান স্ট্যাক অবস্থা (এবং যা সাধারণত একটি নন-টার্মিনাল প্রতীকের সাথে মিলে যায়)। উচ্চ কার্যকারিতা সহ ব্যবহারিক কারণে, টেবিলগুলি সাধারণত দ্বি-বিট প্রতীকগুলির কিছুটা বড়, সহায়ক অ্যারে দ্বারা প্রসারিত হয়, স্পষ্টতই চারটি দ্বি-বিট প্রতীকে সংকুচিত করা হয়, একটি বাইট, বাইট-ভিত্তিক মেশিনে দক্ষ অ্যাক্সেসের জন্য, প্রায়শই এনকোড করা হয়ঃ 00বি ত্রুটির প্রতিনিধিত্ব করে 01বি প্রতিনিধিত্ব করে শিফট 10বি প্রতিনিধিত্ব করে হ্রাস 11বি প্রতিনিধিত্ব করে স্টপ (স্টপ হল শিফটের একটি বিশেষ ক্ষেত্রে)। পুরো অ্যারেতে সাধারণত বেশিরভাগ ত্রুটি কনফিগারেশন, স্থানান্তর এবং হ্রাস কনফিগারেশনের একটি ব্যাকরণ-সংজ্ঞায়িত সংখ্যা এবং একটি স্টপ কনফিগারেশন অন্তর্ভুক্ত থাকে। প্রোগ্রামিং সিস্টেমে যা কোয়াটারনারি সংখ্যা পদ্ধতিতে মানগুলির নির্দিষ্টকরণকে সমর্থন করে (বেস 4, প্রতি কোয়াটারনারি ডিজিটে দুটি বিট), যেমন এক্সপিএল, এগুলি কোড করা হয়, উদাহরণস্বরূপঃ "(2). 0" ত্রুটির প্রতিনিধিত্ব করে "(2). 1" স্থানান্তরের প্রতিনিধিত্ব করে "(2). 2" হ্রাসের প্রতিনিধিত্ব করে "(2). 3" স্থানান্তর বন্ধের প্রতিনিধিত্ব করে এবং হ্রাস টেবিলগুলি অ্যারে থেকে আলাদাভাবে প্রয়োগ করা হয়। অক্জিলিয়ারি অ্যারে শুধুমাত্র বর্তমান অবস্থা এবং লুকহেড প্রতীকের জন্য "তদন্ত" করা হয়। (সহায়ক) অ্যারে "পূর্ণ", যেখানে (স্থানান্তর এবং হ্রাস) টেবিলগুলি প্রকৃতপক্ষে খুব "বিরল" হতে পারে এবং সেই স্থানান্তর এবং হ্রাস টেবিলগুলির সর্বোত্তম "পচন" এর মাধ্যমে উল্লেখযোগ্য দক্ষতা অর্জন করা যেতে পারে (ত্রুটি এবং স্টপের কোনও টেবিলের প্রয়োজন নেই)। একটি স্থানান্তর-হ্রাস পার্সারের মৌলিক সংজ্ঞা থেকে স্থানান্তর এবং হ্রাস কনফিগারেশনগুলি সুস্পষ্ট। তারপর, স্টপ এমন একটি বিন্যাসের প্রতিনিধিত্ব করে যেখানে স্ট্যাকের শীর্ষে থাকা অবস্থা এবং লুকহেড টার্মিনাল প্রতীকটি বিষয় ব্যাকরণের মধ্যে থাকে এবং প্রোগ্রামের সমাপ্তির প্রতিনিধিত্ব করেঃ δ <প্রোগ্রাম> δ এটি চূড়ান্ত δ এর বাইরে স্থানান্তর করা অসম্ভব যাতে ধারণাগতভাবে δ <প্রোগ্রাম> δ> ত্রুটি, তারপর, এমন একটি কনফিগারেশনকে উপস্থাপন করে যেখানে স্ট্যাকের শীর্ষে থাকা অবস্থা এবং লুকহেড টার্মিনাল প্রতীকটি বিষয় ব্যাকরণের মধ্যে নেই। এটি একটি ত্রুটি পুনরুদ্ধার পদ্ধতির আহ্বান করার সুযোগ উপস্থাপন করে, সম্ভবত, তার সবচেয়ে সরল আকারে, লুকহেড টার্মিনাল প্রতীকটি ফেলে দেওয়ার জন্য এবং পরবর্তী টার্মিনাল প্রতীকটি পড়ার জন্য, তবে স্ট্যাকটি ছাঁটাই করা, বা লুকহেড টার্মিনাল প্রতীকটি ফেলে দেওয়া এবং স্ট্যাকটি ছাঁটাই করা সহ অন্যান্য অনেক প্রোগ্রামযুক্ত ক্রিয়া সম্ভব (এবং একটি প্যাথোলজিকাল ক্ষেত্রে, সাধারণত একটি "নাল স্টেটমেন্ট" নিয়ে গঠিত যেখানে "প্রোগ্রাম" পাওয়া সম্ভব)। বেশিরভাগ ক্ষেত্রে, স্ট্যাকটি উদ্দেশ্যমূলকভাবে প্রি-লোড করা হয়, অর্থাৎ, δ· <প্রোগ্রাম> δ দিয়ে শুরু করা হয় যার মাধ্যমে প্রাথমিক δ ইতিমধ্যেই স্বীকৃত হয়েছে বলে ধরে নেওয়া হয়। এটি, তারপর, প্রোগ্রামের শুরুর প্রতিনিধিত্ব করে, এবং এর ফলে, একটি পৃথক START কনফিগারেশন এড়ানো যায়, যা ধারণাগতভাবে একটি বিশেষ ছদ্ম-টার্মিনাল প্রতীক যান্ত্রিকভাবে ব্যাকরণে যোগ করা হয়, ঠিক যেমন <প্রোগ্রাম> একটি বিশেষ ছদ্ম-অ-টার্মিনাল প্রতীক যান্ত্রিকভাবে ব্যাকরণে যোগ করা হয় (যদি প্রোগ্রামার ব্যাকরণে স্পষ্টভাবে <প্রোগ্রাম> অন্তর্ভুক্ত না করে, তবে <প্রোগ্রাম> স্বয়ংক্রিয়ভাবে প্রোগ্রামারের পক্ষ থেকে ব্যাকরণে যোগ করা হবে)। স্পষ্টতই, এই ধরনের পার্সারের সুনির্দিষ্টভাবে একটি (অন্তর্নিহিত) স্টার্ট কনফিগারেশন এবং একটি (স্পষ্ট) স্টপ কনফিগারেশন রয়েছে, তবে এটি করতে পারে, এবং সাধারণত শত শত স্থানান্তর এবং হ্রাস কনফিগারেশন এবং সম্ভবত হাজার হাজার ত্রুটি কনফিগারেশন থাকতে পারে। রেফারেন্স পার্সিং অ্যালগরিদম