تحلیلگر نحوی
از ویکیپدیا، دانشنامهٔ آزاد.
تحلیلنحوی، Syntax Analyzer یا پارسر (Parser) فازم دوم عمل کامپایل میباشد.
گرامر مورد استفاده در این مرحله گرامر مستقل از متن یا Context Free میباشد.
در حین این مرحله از کامپایل میباشد که خطاهای نحوی تشخیص داده میشوند.
- تحلیل واژه ای ( Lexical Analysis) نخستین مرحلۀ کامپایل تحلیل واژه ای میباشد. به واحدی از کامپایلر که کار تحلیل واژه ای را انجام میدهد، اسکنر (scanner) میگویند. اسکنر بین رشتۀ ورودی و تحلیلگر نحوی (یا پارسر-parser) واقع است. وظیفۀ اصلی اسکنر این است که با خواندن کاراکترهای ورودی، توکن ها را تشخیص داده و برای parser ارسال نماید. رابطۀ scanner و parser بصورت زیر است:
به عنوان مثال در صورتیکه رشتۀ ورودی A:=B+C باشد، توکن های زیر تشخیص داده خواهند شد: (آدرسid,C) و (add .op.) و (آدرسid , B) و (ass .op.) و (آدرس id , A) بنابراین اسکنر علاوه بر اینکه تشخیص میدهد که توکن یک شناسه است، وآدرس آن در جدول نشانه ها را نیز برای پارسر میفرستد. علاوه بر این اسکنر میتواند محلهای خالی و توضیحات(comments) موجود در برنامه اصلی را ضمن خواندن برنامه حذف نماید. به آخرین توکنی که اسکنر یافته است، علامت پیش بینی(look a head symbol) و یا توکن جاری گفته میشود.
2-1- الگو (pattern) و واژۀ(Lexem) توکنها: به فرم کلی که یک توکن میتواند داشته الگوی آن توکن میگویند. به عبارتی دیگر در ورودی، رشته هایی وجود دارند که توکنِ یکسانی برای آنها تشخیص داده میشود. فرم کلی این رشته ها توسط الگوی آن توکن توصیف میشود. به دنباله ای از نویسه ها که تشکیل یک توکن میدهند، واژه(Lexem) آن توکن میگویند. جدول زیر حاوی چند نمونه الگو و واژه است:
الگو واژه توکن با حروف الفبا شروع و بدنبال آن حرف ورقم قرار میگیرد A1 id هرثابت عددی 3.14 num هر رشتۀ کاراکتری که بین دو علامت " " قرار گیرد "book" literal < < relation >= >= relation if if if
در بعضی وضعیتها اسکنر قبل از اینکه تصمیم بگیرد که چه توکنی را به پارسر بفرستد، نیاز دارد که چند کاراکتر دیگر را نیز، از ورودی بخواند. مثلاً اسکنر با دیدن علامت < در ورودی نیاز دارد که کاراکتر ورودی بعدی را نیز بخواند. در صورتیکه این کاراکتر = باشد، در نتیجه توکن '<=' و در غیر اینصورت توکن ' < ' تشخیص داده میشود. در این مورد باید کاراکتر اضافی خوانده شده مجدداً به ورودی برگردد. یکی دیگر از مشکلاتی که اسکنر با آن روبروست این است که در زبانهایی نظیر فرترن مثلاَ محل خالی یا (space) بجز در رشته های کاراکتری ، نادیده گرفته میشود. به عنوان مثال کلمۀ Do در زبان فرترن را در دستور زیر در نظر بگیرید: do bi =1.25 تا زمانیکه به نقطۀ اعشار در 1.25 نرسیده باشیم نمیتوان گفت که do در این دستور کلمه کلیدی نیست، بلکه بخشی از متغیری است که نام آن do bi است. به همین ترتیب در دستور do bi=1,25 تا زمانیکه علامت کاما دیده نشود، نمیتوان گفت که این دستور یک حلقۀ do میباشد.
در زبانهایی که کلمات کلیدی آن جزو کلمات رزرو شده نیستند، اسکنر نمیتواند کلمات کلیدی را از شناسه های همنام آنها تشخیص دهد. به عنوان مثال در دستور زیر: IF Then THEN then=else;ELSE Else=Then;
جدا کردن کلمۀ کلیدی THEN از متغیری که نام آن Then است بسیار مشکل است. در این موارد معمولاً پارسر تشخیص نهایی را خواهد داد. 2-2- خطاهای واژه ای(Lexical Errors): بطور کلی خطاهای محدودی را اسکنر میتواند بیابد، زیرا اسکنر تمام برنامۀ ورودی را یکجا نمیبیند بلکه هر بار قسمت کوچکی از برنامۀ منبع را. بعنوان مثال هرگاه رشتۀ fi در یک برنامۀ C برای بار اول مشاهده شود، اسکنر قادر نیست تشخیص دهد که آیا fi یک املای غلط از کلمۀ کلیدی if است یا نام یک متغیر است: fi (x==3) از آنجایی که fi میتواند نام یک متغیر مجاز باشد، اسکنر این توکن را بعنوان یک شناسه به پارسر میفرستد تا اینکه پارسر در اینمورد تصمیم بگیرد. اما ممکن است خطاهایی پیش بیاید که اسکنر قادر به انجام هیچ عملی نباشد. در این مورد، برنامۀ خطا پرداز (error handler) فرا خوانده میشودتاآن خطا را به نحوی برطرف کند. روشهای مختلفی برای این کار وجود دارد که ساده ترین آنها روشی است بنام panic mode (وضعیت هراس) . در این روش آنقدر از رشتۀ ورودی حذف میشود تا اینکه یک توکن درست، تشخیص داده شود. سایر روشهای تصحیح خطا(error recovery) عبارتند از : a) حذف یک کاراکتر غیر مجاز (تبدیل:$= به := ) b) وارد کردن یک کاراکتر گم شده (مثلا تبدیل : به := ) c) تعویض کردن یک کاراکتر غلط با یک کاراکتر درست ( مثلا تبدیل :: به := ) d) جابجایی دو کاراکتر مجاز ( مانند =: به := ) 2-3- روشهایی جهت بهبود کار اسکنر :
الف)استفاده از بافر: در بسیاری از زبانها اسکنر برای تشخیص نهایی توکنها و مطابقت دادن آن با الگوهای موجود، نیاز دارد که چند کاراکتر جلوتر را نیز مورد بررسی قرار دهد. از آنجایی که مقدار زیادی از زمان در جابجایی کاراکترها سپری میشود، از تکنیکهای بافرینگ ، برای پردازش کاراکترهای ورودی استفاده میگردد. در یکی از این تکنیکها از یک بافر که به دو نیمۀ n کاراکتری تقسیم شده است، استفاده میکنند (که در آن n تعداد کاراکترهایی است که در روی یک بلوک از دیسک جای میگیرند). به این ترتیب با یک فرمان read به جای خواندن یک کاراکتر ، میتوان n کاراکتر ورودی را در هر نیمۀ بافر وارد کرد. در صورتیکه ورودی شامل تعداد کاراکترهای کمتر از n باشد، بعد از خواندن این کاراکترها یک کاراکتر خاصِ eof نیز وارد بافر میگردد. کاراکتر eof بیانگر پایان فایل منبع بوده و با سایر کاراکترهای ورودی به نوعی تفاوت دارد.
C * * 2 eof E = M *
forward
Lexam –beginning ابتدای واژه
در بافر ورودی از دو نشانه رو استفاده میشود. رشتۀ کاراکتری بین این دو نشانه رو، معرف Lexem (واژه)جاری میباشد. در ابتدا هر دو نشانه رو به اولین کاراکتر Lexem بعدی که باید پیدا شود اشاره میکنند. نشانه رویِ forward پیش میرود تا اینکه یک توکن تشخیص داده شود . این نحو استفاده از بافر در بیشتر موارد کاملاً خوب عمل میکند . با این وجود در مواردی که جهت تشخیص یک توکن، نشانه روِ forward ناچار است بیشتر از طول بافر جلو برود، این روش درست کار نمیکند. بعنوان مثال دستور declare (arg1,arg2, … ,arn n) را در یک برنامۀ pl/1 در نظر بگیرید. در این دستور تا زمانیکه کاراکتر بعد از پرانتز سمت راست را بررسی نکنیم، نمیتوان گفت که declare یک کلمۀ کلیدی است و یا اسم یک آرایه است. برای کنترل حرکت نشانه رویِ forward و همچنین کنترل بافر میتوان بصورت زیر عمل کرد: If forward is at end of first half then Begin reload second-half;
Forward:=forward+1
End Else
If forward is at end of second-half then
Begin reload first half;
Move forward to begin of first half
End
Else forward:= forward+1;
ب)استفاده از نگهبانها(sentinels):
در حالت قبل با جلو رفتن نشانه رو forward باید چک میشد که آیا این نشانه رو به انتهای یک نیمه از بافر رسیده است یا خیر؟ در صورتیکه به انتهای یک نیمه از بافر رسیده باشد، باید نیمۀ دیگر را دوباره بار میکردیم. در الگوریتم فوق همان طوریکه مشاهده شد برای هر جلورویِ نشانه رویِ forward ، دو بار عمل مقایسه انجام مشود. میتوان این دو را به یک بار تست، تبدیل کرد. برای این کار باید در انتهای هر نیمۀ بافر، یک کاراکتر نگهبان قرار دهیم( نگهبان به عنوان قسمتی از برنامۀ منبع نخواهد بود). به این ترتیب برای کنترل حرکت نشانه روِ forward میتوانیم از الگوریتم زیر استفاده کنیم: forward:=forward + 1 ; if (forward = eof) then begin
if (forward is at end of first half) then
begin
reload second half;
forward := forward+1 ;
end
else
if (forward at end of second half) then
begin
reload first half;
move forward to beginning of first half
end
else /* eof within a buffer signifying end of input */
terminate lexical analysis (آنالیز واژه ای به پایان برسد)
end.

