آنالیز تخصیص قطعی
آنالیز تخصیص قطعی در علوم کامپیوتر، آنالیز جریان داده‌ای است که توسط کامپایلرها استفاده می‌شود تا به‌طور محافظه کارانه مطمئن شویم که یک متغیر یا آدرس، همیشه قبل از استفاده، تخصیص داده شده باشد.
در برنامه‌های C و C ++، یکی از منشاهای خطاهایی که تشخیص آن‌ها بسیار دشوار است، رفتار غیرقطعی‌ حاصل خواندن متغیرهای تعریف نشده است. این رفتار می‌تواند بین سیستم عامل‌ها، ساخت‌ها و حتی بین اجراهای مختلف متفاوت باشد. دو راه متداول برای حل این مشکل وجود دارد. یکی این است که اطمینان حاصل شود که همه‌ی مکان‌ها قبل از خواندن، نوشته شده‌اند. ثابت می‌کند که این مشکل به طور کلی برای همه‌ی برنامه‌ها قابل حل نیست. با این حال، می‌توان یک تحلیل محافظه کارانه (غیر دقیق) به وجود آورد که فقط برنامه‌هایی را بپذیرد که این محدودیت را برآورده کنند، در حالی که برخی از برنامه‌های صحیح را رد کرد، و تحلیل تخصیص قطعی چنین تحلیلی است. مشخصات زبان برنامه نویسی جاوا و سی شارپ مستلزم آن است که کامپایلر یک خطای زمان کامپایل را در صورت شکست آنالیز، گزارش کند. هر دو زبان به شکل خاصی از تحلیل نیاز دارند که با جزئیات دقیق بیان شده باشد. در جاوا، این تجزیه و تحلیل توسط استارک و همکارانش رسمیت یافت و برخی از برنامه‌های صحیح رد می‌شوند و باید برای معرفی تخصیص غیر ضروری و مشخص تغییر داده شوند. در سی شارپ، این تجزیه و تحلیل توسط Fruja رسمیت یافت، و دقیق و درست است، به این معنا که همه متغیرهای تخصیص داده شده در طول تمام مسیرهای جریان کنترل، به طور قطعی، اختصاص داده شده در نظر گرفته می شوند. زبان نیز به برنامه‌ها نیاز دارد که تجزیه و تحلیل تخصیص مشخصی را انجام دهند، اما فقط روی متغیرهایی با انواع پوینتر، تا انتقال برنامه‌های سی آسان شود.
راه دوم برای حل این مشکل این است که همه‌ی مکان‌ها را به یک مقدار ثابت و قابل پیش بینی در نقطه‌ای که در آن تعریف شده اند به طور خودکار مقداردهی کنیم ، اما این وظایف جدیدی را معرفی می کند که ممکن است عملکرد را مختل کند. در این حالت ، تجزیه و تحلیل تکلیف قطعی ، بهینه سازی کامپایلر را امکان پذیر می کند که در آن تکالیف اضافی — تکالیفی که پس از آن تکالیف دیگر دنبال می شوند و هیچ خوانشی احتمالی در آن‌ها وجود ندارد — قابل حذف است. در این مورد ، هیچ برنامه ای رد نمی شود ، اما برنامه‌هایی که تجزیه و تحلیل آن‌ها در تعیین تکلیف مشخص نمی تواند شامل مقداردهی اولیه اضافی باشد. زیرساخت زبان مشترک متکی بر این رویکرد است.
می‌توان گفت که یک متغیر یا آدرس، در طول برنامه، در یکی از سه حالت زیر قرار دارد:موارد زیر بر اساس رسمی‌سازی Fruja در تجزیه و تحلیل تخصیص قطعی درون رویه‌ای (تک روشی) سی شارپ است، که مسئول اطمینان از تخصیص همه متغیرهای محلی قبل از استفاده از آن‌ها است. آن را به طور همزمان تجزیه و تحلیل تخصیص مشخص و انتشار ثابت مقادیر بولین انجام می‌دهد. ما پنج تابع استاتیک را تعریف می کنیم:
ما معادلات جریان داده را ارائه می کنیم که مقادیر این توابع را در عبارات مختلف بر حسب مقادیر توابع در زیرعبارات نحوی آن‌ها تعریف می‌کند. فرض کنید که هیچ دستوری برای رسیدگی به دستورات "goto، break، continue، return" یا کنترل استثنا وجود ندارد. چند نمونه از این معادلات به صورت زیر است:
در ابتدای روش، هیچ متغیر محلی به طور قطعی تخصیص داده نمی‌شود. تأیید کننده به طور مکرر روی درخت نحو انتزاعی مرور می‌کند و از معادلات جریان داده برای انتقال اطلاعات بین مجموعه‌ها استفاده می‌کند تا به یک نقطه ثابت برسد. سپس، تأییدکننده مجموعه‌ی «قبل»، از هر عبارتی که از متغیر محلی استفاده می‌کند، بررسی می‌کند تا مطمئن شود که حاوی آن متغیر است.
این الگوریتم با معرفی پرش‌های کنترل جریان مانند "goto، break، continue، return و کنترل خطا،" پیچیده می شود. هر عبارتی که می‌تواند هدف یکی از این پرش‌ها باشد، باید مجموعه‌ی «قبل» خود را با مجموعه متغیرهای قطعی اختصاص داده شده در منبع پرش، تقاطع بدهد. هنگامی که این‌ها معرفی می شوند، جریان داده‌ی حاصل ممکن است چندین نقطه ثابت داشته باشد، مانند این مثال: از آنجایی که می‌توان به برچسب L دو مکان دسترسی یافت، معادله کنترل جریان برای "goto" حکم می کند که "before"(2) = "after"(1) با "before"(3) تقاطع دارد. اما "before"(3) = "before"(2)، پس "before"(2) = "after"(1) با "before"(2) تقاطع دارد. این دارای دو نقطه ثابت برای "before"(2), {i} و مجموعه‌ی تهی است. با این حال، می‌توان نشان داد که به دلیل شکل یکنواخت معادلات جریان داده، یک نقطه ثابت ماکسیمال منحصر به فرد (نقطه ثابت با بزرگترین اندازه) وجود دارد که بیشترین اطلاعات ممکن را در مورد متغیرهای قطعی اختصاص داده شده ارائه می‌دهد. چنین ماکسیمال (یا ماکسیمم) نقطه ثابت ممکن است با تکنیک‌های استاندارد محاسبه شود. به تحلیل جریان داده رجوع کنید.
یک مسئله دیگر این است که یک پرش جریان کنترلی ممکن است برخی جریان‌های کنترلی را غیرممکن کند. به عنوان مثال، در این قطعه کد، متغیر "i" قطعا قبل از استفاده، اختصاص داده شده است: معادله جریان داده برای "if" می گوید که "after(2) = after(return)" پس از "(i = j)" متقاطع می‌شوند. برای اینکه این کار به درستی انجام شود، تعریف می‌کنیم after(e) = vars(e) برای همه‌ی پرش‌های کنترل جریان. این به همان دلیل تایید شده است که معادله "false(true) = vars(e)" است؛ زیرا امکان ندارد کنترل بلافاصله پس از پرش جریان کنترل، به نقطه‌ای برسد.