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

[Y@SiN]

تعریف کامپایلر:برنامه ای است که متن یک برنامه به زبان برنامه نویسی A را دریافت نموده وپس از اعمال تغییرات خاصی به طوری که معنا و مفهوم آن عوض نشود به زبان برنامه نویسی B تبدیل میکند.

کامپایلر زبان سطح(high level) بالا را به زبان سطح پائین (low level)تبدیل میکند.
اگرتمام داده های ورودی مورد نیاز کامپایلرفراهم باشدکامپایلرمیتواندعمل مشخص شده توسط معنای برنامه را بدون تبدیل به شکل دیگر اجرا نماید.

[Y@SiN]

ساختار مفهومی یک کامپایلر:

کد اجرایی
پردازشگر نهایی
(تحلیل وترکیب)
نمایش معنایی برنامه
(کنترل ترتیب ساختار)
پردازش اولیه
(تجزیه)
متن برنامه


کار داخل کامپایلر بر عهده (پردازش اولیه.نمایش معنایی.پردازشگر نهایی)میباشد.
تعریف مفسر:برنامه ای است که یک برنامه ورودی با زبان منبع را گرفته وآن را اجرا میکند.

[Y@SiN]

تفاوت های بین تفسیر و ترجمه:

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

[Y@SiN]

مراحل کامپایل:

lexical analayzer (تحلیل گر لغوی)
syntax analayzer (تحلیل گر نحوی)
semantic analayzer (تحلیل گر معنایی)
inter mediate code generator (تولید کننده کد میانی)
code oplimization (بهینه ساز کد میانی)
code generation ()
synbol table (جدول سمبلها)
error handling ()

[Y@SiN]

مرحله تحلیل گر لغوی : در این مرحله کامپایل متن برنامه ورودی حرف به حرف خوانده میشود وبه دنبالهای از نشانه ها یا tokenها عبارتند از:کلمات کلید,عملگرها,جداکننده ها,ثابت ها,شناسه ها,... در این مرحله در جدول سمبلها با فرمت خاصی ذخیره می شوند.

[Y@SiN]

وظایف تحلیل گر لغوی :

تولید tokenها
تشخیص خطاهای لغوی
نادیده گرفتن و حذف توضیحات
بعد از تشخیص tokenها،tokenها را وارد جدول نشانه ها می کنیم .

[Y@SiN]

تحلیل گر نحوی :در این مرحله خروجی تحلیل گر لغوی از نظر خطاهای نحوی مورد بررسی قرار میگیرد و با استفاده از نشانه های تولید شده درخت نحوی ان ساخته می شود.

[Y@SiN]

تحلیل گر معنایی :با استفاده از درخت نحوی ساخته شده در مرحله قبل برنامه ورودی از نظر خطاهای مفهومی احتمالی مورد بررسی قرار می گیرد.

[Y@SiN]

تولید کننده کد میانی :برنامه ورودی در این برنامه تبدیل به یک برنامه به زبان میانی می شود.

[Y@SiN]

بهینه ساز کد میانی :در این مرحله کد میانی تولید شده در مرحله قبل در صورت امکان بهینه می شود.

[Y@SiN]

تولید کننده کد نهایی:کد میانی بهینه شده در مرحله قبل تبدیل به کدی به نام کد زبان ماشین می شود.

[Y@SiN]

Scanner(پویشگر) :به واحدی از کامپایلر گفته می شود که کار تحلیل واژه را انجام می دهد.

[Y@SiN]

Parser:به واحدی از کامپایلر گفته می شود که تحلیل نحوی را انجام می دهد.(تحلیل نحوی یعنی ترتیب را گارانتر می کند یعنی اول فاعل بیاید بعد مفعول بعد فعل...طبق گرامر عمل میکند).

[Y@SiN]

