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

[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]

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

1. تحلیلگر واژه lexeme analyzer:در بعضی مواقع اسکنرها قبل از اینکه تصمیم بگیرند جه Tokenرا به پارسل بفرستندنیاز دارن که چند کاراکتر دیگر را از ورودی بخواند به عنوان مثال اسکنر با دیدن علامت ">"نیاز دارد که کاراکترورودی بعدی را نیز بخواند در صورتی که کاراکتر ورودی بعدی مساوی باشد Token "=>" راتشخیص دهد. در صورتی که کاراکتر بعدی "<" باشدToken نامساوی "<>" را تشخیص دهد ودر غیر این دو صورت Token بزرگتر تشخیص داده شود. در مورد اخر کاراکتر اضافی خوانده شده دوباره به ورودی بازگردانده می شود.
2. یکی دیگر از مشکلاتی که در بعضی زبان ها مثل (فرترن) در طراحی Tokenها وجود دارد به این صورت است که در این گونه زبان ها جای خالی را به جز در رشته ی کاراکتری نادیده می گیرند. به عنوان مثال: D05I=1.25 درزبان فرترن کامپایلر اجازه نمی دهد فاصله داشته باشند در اصل باید این گونه باشد D0 5 I = 1.25تا زمانی که به نقطه ی اعشار در 1.25نرسیده باشیم نمی توان گفت که این D0 در این دستور کلمه کلیدی نیست بلکه بخشی از متغییر D05I است،به همین ترتیب در دستور D05I=1.25 تا زمانی که علامت «،» دیده نشود نمی توان گفت که این یک حلقه D0 است.
3. در زبان هایی که در انها کلمات کلیدی جزو کلمات رزرو شده نیستند نظیر 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 :

1. دستی
2. اتوماتیک

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