بعد از مدتها به اینجا سر زدم.
اگر کسی علاقمند هست در مورد کامپایلرها و درس کامپایلر اینجا ادامه بده و یا کلا اینجا رو داشته باشه و به گسترش مفاهیم به زبان فارسی توی وب کمک کنه به من خبر بده. یعنی ایمیل بزنه.
ایمیل من:
ojaghi@gmail.com
به امید آن روز که به جای کپی و پیست یک مطلب و گسترش اون توی وب، تولید کنیم.
مشکل چپگردی در روش تقدم ساده :
U -> U …
U -> …XU..
تداخل به صورت زیر خواهیم داشت:
X = U , X < U
راه حل آن است که :
U -> U ..
V -> …XW…
W -> U
که در این صورت اینگونه خواهد شد :
X = W
X < Head(W) ={U}
مشکل راست گردی:
U -> …U
V ->…UX..
رفع مشکل:
U -> …U
V -> ..W X…
W -> U
در پیوست باید گفت که در این مقاله X,Y,W هم می تواند ناپایانه باشد و هم پایانه .
روش تقدم ساده Simple precedence
این روش بهبود یافته تقدم عملگر است . در این روش رابطه بین پایانه ها و ناپایانه ها هم بررسی می شود.
در آن روابط تقدم بین همه عناصر گرامر یعنی پایانه ها و ناپایانه ها تعریف می شود . محدودیت های این روش کمتر بوده و طیف وسیعتری از گرامر را شامل می شود .
ویژگی ها:
1. وجود ناپایانه ها و پایانه های مجاور مجاز است .
2. قاعده ε نباید در گرامر وجود داشته باشد.
3. محدودیت : سمت راست دو قاعده ای نباید یکسان باشد .
4. جدول پارسی نباید حاوی تداخل باشد .
جدول پارس:
یک جدول مربعی با ابعاد (|T| + | N | + 1) با توان 2 می باشد .
تعریف:
Head(U)={X => X α}
Tail (U)={X => α X}
Head: پایانه یا ناپایانه ای که در ابتدای فرم های جمله ای خاصل از U ظاهر شود .
Tail: پایانه یا ناپایانه هایی که انتهای فرم جمله ای ظاهر شده باشند .
روابط موجود در این روش:
X = Y ó З U ( U -> .. XY ..)
X < Y ó З U ( U -> .. X A ..) Y is member of head(A)
X < Head(A)
X > Y ó З U ( U -> .. A Y ..) X is member of Tail(A)
TaiL(A) . Y
برای مثال برای گرامر زیر:
N -> $S$ این خط را در ابتدا خود اضافه می کنیم ///
S ->(SS)
S -> c
|
|
S |
( |
) |
C |
$ |
|
S |
= |
< |
= |
< |
= |
|
( |
= |
< |
|
< |
|
|
) |
> |
> |
> |
> |
> |
|
c |
> |
> |
> |
> |
> |
|
$ |
= |
< |
|
< |
accepted |
Head(S) = { ( ,c }
Tail(S) = { ),c }
X := stack top terminal / non-terminal
B := lookahead
if p[X,b] = < then push (<); push(b);
if p[X,b] = = then push (=); push(b);
if p[X,b] = > then reduce( );
if p[X,b] = then error( );
reduce: ابتدا دستگیره را پیدا می کنیم به این ترتیب که آنقدر در پشته پایین می رویم تا به اولین نماد کوچکتر برسیم رشته میان > و بالای پشته دستگیره است .
TOP: عنصر بالای پشته پس از حذف دستگیره
LHS : سمت چپ قاعده مورد استفاده برای کاهش
برای کاهش با توجه به تعاریف داده شده اگر روابط به صورت زیر باشد این کارها را انجام می دهیم:
If p[TOP,LHS] = < then push(<);push(LHS);
If p[TOP,LHS] = = then push(=);push(LHS);
S -> $ E $ این خط را در ابتدا خود اضافه می کنیم
E -> E + T | T
T -> T*F | F
F -> (E) | id
که این گرامر دارای جدول پارس زیر است .
|
$ |
Id |
( |
) |
* |
+ |
|
|
> |
< |
> |
< |
> |
< |
+ |
|
< |
> |
< |
> |
< |
> |
* |
|
|
> |
= |
> |
> |
> |
) |
|
< |
|
< |
|
< |
< |
( |
|
< |
|
< |
|
< |
< |
id |
|
= |
> |
|
> |
> |
> |
$ |
اگر سطر اول b و ستون اول از چپ a باشد :
a := stack top terminal
b:= lookahead
اول از همه با push($) آغاز می شود .
if p[a,b] = < => a
if p[a,b] = = => a=b then push(=);push(b);
if p[a,b] = > => a>b then reduce();
if p[a,b] = => a b then error();
a+(a*a)
|
Input |
Stack |
|
a+(a*a)$ +(a*a)$ a*a)$ a*a)$ *a)$ *a)$ a)$ )$ )$ )$ $ $ $ |
$ $ N $N<+ $N<+<( $N<+<( $N<+<(N $N<+<(N<* $N<+<(N<* $N<+<(N<*N $N<+<(N $N<+<(N=) $N<+N $N |
reduce( ): یافتن دستگیره بالای پشته ، حذف آن از بالای پشته و قرار دادن ناپایانه نوعی N در بالای پشته
به عبارتی ساده تر آنقدر از بالای پشته پایین می آییم تا به اولین نماد کوچکتر برسیم. رشته میان نماد کوچکتر و بالای پشته و ناپایانه زیر > (در صورت وجود) دستگیره است .
حالا با یک عبارت ، جدول را تست می کنیم .
با حذف آنها یک ناپایانه N جایگزین می شود و همراه دستگیره کاهش می یابد .
روش به دست آوردن جدول پارس :
P: (T Ụ {$}) * (T Ụ {$}) ->{<,>,+, }
firstterm(A)={a :A=>a α or A =>B a α }
Lastterm(A)={ a :A=>α a or A =>α a β}
a = b <=> ЗU (U-> …ab…. Or U->…a W b ….)
a < b <=> ЗU (U-> a W , b is member of firstterm(W) )
a < first term (W)
a > b <=> ЗU (U-> W b , a is member of lastterm(W) )
lastterm(W) > b
a b <=> ~(بالایی ها )
تحلیل نحوی (Syntax Analysis)
که همان تجزیه یا parsing است .
پارسینگ وظیفه اش برعکس است ، یعنی چگونه اشتقاق انجام شده است .
در پارسینگ در اشتقاقهای ایجاد شده برعکس مگاه می کنیم تا به چگونگی اشتقاق پی ببریم .
روش تجزیه Parsing
1. روشهای عمومی { که این روش ها کارایی بهینه ندارند }
2. روشهای بالا به پایین
در این روش د درخت تجزیه از ریشه ها به سمت برگها حرکت می کنیم و روند طی شده را از ریشه ها به برگها طی می کنیم و یا در جمله ای بهتر آن که درخت تجزیه را از ریشه به برگها تولید می کنیم .
که به طور کلی به دو روش :
· پایین گرد
· LL(1)
دسته بندی می شوند .
3. روشهای پایین به بالا
در این روش برعکس روش قبل درخت تجزیه از برگها آغاز شده و به سمت ریشه گسترش می یابد .
که این روش نیز به سه گروه کلی تقسیم بندی می شود :
· تقدم عملگر
· تقدم ساده
· LR که این روش هم به طور کلی به 3 روش دیگر دسته بندی می شود :
1. SLR
2. LALR
3. CLR
در اینجا ما به روشهای پایین به بالا می پردازیم .
تجزیه پایین به بالا Bottom-Up Parsing
مقدمه:
ایده اصلی آن ، ساخت درخت تجزیه با شروع از برگ ها تا رسیدن به ریشه درخت می باشد .
در این روش از سمت راست گرامرها شروع کرده و با تشخیص آنها به سمت چپ هر گرامر رسیده و در آخر آنقدر جلو یم رویم تا به Start Symbol برسیم .
به طور مثال در گرامر زیر :
S -> aABe (1
A -> Abc|b (2,3
B->d (4
و در زیر رشته تولید شده توسط آن :
abbcde
این مراحل را طی می کنیم :
Abbcde
Abcde (3 گرامر سوم
aAde (2
aABe (4
S (1
مشاهده می شود که در گرامر از سمت چپ ها به سمت راست ها می رویم تا به سمبل شروع برسیم .
رشته ورودی را با جستجو به دنبال زیررشته ای که با سمت راست یک قاعده تولید منطبق شود پویش می کنیم .
مساله اصلی در تجزیه پایین به بالا انتخاب درست دست گیره (handle) و قاعده مربوط به آن است .
هدف :
ساخت درخت پارس رشته w با شروع از برگها تا رسیدن به ریشه پارسر به طور مکرر سمت راست یک قاعده تولید را در مقابل یک زیر رشته در فرم جمله ای راست تطابق می دهد .
در هر تطابق برای ساخت درخت پارس یک عمل کاهش reduce انجام میشود .
o هر کاهش زیررشته تطابق یافته ها با ناپایانه واقع در سمت چپ قاعده تولید جایگزین می کند و
o هر کاهش ، یک گره داخلی به درخت تجزیه ها می افزاید .
o حاصل هر عمل کاهش یک فرم جمله ای دیگر است.
o در نهایت حاصل یک اشتقاق راست به صورت معکوس خواهد بود .
دستگیره Handle
دسگیره بر اساس زیررشته ای تعیین می شود که:
- با سمت راست یک قاعده تولید A->α تطابق یابد
- کاهش α به A یک مرحله از عکس اشتقاق راست می باشد
به شکل رسمی : یک دستگیره از فرم جمله ای راست γ یک زوج مرتب از قاعده تولید βA -> و مکانی است که β در آن دریافت می شود .
Handle(γ) = <A -> β ,k>
1<= k <= |β|
اگر <A -> β ,k> دستگیره γ باشد ، آنگاه جایگزین β در مکان k با A، فرم جمله ای راست قبلی در اشتقاق راست را مشخص می کند .
هرس کردن دستگیره ها Handle pruning
برای بنا کردن درخت تجزیه از پایین به بالا ، فرزندان یک گره خذف می شوند و با پدر جایگزین می شوند .
قضیه:
اگر گرامر G مبهم نباشد آنگاه هر فرم جکله ای راست یک دستگیره یکتا دارد .
پارسر شیفت-کاهش Shift-Reduce
یکی از روشهای پیاده سازی هرس کردن دستگیره ها ، پارسر پایین به بالاست که shift-reduce parser نام دارد . این پارسر مطابق مدل [1]PDA از یک پشته و یک بافر ورودی استفاده می کند .
1. ابتدا یک علامت داده درون پشته push می شود.
2. مراحل زیر را تکرار می کنیم تاب الای پشته علامت δ و توکن جاری $ گردد :
i. دستگیره را می یابیم
اگر دستگیره ای بالای پشته وجود نداشت توکن ورودی را درون پشته شیفت می دهیم .
ii. دستگیره یافت شده را هرس می کنیم .
اگر دستگیره <A -> β ,k> بر روی پشته قرار داشت عمل reduce را انجام می دهیم : | β | علامت از بالای پشته pop می کنیم و به جای آن A را push می کنیم .
یک پارسر شیفت=کاهش چهار عمل اصلی دارد :
1. shift : push کردن توکن جاری به پشته
2. reduce : pop کردن دستگیره از بالای پشته و قرار دادن ناپایانه سمت راست قاعده به جای آن در پشته
3. accept : پارس با موفقیت حاتمه پیدا کند . ( lookahead =$, top=S)
4. error : در صورت عدم تطابق نحوی
یک دستگیره همیشه بالای پشته است چون گرامر و زبان مستقل از متن است .
دو نوع تداخل Conflict داریم :
o Shift –reduce conflict عدم تشخیص شیفت یا کاهش
o Reduce-reduce conflict عدم تشخیص قاعده مورد استفاده برای reduce
--------------------------------------------------------------------------------
[1] Push Down Automata
کامپایلر( Compiler ) :
خلاصه:
نرم افزاری است که کد یک زبان سطح بالا مانندC را به کد یک زبان سطح پایین معمولا Assemblyو یا زبان ماشین ( زبان ماشین زبان واقعی کامپیوتر و همان مجموعه ای از1,0 ها است ) ترجمه می کند.
اصطلاح سطح بالا و سطح پایین به معنای نزدیکی به سخّّت افزار است یعنی زبان C و Java نسبت به اسمبلی یا زبان ماشین از سخت افزار فاصله بیشتری دارند .
مقایسه کامپایلرها :
کامپایلر ها معمولا بر مبنای سرعت عمل کامپایل وسرعت کد ایجاد شده و اندازه کد ایجاد شده مقایسه می شوند.
تاریخچه کامپایلر
در تاریخچه کامپایلر سه دوره می‌توان در نظر گرفت:
از 1945تا1960:تولید کد
در این دوره , زبانها به تدریج به وجود آمدند و ماشینها چندان متعارف نبودند . مسئله این بود که چگونه باید کدی را برای یک ماشین تولید کرد . با توجه به اینکه برنامه نویسی به زبان اسمبلی رواج داشت , این مسئله وخیمتر شد. استفاده از کامپایلر , برنامه نویسی خودکار نامیده شد . طرفداران زبانهای سطح بالا می‌ترسیدند که کد تولید شده نسبت به زبان اسمبلی کارایی چندان نداشته باشد. اولین کامپایلر فرترن(شریدان 1959) به خوبی بهینه سازی شد
از 1960تا1975 :تجزیه کردن
در دهه‌های 1960و1970 زبانهای برنامه‌سازی جدید به وجود آمدند و طراحان زبان معتقد بودند که طراحی سریع کامپایلر برای زبان جدید , مهمتر از وجود کامپایلری با کد کارآمد است .بدین ترتیب , در ساخت کامپایلر به پردازشگر جلویی تاکید شده است . در همین زمان , مطالعه زبانهای رسمی , تکنیکهای قدرتمندی را برای ساخت پردازشگر جلوی , بخصوص تولید تجزیه کننده به وجود آورد
از 1975 تاکنون :تولید کد و بهینه سازی کد
از 1975 تاکنون , تعداد زبانهای جدید و انواع ماشین مختلف کاهش یافت در نتیجه نیاز به کامپایلرهای سریع و ساده یا سریع و ناقص برای زبانها یا ماشینهای جدید , کاهش یافت . بزرگترین آشفتگی در طراحی زبان و ماشین خاتمه یافت و افراد خواستار کامپایلرهای قابل اعتماد , کارآمد و با واسط کاربر مناسب شدند . بدین ترتیب , توجه کیفی به کد بیشتر شد زیرا با تغیر اندکی که در ساختار ماشینها ایجاد میشود , طول عمر کدها افزایش می‌یابد.در همین دوره , مدلهایی در برنامه نویسی به وجود آمدند که برنامه نویسی تابعی , منطقی و توزیعی نمونه‌های از این مدلها هستند, خواسته‌های زمان اجرای این زبانها نسبت به زبانهای دستور, افزایش یافت .
شرح مختصری بر کامپایلر
به طور کلی , کامپایلر برنامه‌ای است که متن برنامه‌ای را که به یک زبان برنامه‌سازی نوشته شده است ,به عنوان ورودی می‌پذیرد , و خروجی آن , متن برنامه‌ای به یک زبان دیگر است , به طوری که معنای آن متن تغییر نمی‌کند. این فرآیند , در زبان طبیعی , ترجمه نام دارد. مترجمها جملات یک زبان طبیعی را به زبان طبیعی دیگر ترجمه می‌کنند. تقریبا تمام کامپایلرها ,برنامه‌ای به یک زبان منبع را گرفته به برنامه‌ای به زبان مقصد تبدیل می‌کنند . به عنوان مثال , زبان منبع می‌تواند c و زبان مقصد می‌تواند زبان ماشین برای کامپیوتر پنتیوم باشد. زبانی که خود کامپایلر با آن نوشته میشود, زبان پیاده ساز نام دارد.
علت انجام ترجمه این است که , سخت افزار عملیاتی را انجام می‌دهد که توسط معنای برنامه توصیف میشود . به طور کلی , سخت افزار تنها منبع واقعی انجام محاسبات است. اجرای برنامه ترجمه شده, شامل خواندن داده‌های آن بار فرمت خاص , و چاپ نتایج با فرمت دیگری است . داده‌های ورودی می‌تواند از منابع متعددی خوانده شود , مثل فایلها , صفحه کلید و پکیج‌های شبکه‌به همین ترتیب , خروجی نیز می‌تواند در فایلها , صفحه نمایش رایانه , و چاپگر قرار گیرد .
برای ترجمه برنامه,از کامپایلر استفاده می‌کنیم . کامپایلر برنامه‌ای است که ورودی آن، , فایلی با فرمت متن برنامه و خرجی آن، فایلی با فرمت کد اجرایی است .
برای تهیه یک کامپایلر , کامپایلر دیگری رااجرا می‌کنیم که ورودی آن ,متن منبع این کامپایلر و خروجی آن , کد اجرایی برای این کامپایلر است . این فرآیند کامپایل است . اگر زبان منبع , همان زبان پیاده ساز باشد, و متن منبعی که کامپایل میشود, نسخه جدید خود کامپایلر باشد, این فرآیند خودرانی نام دارد.
کامپایل کردن یک برنامه, با تبدیل فرمت یک فایل به فرمت دیگر , مثل EBCDIC به اسکی تفاوت عمده‌ای ندارد . در کامپایل کردن برنامه, معنای برنامه باید حفظ شود . به دو دلیل زیر کامپایلر می‌تواند کار کند:
*ورودی, به یک زبان برنامه سازی است و در نتیجه دارای ساختاری است که در مراجع آن زبان مشخص شده است .
*معنای ورودی بر اساس این ساختار توصیف میشود ,و به آن ساختار مربوط است.
این عوامل موجب می‌شوند تا کامپایلر برنامه را "درک کند " و معنای آن را در یک نمایش معنایی جمع آوری کند .هریک از دو عامل فوق , در زبان مقصد نیز وجود دارد . بدین ترتیب , کامپایلر می‌تواند معنای جمع آوری شده را بر حسب ساختار زبان مقصد ارائه کند .
بخشی از کامپایلر که متن زبان منبع را تحلیل می‌کند , پردازشگر جلویی و بخشی از کامپایلر که زبان مقصد را ترکیب می‌کند, پردازشگر نهایی نام دارد اگر کامپایلر به خوبی طراحی شده باشد, پردازشگر نهایی, کاملا از زبان مبدا و پردازشگر جلویی از زبان منبع بی خبر است . هر یک از این دو بخش از نمایش معنایی برنامه خبر دارند .این تفکیک دقیق , دلایل فنی دارد و منجر به کامپایلرهای ساخت یافته میشود.
حالت دیگری از عملیات برای کامپایلر پیشنهاد میشود: اگر تمام داده‌های ورودی مورد نیاز , فراهم باشند, کامپایلر می‌تواند مفهوم مشخص شده توسط معنای برنامه را بدون تبدیل به شکل دیگر , اجرا نماید . در این صورت به جای مولد کد پردازشگر نهایی, مفسر پردازشگر نهایی قرار می‌گیرد و این برنامه, مفسر نامیده میشود . چند دلیل برای این کار وجود دارد . یکی از دلایل مهم این است که مفسر معمولا در ماشین خاصی اجرا می‌گردد. به عبارت دیگر , استفاده از مفسر منجر به افزایش قابلیت حمل می‌گردد. دلیل دیگر این است که نوشتن مفسر, آسانتر از پردازشگر نهاییت کامپایلر است .دلیل سوم برای استفاده از مفسر به جای کامپایلر این است که , اجرای مستقیم برنامه , عیب یابی و گزارش خطا را آسانتر می‌کند . دلیل چهارم این است که امنیت از طریق مفسرها افزایش می‌یابد . این کار , در جاوا اهمیت فراوانی دارد.
________________________________________
اجزای کامپایلر
هر کامپایلر از قسمت های اصلی زیر تشکیل شده است:
• فاز تحلیلگر لغوی
• فاز تحلیلگر نحوی
• فاز تحلیلگر معنایی
• فاز تولید کننده کد میانی
• فاز بهینه ساز کد
• فاز تولید کننده کد
و نیز دو بخش کمکی:
• اداره کننده خطا
• مدیر جدول نماد ها