کار تحلیل گر مفهومی :تعیین صحت مفهوم جملات میباشد؛ممکن است یک جمله از لحاظ نحوی صحیح باشد ولی از بابت مفهومی دارای خطا باشد مثل«علی اتش را خورد».تحلیل گر مفهومی وابسته به نوع اسمی و متغییرها که در جدول نمادها است، می باشد.

[Y@SiN]

مولد کد میانی :بخشی از کامپایلر است که در ورودی خود جملات تشخیص داده شده توسط تحلیل گر مفهومی را پذیرفته و در خروجی کد وابسته یا میانی تولید می کند ،کد میانی به سادگی قابل تبدیل است و به زبان ماشین نزدیک تر می باشد اما مستقل از ساختار و جزیيات هر گونه ماشین می باشد.

[Y@SiN]

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

[Y@SiN]

خطا پرداز یا error handling : هر بار خطایی در یکی از مراحل پیش آید ،رویدادی به نام خطاپرداز فراخوانی می شود،این بخش سعی می کند خطا را به نحوی برطرف کند تا در نتیجه کامپایلر بتواند علاوه بر اینکه تعداد خطاهای بیشتری را تشخیص می دهد با تشخیص اولین خطا متوقف نشود ،وظیفه اصلی این بخش راهنمایی واضح و شفاف برنامه نویس برای رفع خطای برنامه نوشته شده می باشد.معمولا بیشترین خطای تشخیص داده شده در یک کامپایلر در قسمت (scanner,parsser) اتفاق می افتد.

[Y@SiN]

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

[Y@SiN]

Front_end ـ 5 فاز اول ابتدای کامپایلر که وابسته به زبان منبع است و مستقل از زبان ماشین می باشد و شامل مراحل زیر است:

متن برنامه مورد کامپایل
تحلیل گر لغوی
تحلیل گرنحوی
تحلیل گر مفهومی
مولد کد میانی

[Y@SiN]

Back_End به 3 فاز اخر کامپایلر که وابسته به زبان ماشین است و شامل مراحل زیر است :

بهینه سازی
مولد کد
بهینه ساز کد میانی
یادآوری :

به سه نحو می توانیم یک درخت را پیمایش کنیم:

PREORDER (چپ-ریشه-راست)
POSTORDER (چپ-راست-ریشه)
INORDER (ریشه-چپ-راست)

نکته : مولد کد نهایی یک ماژول است و بستگی به سخت افزار ماشین زبان مقصد دارد.

[Y@SiN]

A تحلیل گر نحوی(گرامر یک زبان)

اصطلاحات:


الفبا:یک مجموعه محدود از علامتها

مجموعه(تمامی قوانین مجموعه ها مثل عضویت زیر مجموعه،مجموعه جهانی و...صدق می کند.)

رشته:دنباله ای از علامت ها مانند : abba

طول رشته:طول علامت ها می باشد به عنوان مثال ۳ = |aba|

رشته تهی:رشته ای با طول صفر که با لاندا نمایش داده می شود.

[Y@SiN]

عملگرها روی یک رشته :


عملگر اتصال یا concat : برای اتصال دو رشته به همدیگر استفاده میشود.

عملگر معکوس : جهت معکوس کردن یک رشته استفاده میشود.


زبان: زبان عبارت است از مجموعه ای محدود یا نامحدود از رشته ها






L1={aa,abb,bab} L2={a,b,bb,aa} L3={a,aa,aaa,...et}

[Y@SiN]

عملگر روی زبان ها :


اجتماع

اشتراک

اتصال

