سلام و وقت بخیر خدمت همراهان وب سایت آموزشی پی وی لرن. با دوره کامل آموزش طراحی کامپایلر در خدمت شما عزیزان خواهیم بود. در این بخش نیز به بررسی تحلیلگر نحوی یا Syntax analyser می پردازیم و مباحثی چون بازگشتی چپ (Left recursion) و حذف بازگشتی چپ ، فاكتورگيري از چپ (factoring Left) ، مجموعه آغازين و تابع Follow ، محدودیت های تحلیل گر نحوی و الگوریتم محاسبه مجموعه آغازين (First Set) را مورد بررسی قرار خواهیم داد.
بررسی تحلیلگر نحوی یا Syntax analyser
بازگشتی چپ (Left recursion)
در صورتی که متغیری در گرامر خودش را دوباره از سمت چپ تولید نماید، بازگشتی چپ (Left recursion) دارد. و اگر خود را از سمت راست تولید کند، بازگشتی راست دارد. گرامر در صورتی که دارای نماد غیرپایانی A باشد که اشتقاق آن شامل خود “A” به عنوان چپ ترین نماد باشد، بازگشتی چپ (Left recursion) نامیده می شود. گرامر چپ ترین به عنوان یک دردساز برای تجزیه کننده های بالا به پایین در نظر گرفته می شود. تجزیه کننده های بالا به پایین تجزیه را از نماد آغازین شروع به تجزیه می نمایند، که به خودی خود یک نماد غیر پایانی است. بنابراین ، هنگامی که تجزیه کننده در اشتقاق خود با همان نماد غیر پایانی برخورد می کند ، نمی‌تواند دیگر راجع به این که کجا تجزیه را متوقف کند تصمیمی بگیرد از این رو وارد حلقه نامتناهی می شود.
مثال:
مثال :
| (1) A => Aα | β (2) S => Aα | β A => Sd |
(۱) نمونه ی بالا نمونه ای از بازگشتی بی درنگ چپ می باشد، که A می تواند هر نمادی غیر پایانی باشد و α نمایانگر رشته ای از نمادهای غیر پایانی است.
(۲) مثال بالا نمونه ای از بازگشتی چپ غیر مستقیم است.
بررسی تحلیلگر نحوی یا Syntax analyser
یک تجزیه کننده بالا به پایین ، ابتدا A را تجزیه می کند ، که به نوبه خود رشته های متشکل از خود A ارائه می دهد و تجزیه کننده ممکن است برای همیشه به یک حلقه بی نهایت برود.
حذف بازگشتی چپ (Left recursion)
یکی از راه های حذف بازگشتی چپ بی درنگ (Left recursion) استفاده از روش زیر است:
ترکیب
به ترکیبات زیر تبدیل می شود.
این کار روی رشته های اشتقاق یافته از گرامر تأثیر نمی گذارد ، اما بازگشتی چپ بی درنگ را حذف می کند.
روش دوم استفاده از الگوریتم زیر است که باید همه بازگشتی های چپ مستقیم و غیر مستقیم را از بین ببرد.
مثال :
| START Arrange non-terminals in some order like A1, A2, A3,…, An for each i from 1 to n { for each j from 1 to i-1 { replace each production of form Ai ⟹Aj𝜸 with Ai ⟹ δ1𝜸 | δ2𝜸 | δ3𝜸 |…| 𝜸 where Aj ⟹ δ1 | δ2|…| δn are current Aj productions } } eliminate immediate left-recursion END |
مثال
مجموعه ترکیب زیر:
پس از اعمال الگوریتم فوق ، باید داشته باشیم.
مثال :
| S => Aα | β A => Aαd | βd |
و سپس ، با استفاده از روش اول ، بازگشتی چپ بی درنگ را حذف کنید.
اکنون هیچ کدام از ترکیب ها دارای بازگشتی چپ مستقیم یا غیرمستقیم نیست.
در ادامه ی مبحث بررسی تحلیلگر نحوی یا Syntax analyser با فاكتورگيري از چپ (factoring Left) همراه هستیم.
فاكتورگيري چپ (factoring Left)
اگر بیشتر از یک قاعده ی ترکیب گرامری، رشته پیشوندی مشترکی داشته باشد (برای غير پايانی A دو قاعده به صورت αβ۱ <– A و αβ۲ <– A وجود دارد) در این صورت تجزیه کننده بالا به پایین نمی تواند تصمیم بگیرد که کدام یک از ترکیب ها باید رشته ی موجود را تجزیه کنند.
مثال
اگر یک تجزیه کننده بالا به پایین با ترکیبی مانند زیر مواجه شود:
بنابراین نمی تواند تعیین کند که کدام ترکیب را جهت تجزیه رشته دنبال کند تا رشته را تجزیه کند زیرا هر دو ترکیب از نماد پایانی (یا غیر پایانی) یکسانی شروع می شوند. برای از بین بردن این سردرگمی ، از تکنیکی به نام فاکتورگیری سمت چپ استفاده می کنیم.
فاكتورگيري چپ گرامر را تغییر می دهد تا آن را برای پارسرهای بالا به پایین مناسب سازد. در این تکنیک ، ما برای هر یک از پیشوندهای مشترک انتخاب می کنیم و برای بقیه اشتقاق با ترکیب های جدید اضافه می شوند.
مثال
ترکیب های فوق را می توان به صورت زیر نوشت.
مثال
در حال حاضر پارسر فقط یک تولید در هر پیشوند دارد که تصمیم گیری را آسان تر می کند.
مجموعه اول-First و پیرو-Follow
بخش مهمی از ساخت جدول parser (تجزیه) در ایجاد اولین مجموعه های اول و پیرو است. این مجموعه ها می توانند موقعیت واقعی هر نماد پایانی در اشتقاق را تعیین کنند. این کار برای ایجاد جدول تجزیه در جایی صورت می گیرد که با کمک آن تصمیم می گیریم که T [A، t] = α را با برخی از قوانین ترکیبی جایگزین کنیم.
مجموعه اول (First Set)
این مجموعه جهت شناخت نماد پایانی مشتق شده از موقعیت اولیه توسط یک نماد غیر پایانی ایجاد شده است. مثلا،
این α در اولین موقعیت اشتقاق شده از t (پایانی) است. بنابراین ،(t ∈ FIRST (α.
الگوریتم محاسبه مجموعه اول (First Set)
به تعریف مجموعه (FIRST (α نگاه کنید:
اگر α یک پایانی است ، سپس {FIRST (α) = {α.
اگر α غیر پایانی باشد و α →ℇ یک ترکیب باشد ، سپس {FIRST (α) = {ℇ.
اگر α غیر پایانی باشد و α → 𝜸۱ 𝜸۲ 𝜸۳ … 𝜸n و هر یک از اعضای (FIRST(𝜸 حاوی t است ، پس t در (FIRST (α است.
مجموعه اول را می توان به صورت زیر مشاهده کرد:
بررسی تحلیلگر نحوی (Syntax analyser)
مجموعه پیرو – Follow set
به همین ترتیب و مانند مجموعه اول محاسبه می کنیم که کدام نماد پایانی بی درنگ بعد از یک α غیر پایانی در قوانین ترکیب ظاهر می شود. ما ظاهر چیزی را که نمادهای غیر پایانی می توانتد تولید کنند در نظر نمی گیریم اما در عوض آن ، بررسی می کنیم که نماد پایانی بعدی که از ترکیب یک غیر پایانه پیروی می کند چه خواهد بود.
الگوریتم محاسبه مجموعه پیرو- Follow:
- اگر α نمادی آغازین باشد ، سپس $=()FOLLOW
- اگر α غیر پایانی باشد و دارای ترکیبی به شکل α → AB باشد ، سپس (FIRST (B در F L در (FOLLOW (A به جز ℇ قرار دارد.
- اگر α غیر پایانی باشد و دارای ترکیب α → AB باشد ، که B ℇ است، سپس (FOLLOW (A در (FOLLOW (α قرار دارد.
مجموعه پیرو زیر را می توان مشاهده کرد:
{ *FOLLOW (α) = {t | S * αt *
محدودیت های تحلیل گر نحوی
تحلیل گرهای نحوی ورودی های خود را به صورت توکن هایی از تحلیل گرهای واژگانی دریافت می کنند. تحلیل گرهای واژگانی مسئول اعتبارسنجی توکن تهیه شده توسط تحلیل گرهای نحوی هستند. تحلیل گرهای نحوی دارای اشکالات زیر هستند.
- نمی تواند تعیین کند که آیا یک توکن معتبر است یا خیر.
- نمی تواند تعیین کند که آیا یک توکن قبل از استفاده اعلام شده است یا خیر.
- نمی تواند تشخیص دهد که آیا یک توکن قبل از استفاده مقداردهی اولیه شده است یا خیر.
- نمی تواند تعیین کند که آیا عملیاتی که بر روی یک نوع توکن انجام شده معتبر است یا خیر.
این وظایف توسط تحلیل گر معنایی انجام می شود ، که ما در مبحث تحلیل گر معنایی مطالعه خواهیم کرد.
در این بخش مبحث بررسی تحلیلگر نحوی یا Syntax analyser را به پایان می رسانیم.
کلام پایانی
دوستان با آموزش طراحی کامپایلر همراه بودیم و مبحث بررسی تحلیلگر نحوی یا Syntax analyser را در سه بیان نمودیم. در این بخش مباحثی چون بازگشتی چپ (Left recursion) و حذف بازگشتی چپ ، فاكتورگيري از چپ (factoring Left) ، مجموعه آغازين و تابع Follow ، محدودیت های تحلیل گر نحوی و الگوریتم محاسبه مجموعه آغازين (First Set) را بررسی نمودیم. در جلسه ی آینده با مبحث انواع تجزیه در خدمتتون خواهیم بود.
فروشگاه
فیلم های آموزشی
کتاب های آموزشی
مقالات آموزشی
وردپرس
