طراحی کامپایلر - تجزیه و تحلیل نحو

تجزیه و تحلیل نحو یا تجزیه و تحلیل مرحله دوم کامپایلر است. در این فصل ، مفاهیم اساسی مورد استفاده در ساخت یک تجزیه کننده را می آموزیم.

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

از طرف دیگر ، CFG یک سوپراست از دستور زبان منظم است ، همانطور که در زیر نشان داده شده است:

این بدان معنی است که هر دستور زبان معمولی نیز بدون زمینه است ، اما برخی از مشکلات وجود دارد که فراتر از محدوده دستور زبان منظم است. CFG ابزاری مفید در توصیف نحو زبانهای برنامه نویسی است.

دستور زبان بدون متن

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

یک دستور زبان بدون زمینه چهار مؤلفه دارد:

• مجموعه ای از غیر ترمینال ها (V). غیر پایانه ها متغیرهای نحوی هستند که مجموعه ای از رشته ها را نشان می دهند. غیر ترمینال مجموعه هایی از رشته ها را تعریف می کند که به تعریف زبان تولید شده توسط دستور زبان کمک می کند.
• مجموعه ای از نشانه ها ، معروف به نمادهای ترمینال (σ). پایانه ها نمادهای اساسی هستند که رشته ها از آن تشکیل می شوند.
• مجموعه ای از تولیدات (P). تولیدات یک دستور زبان شیوه ترکیب پایانه ها و غیر ترمینال ها را برای تشکیل رشته ها مشخص می کند. هر تولید شامل یک ترمینال به نام سمت چپ تولید ، یک فلش و دنباله ای از نشانه ها و/یا پایانه ها است که سمت راست تولید نامیده می شود.
• یکی از غیر ترمینال ها به عنوان نماد (های) شروع تعیین شده است. از جایی که تولید شروع می شود.

رشته ها از نماد شروع با جایگزینی مکرر یک غیر ترمینال (در ابتدا نماد شروع) توسط سمت راست یک تولید ، برای آن غیر ترمینال بدست می آیند.

مثال

ما مشکل زبان Palindrome را در نظر می گیریم ، که با استفاده از بیان منظم قابل توصیف نیست. یعنی L =یک زبان معمولی نیست. اما می توان آن را با استفاده از CFG توصیف کرد ، همانطور که در زیر نشان داده شده است:

g = (v ، σ ، p ، s)

V = Σ = <0, 1>P = S =

این گرامر زبان پالیندروم را توصیف می کند ، مانند: 1001 ، 11100111 ، 00100 ، 1010101 ، 11111 و غیره.

تجزیه و تحلیل نحو

آنالایزر یا تجزیه کننده نحو ورودی را از یک آنالایزر واژگانی به شکل جریان های توکن می گیرد. تجزیه کننده کد منبع (جریان توکن) را در برابر قوانین تولید تجزیه و تحلیل می کند تا هرگونه خطایی در کد را تشخیص دهد. خروجی این مرحله یک درخت پارس است.

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

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

استخراج

مشتق اساساً دنباله ای از قوانین تولید است ، به منظور به دست آوردن رشته ورودی. در حین تجزیه ، ما برای برخی از فرم های ورودی دو تصمیم گیری می گیریم:

• تصمیم گیری در مورد غیر ترمینال که قرار است جایگزین شود.
• تصمیم گیری در مورد قانون تولید ، که توسط آن ، غیر ترمینال جایگزین می شود.

برای تصمیم گیری در مورد کدام غیر ترمینال با قانون تولید ، می توانیم دو گزینه داشته باشیم.

بیشترین اشتقاق

اگر فرم حتمی ورودی از چپ به راست اسکن شود و جایگزین آن شود ، آن را به عنوان چپ ترین مشتق می نامند. فرم حساس به دست آمده از مشتق سمت چپ ، فرم سمت چپ نامیده می شود.

بالاترین اشتقاق

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

E → E + E E → E * E E → ID

رشته ورودی: شناسه + شناسه * شناسه

مشتق سمت چپ:

E → E * E E → E + E * E * E → ID + E * E E → ID + ID + ID * E E → ID + ID * ID

توجه کنید که در سمت چپ و انتهای سمت چپ همیشه ابتدا پردازش می شود.

بالاترین مشتق این است:

E → E + E E → E + E * E * E → E + E * ID E → E + E + ID * ID E → ID + ID * ID

درخت تجزیه

یک درخت پارس یک تصویر گرافیکی از مشتق است. راحت است که ببینید چگونه رشته ها از نماد شروع به دست می آیند. نماد شروع مشتق ریشه درخت تجزیه می شود. بگذارید این موضوع را با نمونه ای از آخرین موضوع ببینیم.

ما به سمت چپ ترین مشتق A + B * C می گیریم

مشتق سمت چپ:

