سلام و وقت بخیر خدمت همراهان وب سایت آموزشی پی وی لرن. با دوره کامل آموزش طراحی کامپایلر در خدمت شما عزیزان خواهیم بود. در این بخش به بررسی تحلیلگر نحوی (Syntax analyser) می پردازیم. با ادامه ی آموزش ها همراه باشید. با ما همراه باشید.
یک درخت تجزیه یک تصویر گرافیکی از یک اشتقاق است. به راحتی می توان دریافت که رشته ها از نماد آغازین چگونه به دست می آیند. نماد آغازین به ریشه درخت تجزیه تبدیل می شود. حال این موضوع را با نمونه ای مورد بررسی قرار دهیم.
اشتقاق چپ ترین a + b * c را در نظر می گیریم.
اشتقاق چپ ترین آن به صورت زیر است:
1 2 3 4 5 | E → E * E E → E + E * E E → id + E * E E → id + id * E E → id + id * id |
مرحله ۱:
E → E * E |
مرحله ۲:
E → E + E * E |
مرحله ۳:
E → id + E * E |
مرحله ۴:
E → id + id * E |
مرحله ۵:
E → id + id * id |
در یک درخت تجزیه:
یک درخت تجزیه شرکت پذیری و تقدم عملگر ها را به تصویر می کشد. در ابتدا عمیق ترین زیر درخت پیمایش می شود ، بنابراین عملگر موجود در آن زیر درخت نسبت به عملگری که در گره های والد است تقدم می یابد.
گفته می شود گرامر G، اگر بیش از یک درخت تجزیه (چپ ترین یا راست ترین انشقاق) برای حداقل یک رشته داشته باشد مبهم است.
مثال
1 2 3 | E → E + E E → E – E E → id |
گرامر بالا برای رشته id + id – id ، دو درخت تجزیه ایجاد می کند:
گفته می شود این زبان توسط گرامری مبهم تولید شده که دارای ابهامی ذاتی است. ابهام در گرامر برای ساخت کامپایلر خوب نیست. هیچ روشی نمی تواند ابهام را به طور خودکار تشخیص دهد و از بین ببرد ، اما می توان آن را با نوشتن مجدد کل گرامر به صورت بدون ابهام ، یا با تنظیم و پیروی از محدودیت های تقدم و شرکت پذیری (associativity) برطرف نمود.
اگر یک عملوند از دو طرف دارای عملگر باشد ، این که آن عملوند از عملگر کدام سمت خود استفاده کند بستگی به شرکت پذیری عملگرها دارد. اگر این عملیات به صورت شرکت پذیری از چپ باشد ، عملوند توسط عملگر سمت چپ عمل می کند و یا اگر عملیات به صورت شرکت پذیری از راست باشد ، عملگر سمت راست آن عملوند را انتخاب می کند.
مثال
عملیاتی مانند جمع کردن، ضرب ، تفریق و تقسیم به صورت شرکت پذیر از چپ هستند. اگر این عبارت شامل موارد زیر باشد:
1 | id op id op id |
که به صورت زیر ارزیابی خواهد شد:
1 | (id op id) op id |
به عنوان مثال ، id + id) + id)
عملیاتی مانند به توان شرکت پذیر از راست هستند ، یعنی ترتیب ارزیابی در همان عبارت به صورت زیر خواهد بود:
1 | id op (id op id) |
به عنوان مثال ، (id ^ (id ^ id
اگر دو عملگر مختلف با یک عملوند مشترک وجود داشته باشد ، تقدم عملگر ها تصمیم می گیرد که کدام یک از این عملوند را بگیرد. یعنی ۲ + ۳ * ۴ می تواند دارای دو درخت مختلف تجزیه باشد که یکی مربوط به (۲ + ۳) * ۴ و دیگری مربوط به ۲+ (۳ * ۴) است. با تعیین اولویت در بین اپراتورها ، می توان این مشکل را به راحتی برطرف کرد. مانند مثال قبلی ، از نظر ریاضی * (ضرب) بر + (جمع) اولویت دارد ، بنابراین عبارت ۲ + ۳ * ۴ همیشه این گونه تعبیر خواهد شد:
1 | 2 + (3 * 4) |
این روش ها احتمال ابهام در یک زبان یا دستور زبان آن را کاهش می دهد.
در این بخش از آموزش طراحی کامپایلر و مبحث بررسی تحلیل گر نحوی (Syntax analyser) به صحبت در مورد درخت تجزیه (Parse) ، ابهام یا Ambiguity و موراد دیگر پرداختیم. در جلسه ی آینده نیز مبحث بررسی تحلیل گر نحوی (Syntax analyser) را با موضوعات جدیدی ادامه خواهیم داد. با ما همراه باشید.