*بستار ستاره یا star closure: مجموعه ای است متشکل از الفبای ان زبان با هر طول.
گرامر:تعریف یک زبان را گرامر گویند.یعنی بایدها و نبایدها -روش ها وقاعده ها
( G=(N,T,P,S
N:non-Terminal=variable (غیر پایانی ها که قابل بسط دادن می باشند).
T:Terminal(پایانی ها که قابل بسط دادن نمی باشند).
P:production Rules(قواعد تولید)
S:start symbol(سمبل استارت)

کار کامپایلر تبدیل اسامی عام به اسامی خاص می باشد.

[Y@SiN]

زبان ها و گرامرها
به ازای هر گرامر یک زبان و به ازای هر زبان یک پذیرنده داریم:

انواع گرامرها:

گرامر منظم یا با قاعده یا نوع سوم
گرامر مستقل از متن یا نوع دوم
گرامر حساس به متن یا نوع اول
گرامر بی قاعده یا نوع صفر
نکته:زبان از نوع سوم تا نوع صفرم بی قاعده ترونامحدود تر می شود.

[Y@SiN]

انواع زبان:


زبان های منظم یا با قاعده
زبان های مستقل از متن
زبان های حساس به متن
زبان های بی قاعده

[Y@SiN]

انواع پذیرنده ها:


پذیرنده زبان های نوع سوم یا پذیرنده متناهی: F.A (finite automata)
پذیرنده زبان های مستقل از متن : P.D.A (push down automata)
پذیرنده زبان های حساس به متن: L.B.A (linear bounded automata)
پذیرنده زبان های بی قاعده: T.M (turing machine)


یک پذیرنده آتاماتا ماشینی است که یک رشته ای از زبان را می گیرد و می گوید این رشته متعلق به آن زبان است یا نه!
پذیرنده زبان های بی قاعده زبان تورینگ است.

[Y@SiN]

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

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

[Y@SiN]

جمله: به آخرین فرم جمله ای که در آن هیچ غیر پایانی وجود ندارد جمله گفته می شود.

[Y@SiN]

بسط یا اشتقاق : به صورت رسمی یا قانون مند به دو صورت است:

L.M.D اگر هر بار در عمل اشتقاق سمت چپ ترین غیر پایانی انتخاب شود بسط چپ است.
R.M.D اگر هر بار در عمل اشتقاق سمت راست ترین غیر پایانی انتخاب شود بسط راست است.
مثال:نمونه روبرو را به دو روش نام برده اشتقاق می دهیم:




S→ABC

A →aA|λ
B→bB|bb
C→ccC|λ


روش اول:




S→ABC
→aABC
→aBC
→abbc
→abb



روش دوم:



S→ABC
→AB
→Abb
→aAbb
→abb



تقدم وتاخردر روشهای نام برده متفاوت است ولی در نهایت به جمله پایانی یکسانی منتهی می شود.

[Y@SiN]

*برای تشخیص دادن اینکه یک جمله متعلق به یک زبان است یا نه دو راه وجود دارد :

1)استفاده از درخت نحو یا pars tree

2)بسط جمله Derivation

مثال:با فرض گرامر S→AB آیا رشته aabbb متعلق به گرامر فوق می باشد یا نه ؟ بله



A →aA|a
B→bB|b
T={a,b}
V={S,A,B}



Derivation:


S→AB
aAB →
aaB →
aabB →
aabbB →
aabbb →


*پیمایش یک درخت پارس در برگ های آن انجام می شود.

pars tree:



S
B A / \
/ \ / \
B b A a
\ / /
B b a
/
b

[Y@SiN]

*روشهای طراحی کامپایلر:

1) Top-Down (از بالا به پایین): از علامت شروع گرامر استفاده می کنیم بسط های مربوطه را می دهیم

تا به یک فرم جمله ای برسیم.

2)Bottom-up (از پایین به بالا): یک عبارت را می دهیم و از کامپایلر می خواهیم که از این عبارت به

سمبل استارت برسد در صورت رسیدن مشخص می شود که این عبارت قواعد گرامر مورد نظر را رعایت

کرده است.

*تعریف گرامر مبهم(گنگ) :

گرامری را گنگ می گوییم؛اگر برای یک جمله از زبانی که گرامر تعریف می کند بتوان دو بسط از سمت

راست ویا دو بسط از سمت چپ به صورت متفاوت ایجاد کرد.

