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

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

تاریخچه

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

معرفی

مشخصات فرم ف.ب. ن ، به صورت مجموعه‌ایی از قوانین مشتق‌شده‌است و به صورت زیر نوشته می‌شود
 <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> :: = ...
 ...