فرم باکوس نائور
در علوم رایانه فرم باکوس نائور یا فرم بکوس-نائور ∗ (فرم نرمال باکوس یا فرم نرمال باکوس-نائور) یکی از روش‌های بیان قواعد است[۱] که برای گرامر مستقل از متن ارائه شده‌است. اغلب از آن به عنوان دستور زبان رسمی در علوم رایانه مورد استفاده قرار می‌گیرد؛ از این میان می‌توان به زبان‌های برنامه‌نویسی، قالب اسناد، دستورزبان دستورها و پروتکل‌های ارتباطی نام برد. روی دیگر برای نوشتن در گرامرهای مستقل از متن گرامر ون وینگاردن است. این دو گرامر را زمانی به کار می‌برند که توصیفات دقیق از زبان لازم است. برای نمونه در زبان رسمیِ تعیین نیامندی‌ها، در راهنماها و در کتب آموزش زبان‌های برنامه‌سازی. بسیاری از توسعه‌ها بر روی فرم اصلی صورت گرفته‌است. برخی از آنها به صورت کامل تعریف شده‌اند: فرم گسترش یافته بکوس-نائور ∗ و فرم تکمیل‌شده بکوس-نائور ∗.
تاریخچه
[ویرایش]در ماه مهٔ سال ۱۹۵۸ یک کمیتهٔ بین‌الملی متشکل از دانشمندانی از بخش‌های تجاری و دانشگاهی در زوریخ تشکیل شد. هدف آنها، توسعهٔ زبان فرتن و دستیابی به یک زبان واحد و استاندارد برای برنامه سازی بود. این زبان بعدها به نام الگول معروف شد. الگول دو مزیت عمده نسبت به فورترن داشت. اول اینکه در زبان جدید مفهوم متغیرهای محلی به وجود آمده بود و در حالی که در فورترن تنها نام‌گذاری سراسری مجاز بود. امکان استفاده از متغیرهای محلی علاوه بر سهولت بیشتر، امکان به‌کارگیری شکلی از برنامه‌سازی را که بعدها توسط جان مک‌کارتی معرفی شد و به بازگشت‌پذیری معروف گردید نیز فراهم ساخت. جان باکوس (سرپرست طراحی زبان فورترن) ایده‌های به کار رفته در الگول را پسندید ولی از نحوهٔ بیان آن خوشش نیامد. او می‌گوید:
«آنها همه چیز را به زبان انگلیسی توضیح داده بودند و به‌نظرم رسید که باید کاری کرد تا بتوان به صورت دقیق‌تری به بیان اینگونه مفاهیم پرداخت.»
برای حل این مشکل، باکوس گرامر مستقل از متن را که به تازگی توسط نوام چامسکی زبانشناس معروف اختراع شده بود، به‌کار گرفت. کار چامسکی هم به نوبهٰ خود ریشه در کارهای نظری امیل لئون پست دربارهٔ بازنویسی گرامرهای داشت. باکوس به دلیل مشغلهٔ زیاد در ژوئن سال ۱۹۵۹ نتوانست مقاله‌اش را به کنفرانس یونسکو که در پیرامون زبان الگول برگزار می‌شد بفرستد، اما دست‌نوشته‌های او بین برخی از شرکت کنندگان توزیع شد. پیتر نائور ریاضیدان دانمارکی که در آن کنفرانس حضور داشت، مقالهٔ باکوس را خواند و علائم بکار رفته توسط باکوس را اصلاح کرد و از آنها برای تشریح زبان الگول استفاده نمود. به همین دلیل این فرم به نام هر دو آنها یعنی جان باکوس و پیتر نائور نام‌گذاری شد.
معرفی
[ویرایش]مشخصات فرم ف.ب. ن ∗، به صورت مجموعه‌ایی از قوانین مشتق‌شده‌است و به صورت زیر نوشته می‌شود
<symbol> ::= __expression__
که در آن <symbol> ∗ نمادی غیرپایانه‌ایی ∗ است و عبارتی است که شامل حداقل یک یا بیشتر از نمادهاست. در بخش بعدی که با علامت خط عمودی ،|، جدا شد، می‌توان دنباله‌های دیگری ذکر شود. نماد خطِ عمودی، بیانگر توانایی انتخاب است. انتخابی که از بین جایگزین‌هایِ نمادهایِ سمت چپ خط است. نماد پایانه‌ایی ∗نمی‌توانند در سمت چپ قرار گیرند. به عبارت صریح‌تر، آنچه که در سمت چپ قرار می‌گیرد نمادی غیرِپایانه‌ایی ∗ است.
نمادِ '=::' بیانگر آن است که نمادِ سمت چپ باید با نمادِ انتخاب‌شده از سمت راست، جایگزین گردد.
اعداد به صورت :
<Non-Zero Digit> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
بیان می‌شوند؛ که بیانگر عدد ۱ یا ۲ یا ۳ یا سایر اعداد غیرِ صفر است. در صورتی که نیاز به ایجاد دنباله‌ایی از اعداد باشد می‌توان با فرم توضح داده شده آن را ایجاد نمود. به صورت:
<Digit> ::= 0 | <Non-Zero Digit>
<Two-Digit Number> ::= <Non-Zero Digit> <Digit>
<Ten To Nineteen> ::= 1 <Digit>
<FortyTwo> ::= 42
یک رقم (Digit)، می‌تواند صفر(۰) یا هر عددِ غیرِصفری (Non-Zero Digit) باشد. یک عددِ دورقمی، می‌تواند عددی باشد که با یک رقمِ غیرِ صفر آغاز شده و در ادامه هر رقمی، حتی صفر بیاید؛ و نیز یک عدد بین ۱۰ تا ۱۹ به صورت دنباله‌ایی از عدد یک به همراه یک عدد است، صفر یا غیرِ صفر.
تکرار در «ف.ب. ن» لازم است که از طرق رابطه بازگشتی امکان‌پذیر است. یک قانون مشتق‌شده از قوانین بالا، برای بیان یک رشته از اعداد به صورتِ:
<DigitString> ::= <Digit> | <Digit> <DigitString>
خواهد بود. یعنی یک دنبالهٔ عدد به صورتِ عدد (که ممکن است صفر یا غیرِ صفر باشد) یا اینکه یک عدد در ابتدایِ یک دنبالهٔ عددی بیاید. این دنباله اعدادی مانند ۱، ۹، ۱۰۰، ۱۹۲۳، ۰۰۱۲، .... را می‌سازد. از آنجا که اعداد مثبت با صفر آغاز نمی‌شوند، به قانونِ بهتری نیاز است.
قانونِ زیر به شکل درستی اعداد مثبت را ایجاد می‌نماید
<Positive Number> ::= <Non-Zero Digit> | <Non-Zero Digit> <DigitString>
ف.ب. ن دز زبان‌های برنامه‌سازی
[ویرایش]قواعدِ زبان‌هایی مانند الگول، پاسکال، جاوا در فرم بکوس‌نائور ارائه شده‌اند. کلمات کلیدی مانند IF و Switch به عنوان پایانه تعریف شده‌اند. کامپایلر در تحلیل لغوی اول، این کلمات کلیدی را شناسایی می‌نماید و به عنوان نمادهایِ خاص، نشان‌گذاری می‌نماید. همچنین توضحیاتِ موجود در کد نیز شناسایی و خذف می‌شوند. اعداد اعشاری، متغیرهای، شناسه‌های و رشته‌های از عناصرِ دیگری هستند نیز در متن شناسایی می‌شوند.
این فرم، این امکان را فراهم می‌آورد تا عبارتِ زیر در زبان برنامه‌سازی پاسکال قابل بیان باشد.
<Program> :: = 'PROGRAM' <Identifier> 'BEGIN' <Full Sequence> 'END'.
<Identifier> :: = <letter> <Restbezeichner>
<Empty> :: = | <Letter or Digit> <Empty>
<Letter or Digit> :: = <letter> | <digit>
<letter> :: = A | B | C | D | ... | Z | a | b | ... | z *)
<digit> :: = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<Full Sequence> :: = ...
...
انواع
[ویرایش]انواع مختقلی برای ف.ب. ن ارائه شده‌اند. هریک به دلیل عدم وجود سادگی و نیز عدم موجز بودن ارائه شده‌اند. برخی نیز به دلیل تطابق با برنامه خاصی مطرح شده‌اند. یک ویژگی مشتریک بین انواع مختلف، استفاده از نمادهای عبارات باقاعده مانند * یا +است. فرم بکوس-نائور توسعه‌یافته یکی از رایج‌ترینِ این انواع است. در واقع مثال بالا به‌طور دقیق و خالص بکوس-نائوری نیست که برای زبان الگول ۶۰ طراحی شده. استفاده از براکت «[ ]» چند سال بعد از ارائه نسخه اصلی و در پی‌ال/آی متلق به آی‌بی‌ام معرفی شده ولی امروزه از آن در ب.ن. ف استفاده می‌شود. «فرم تکمیل‌شده بکوس-نائور» و آربی‌ان‌اف سایر اضافاتی است که در گزارش‌هایی ارائه شده توسط نیروی وظیفه مهندسی اینترنت مورد استفاده قرار می‌گیرد.
گرامر پارس عبارات بر روی ب.ن. ف ساخته شده و از روش‌های عبارات باقاعده پیروی می‌کند تا جایگزینی برای کلاسِ گرامر رسمی باشد؛ که خود به جای آنکه گرامرزا ∗ باشد یک گرامر تحلیلی است. بسیاری از مشخصات ب.ن. ف امروزه در نوشتارهای انسانی که به صورت غیرِرسمی است قابل مشاده است. از این میان می‌توان به برخی اشاره نمود:
- موارد قابل انتخاب در یک براکت ذکر می‌شوند : [<item-x>].
- مواردی که ۰ یا بیشتر مورد استفاده قرار می‌گیرند بین دو براکت ذکر شده و به نشانِ ستاره ('*') مزین می‌گردد. برای مثال "<word> ::= <letter> {<letter>}" or "<word> ::= <letter> <letter>*", respectively.
- نشانِ '+' نشانگر تکرارِ ۱ یا بیش از آن برای نشانی است که قبل از آن ذکر می‌گردد.
- عبارات پایانی ∗ ممکن از به جای کج نویسی به صورت ضخیم نوشته شوند و عبارت غیرِپایانی به جای براکت به صورت معمولی ذکر گردند.
- انتخاب جایگزین در تولید عبارات، نشانِ '|' است برای مثال: <alternative-A> | <alternative-B>.
- هنگامی که از گروهی از موارد استفاده می‌شود، آنها را در پرانتز قرار می‌دهیم
نرم‌افزارهایی که از فرم بکوس-نائور استفاده می‌کنند
[ویرایش]- ANTLR، یک تولیدگر پارس‌کننده که به زبان برنامه‌نویسی جاوا نوشته شده‌است.
- تبدیل‌گر بی‌ان‌اف[۲])
- کوکو/آر، تولیدگر مترجمِ برنامه که عبارتی با ویژگی فرم بکوس-نائور توسعه‌یافته را قبول می‌کند
- ابزار مهندسی مجدد دی‌ام‌اس، برنامه‌ایی که برای تحلیل و تبدیل سیستم است برای زبانِ دلخواه
- گلد، پارس‌گری برای ب.ن. ف
- گنو بایسون، نگارش گنو از yacc
- پارس‌گرِ آرپی‌آ برای ف.بک. ن[۳] Online (PHP) demo parsing: JavaScript, XML
- XACT X4MR System,[۴] a rule-based expert system for programming language translation
- یک تولیدگرِ پارس‌گر
- پارس‌گر ف.ب. ن ۲.[۵] a universal syntax verification utility
- سازنده کامپایلر sableCC
پانویس
[ویرایش]- ^ Backus Normal Form
- ^ Extended Backus–Naur Form
- ^ Augmented Backus–Naur Form
- ^ Metalinguistic Formulas
- ^ Generative Grammar
- ^ Terminal
منابع
[ویرایش]- ↑ Grune, Dick (1999). Parsing Techniques: A Practical Guide. US: Springer.
- ↑ "BNFC", Language technology, SE: Chalmers.
- ↑ "Online demo", RPatk, archived from the original on 2 November 2012, retrieved 2 January 2013.
- ↑ "Tools", Act world, archived from the original on 29 January 2006, retrieved 2 January 2013.
- ↑ "BNF parser²", Source forge (project).