اصول طراحی کامپایلرها: تحلیلگر لغوی

یک رشته از یک زبان منظم را دریافت می کند و در صورتیکه رشته متعلق به زبان باشد آنرا تصدیق می کند و در غیر این صورت انرا رد می کند.

یک نوع ماشین خودکار متناهی که در هر حالت با خواندن یکی از الفبای زبان تنها یک گذر وجود دارد.

یک نوع ماشین خودکار متناهی که در هر حالت با خواندن یکی از الفبای زبان امکان چندین گذر وجود دارد.

مجموعه متناهی از حالات (q) که ماشین ممکن است در آن قرار داشته باشد.

مجموعه متناهی از نمادها که الفبای زبان است (∑)

یک تابع که تغییر حالت ماشین را بر اساس نماد ورودی مشخص می کند (δ)

حالت اولیه ماشین که ماشین از آن شروع به کار می کند (q0)

حالت یا حالت های نهایی که ماشین در آنها عملیات خود را با موفقیت به پایان می رساند (F)

یک الگوریتم برای رسم یک NFA برای یک عبارت باقاعده (منظم).

مجموعه حاالت از NFA که از حالت q با تبدیل λ قابل دسترس هستند.

مجموعه حاالت از NFA که از حاالت مجموعه T با تبدیل λ قابل دسترس هستند.

مجموعه حاالت از NFA که از حالت s در مجموعه T و با نماد ورودی a یک گذر به آنها انجام می شود.

یک الگوریتم که یک NFA را به یک DFA تبدیل می کند.

یک مجموعه شامل حداقل یکی از حالت های پایانی NFA که به عنوان حالت پایانی DFA مشخص می شود.

یک NFA را به یک DFA تبدیل می کند.

تعیین می کند که DFA با خواندن کدام نماد به کدام حالت می رود.

एक नियमित अभिव्यक्ति के लिए एक NFA का निर्माण करने की एक विधि।

नियमित अभिव्यक्ति लें और उसे सरल घटकों में विभाजित करें.

प्रत्येक उप-अभिव्यक्ति के लिए, संबंधित NFA बनाएँ।

अभिव्यक्तियों को संयोजित करके NFA बनाएँ।

एक NFA की अवस्था से उस NFA की अवस्थाओं का एक सेट है जिसे λ - संक्रमणों द्वारा पहुँचा जा सकता है।

एक NFA के राज्य के एक सेट से उस NFA के राज्य का एक सेट है जिसे λ - संक्रमणों द्वारा पहुँचा जा सकता है।

एक NFA के राज्य के एक सेट से उस NFA के राज्य का एक सेट है जो वर्तमान राज्य से इनपुट प्रतीक a पर एक संक्रमण द्वारा पहुँचा जा सकता है।

एक NFA को DFA में बदलने की एक विधि।

DFA में एक ही राज्य को कई NFA राज्य का समूह दर्शाता है।

DFA में प्रारंभिक राज्य के लिए प्रारंभिक NFA राज्य के λ-closure सेट का प्रयोग करके बनाया जाता है।

DFA के राज्य को इस प्रकार चिह्नित किया जाता है कि DFA के राज्य का संग्रह उस NFA राज्य को शामिल करता है जो एक अंतिम राज्य है।

DFA में राज्य संक्रमणों को निर्धारित करने में मदद करने के लिए उपयोग किया जाता है।