رد کردن این محتوا

ساخت زبان برنامه نویسی ریاضی : بخش Parser

در مقاله ی ساخت زبان برنامه نویسی ریاضی : بخش Lexer توضیح دادیم چگونه برای زبان برنامه نویسی خود یک Lexer طراحی کنیم.
در این مقاله قصد داریم Parser این زبان طراحی کنیم برای این کار از Bison استفاده می کنیم.

انواع Parser

در مهندسی نرم افزار الگوریتم های مختلفی برای شناسایی گرامر زبان‌ها وجود دارد که به این الگوریتم‌ها Parser گفته می شود.
Parser ها به روش‌های مختلفی ساخته می‌شوند که در دروس مقاطع مختلف دانشگاهی در دسترس هستند. چند نوع از معروفترین های آن‌ها LL(1) , LR(1) , LALR و … هستند.

در نرم افزار Bison از الگوریتم SLR استفاده می‌شود که به صورت خطی گرامر را بررسی می کند و سرعت بالایی دارد. در این الگوریتم و در تمام الگوریتم‌های LR امکان رخداد دو خطا وجود دارد، خطای Shift/Reduce یا Reduce/Reduce که به سادگی قابل رفع هستند. مطالعه ی آن‌ها را به خواننده می سپارم.

ساخت Parser

به صورت کلی Parser وظیفه ی شناسایی گرامر زبان را دارد و در واقع جملات زبان را شناسایی می کند و در اختیار سازنده ی درخت Parse قرار می دهد.

برای ساخت Parser ابتدا باید ساختارها و گرامرهای زبان را به صورت زبان مستقل از متن بنویسیم و سپس در قالب نرم افزار Bison درآوریم تا نرم افزار Bison کد Parser متناسب با ساختار زبان را برای ما تولید کند.

گرامر زبان ریاضی

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

به صورت کلی ساختار‌های ریاضی در زیر مشخص شده اند.

یکی از مهمترین بخش های ساختارهای بالا اولویت عملگرهاست. به عنوان مثال قبل از هر کاری محتوای پرانتز محاسبه می‌شود و یا عملیات ضرب بر جمع اولویت دارد. در بعضی موارد عملیات‌های ضرب و تقسیم می توانند نسبت به هم اولویت داشته باشند که در این زبان اولویت آنها را برابر در نظر می‌گیریم.

در مقاله‌ی قبل کلمات زبان را توسط Lexer شناسایی کردیم، حال بر اساس آن‌ها گرامر این زبان را می نویسیم و سپس توضیحات لازم را ارائه می کنم.

قبل از هر چیز علامت‌های استفاده شده در این گرامر را توضیح دهیم.

  • علامت : :  این علامت به معنای تعریف متغییر یا NonTerminal است و حروف یا کلماتی که قبل از آن نوشته می شوند nonTerminal هستند.
  • علامت | : این علامت به معنای “یا” است. برای تولید یک جمله هر متغییر می تواند به مجموعه‌ ای از متغیر و کلمه تبدیل شود، که برای نشان دادن جملات مختلف به ازای یک متغییر از | استفاده می کنیم.
  • متغییر S : متغییر S شروع گرامر است و همه ی جملات از S شروع می شوند.
  • فضای خالی : در بعضی حالات بعد از علامت | هیچ کاراکتری نوشته نمی‌شود و به معنای خالی است. یعنی متغییر مربوطه می‌تواند به فضای خالی تبدیل شود.

مثلا فرض کنید قصد داریم جمله ی 1 + 2 را توسط این زبان شناسایی کنیم مراحل کار به شرح زیر است.

S => A S  => E + E S => NUMBER + E S => 1 + E S =>  1 + NUMBER S => 1 + 2  S => 1 + 2

ابتدا از جمله ی اول S به A S تبدیل می شود، سپس A از جمله ی دوم به E + E و همینطور ادامه پیدا می کند تا 1 + 2 S و در نهایت S از جمله ی اول به فضای خالی تبدیل شود و جمله شناسایی شود.

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

این مقاله ادامه دارد !

منتشر شده آموزش

یک نظر

  1. امیرحسین امیرحسین

    سلام ممنونم از مطالب عالیه سایتتون میشه ادامه این رو هم بزارید ممنون .

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *