جلسه ۰۶ : اتوماتای متناهی (Finite Automata) – طراحی کامپایلر

• جزئیات
• نوع محتواآموزشی

سلام و وقت بخیر خدمت همراهان وب سایت آموزشی پی وی لرن. با دوره کامل آموزش طراحی کامپایلر در خدمت شما عزیزان خواهیم بود. در این بخش به بررسی اتوماتای متناهی (Finite Automata) می پردازیم.

بررسی اتوماتای متناهی (Finite Automata)

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

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

• (Q) مجموعه ای متناهی از وضعیت ها
• (Σ) مجموعه متناهی از نمادهای ورودی
• (q0) یک وضعیت آغازین
• (qf)مجموعه وضعیت های نهایی
• (δ)تابع انتقال

تابع انتقال (δ) مجموعه متناهی از حالت ها (Q) را به یک مجموعه متناهی از نمادهای ورودی (Σ) نگاشت می کند. Q × Σ ➔ Q

ساختار اتوماتای متناهی (Finite Automata)

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

وضعیت ها (State) : حالت های FA توسط دایره نمایش داده می شوند. نام وضعیت ها در داخل دایره ها نوشته شده است.

وضعیت آغازین (Start state): وضعیتی که از آن جا اتوماتا شروع می شود ، به عنوان حالت اولیه نیز شناخته می شود. وضعیت اولیه با یک پیکانی که به سمت داخل آن اشاره می کند مشخص شده است.

وضعیت میانی (Intermediate states) : تمام حالت های میانی حداقل دو فلش دارند. یکی به داخل آن ها اشاره می کند و دیگری به بیرون از آن ها اشاره می کند.

وضعیت نهایی (Final state): اگر رشته ورودی با موفقیت تجزیه شد ، انتظار می رود که اتوماتا در این وضعیت باشد. وضعیت نهایی دو دایره نمایش داده می شود. ممکن است تعداد فردی از فلش ها به سمت داخل این حالت اشاره کند و تعداد زوجی از فلش ها به بیرون از آن اشاره کند. تعداد فلش های فرد یکی بیشتر از فلش های زوج است ، یعنی فلش های فرد = فلش های زوج + ۱٫

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

مثال: فرض می کنیم FA هر مقدار دودویی سه رقمی را که به رقم ۱ منتهی می شود را قبول کند. {FA = {Q(q0, qf), Σ(۰,۱), q0, qf, δ

بررسی اتوماتای متناهی (Finite Automata)

کلام پایانی

با مبحث بررسی Finite Automata در این بخش از آموزش طراحی کامپایلر همراه بودیم. در بخش بعد به بررسی تحلیل گر نحوی (Syntax analyser) خواهیم پرداخت.