বৃহৎ ভাষার মডেলের জন্য দক্ষ নির্দেশিত প্রজন্ম: পুনরাবৃত্তিমূলক পার্সিংয়ের এক্সটেনশন

লিঙ্কের টেবিল

• বিমূর্ত এবং ভূমিকা
• এলএলএম স্যাম্পলিং এবং গাইডেড জেনারেশন
• পুনরাবৃত্তিমূলক FSM প্রক্রিয়াকরণ এবং সূচীকরণ
• পুনরাবৃত্তিমূলক পার্সিংয়ের এক্সটেনশন
• আলোচনা, রেফারেন্স এবং স্বীকৃতি

4. পুনরাবৃত্তিমূলক পার্সিংয়ের এক্সটেনশন

এই বিভাগে, আমরা আমাদের ফোকাসকে সাধারণ পার্সার-নির্দেশিত প্রজন্মের দিকে নিয়ে যাই এবং CFG হিসাবে দেওয়া পাইথনের মতো ব্যাকরণের জন্য একটি সাধারণ ওয়াক-থ্রু দিয়ে শুরু করি।

"d" এবং "ef" এর মতো স্ট্রিংগুলির সমন্বয়ে গঠিত একটি শব্দভাণ্ডার বিবেচনা করুন যা একটি অন্তর্নিহিত CFG অনুসারে পাইথনের মতো সিনট্যাক্স তৈরি করতে একত্রিত হতে পারে, এবং ধরে নিন যে এই স্ট্রিংগুলি অ্যালগরিদম 1 এর মতো একটি প্রক্রিয়া অনুসারে ক্রমানুসারে নমুনাযুক্ত এবং সংযুক্ত করা হয়েছে।

অধিকন্তু, CFG-তে একটি টার্মিনাল প্রতীক DEF বিবেচনা করুন যা "def" স্ট্রিং এর সাথে মিলে যায় এবং তুচ্ছ রেগুলার এক্সপ্রেশন def দ্বারা দেওয়া হয়। এছাড়াও, রেগুলার এক্সপ্রেশন [^\W\d]\w* (যেমন পাইথন আইডেন্টিফায়ার) দ্বারা প্রদত্ত একটি NAME চিহ্ন বিবেচনা করুন। আমরা ক্রমানুসারে পূর্বোক্ত শব্দভান্ডার থেকে নমুনাকৃত স্ট্রিংগুলিকে এমনভাবে পার্স করতে চাই যা পাইথন সিনট্যাক্স মেনে চলে।

উদাহরণস্বরূপ, নিম্নলিখিতটি এরকম একটি ক্রম হতে পারে: ["d", "ef", "f", "oo(", "):", " ", "pass"]। অনুক্রমের সমস্ত উপাদান শব্দভান্ডারের সংজ্ঞা উপাদান দ্বারা। সিকোয়েন্সকে সংযুক্ত করার ফলে "def foo(): pass তৈরি হয়, যা একটি ফাংশন সংজ্ঞায়িত টোকেনগুলির একটি বৈধ ক্রম। আমরা যে পরিস্থিতি বিবেচনা করছি তাতে, আমরা একটি নির্দিষ্ট বিন্দু পর্যন্ত সমস্ত টোকেন পর্যবেক্ষণ করব এবং সেই বিন্দুর পরেরগুলি সম্পর্কে কিছুই জানি না।

উদাহরণস্বরূপ, উদাহরণের ক্রমানুসারে তৃতীয় পর্যবেক্ষণে, আমাদের কাছে সংযুক্ত স্ট্রিং "def f" আছে। যদি আমরা এই স্ট্রিংটিকে লেক্স/পার্স করি তাহলে একটি প্রথাগত পদ্ধতি DEF NAME প্রতীক ক্রম ফিরিয়ে দেবে, যা "f" কে সম্পূর্ণ NAME টোকেন হিসাবে ভুল শনাক্ত করে। আমরা বাকি ক্রম থেকে দেখতে পাচ্ছি, সঠিক NAME টোকেন হবে "foo"।

সাধারণভাবে, পরবর্তী বৈধ স্ট্রিংগুলি যা শব্দভাণ্ডার থেকে নমুনা করা যেতে পারে সেগুলি হল

1. বর্তমানে "f" দিয়ে শুরু হচ্ছে (আমাদের উদাহরণে সম্পূর্ণ ক্রম অনুসারে) এবং/অথবা

   
   

