LL grammar
আনুষ্ঠানিক ভাষা তত্ত্বে, একটি এলএল ব্যাকরণ হল একটি প্রসঙ্গ-মুক্ত ব্যাকরণ যা একটি এলএল পার্সার দ্বারা বিশ্লেষণ করা যেতে পারে, যা বাম থেকে ডানে ইনপুট বিশ্লেষণ করে এবং বাক্যের বামতম ব্যুৎপত্তি তৈরি করে (তাই এলএল, এলআর পার্সারের তুলনায় যা একটি ডানতম ব্যুৎপত্তি গঠন করে)। যে ভাষায় এল. এল ব্যাকরণ রয়েছে তাকে এল. এল ভাষা বলা হয়। এগুলি যথাক্রমে নির্ধারক প্রসঙ্গ-মুক্ত ব্যাকরণ (ডিসিএফজি) এবং নির্ধারক প্রসঙ্গ-মুক্ত ভাষার (ডিসিএফএল) উপসেট গঠন করে। একটি বলে যে একটি প্রদত্ত ব্যাকরণ বা ভাষা "একটি এলএল ব্যাকরণ/ভাষা" বা কেবল "এলএল" নির্দেশ করে যে এটি এই শ্রেণীতে রয়েছে। এলএল পার্সার হল টেবিল-ভিত্তিক পার্সার, যা এলআর পার্সারের অনুরূপ। এলএল ব্যাকরণগুলি বিকল্পভাবে সুনির্দিষ্টভাবে চিহ্নিত করা যেতে পারে যেগুলি একটি ভবিষ্যদ্বাণীমূলক পার্সার দ্বারা বিশ্লেষণ করা যেতে পারে-ব্যাকট্র্যাকিং ছাড়াই একটি পুনরাবৃত্তিমূলক অবতরণ পার্সার-এবং এগুলি সহজেই হাত দিয়ে লেখা যেতে পারে। এই নিবন্ধটি এলএল ব্যাকরণের আনুষ্ঠানিক বৈশিষ্ট্য সম্পর্কে; বিশ্লেষণের জন্য, এলএল পার্সার বা রিকার্সিভ ডিসেন্ট পার্সার দেখুন। আনুষ্ঠানিক সংজ্ঞা সীমাবদ্ধ ক্ষেত্রে একটি প্রাকৃতিক সংখ্যা দেওয়া হলে, একটি প্রসঙ্গ-মুক্ত ব্যাকরণ হল একটি এলএল (কে) ব্যাকরণ, যদি প্রতীক পর্যন্ত দৈর্ঘ্যের প্রতিটি টার্মিনাল প্রতীক স্ট্রিংয়ের জন্য, প্রতিটি নন-টার্মিনাল প্রতীকের জন্য এবং প্রতিটি টার্মিনাল প্রতীক স্ট্রিংয়ের জন্য, সর্বাধিক একটি উৎপাদন নিয়ম থাকে যাতে কিছু টার্মিনাল প্রতীক স্ট্রিংয়ের জন্য, স্ট্রিংটি শুরু প্রতীক থেকে উদ্ভূত করা যেতে পারে, প্রথম প্রয়োগের নিয়ম থেকে উদ্ভূত করা যেতে পারে এবং সম্মত এবং এর প্রথম চিহ্নগুলি থেকে উদ্ভূত করা যেতে পারে। একটি বিকল্প, কিন্তু সমতুল্য, আনুষ্ঠানিক সংজ্ঞা নিম্নরূপঃ একটি এলএল (কে) ব্যাকরণ যদি, নির্বিচারে ব্যুৎপত্তিগুলির জন্য যখন প্রথম চিহ্নগুলি এর সাথে একমত হয়। অনানুষ্ঠানিকভাবে, যখন কোনও পার্সার তার বাম দিকের নন-টার্মিনাল সহ উদ্ভূত হয় এবং ইতিমধ্যে ইনপুট থেকে গ্রহণ করা হয়, তখন সেটি দেখে এবং বর্তমান ইনপুটের পরবর্তী চিহ্নগুলিতে উঁকি দিয়ে, পার্সার নিশ্চিতভাবে উৎপাদন নিয়মটি সনাক্ত করতে পারে। অতীতের ইনপুট বিবেচনা না করেও যখন নিয়ম শনাক্তকরণ সম্ভব হয়, তখন ব্যাকরণকে একটি শক্তিশালী এলএল (কে) ব্যাকরণ বলা হয়। একটি শক্তিশালী এলএল (কে) ব্যাকরণের আনুষ্ঠানিক সংজ্ঞায়, এর জন্য সর্বজনীন পরিমাপ বাদ দেওয়া হয় এবং এর জন্য "কিছু" পরিমাপের সাথে যুক্ত করা হয়। প্রতিটি এলএল (কে) ব্যাকরণের জন্য, একটি কাঠামোগতভাবে সমতুল্য শক্তিশালী এলএল (কে) ব্যাকরণ তৈরি করা যেতে পারে। এলএল (কে) ভাষাগুলির শ্রেণীটি সেটগুলির একটি কঠোরভাবে ক্রমবর্ধমান ক্রম গঠন করেঃ এলএল (0) এলএল (1) এলএল (2)। একটি প্রদত্ত ব্যাকরণ জি এলএল (কে) কিনা তা নির্ধারণযোগ্য, তবে একটি স্বেচ্ছাচারী ব্যাকরণ কিছু কে-এর জন্য এলএল (কে) কিনা তা নির্ধারণযোগ্য নয়। একটি প্রদত্ত এলআর (কে) ব্যাকরণও যদি কিছু মিটারের জন্য এলএল (এম) ব্যাকরণ হয় তবে এটিও নির্ধারণযোগ্য। প্রতিটি এলএল (কে) ব্যাকরণও একটি এলআর (কে) ব্যাকরণ। একটি ε-মুক্ত এলএল (1) ব্যাকরণও একটি এসএলআর (1) ব্যাকরণ। একটি এলএলআর (1) ব্যাকরণও একটি এলএলআর (1) ব্যাকরণ যার প্রতীকগুলির শূন্য এবং অ-শূন্য উভয়ই ব্যুৎপত্তি রয়েছে। একটি এলএল (1) ব্যাকরণ যার প্রতীকগুলির মধ্যে কেবল খালি ব্যুৎপত্তি রয়েছে তা এলএএলআর (1) হতে পারে বা নাও হতে পারে। এল. এল ব্যাকরণের বাম পুনরাবৃত্তি সম্বলিত নিয়ম থাকতে পারে না। প্রতিটি এলএল (কে) ব্যাকরণ যা ε-মুক্ত তা গ্রেবাচের স্বাভাবিক আকারে সমতুল্য এলএল (কে) ব্যাকরণে রূপান্তরিত করা যেতে পারে (যার সংজ্ঞা অনুসারে বাম পুনরাবৃত্তির নিয়ম নেই)। রেগুলার কেস একটি টার্মিনাল বর্ণমালা হতে দিন। একটি বিভাজনকে নিয়মিত বিভাজন বলা হয় যদি প্রত্যেকটির জন্য ভাষা নিয়মিত হয়। একটি প্রসঙ্গ মুক্ত ব্যাকরণ হতে দিন এবং এর একটি নিয়মিত বিভাজন হতে দিন। আমরা বলি যে এটি একটি এলএল () ব্যাকরণ যদি, নির্বিচারে ব্যুৎপত্তিগুলির জন্য এটি অনুসরণ করে। একটি ব্যাকরণ জি কে এলএল-রেগুলার (এলএলআর) বলা হয় যদি এমন একটি নিয়মিত পার্টিশন থাকে যে জি হল এলএল ()। একটি ভাষা এলএল-নিয়মিত হয় যদি এটি একটি এলএল-নিয়মিত ব্যাকরণ দ্বারা উত্পন্ন হয়। এলএলআর ব্যাকরণগুলি দ্ব্যর্থহীন এবং বাম-পুনরাবৃত্তিমূলক হতে পারে না। প্রতিটি এলএল (কে) ব্যাকরণ হল এলএলআর। প্রতিটি এলএল (কে) ব্যাকরণ নির্ধারণমূলক, তবে একটি এলএলআর ব্যাকরণ রয়েছে যা নির্ধারণমূলক নয়। সুতরাং এলএলআর ব্যাকরণের শ্রেণী প্রতিটি কে-এর জন্য এলএল (কে)-এর সংযোগের চেয়ে কঠোরভাবে বড়। একটি নিয়মিত বিভাজন দেওয়া হলে, প্রদত্ত ব্যাকরণটি এলএল () কিনা তা নির্ধারণযোগ্য। তবে, একটি স্বেচ্ছাচারী ব্যাকরণ জি এলএলআর কিনা তা নির্ধারণযোগ্য নয়। এর কারণ হল একটি ব্যাকরণ জি একটি নিয়মিত ভাষা তৈরি করে কিনা তা নির্ধারণ করা, যা জি-এর জন্য একটি নিয়মিত পার্টিশন খুঁজে বের করার জন্য প্রয়োজনীয় হবে, পোস্ট চিঠিপত্রের সমস্যায় হ্রাস করা যেতে পারে। প্রতিটি এলএলআর ব্যাকরণ এলআর-নিয়মিত (এলআরআর, এলআর (কে) ব্যাকরণের সমতুল্য), তবে একটি এলআর (1) ব্যাকরণ রয়েছে যা এলএলআর নয়। ঐতিহাসিকভাবে, এলএলআর ব্যাকরণ এলআরআর ব্যাকরণের আবিষ্কার অনুসরণ করে। একটি নিয়মিত বিভাজনের পরিপ্রেক্ষিতে একটি মুর মেশিন তৈরি করা যেতে পারে যাতে পার্সিংটি ডান থেকে বামে স্থানান্তরিত করা যায়, নিয়মিত উৎপাদনের উদাহরণগুলি চিহ্নিত করা যায়। একবার এটি হয়ে গেলে, একটি এলএল (1) পার্সার রৈখিক সময়ে ট্রান্সডিউসড ইনপুট পরিচালনা করার জন্য যথেষ্ট। সুতরাং, এলএলআর পার্সারগুলি সমান দক্ষতার সাথে এলএল (কে) পার্সারগুলির চেয়ে কঠোরভাবে বড় ব্যাকরণের একটি শ্রেণী পরিচালনা করতে পারে। তা সত্ত্বেও এলএলআর তত্ত্বের কোনও বড় প্রয়োগ নেই। একটি সম্ভাব্য এবং অত্যন্ত যুক্তিসঙ্গত কারণ হল যে এলএল (কে) এবং এলআর (কে) পার্সারের জন্য জেনারেটিভ অ্যালগরিদম থাকলেও, একটি এলএলআর/এলআরআর পার্সার তৈরির সমস্যা অনিশ্চিত, যদি না কেউ আগে থেকে একটি নিয়মিত পার্টিশন তৈরি করে থাকে। কিন্তু ব্যাকরণের পরিপ্রেক্ষিতে একটি উপযুক্ত নিয়মিত বিভাজন তৈরি করার সমস্যাও অনিশ্চিত। সরল নিয়ামক ভাষাসমূহ একটি প্রসঙ্গ-মুক্ত ব্যাকরণকে সরল নিয়ামক বা সহজ বলা হয়, যদি এটি গ্রেবাচের স্বাভাবিক আকারে হয় (অর্থাৎ। প্রতিটি নিয়মের ফর্ম রয়েছে), এবং একই নন-টার্মিনালের জন্য বিভিন্ন ডান দিক সর্বদা বিভিন্ন টার্মিনাল দিয়ে শুরু হয়। স্ট্রিংয়ের একটি সেটকে একটি সহজ নির্ধারক বা কেবল সহজ ভাষা বলা হয়, যদি এটির একটি সহজ নির্ধারক ব্যাকরণ থাকে। গ্রেবাচের স্বাভাবিক আকারে ε-মুক্ত LL (1) ব্যাকরণ সহ ভাষাগুলির শ্রেণী সহজ নির্ধারক ভাষার শ্রেণীর সমান। এই ভাষা শ্রেণীতে ε না থাকা নিয়মিত সেটগুলি অন্তর্ভুক্ত রয়েছে। সমতুল্যতা এর জন্য নির্ণায়ক, যদিও অন্তর্ভুক্তি নয়। এল. এল ব্যাকরণ, বিশেষ করে এল. এল (1) ব্যাকরণ, অত্যন্ত ব্যবহারিক আগ্রহের বিষয়, কারণ এগুলি বিশ্লেষণ করা সহজ, হয় এল. এল পার্সার দ্বারা বা পুনরাবৃত্তিমূলক ডিসেন্ট পার্সার দ্বারা, এবং এই কারণে এল. এল (1) হওয়ার জন্য ডিজাইন করা হয়েছে। K-এর উচ্চ মান সহ ব্যাকরণের উপর ভিত্তি করে ভাষাগুলি ঐতিহ্যগতভাবে বিশ্লেষণ করা কঠিন বলে মনে করা হয়, যদিও স্বেচ্ছাচারী k-এর জন্য LL (k) ব্যাকরণকে সমর্থনকারী পার্সার জেনারেটরের প্রাপ্যতা এবং ব্যাপক ব্যবহারের কারণে এটি এখন কম সত্য। আরও দেখুন LL (k) এবং LL (*) পার্সারের তালিকার জন্য পার্সার জেনারেটরের তুলনা।