تجزیه‌کننده - ویکی‌پدیا، دانشنامهٔ آزاد

این مقاله دقیق، کامل و صحیح ترجمه نشده و نیازمند ترجمه به فارسی است. کل یا بخشی از این مقاله به زبانی به‌جز زبان فارسی نوشته شده‌است. اگر مقصود ارائهٔ مقاله برای مخاطبان آن زبان است، باید در نسخه‌ای از ویکی‌پدیا به همان زبان نوشته شود (فهرست ویکی‌پدیاها را ببینید). در غیر این صورت، خواهشمند است ترجمهٔ این مقاله را با توجه به متن اصلی و با رعایت سیاست ویرایش، دستور خط فارسی و برابر سازی به زبان فارسی بهبود دهید و سپس این الگو را از بالای صفحه بردارید. همچنین برای بحث‌های مرتبط، مدخل این مقاله در فهرست صفحه‌های نیازمند ترجمه به فارسی را ببینید. اگر این مقاله به زبان فارسی بازنویسی نشود، تا دو هفتهٔ دیگر نامزد حذف می‌شود و/یا به نسخهٔ زبانی مرتبط ویکی‌پدیا منتقل خواهد شد. اگر شما اخیراً این مقاله را به‌عنوان صفحهٔ نیازمند ترجمه برچسب زده‌اید، لطفاً عبارت {{جا:نیاز به ترجمه|صفحه=تجزیه‌کننده |زبان=نامشخص |نظر= }} ~~~~ را به پایین این بخش از فهرست صفحه‌های نیازمند ترجمه به فارسی بیفزایید. لطفاً {{جا:هبک-ترجمه به فارسی|1=تجزیه‌کننده}} ~~~~ را نیز در صفحهٔ بحث نگارنده قرار دهید.

این مقاله نیازمند ویکی‌سازی است. لطفاً با توجه به راهنمای ویرایش و شیوه‌نامه، محتوای آن را بهبود بخشید.

تجزیه‌گر^[۱] یا تجزیه‌کننده یا پارسر (به انگلیسی: Parser) فازم دوم عمل کامپایل است. گرامر مورد استفاده در این مرحله گرامر مستقل از متن یا Context Free است. در حین این مرحله از کامپایل است که خطاهای نحوی تشخیص داده می‌شوند.

نخستین مرحلهٔ کامپایل تحلیل واژه‌ای (به انگلیسی: Lexical Analysis) است. به واحدی از کامپایلر که کار تحلیل واژه‌ای را انجام می‌دهد، اسکنر می‌گویند. اسکنر بین رشتهٔ ورودی و تحلیلگر نحوی (یا پارسر-parser) واقع است. وظیفهٔ اصلی اسکنر این است که با خواندن کاراکترهای ورودی، توکن‌ها را تشخیص داده و برای parser ارسال نماید. رابطهٔ scanner و parser به صورت زیر است:

به عنوان مثال در صورتی‌که رشتهٔ ورودی A:=B+C باشد، توکن‌های زیر تشخیص داده خواهند شد: (آدرسid,C) و (add .op.) و (آدرسid, B) و (ass .op.) و (آدرس id, A) بنابراین اسکنر علاوه بر اینکه تشخیص می‌دهد که توکن یک شناسه‌است، آدرس آن در جدول نشانه‌ها را نیز برای پارسر می‌فرستد. علاوه بر این اسکنر می‌تواند محل‌های خالی و توضیحات(comments) موجود در برنامه اصلی را ضمن خواندن برنامه حذف نماید. به آخرین توکنی که اسکنر یافته‌است، علامت پیش‌بینی (look ahead symbol) یا توکن جاری گفته می‌شود.

۲–۱- الگو (pattern) و واژهٔ (Lexem) توکنها: به فرم کلی که یک توکن می‌تواند داشته باشد، الگوی آن توکن می‌گویند. به عبارتی دیگر در ورودی، رشته‌هایی وجود دارند که توکنِ یکسانی برای آن‌ها تشخیص داده می‌شود. فرم کلی این رشته‌ها توسط الگوی آن توکن توصیف می‌شود. به دنباله‌ای از نویسه‌ها که تشکیل یک توکن می‌دهند، واژه (Lexem) آن توکن می‌گویند. جدول زیر حاوی چند نمونه الگو و واژه‌است:

الگو واژه توکن با حروف الفبا شروع و به‌دنبال آن حرف ورقم قرار می‌گیرد A1 id هرثابت عددی ۳٫۱۴ num

هر رشتهٔ کاراکتری که بین دو علامت " " قرار گیرد "book" literal

