فرم بکوس-نائور

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در علوم رایانه فرم بکوس-نائور (فرم نرمال بکوس یا فرم بکوس-نائور) یکی از دو فنون قواعد است[۱] که برای گرامر مستقل از متن ارایه شده است. اغلب از آن به عنوان دستور زبان رسمی در علوم رایانه مورد استفاده قرار می‌گیرد؛ از این میان می‌توان به زبان‌های برنامه‌نویسی، قالب اسناد، دستورزبان دستورات و پروتکل‌های ارتباطی نام برد. روی دیگر برای نوشتن در گرامرهای مستقل از متن گرامر ون وینگاردن است. این دو گرامر را زمانی به کار می‌برند که توصیفات دقیق از زبان لازم است. برای نمونه در زبان رسمیِ تعیین نیامندی‌ها، در راهنماها و در کتب آموزش زبان‌های برنامه‌سازی. بسیاری از توسعه‌های بر روی فرم اصلی صورت گرفته است. برخی از آن‌ها به صورت کامل تعریف شده‌اند : فرم گسترش یافته بکوس-نائور و فرم تکمیل‌شده بکوس-نائور .

تاریخچه[ویرایش]

در ماه مهٔ سال ۱۹۵۸ یک کمیتهٔ بین‌الملی متشکل از دانشمندانی از بخش‌های تجاری و دانشگاهی در زوریخ تشکیل شد. هدف آنها، توسعهٔ زبان فرتن و دستیابی به یک زبان واحد و استاندارد برای برنامه سازی بود. این زبان بعدها به نام الگول معروف شد. الگول دو مزیت عمده نسبت به فورترن داشت. اول اینکه در زبان جدید مفهوم متغیر‌های محلی به وجود آمده بود و در حالی که در فورترن تنها نام‌گذاری سراسری مجاز بود. امکان استفاده از متغیرهای محلی علاوه بر سهولت بیشتر، امکان به‌کارگیری شکلی از برنامه‌سازی را که بعد‌ها توسط جان مک‌کارتی معرفی شد و به بازگشت‌پذیری معروف گردید نیز فراهم ساخت. جان بکوس(سرپرست طراحی زبان فورترن) ایده‌های به کار رفته در الگول را پسندید ولی از نحوهٔ بیان آن خوشش نیامد. او می‌گوید:

« آنها همه چیز را به زبان انگلیسی توضیح داده بودند و به‌نظرم رسید که باید کاری کرد تا بتوان به صورت دقیق‌تری به بیان اینگونه مفاهیم پرداخت.»

برای حل این مشکل، بَکوس گرامر مستقل از متن را که به تازگی توسط نوام چامسکی زبانشناس معروف اختراع شده بود، به‌کار گرفت. کار چامسکی هم به نوبهٰ خود ریشه در کار‌های نظری امیل لئون پست دربارهٔ بازنویسی گرامر‌های داشت. بَکوس بدلیل مشغلهٔ زیاد در ژوئن سال ۱۹۵۹ نتوانست مقاله‌اش را به کنفرانس یونسکو که در پیرامون زبان الگول برگزار می‌شد بفرستد، اما دست‌نوشته‌های او بین برخی از شرکت کنندگان توزیع شد. پیتر نائور ریاضیدان دانمارکی که در آن کنفرانس حضور داشت، مقالهٔ بَکوس را خواند و علائم بکار رفته توسط بَکوس را اصلاح کرد و از آنها برای تشریح زبان الگول استفاده نمود. به همین دلیل این فرم به نام هر دو آنها یعنی جان بَکوس و پیتر نائور نام‌گذاری شد.

معرفی[ویرایش]

مشخصات فرم ف.ب.ن ، به صورت مجموعه‌ایی از قوانین مشتق‌شده است و به صورت زیر نوشته می‌شود

 <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>.
  • هنگامی که از گروهی از موارد استفاده می‌شود، آن‌ها را در پرانتز قرار می‌دهیم

نرم‌‌افزارهایی که از فرم بکوس-نائور استفاده می‌کنند[ویرایش]

پانویس[ویرایش]

  • ^  Backus Normal Form
  • ^  Extended Backus–Naur Form
  • ^  Augmented Backus–Naur Form
  • ^  Metalinguistic Formulas
  • ^  Generative Grammar
  • ^  Terminal

منابع[ویرایش]

  1. Grune, Dick (1999). Parsing Techniques: A Practical Guide. US: Springer. 
  2. "BNFC", Language technology, SE: Chalmers .
  3. "Online demo", RPatk .
  4. "Tools", Act world, archived from the original on 2006-01-02 .
  5. "BNF parser²", Source forge (project) .