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

[Y@SiN]

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

اصطلاحات:

• الفبا:یک مجموعه محدود از علامتها
• مجموعه(تمامی قوانین مجموعه ها مثل عضویت زیر مجموعه،مجموعه جهانی و...صدق می کند.)
• رشته:دنباله ای از علامت ها مانند : abba
• طول رشته:طول علامت ها می باشد به عنوان مثال ۳ = |aba|
• رشته تهی:رشته ای با طول صفر که با لاندا نمایش داده می شود.

[Y@SiN]

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

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

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

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

[Y@SiN]

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

1. اجتماع
2. اشتراک
3. اتصال

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

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

[Y@SiN]

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

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

1. گرامر منظم یا با قاعده یا نوع سوم
2. گرامر مستقل از متن یا نوع دوم
3. گرامر حساس به متن یا نوع اول
4. گرامر بی قاعده یا نوع صفر

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

[Y@SiN]

انواع زبان:

1. زبان های منظم یا با قاعده
2. زبان های مستقل از متن
3. زبان های حساس به متن
4. زبان های بی قاعده

[Y@SiN]

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

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

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

[Y@SiN]

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

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

[Y@SiN]

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

[Y@SiN]

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

1. L.M.D اگر هر بار در عمل اشتقاق سمت چپ ترین غیر پایانی انتخاب شود بسط چپ است.
2. 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