بیشینه خردکردن

از ویکی‌پدیا، دانشنامهٔ آزاد
(تغییرمسیر از حداكثر تطبيق)

در برنامه‌نویسی رایانه و علوم رایانه، «بیشینه خردکردن» یا «بلندترین تطبیق» (به انگلیسی: Maximal munch) اصلی است که هنگام ایجاد برخی از ساختارها، تا حد ممکن باید بیشتر از ورودی موجود مصرف شود.

اولین کاربرد شناخته شده این اصطلاح توسط آر.جی. جی کاتل در پایان‌نامه دکترایش[۱] در مورد استخراج خودکار مولدهای کد برای کامپایلرها است.

کاربرد[ویرایش]

برای مثال، نحو لُغوی بسیاری از زبان‌های برنامه‌نویسی ایجاب می‌کند که توکن‌ها از حداکثر تعداد ممکن کاراکترها از رشته ورودی، ساخته شوند. این کار برای حل مشکل ابهام ذاتی در عبارات منظم رایج استفاده می‌شود مانند [a-z]+ (یک یا چند حرف کوچک).[۲]

این اصطلاح همچنین در کامپایلرها در مرحله انتخاب دستورالعمل برای توصیف روشی از «کاشی کاری» به کار می‌رود - تعیین اینکه چگونه یک درخت ساختار یافته نشان می‌دهد یک برنامه به زبان میانی باید به کد ماشین خطی تبدیل شود. یک زیر درخت کامل ممکن است فقط به یک دستورالعمل ماشین تبدیل شود، و مسئله این است که چگونه درخت را به «کاشی‌های» غیر همپوشان تقسیم کنید، که هر کدام نشان دهنده یک دستورالعمل ماشین است. یک استراتژی مؤثر به سادگی ساخت یک کاشی از بزرگترین زیر درخت ممکن در هر نقطه داده شده‌است که «بیشینه خردکردن» نامیده می‌شود.[۳]

اشکالات[ویرایش]

در برخی شرایط، «بیشینه خردکردن» منجر به نتایج نامطلوب یا غیرشهودی می‌شود. برای مثال، در زبان برنامه‌نویسی سی، عبارت؛ x=y/*z (بدون هیچ گونه فضای خالی) احتمالاً به یک خطای نحوی منجر خواهد شد، از آنجایی‌که */ آغاز (ناخواسته) توضیح است که یا پایان نیافته یا پایان یافته با توکن پایانی /* در جلوتر، توضیح نامربوط واقعی (نظرات در C تو در تو نیست). آنچه در واقع در این عبارت مدنظر بود اختصاص دادن به متغیر x نتیجه تقسیم مقدار y بر مقدار بدست آمده از ارجاع مجدد اشاره گر z . این کد کاملاً معتبر است (البته نه چندان رایج). می‌توان با استفاده از فضای خالی، یا با استفاده از x=y/(*z); جایگذاری کرد.

مثال دیگر، در سی++، با استفاده از «پرانتز گوشه‌دار» کاراکترهای < و > در نحو برای الگو مشخص، اما دو بار پیاپی کاراکتر < به عنوان عملگر انتقال به راست << تفسیر می‌شود.[۴] قبل از C ++ 11، کد زیر خطای تجزیه ایجاد می‌کرد، توکن عملگر انتقال به راست در عوض با دو توکن پرانتز گوشه‌دار راست مواجه شده‌است:

    std::vector<std::vector<int>> my_mat_11; //Incorrect in C++03, correct in C++11.
    std::vector<std::vector<int> > my_mat_03; //Correct in either C++03 or C++11.

استاندارد سی++۱۱ که در اوت ۲۰۱۱ به تصویب رسید ، دستور زبان را اصلاح کرد تا توکن انتقال به راست به عنوان مترادف با یک جفت پرانتز گوشه‌دار راست پذیرفته شود (مانند جاوا)، که این گرامر را پیچیده می‌کند اما استفاده مستمر از اصل بیشینه خردکردن را امکان‌پذیر می‌کند.

جایگزین‌ها[ویرایش]

محققان زبان‌های برنامه‌نویسی همچنین با جایگزینی یا تکمیل اصل بیشینه خردکردن با سایر تاکتیک‌های ابهام زدایی لغوی پاسخ داده‌اند. یک رویکرد استفاده از «پیروی از محدودیت‌ها» است، که به جای اینکه مستقیماً بلندترین تطبیق را در نظر بگیرید، محدودیت‌هایی را برای کاراکترهایی که می‌توانند یک تطبیق معتبر را دنبال کنند، ایجاد می کند. برای مثال، شرط اینکه رشته‌های منطبق بر [a-z]+ نتوانند با یک حرف حروف الفبا دنبال شوند، همان اثر بیشینه خردکردن را با آن عبارت منظم بدست می‌آورند.[۵] یک رویکرد دیگر این است که اصل بیشینه خردکردن را حفظ کنید اما آن را تابع برخی از اصول دیگر مانند زمینه (به عنوان مثال، توکن انتقال به راست در جاوا در زمینه یک عبارت ژنریک منطبق نمی‌شود، در صورتی که از نظر نحوی نامعتبر است).[۶]

منابع[ویرایش]

  1. ↑ Cattell, R. G. G. “Formalization and Automatic Derivation of Code Generators”. PhD thesis, 1978. Carnegie Mellon University, Pittsburgh, Pennsylvania, USA
  2. ↑ Aho et al., 168.
  3. ↑ Page, 470.
  4. ↑ Vandevoorde.
  5. ↑ Van den Brand et al., 26.
  6. ↑ Van Wyk et al., 63.

فهرست کتب[ویرایش]

    • Aho, Alfred V.; Lam, Monica S.; Sethi, Ravi; Ullman, Jeffrey D. (2007). Compilers: Principles, Techniques & Tools (2nd ed.). Boston: Addison-Wesley. ISBN 978-0-321-48681-3.
    • Page, Daniel (2009). "Compilers". Practical Introduction to Computer Architecture. Texts in Computer Science. London: Springer. pp. 451–493. doi:10.1007/978-1-84882-256-6_11. ISBN 978-1-84882-255-9.
    • Van den Brand, Mark G.J.; Scheerder, Jeroen; Vinju, Jurgen J.; Visser, Eelco (2002). Disambiguation Filters for Scannerless Generalized LR Parsers. Lecture Notes in Computer Science. Vol. 2304/2002. Berlin/Heidelberg: Springer. pp. 21–44. doi:10.1007/3-540-45937-5_12. ISBN 978-3-540-43369-9. ISSN 0302-9743.
    • Vandevoorde, Daveed (14 January 2005). "Right Angle Brackets". Retrieved 31 March 2010.
برگرفته از «https://fa.wikipedia.org/w/index.php?title=بیشینه_خردکردن&oldid=35904773»