مثال:آیا گرامر فوق مبهم است یا نه ؟

گرامر:

E→E+E
E→E*E
E→(E)
E→id
T={id,+,*,(,)}
N={E}



عبارت: id+id*id

راه حل:L.M.D(1)


E
E→E+E \ | /
E→id+E ابتدا عمل جمع سپس ضرب E + E
E→id+E *E \ | / /
E→id+id *E E * E id
E→id+id *id \ /
id id
L.M.D(2)


E→E*E E
E→E+E*E ابتدا عمل ضرب سپس جمع \ | /
Id+E*E E→ E * E
Id+id*E E→ \ \ | /
Id+id*id E→ id E + E
\ /
Id id





*روش رفع ابهام قرار داد می کنیم ضرب به جمع اولویت داشته باشد.

[Y@SiN]

Pattern(الگو):به شکلهای مختلف از یک Token که می تواند به خود بگیرد اطلاق می شود به عبارت دیگر در ورودی رشته هایی وجود دارد که Tokenیکسانی برای انها تشخیص داده می شود فرم کلی این رشته ها توسط الگو یا pattern الگو توزیع می شود

[Y@SiN]

Lexeme(واژه): به دنباله ای از کاراکترها (نویسه ها) که تشکیل یک Token را می دهند واژه گفته می شود.


ورودی اسکنر---> lexeme
خروجی اسکنر --->Token
پردازش pattern بر اساس

(براساس patternها می توان lexeme را به Token تبدیل کرد.و اولین قدم برای تولید Token،تعریف pattern می باشد)

[Y@SiN]

مشکلات اسکنرها

تحلیلگر واژه lexeme analyzer:در بعضی مواقع اسکنرها قبل از اینکه تصمیم بگیرند جه Tokenرا به پارسل بفرستندنیاز دارن که چند کاراکتر دیگر را از ورودی بخواند به عنوان مثال اسکنر با دیدن علامت ">"نیاز دارد که کاراکترورودی بعدی را نیز بخواند در صورتی که کاراکتر ورودی بعدی مساوی باشد Token "=>" راتشخیص دهد. در صورتی که کاراکتر بعدی "<" باشدToken نامساوی "<>" را تشخیص دهد ودر غیر این دو صورت Token بزرگتر تشخیص داده شود. در مورد اخر کاراکتر اضافی خوانده شده دوباره به ورودی بازگردانده می شود.
یکی دیگر از مشکلاتی که در بعضی زبان ها مثل (فرترن) در طراحی Tokenها وجود دارد به این صورت است که در این گونه زبان ها جای خالی را به جز در رشته ی کاراکتری نادیده می گیرند. به عنوان مثال: D05I=1.25 درزبان فرترن کامپایلر اجازه نمی دهد فاصله داشته باشند در اصل باید این گونه باشد D0 5 I = 1.25تا زمانی که به نقطه ی اعشار در 1.25نرسیده باشیم نمی توان گفت که این D0 در این دستور کلمه کلیدی نیست بلکه بخشی از متغییر D05I است،به همین ترتیب در دستور D05I=1.25 تا زمانی که علامت «،» دیده نشود نمی توان گفت که این یک حلقه D0 است.
در زبان هایی که در انها کلمات کلیدی جزو کلمات رزرو شده نیستند نظیر PL1اسکنر نمی تواند تمام شناسه های هم نام را از کلمات کلیدی تشخیص دهد به عنوان مثال در دستور if then THEN Then=Else,ELSE,ELSE جدا کردن کلمه کلیدی then از THENکاری بسیار مشکل می باشد در این گونه موارد تشخیص نهایی بر عهده پارسل خواهد بود.

[Y@SiN]

روشهایی جهت بهبود کار اسکنرها:
1)استفاده از بافر 2)استفاده از نگهبانها Sentinels

