آموزش جامع و کاربردی طراحی کامپایلر

دیاگرام غیرقطعی :
دیاگرامی غیرقطعی است که در یک وضعیت برای خواندن یک کاراکتر حالت قطعی وجود نداشته باشد و روی یالهای دیاگرام λ وجود داشته باشد.

می توان دیاگرام های غیر قطعی را با استفاده از الگوریتم به دیاگرام های قطعی تبدیل کرد.

*برای پیاده کردن یک اسکنر ابتدا دیاگرام های انتقال معرف الگوهای یک Tokenرا رسم می کنیم ;از این دیاگرام ها برای بدست اوردن اطلاعات در مورد کاراکترهایی که توسط نشانه روی forwardباید در ورودی دیده شود ،استفاده می کنیم.به این ترتیب همان طور که کاراکترهای ورودی خوانده می شود از یک وضعیت در دیاگرام به وضعیت دیگر حرکت می کنیم تا اینکه به وضعیت نهایی برسیم.

نکته (1): برای تشخیص هر کلمه کلیدی دو راه حل وجود دارد:

1. برای هر کدام از کلمات کلیدی یک stateدیاگرام داشته باشیم در این حالت (state diagram) تعداد state ها و شرط ها زیاد خواهد شد .
2. با کلمات کلیدی همانند یک شناسه برخورد می شود در این صورت کلمات کلیدی را داخل یک ارایهیا جدول قرار می دهیم یعنی در ابتدای جدول علائم کلمات کلیدی را وارد می کنیم،وقتی که یک شناسه شخیص داده شد اسکنر لیست را می گردد تا پی ببرد به اینکه ایا این شناسه کلمه کلیدی می باشد یا نه!در صورتی که ان شناسه در جدول پیدا شد ،خود ان کلمه را به عنوان Token انتقال پیدا کرده و attributeان صفر می شود در غیر این صورت در جدول علائم جستجو می کند تا ببیند که ان شناسه جود دارد یا خیر !اگر وجود داشت انرا وارد جدول نمی کند بلکه ادرس ان را انتقال می دهد.در غیر این صورت متغیر را وارد جدول کرده و ادرس جدول علائم را به عنوان attribute به پارسل انتقال می دهد.

*ترتیب را چگونه مشخص کنیم:

دیاگرام ها باید طوری قرار گیرد که ابتدا طولانی ترین دیاگرام قرار گیرد مثلا دیاگرامی که تشخیس اعداد اعشاری را می دهد باید قبل از دیاگرام تشخیص اعداد صحیح باشد.
دیاگرام تشخیص Tokenهایی که مورد استفاده بیشتری دارند مثل space,tab: باید قبل از دیاگرام های کم یاب قرار گیرند تا در نهایت تست کمتری در تشخیص Token انجام گیرد پس از اینکه دیاگرام تشخیص Tokenها شد به راحتی می توان ان را با دستور case پیاده سازی کرد.

*پذیرنده زبانها (ماشین پذیرنده زبان )AUTAMATA
معماری پذیرنده زبان نوع سوم:همیشه ورودی پذیرنده یک رشته می باشد ،ماشین نوع سوم یک نوار نیمه متناهی دارد و یک کنترل متناهی و یک هد فقط خواندنی داریم
کنترل متناهی در هر حالت وضعیت ماشین را به ما نشان می دهد.

http://pnu-club.com/imported/mising.jpg

چگونه با ماشین برخورد می کنیم:

1)رشته را روی نوار قرار می دهیم.

2)ماشین را در وضعیت اولیه می گذاریم تا ماشین شروع به پردازش نماید.

3)پس از اینکه ماشین شروع به کار کرد در انتهای رشته وضعیت ماشین بررسی می شود که ایا در وضعیت

نهایی قرار دارد یا نه؟!

*پذیرش:زمانی اتفاق میافتد که در انتهای رشته ماشین در یکی از حالات نهایی خود باشد. Accep

*عدم پذیرش:زمانی اتفاق می افتد که در انتهای رشته ماشین در یکی از حالات غیر نهایی خود باشد و یا اینکه ماشین به دلایلی نامعلوم متوقف شود Regict

آیتم های ماشین نوع سوم:
M:(مجموعه حالات , Qالفبای زبان ,∑تابع انتقال , δ حالت اولیه , qمجموعه حالات نهاییf )

{همیشه یک نقطه شروع داریم ولی می توانیم چندین نقطه پایان داشته باشیم}
*تعریف تابع انتقال :
Q×∑→Q : δ

Q =(Q,∑)δ
http://pnu-club.com/imported/mising.jpg
طریقه خواندن بر حسب نوار است:

b a b b a
q0→q0→q1→q1→q0→q1

*رشته ی abbab توسط ماشین فوق پذیرفته شد (accept)

*مثالی دیگر
:http://pnu-club.com/imported/mising.jpg

a b b a
0→q0→q1→q1→q0 q

چون به حالت نهایی نرسیده است می شود reject))

*تابع انتقال دو حالت دارد:1)گراف انتقال 2)جدول انتقال