এলএল(1) এবং এলআর(1) পার্সার

এডভান্সড টপিকস - কম্পাইলার ডিজাইন (Compiler Design) - Computer Science

166

এলএল(1) পার্সার (LL(1) Parser)

এলএল(1) পার্সার হল একটি টপ-ডাউন পার্সিং টেকনিক, যা লেফট টু রাইট ইনপুট পড়ে এবং লেফট-রাইট আউটপুট তৈরি করে। এখানে "LL" নির্দেশ করে:

L: লেফট টু রাইট ইনপুট পড়া
L: লেফট-রাইট আউটপুট তৈরি করা
1: পূর্বাভাসের জন্য একটিমাত্র টোকেন (lookahead token) ব্যবহার করা

বৈশিষ্ট্য:

সহজ বোঝা: এলএল(1) পার্সার সাধারণত সহজ এবং স্বচ্ছ বোঝার জন্য পরিচিত।
প্রেডিক্টিভ পার্সিং: এটি সিনট্যাক্স ট্রি তৈরি করতে পূর্বাভাস ব্যবহার করে, যা ইনপুট স্ট্রিমের ভিত্তিতে পরবর্তী ইনস্ট্রাকশন নির্বাচন করতে সহায়ক।
পূর্বাভাস টেবিল: এলএল(1) পার্সিংয়ের জন্য একটি পূর্বাভাস টেবিল তৈরি করা হয়, যা বিভিন্ন উৎপাদনের জন্য টোকেনগুলি নির্দেশ করে।

উদাহরণ:

ধরি, নিচের গ্রামার:

E → E + T | T
T → int

এখন E উৎপাদনের জন্য এলএল(1) পার্সার একটি পূর্বাভাস টেবিল তৈরি করবে যা ইনপুট অনুযায়ী সিদ্ধান্ত নেবে।

এলআর(1) পার্সার (LR(1) Parser)

এলআর(1) পার্সার হল একটি বটম-আপ পার্সিং টেকনিক, যা ইনপুটের লেফট টু রাইট পড়ে এবং ডান থেকে বামে উৎপাদন তৈরি করে। এখানে "LR" নির্দেশ করে:

L: লেফট টু রাইট ইনপুট পড়া
R: ডান থেকে বামে উৎপাদন করা
1: পূর্বাভাসের জন্য একটিমাত্র টোকেন ব্যবহার করা

বৈশিষ্ট্য:

জটিল গ্রামারের সমর্থন: এলআর(1) পার্সার জটিল এবং বেশি বৈচিত্র্যময় গ্রামারের সাথে কাজ করতে সক্ষম।
শিফট-রিডিউস কৌশল: এটি শিফট এবং রিডিউস কৌশল ব্যবহার করে ইনপুট বিশ্লেষণ করে।
রিডিউস টেবিল: এলআর(1) পার্সিংয়ের জন্য একটি রিডিউস টেবিল তৈরি করা হয়, যা নির্দেশ করে কখন ইনপুটকে রিডিউস করতে হবে।

উদাহরণ:

ধরি, নিচের গ্রামার:

E → E + T | T
T → int

এখন E উৎপাদনের জন্য এলআর(1) পার্সার শিফট এবং রিডিউস কৌশল ব্যবহার করে ইনপুট স্ট্রিম বিশ্লেষণ করবে এবং একটি সিনট্যাক্স ট্রি তৈরি করবে।