طراحی کامپایلر - تجزیه و تحلیل واژگانی

تجزیه و تحلیل واژگانی اولین مرحله از کامپایلر است. این کد منبع اصلاح شده را از پیش پردازنده های زبان که به صورت جملات نوشته شده است ، می گیرد. آنالایزر واژگانی با از بین بردن هرگونه فضای سفید یا اظهار نظر در کد منبع ، این نحو ها را به یک سری از نشانه ها می شکند.

اگر آنالایزر واژگانی یک نشانه نامعتبر پیدا کند ، خطایی ایجاد می کند. آنالایزر واژگانی از نزدیک با آنالایزر نحو کار می کند. این جریان شخصیت ها را از کد منبع می خواند ، نشانه های قانونی را بررسی می کند و داده ها را در صورت نیاز به آنالایزر نحوی منتقل می کند.

توکن

گفته می شود که لکسم ها دنباله ای از شخصیت ها (الفبایی) در یک نشانه هستند. برخی از قوانین از پیش تعریف شده وجود دارد که هر یک از آنها به عنوان یک نشانه معتبر شناخته می شوند. این قوانین توسط قوانین گرامر ، با استفاده از یک الگوی تعریف می شوند. یک الگوی توضیح می دهد که چه چیزی می تواند یک نشانه باشد و این الگوهای با استفاده از عبارات منظم تعریف می شوند.

در زبان برنامه نویسی ، کلمات کلیدی ، ثابت ها ، شناسه ها ، رشته ها ، شماره ها ، اپراتورها و نمادهای سوراخ شده را می توان به عنوان نشانه ها در نظر گرفت.

به عنوان مثال ، در زبان C ، خط اعلامیه متغیر

مقدار int = 100 ؛

شامل نشانه ها:

int (کلمه کلیدی) ، مقدار (شناسه) ، = (اپراتور) ، 100 (ثابت) و ؛(سمبل).

مشخصات نشانه ها

بگذارید درک کنیم که چگونه تئوری زبان اصطلاحات زیر را انجام می دهد:

حروف الفبا

هر مجموعه محدود از نمادها مجموعه ای از الفبای باینری است ، مجموعه ای از الفبای شش ضلعی است ، مجموعه ای از الفبای زبان انگلیسی است.

رشته های

هر توالی محدود از الفبای (کاراکترها) یک رشته نامیده می شود. طول رشته تعداد کل وقایع الفبای است ، به عنوان مثال ، طول آموزش رشته رشته 14 است و توسط | TutorialSpoint |= 14. رشته ای که دارای الفبای نیست ، یعنی یک رشته با طول صفر به عنوان یک رشته خالی شناخته می شود و توسط ε (اپسیلون) مشخص می شود.

نمادهای خاص

یک زبان سطح بالا معمولی شامل نمادهای زیر است:-

شناسه = (نامه) (نامه | رقم)*

تنها مشکلی که در مورد آنالایزر واژگانی باقی مانده است ، چگونگی تأیید صحت یک عبارت منظم مورد استفاده در مشخص کردن الگوهای کلمات کلیدی یک زبان است. یک راه حل خوب پذیرفته شده استفاده از اتومات های محدود برای تأیید است.

اتومات های محدود

Automata محدود یک دستگاه دولتی است که به عنوان ورودی رشته ای از نمادها را می گیرد و بر این اساس وضعیت خود را تغییر می دهد. Automata محدود یک تشخیص دهنده برای عبارات منظم است. هنگامی که یک رشته بیان منظم در اتومات های محدود تغذیه می شود ، وضعیت خود را برای هر لفظی تغییر می دهد. اگر رشته ورودی با موفقیت پردازش شود و اتومات به حالت نهایی خود برسد ، پذیرفته می شود ، یعنی گفته می شود که رشته ای که فقط تغذیه شده است ، یک نشانه معتبر از زبان در دست است.

مدل ریاضی اتومات های محدود شامل:

• مجموعه محدود ایالات (Q)
• مجموعه محدود از نمادهای ورودی (σ)
• حالت شروع (Q0)
• مجموعه حالتهای نهایی (QF)
• تابع انتقال (δ)

عملکرد انتقال (δ) مجموعه محدود حالت (q) را به مجموعه محدودی از نمادهای ورودی (σ) ، q × σ ➔ q نقشه می کند

ساخت اتومات های محدود

بگذارید L (r) یک زبان معمولی باشد که توسط برخی از اتومات های محدود (FA) شناخته شده است.

• ایالات: ایالات FA توسط محافل نشان داده می شود. نام دولت از ایالت است که در داخل دایره نوشته شده است.
• حالت شروع: وضعیتی که از آنجا شروع می شود ، به عنوان Start State شناخته می شود. حالت شروع یک فلش به سمت آن اشاره دارد.
• حالتهای واسطه: تمام کشورهای واسطه حداقل دو فلش دارند. یکی اشاره به و دیگری که از آنها اشاره می کند.
• حالت نهایی: اگر رشته ورودی با موفقیت تجزیه شود ، انتظار می رود اتومات در این حالت قرار بگیرد. حالت نهایی توسط محافل دوتایی نشان داده شده است. این ممکن است تعداد فلش های عجیب و غریب به آن نشان دهد و حتی تعداد فلش هایی که از آن اشاره می کنند. تعداد فلش های عجیب و غریب یکی بیشتر از یکنواخت است ، یعنی عجیب = حتی+1.
• انتقال: انتقال از یک حالت به حالت دیگر هنگامی اتفاق می افتد که یک نماد مورد نظر در ورودی پیدا شود. پس از انتقال ، اتوماتیک می تواند به حالت بعدی منتقل شود یا در همان حالت بماند. حرکت از یک ایالت به حالت دیگر به عنوان یک فلش کارگردانی نشان داده شده است ، جایی که فلش به حالت مقصد اشاره می کند. اگر Automata در همان حالت بماند ، یک فلش که از یک حالت به خود نشان می دهد ، کشیده می شود.

مثال: ما فرض می کنیم FA هر مقدار باینری سه رقمی را که به رقم پایان می یابد قبول می کند. FA =0, q_f) ، σ (0،1) ، q₀, q_f, δ>

طولانی ترین قانون مسابقه

هنگامی که آنالایزر واژگانی کد منبع را خواند ، نامه کد را با نامه اسکن می کند. و هنگامی که یک فضای سفید ، نماد اپراتور یا نمادهای خاص رخ می دهد ، تصمیم می گیرد که یک کلمه تکمیل شود.

مثلا:

int intvalue ؛

در حالی که اسکن هر دو lexemes تا "int" ، آنالایزر واژگانی نمی تواند تعیین کند که آیا این یک کلمه کلیدی int است یا مقدمات ارزش int شناسه.

طولانی ترین قانون مسابقه بیان می کند که Lexeme اسکن شده باید بر اساس طولانی ترین مسابقه در بین تمام نشانه های موجود تعیین شود.

آنالایزر واژگانی همچنین از اولویت قانون پیروی می کند که در آن یک کلمه رزرو شده ، به عنوان مثال ، یک کلمه کلیدی ، از یک زبان در اولویت ورودی کاربر قرار می گیرد. یعنی اگر آنالایزر واژگانی یک لکسمی پیدا کند که با هر کلمه رزرو شده موجود مطابقت داشته باشد ، باید خطایی ایجاد کند.