۱) استفاده از بافر:در بسیاری از زبانهای اسکنر برای تشخیص نهایی Tokenها ومطابقت دادن ان ها با الگوهای موجود این نیاز وجود دارد که چندین کاراکتر جلوتر را نیز مورد بررسی قرار دهد از انجا که مقدار زمان زیادی در جابجایی کاراکترها سپری می شود از تکنیک های بافرینگ برای پردازش کاراکترهای ورودی استفاده می شود. در یکی از این تکنیک ها از یک بافر که به دو نیمه ی n کاراکتری تقسیم شده است استفاده می کنند که در ان n برابر تعدادکاراکترهایی است که روی یک بلاک از دیسک جای می گیرند به این ترتیب با یک فرمان read به جای خواندن یک کاراکتر می توان n کاراکتر ورودی را در هر بافر وارد کرد در صورتی که ورودی کمتر از nکاراکتر باشد بعد از خواندن کاراکترها یک کاراکتر خاص (end of file)EOF نیز به کاراکتر وارد می گردد (EOFبیانگر پایان فایل منبع بوده و با سایر کاراکترهای ورودی به نوعی تفاوت دارد)
در این تکنیک در بافر ورودی از دو نشانه رو یا pointer استفاده می شود رشته کاراکتری بین دو نشانه رو معرف lexemeدو واژه جاری می باشد.در ابتدا هر دو نشانه رو به اولین کاراکتر lexeme بعدی که باید پیدا شود اشاره می کند.
نشانه رو اول را forwardونشانه رو بعدی را lexeme-beginig میگویند،نشانه رو forward تا انجایی پیش می رود که یک Token تشخیص داده شود .
این نحوء استفاده از بافر در بیشتر موارد کاملا خوب کار می کند با این حال در مواردی که جهت تشخیص یک Tokenنشانه رو forward ناچار است بیشتر از طول بافر جلو برود که کارایی ندارد.

به عنوان مثال دستور (ARG1,ARG2,…,ARGn) DECLARE را در یک برنامه PL1 در نظر بگیرید در این دستور تا زمانی که کاراکتر بعد از پرانتز سمت راست را بررسی نکنیم نمی توان گفت که DECLARE یک کلمه کلیدی است یا یک اسم ارایه ،برای کنترل حرکت نشانه رو pointer,forward و همچنین کنترل بافر می توان به صورت زیر عمل کرد :
شبه کد pseudo code :





if forward is at end of first half then
begin
reload second-half+1
end;
else
if forward is at end-of-second half
begin
reload first half
move forward to begin of first-half
end;
else
forward=forward+1

[Y@SiN]

۲) استفاده از نگهبانها (sentinels)

در حالت قبل با رفتن نشانه رو (forward) باید چک می شد که ایا این نشانه را به انتهای یک نیمه از بافر رسیده است یا خیر؟ در صورتی که به انتهای یک نیمه ی بافر رسیده باشد ، باید نیمه ی دیگر را دوباره باز می کردیم در الگوریتم فوق همان طوری که مشاهده شد برای هر جلوبندی نشانه روی forward _ forward+1عمل مقایسه انجام می شود،می توان این دو را به یک بار تست کرد برای این کار باید در انتهای هر نیمه ی بافر یک کاراکتر نگهبان یا sentinels قرار دهیم لازم به ذکر است که sentinels به عنوان قسمتی از برنامه منبع نخواهد بود به این ترتیب برای کنترل حرکت نشانه رو forward می توانیم از الگوریتم زیر استفاده کنیم.




Forward:=forward+1
If forward =eof then
Begin
If forward is at end of first half then
Begin
reload scand half;
Forward:=forward+1;
end
else if forward at end of second half then
Begin
reload first half
Move forward to beging of first half .
end
else /*eof wit in a buffer signifging end of input*/comment
termate lexical Analysis
end;

[Y@SiN]

چند مفهوم مرتبط