2. যেকোনো কিছু যা "(" দিয়ে শুরু হয়-অর্থাৎ রেগুলার এক্সপ্রেশন সহ একটি LPAR চিহ্ন (-এবং একটি বৈধ আর্গুমেন্ট স্বাক্ষর নির্দিষ্ট করতে এগিয়ে যায়।

প্রথম ক্ষেত্রে, "f" কে পাইথনে আংশিকভাবে মিলে যাওয়া NAME চিহ্ন হিসাবে দেখা যেতে পারে, এবং–মনে করে যে এটির রেগুলার এক্সপ্রেশন হল [^\W\d]\w*–আমরা বলতে পারি যে এটি উভয় সাব-প্যাটার্নের সাথে মেলে। (যেমন [^\W\d] এবং \w*) রেগুলার এক্সপ্রেশনে। আমাদের FSM-এর ব্যবহার FSM-এর রাজ্যগুলির মাধ্যমে সাব-প্যাটার্নের ধারণাকে আনুষ্ঠানিক করে তোলে। এই ক্ষেত্রে, NAME এর রেজেক্স একটি FSM, M দ্বারা তিনটি অবস্থার সাথে উপস্থাপন করা যেতে পারে: 0 (অর্থাৎ প্রাথমিক অবস্থা q0), 1 (যেমন [^\W\d]), এবং 2 (অর্থাৎ \w*) , যেখানে 1, 2 ∈ F.

অ্যালগরিদম 3 ব্যবহার করে, আমরা "f" এর জন্য FSM স্টেট সিকোয়েন্স (0, 1), (1, 2), (2, 2) এবং FSM, M, NAME চিহ্নের সাথে সম্পর্কিত। "f"-এর এই FSM ক্রমগুলি আমাদের বলে যে এই শব্দভান্ডারের স্ট্রিংটির জন্য ম্যাচিং 0, 1, বা 2 রাজ্যে শুরু হতে পারে এবং এটি 1 বা 2 রাজ্যে শেষ হতে পারে।

কেস 1. উপরে অনুসারে, পার্সিং চালিয়ে যেতে পারে-NAME চিহ্নের জন্য-পূর্বে 1 বা 2 রাজ্যে শেষ হওয়ার পরে। কেস 2 অনুসারে, পরবর্তী স্ট্রিংটি একটি LPAR দিয়েও শুরু হতে পারে বা ধারণ করতে পারে, ইঙ্গিত করে যে M শেষ হয়ে যাবে , যা এটি দিতে পারে যে 1 এবং 2 হল M-এর চূড়ান্ত অবস্থা যেখানে "f" পড়ার পরে পার্সিং বন্ধ হয়ে যাবে। M সমাপ্ত করাও ইঙ্গিত করে যে একটি NAME চিহ্ন সম্পূর্ণ হয়েছে, এবং LPAR গ্রহণকারী একটি রাষ্ট্রে রূপান্তর ব্যাকরণ দ্বারা অনুমোদিত ছিল।

এই দৃষ্টান্তে, পরবর্তী বৈধ শব্দভান্ডারের স্ট্রিংগুলি কমপক্ষে "d", "ef", "pass", " ", "oo(", কারণ এই সমস্ত স্ট্রিংগুলি আংশিকভাবে মিলে যাওয়া NAMEকে প্রসারিত করবে এবং শেষটিও হবে একটি LPAR পড়া বাকি স্ট্রিং, "): পার্স স্টেট অগ্রগতি, আমরা বিবেচনা করেছি শব্দভান্ডার থেকে একটি ক্রম অবৈধ সিনট্যাক্স হবে.

FSM সূচীকরণ পদ্ধতির সাথে সম্পর্কিত, এর মানে হল যে অ্যালগরিদম 4 FSM রাজ্যগুলি 0, 1, এবং 2 সাবসেট "d", "ef", "pass", " ", "oo(" প্রতীকের জন্য ম্যাপ করবে এবং এর এফএসএম, এম।

এই দৃষ্টান্তটি অন্তর্নিহিত পার্সার স্টেটগুলি বাদ দেয় যা নির্ধারণ করে কোন ব্যাকরণ চিহ্ন এবং রূপান্তর অনুমোদিত। আমরা পুশডাউন অটোমেটা (পিডিএ) ব্যবহার করি এফএসএম পদ্ধতির প্রসারিত করার জন্য এবং অবশিষ্ট বিবরণগুলিকে সম্বোধন করার জন্য।

4.1 পুশডাউন অটোমেটা ফর্মুলেশন

আমরা নিম্নলিখিত 6-টুপল উপস্থাপনা ব্যবহার করে পুশডাউন অটোমেটা সংজ্ঞায়িত করি [Sipser, 1996, সংজ্ঞা 2.13]:

একটি PDA-চালিত পার্সারের জন্য একটি সূচীকরণ পদ্ধতি তৈরি করার জন্য, আমাদের একটি CFG-এর চিহ্নগুলির মধ্যে সংযোগ ব্যবহার করতে হবে-একটি সংশ্লিষ্ট PDA-এর বর্ণমালার মাধ্যমে-এবং PDA দ্বারা পঠিত প্রতীকগুলি তৈরি করে এমন লেক্সিং এবং স্ক্যানিং ধাপগুলি।

আরও বিশেষভাবে, পার্সারগুলি লেক্সার এবং স্ক্যানারদের দ্বারা সমর্থিত হয় যা অক্ষর ইনপুটগুলির একটি ক্রম থেকে প্রতীকগুলি সনাক্ত করে, যেমনটি আমরা অনুচ্ছেদ 4 এ স্পষ্টভাবে চিত্রিত করেছি। প্রতীক এবং স্ট্যাক ট্রানজিশনের উপর ভিত্তি করে প্রতিটি পার্স/পিডিএ অবস্থার জন্য টার্মিনাল প্রতীকগুলির অর্ডারকৃত তালিকা তৈরি করা যেতে পারে। প্রতিটি রাজ্যে মানচিত্র δ দ্বারা। এর মানে হল যে আমরা প্রতিটি পার্স স্টেটের জন্য একটি FSM তৈরি করতে পারি যা প্রতিটি FSM-এর মিলন যা রাষ্ট্র দ্বারা পড়া একটি টার্মিনাল চিহ্নের সাথে সম্পর্কিত।

একটি স্ক্যানিং ধাপ তারপর পার্সিং প্রক্রিয়ায় শেষ সম্পূর্ণরূপে চিহ্নিত চিহ্নের পর থেকে পড়া অক্ষরের জন্য সম্ভাব্য টার্মিনাল চিহ্ন V ⊂ Σ এর একটি সেট সনাক্ত করবে। উদাহরণস্বরূপ, বিভাগ 4-এ পাইথন-লাইক CFG-এর জন্য PDA-এর প্রাথমিক অবস্থায় q0, স্ট্রিং "de" স্ক্যান করা এবং লেক্স করার ফলে V = {DEF, NAME}: অর্থাৎ স্ট্রিং "def" সম্পূর্ণ করা যেকোনো শব্দভাণ্ডার স্ট্রিংয়ের জন্য DEF হবে। -অনুসরণ করে একটি স্ট্রিং যা NAME FSM দ্বারাও পড়া হয় না (যেমন "def")– এবং NAME অন্য কোনো স্ট্রিং এর FSM দ্বারা পড়া হয় (যেমন "ডিফল্ট")। লক্ষ্য করুন যে স্ক্যানারের ধাপগুলি-এবং LLM-এর নমুনা ধাপগুলি- অবশেষে V সেট কমিয়ে দেবে যতক্ষণ না একটি একক টার্মিনাল প্রতীক v ∈ V নির্ধারণ করা হয়।

প্রতিটি পার্স স্টেটের জন্য সম্মিলিত FSM ব্যবহার করে V-এর প্রতিটি স্ট্রিং-এ অ্যালগরিদম 3 প্রয়োগ করে, আমরা PDA স্টেট, সংশ্লিষ্ট FSM স্টেট এবং সম্ভাব্য টার্মিনাল চিহ্ন নিয়ে গঠিত পার্সার কনফিগারেশন নির্ধারণ করতে পারি।

অ্যালগরিদম 3-এর ধাপগুলির সাথে সাদৃশ্য অনুসারে, আমরা PDA স্ট্যাকের মানগুলি নির্ধারণ করতে PDA-এর রূপান্তর মানচিত্রের প্রাক-ইমেজ ব্যবহার করতে পারি যা PDA স্টেট q ∈ Q এবং টার্মিনাল চিহ্ন একটি পার্সার কনফিগারেশনের V সেটগুলি পড়বে:

এই মানচিত্রের দ্বারা প্রদত্ত স্ট্যাকের মানগুলি পাথগুলি খুঁজে বের করার জন্য প্রয়োজন- যদি থাকে- PDA-এর মাধ্যমে যা তাদের সম্ভাব্য পার্সার কনফিগারেশন থেকে শুরু করে V-তে প্রতিটি স্ট্রিংয়ের সফল, সম্পূর্ণ পার্স করার অনুমতি দেয়। পার্সার স্টেট এবং টার্মিনাল কম্বিনেশনের জন্য যা একটি LALR(1) পার্সারের ক্রিয়াকলাপ কমানোর সাথে মিলে যায়, এই পার্সার কনফিগারেশনগুলি শুধুমাত্র Γ-এ টপ-অফ-স্ট্যাক মানগুলির চেয়ে বেশি ধারণ করবে; তারা একটি শব্দভাণ্ডার স্ট্রিং দ্বারা entailed কমানো ক্রিয়াকলাপগুলির জন্য সমস্ত বৈধ উপসর্গের সাথে সম্পর্কিত সাব-স্ট্যাকগুলি নিয়ে গঠিত। পরিশেষে, প্রতিটি পার্সার কনফিগারেশন যা একটি শব্দভাণ্ডার স্ট্রিংয়ের সম্পূর্ণ পার্স করার অনুমতি দেয় তা PDA-এর জন্য সূচকে একটি এন্ট্রি হিসাবে যোগ করা হয় এবং, এই ক্ষেত্রে, সূচকটিকে একটি ট্রাই ডেটা স্ট্রাকচার হতে হবে যাতে পার্সারের বিরুদ্ধে প্রশ্ন করার অনুমতি দেওয়া যায়। স্ট্যাক মান।