<<relation >=>= relation if if if 

در بعضی وضعیتها اسکنر قبل از اینکه تصمیم بگیرد که چه توکنی را به پارسر بفرستد، نیاز دارد که چند کاراکتر دیگر را نیز، از ورودی بخواند. مثلاً اسکنر با دیدن علامت <در ورودی نیاز دارد که کاراکتر ورودی بعدی را نیز بخواند. در صورتی‌که این کاراکتر = باشد، در نتیجه توکن '<=' و در غیر اینصورت توکن ' <' تشخیص داده می‌شود. در این مورد باید کاراکتر اضافی خوانده شده مجدداً به ورودی برگردد.

یکی دیگر از مشکلاتی که اسکنر با آن روبروست این است که در زبان‌هایی نظیر فرترن مثلاً محل خالی یا (space) بجز در رشته‌های کاراکتری، نادیده گرفته می‌شود. به عنوان مثال کلمهٔ Do در زبان فرترن را در دستور زیر در نظر بگیرید: do bi =۱٫۲۵ تا زمانی‌که به نقطهٔ اعشار در ۱٫۲۵ نرسیده باشیم نمی‌توان گفت که do در این دستور کلمه کلیدی نیست، بلکه بخشی از متغیری است که نام آن do bi است. به همین ترتیب در دستور do bi=۱٬۲۵ تا زمانی‌که علامت کاما دیده نشود، نمی‌توان گفت که این دستور یک حلقهٔ do است.

در زبان‌هایی که کلمات کلیدی آن جزو کلمات رزرو شده نیستند، اسکنر نمی‌تواند کلمات کلیدی را از شناسه‌های همنام آن‌ها تشخیص دهد. به عنوان مثال در دستور زیر:

IF Then THEN then=else;ELSE Else=Then; 

جدا کردن کلمهٔ کلیدی THEN از متغیری که نام آن Then است بسیار مشکل است. در این موارد معمولاً پارسر تشخیص نهایی را خواهد داد.

۲–۲- خطاهای واژه‌ای (Lexical Errors): به‌طور کلی خطاهای محدودی را اسکنر می‌تواند بیابد، زیرا اسکنر تمام برنامهٔ ورودی را یکجا نمی‌بیند بلکه هر بار قسمت کوچکی از برنامهٔ منبع را. به‌عنوان مثال هرگاه رشتهٔ fi در یک برنامهٔ C برای بار اول مشاهده شود، اسکنر قادر نیست تشخیص دهد که آیا fi یک املای غلط از کلمهٔ کلیدی if است یا نام یک متغیر است: fi (x==۳) از آنجایی که fi می‌تواند نام یک متغیر مجاز باشد، اسکنر این توکن را به‌عنوان یک شناسه به پارسر می‌فرستد تا اینکه پارسر در اینمورد تصمیم بگیرد. اما ممکن است خطاهایی پیش بیاید که اسکنر قادر به انجام هیچ عملی نباشد. در این مورد، برنامهٔ خطا پرداز (error handler) فرا خوانده می‌شودتاآن خطا را به نحوی برطرف کند. روش‌های مختلفی برای این کار وجود دارد که ساده‌ترین آن‌ها روشی است بنام panic mode (وضعیت هراس). در این روش آنقدر از رشتهٔ ورودی حذف می‌شود تا اینکه یک توکن درست، تشخیص داده شود. سایر روش‌های تصحیح خطا (error recovery) عبارت‌اند از: a) حذف یک کاراکتر غیرمجاز (تبدیل:$= به :=) b) وارد کردن یک کاراکتر گم شده (مثلاً تبدیل: به :=) c) تعویض کردن یک کاراکتر غلط با یک کاراکتر درست (مثلاً تبدیل :: به :=) d) جابجایی دو کاراکتر مجاز (مانند =: به :=)

۲–۳- روشهایی جهت بهبود کار اسکنر:

الف)استفاده از بافر: در بسیاری از زبان‌ها اسکنر برای تشخیص نهایی توکن‌ها و مطابقت دادن آن با الگوهای موجود، نیاز دارد که چند کاراکتر جلوتر را نیز مورد بررسی قرار دهد. از آنجایی که مقدار زیادی از زمان در جابجایی کاراکترها سپری می‌شود، از تکنیک‌های بافرینگ، برای پردازش کاراکترهای ورودی استفاده می‌گردد. در یکی از این تکنیک‌ها از یک بافر که به دو نیمهٔ 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. 

• تجزیه‌کننده (زیست‌شناسی)