الفبا (Alphapet): مجموعه ای محدود از علامت ها. {الف،ب،...،ی}
رشته(string) : دنباله محدود از علامتها. «علی»
زبان (language) : مجموعه ای محدود یا نا محدود از الفبا ایجاد می شود.
پیشوند رشته (prefix) : رشته حاصل از حذف،یا بیشتر علائم از انتهای رشته را گویند.
زیر رشته (substring) : رشته حاصل از حذف یک پیشوند و یا یک پسوند را زیر رشته می گویند.
رشته تهی(null string) : اگر طول رشته برابر صفر باشد گوئیم رشته تهی است و با λ نمایش می دهیم.
پسوند رشته(saffix) رشته حاصل از حذف یا بیشتر علائم از ابتدای رشته را می گویند.

[Y@SiN]

عملیات روی زبان ها با فرض دو زبان M,L:




1) L U M = { S | S€L or T€M}
2) L.M={S|S€L and T€M}


3) L* = L0UL¹UL² ….
۴)L+=L¹UL²UL³....

[Y@SiN]

مفهوم عبارات منظم:(Logular expression):

ابزاری است برای نمایش زبانهای منظم از نظر قدرت دقیقا معادل گرامرهای منظم می باشد یعنی هر زبانی که بتوان برای ان یک گرامر منظم تعریف کرد.فشرده بودن و خواناتربودن عبارات منظم دلیل استفاده از ان می باشد.
عبارات منظم برای نمایش Tokenها نیز مناسب اند یک نرم افزاری به نام Lexوجود دارد که عبارت منظم را به Tokenهاتبدیل می کند،عبارات منظم روی زبان∑ (الفبای زبان)به صورت زیر تعریف می شود.

۱) ( λ)(منظور رشته است) یک عبارت منظم است و {λ}تک عضوی را تعریف می کند.
۲) اگر (a € ∑ ) باشد انگاه a یک عبارت منظم است و زبان a را تعریف می کند


هر کاراکتر به تنهایی یک عبارت منظم است.


3) اگر r,sعبارت منظم باشند که زبان L(r),L(s) ,را تعریف می کنند در ان صورت :

(r).(s یک عبارت منظم است که زبان L(r).L(s) را تعریف می کند.
r¦s یک عبارت منظم است که L(r)u L(s) را توصیف می کند.
(r) یک عبارت منظم است که زبانL(r) را توصیف می کند.
نکته : چون عبارتهای منظم از نظر نمایش خواناتر هستند و حجم کمتری را اشغال می کنند
(از نظر حافظه) معمولا در نمایش گرامرهای یک زبان از عبارات منظم استفاده می کنند و به بیان دیگر هر جایی که بتوان از زبان نوع سوم استفاده کنیم قادریم از عبارات منظم برای نمایش ان زبان استفاده نماییم.

*سوال:
_برخی از زبان ها دارای Tokenهایی هستند که نمی توان با استفاده از عبارات منظم انها را توصیف کرد؛چرا؟

*جواب:
_به دلیل اینکههمه گرامرهای ما منظم نیستند تا بتوان در قالب عبارات منظم انها را بیان کرد.به عنوان مثال

مجموعه همه رشته های با پرانتزهای تودرتو را نمی توان توسط عبارات منظم تعریف کرد(((®((( این قبیل گرامرها(گرامرهایی که تعداد پرانتزهای تودرتو زیادی دارند) تحت عنوان گرامر مستقل از متن می باشد.

تمرین:
جستجو در اینترنت برای پیدا کردن patternهای زبان پاسکال به صورت عبارت منظم و ویرایش ان انجام دهید(قاعده های زبان پاسکال).

[Y@SiN]

روش های اسکنر برای تشخیص Token :

دستی
اتوماتیک

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

[Y@SiN]

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

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

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

[Y@SiN]

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

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

[Y@SiN]

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

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

[Y@SiN]

*پذیرنده زبانها (ماشین پذیرنده زبان )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)جدول انتقال