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

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

اولین کاربرد شناخته شده این اصطلاح توسط آر.جی. جی کاتل در پایان‌نامه دکترایشCattell, R. G. G. “Formalization and Automatic Derivation of Code Generators”. PhD thesis, 1978. Carnegie Mellon University, Pittsburgh, Pennsylvania, USA در مورد استخراج خودکار مولدهای کد برای کامپایلرها است.

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

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

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

مثال دیگر، در سی++، با استفاده از «پرانتز گوشه‌دار» کاراکترهای < و > در نحو برای الگو مشخص، اما دو بار پیاپی کاراکتر < به عنوان عملگر انتقال به راست << تفسیر می‌شود.Vandevoorde. قبل از 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]+ نتوانند با یک حرف حروف الفبا دنبال شوند، همان اثر بیشینه خردکردن را با آن عبارت منظم بدست می‌آورند.Van den Brand et al., 26. یک رویکرد دیگر این است که اصل بیشینه خردکردن را حفظ کنید اما آن را تابع برخی از اصول دیگر مانند زمینه (به عنوان مثال، توکن انتقال به راست در جاوا در زمینه یک عبارت ژنریک منطبق نمی‌شود، در صورتی که از نظر نحوی نامعتبر است).Van Wyk et al., 63.

 منابع 

 فهرست کتب 






رده:کامپایلرها