E → E * E E → E + E * E * E → ID + E * E E → ID + ID + ID * E E → ID + ID * ID

E → E * e

E → E + E * E

E → ID + E * E

E → شناسه + شناسه * E

E → شناسه + شناسه * شناسه

در یک درخت پارس:

• تمام گره های برگ پایانه هستند.
• همه گره های داخلی غیر ترمینال هستند.
• Traversal In-سفارش رشته ورودی اصلی را می دهد.

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

گنگ

گفته می شود که اگر بیش از یک درخت پارس (مشتق چپ یا راست) برای حداقل یک رشته داشته باشد ، گرامر G مبهم است.

E → E + E E → E - E E → ID

برای شناسه String + ID - ID ، دستور زبان فوق دو درخت پارس تولید می کند:

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

وابسته بودن

اگر یک اپراتور از هر دو طرف اپراتورهایی داشته باشد ، طرفی که اپراتور این عمل را با همکار آن اپراتورها انجام می دهد ، تصمیم می گیرد. اگر این عملیات به چپ و چپ باشد ، عملگر توسط اپراتور چپ انجام می شود یا اگر عملیات مناسب باشد ، اپراتور سمت راست عمل را انجام می دهد.

عملیاتی مانند افزودن ، ضرب ، تفریق و تقسیم از انجمنی باقی مانده است. اگر عبارت حاوی:

شناسه id op id id

ارزیابی می شود:

(شناسه شناسه) شناسه op

به عنوان مثال ، (شناسه + شناسه) + شناسه

عملیاتی مانند نمایشگاه ، درست انجمنی هستند ، یعنی ترتیب ارزیابی در همان عبارت عبارتند از:

ID OP (شناسه id op)

به عنوان مثال ، id ^ (id ^ id)

تقدم

اگر دو اپراتور مختلف یک عمل مشترک مشترک داشته باشند ، تقدم اپراتورها تصمیم می گیرد که این عمل را انجام می دهد. یعنی 2+3*4 می تواند دو درخت پارس متفاوت داشته باشد ، یکی مربوط به (2+3)*4 و دیگری مربوط به 2+ (3*4). با تنظیم تقدم در بین اپراتورها ، این مشکل به راحتی قابل رفع است. همانطور که در مثال قبلی ، از نظر ریاضی * (ضرب) بر + (علاوه بر این) تقدم دارد ، بنابراین عبارت 2 + 3 * 4 همیشه به این صورت تعبیر می شود:

2 + (3 * 4)

این روشها شانس ابهام در یک زبان یا دستور زبان آن را کاهش می دهد.

بازگشت چپ

گرامر اگر هرگونه غیر ترمینال "A" باشد ، که مشتق آن شامل "A" به عنوان نماد چپ است ، چپ می شود. گرامر بازخوانی چپ یک وضعیت مشکل ساز برای تجزیه کننده های از بالا به پایین در نظر گرفته می شود. تجزیه کنندگان از بالا به پایین از نماد شروع شروع به تجزیه و تحلیل می کنند ، که به خودی خود غیر ترمینال است. بنابراین ، هنگامی که تجزیه کننده در مشتق خود با همان ترمینال روبرو می شود ، قضاوت در مورد زمان متوقف کردن تجزیه غیر ترمینال چپ و آن را به یک حلقه نامحدود می رساند.

(1) A => Aα | β (2) S => Aα | β A =>SD

(1) نمونه ای از بازگشت فوری چپ است ، جایی که A هر نماد غیر ترمینال است و α نمایانگر رشته ای از غیر ترمینال ها است.

(2) نمونه ای از بازگشت غیر مستقیم چپ است.

یک تجزیه کننده از بالا به پایین ابتدا A را تجزیه می کند ، که به نوبه خود رشته ای از خود را تشکیل می دهد و تجزیه کننده ممکن است برای همیشه به یک حلقه برود.

حذف بازگشت چپ

یکی از راه های حذف بازگشت چپ استفاده از تکنیک زیر است:

A =>Aα |عاقبت

به تولیدات زیر تبدیل می شود

A => βA' A'=>αa '|ε

این بر روی رشته های به دست آمده از دستور زبان تأثیر نمی گذارد ، اما بازگشت فوری چپ را از بین می برد.

روش دوم استفاده از الگوریتم زیر است که باید تمام عقب نشینی های چپ مستقیم و غیرمستقیم را از بین ببرد.

شروع به ترتیب غیر ترمینال به ترتیب مانند A1 ، A2 ، A3 ،… ، aبرای هر من از 1 تا ni⟹aj پرسش و پاسخ بورس...

 


ما را در سایت پرسش و پاسخ بورس  دنبال می کنید

برچسب :   
نویسنده : ماندانا اصلانی  
 بازدید : <-PostHit-> 
  
 تاريخ : يکشنبه
 1 مرداد
 1402 ساعت: 19:30