جلسه ۰۵ : عبارات منظم در طراحی کامپایلر

• جزئیات
• نوع محتواآموزشی

سلام و وقت بخیر خدمت همراهان وب سایت آموزشی پی وی لرن. با دوره کامل آموزش طراحی کامپایلر در خدمت شما عزیزان خواهیم بود. با بررسی عبارات منظم در طراحی کامپایلر همراه خواهیم بود. با ادامه ی آموزش ها همراه باشید.

بررسی عبارات منظم در طراحی کامپایلر

تحلیلگر واژه ای فقط باید مجموعه متناهی از رشته معتبر / توکن / تکواژه‌ های معتبر را كه متعلق به زبان مورد نظر است ، اسكن و شناسایی كند. این تحلیل‌ گر الگوهایی تعریف شده توسط قوانین زبان را جستجو می کند.

عبارات منظم این قابلیت را دارند که از طریق تعریف الگویی برای رشته های متناهی از نمادها ، زبان های متناهی را بیان کنند. گرامر تعریف شده توسط عبارات منظم به عنوان گرامر منظم شناخته می شود. زبان تعریف شده توسط گرامر منظم به عنوان زبان منظم شناخته می شود.

عبارات منظم یک نماد گذاری مهمی برای مشخص کردن الگوها هستند. هر الگو با مجموعه ای از رشته ها مطابقت دارد ، بنابراین عبارات منظم به صورت نام هایی برای مجموعه ای از رشته ها استفاده می ‌شوند. توکن های زبان برنامه نویسی را می توان به صورت زبان ‌های منظم توصیف کرد. مشخصات عبارات منظم نمونه از تعریف بازگشتی است. زبان های منظم به راحتی قابل فهم هستند و پیاده‌ سازیشان کارآمد است.

تعدادی قانون جبری وجود دارد که از عبارات منظم پیروی می کنند ، که از آن ‌ها می توان برای تبدیل عبارات منظم به فرم های معادل استفاده کرد.

عملیات (Operations)

عملیات های مختلف روی یک زبان عبارتند از:

اتحاد (Union) دو زبان L و M به صورت زیر نوشته شده است.

{L U M = {s | s is in L or s is in M

الحاق (Concatenation) دو زبان L و M به صورت زیر نوشته شده است.

{LM = {st | s is in L and t is in M

بستار کلین – Kleene Closure یک زبان L به صورت زیر نوشته شده است.

L* = Zero or more occurrence of language L.

نماد گذاری (Notations)

اگر r و s عباراتی منظم باشند که زبان های (L (r و (L(s را نشان می دهند ، پس:

اتحاد : (r)|(s) یک عبارت منظم است که زبان‌ های (L(r) U L(s را نشان می دهد.

الحاق : (r)(s) یک عبارت منظم است که (L(r)L(s را نشان می دهد.

بستار کلین : *(r) یک عبارت منظم است که *((L (r) را نشان می دهد.

(r) یک عبارت منظم است که (L (r را نشان می دهد.

تقدم و شرکت‌ پذیری (Precedence and Associativity)

* و الحاق(.) و | (خط عمودی) از سمت چپ صورت شرکت ‌پذیر هستند.
* بالاترین تقدم را دارد.
الحاق(.) دومین درجه از تقدم را دارد.
(خط عمودی) | دارای پایین ترین تقدم است.

نمایش توکن معتبر یک زبان در عبارت منظم

اگر x یک عبارت منظم باشد ، پس :

• *x به معنای رخداد صفر یا تعداد بیش تری از x است.

یعنی می تواند { …,e, x, xx, xxx, xxxx } را تولید کند.

• +x به معنای یک یا چند مورد وقوع x است.

یعنی می تواند {…x، xx، xxx، xxxx} یا *x.x را تولید کند.

• ?x یعنی حداکثر رخداد یک مورد x می باشد.

یعنی می تواند {x} یا {e} را تولید کند.

[a-z] همه حروف کوچک الفبای زبان انگلیسی هستند.

[A-Z] همه حروف بزرگ الفبای زبان انگلیسی هستند.

[۰-۹] تمام ارقام طبیعی است که در ریاضیات استفاده می شود.

نشان دادن رخداد نمادها با استفاده از عبارات منظم

حرف = [a – z] یا [A – Z]

رقم = ۰ | ۱ | ۲ | ۳ | ۴ | ۵ | ۶ | ۷ | ۸ | ۹ یا [۰-۹]

علامت = [+ | -]

نمایش توکن های زبان با استفاده از عبارات منظم

دهدهی = +(sign)?(digit)

شناسه *(Identifier ) =  (letter)(letter | digit)

تنها مشکلی که در مورد تحلیلگر لغوی باقی مانده است ، چگونگی تأیید اعتبار سنجی یک عبارت منظم است که در تعیین الگوهای کلید واژه‌های یک زبان مورد استفاده قرار می گیرد. یک راه حل کاملا پذیرفته شده استفاده از اتوماتای متناهی برای اعتبار سنجی است.

به پایان مبحث بررسی عبارات منظم در طراحی کامپایلر رسیدیم.

کلام پایانی

بررسی عبارات منظم در طراحی کامپایلر را در این بخش دنبال نمودیم. در بخش بعدی به بررسی Finite Automata می پردازیم. با ما همراه باشید.