バッカス・ナウア形式

コンピュータサイエンスにおいて、バッカス・ナウア記法（BNF ; / ˌ b æ k ə s ˈ n aʊər / ;バッカス正規形）は、プログラミング言語やその他の形式言語の構文を記述するために使用される表記法です。ジョン・バッカスとピーター・ナウアによって開発されました。BNFは、文脈自由文法のメタ構文表記法として説明できます。バッカス・ナウア記法は、公式の言語仕様、マニュアル、プログラミング言語理論の教科書など、言語の正確な記述が必要なところならどこでも適用されます。BNFは、ドキュメント形式、命令セット、通信プロトコルの記述に使用できます。

時間の経過とともに、元のバッカスナウア記法の多くの拡張と変形が作成されました。拡張バッカスナウア記法(EBNF) や拡張バッカスナウア記法(ABNF) など、正確に定義されているものもあります。

BNFは、異なる記号を組み合わせて構文的に正しいシーケンスを生成する方法を記述します。BNFは、非終端記号のセット、終端記号のセット、および非終端記号をシンボルのシーケンスに置き換える規則の3つのコンポーネントで構成されます。^[1]これらのいわゆる「導出規則」は次のように記述されます 。

 <シンボル>  ::= __式__

どこ：

• <symbol>^[2]は常に<>で囲まれた非終端変数です。
• ::=左側の記号を右側の式に置き換える必要があることを意味します。
• __expression__終端記号または非終端記号の 1 つ以上のシーケンスで構成されます。各シーケンスは選択を示す縦棒"|"で区切られ、全体が左側の記号の可能な代替となります。

構文的に正しいシーケンスはすべて、次の方法で生成する必要があります。

• 開始シンボルが 1 つだけ含まれるようにシーケンスを初期化します。
• この開始記号とそれに続く記号のシーケンスに導出規則を適用します。^[1]

この方法でルールを適用すると、シーケンスがどんどん長くなる可能性があるため、多くの BNF 定義では、仕様に特別な「削除」記号を含めることが許可されています。一部の記号をこの「削除」記号に置き換えることを許可するルールを指定できます。これは、シーケンスから記号を削除しても構文的に正しいシーケンスを維持できることを示します。^[1]

例として、米国の郵便番号を表す次の BNF を考えてみましょう。

 <郵便番号>  ::=  <名前部分>  <番地>  <郵便番号部分>

      <名前部分>  ::=  <個人情報部分>  <姓>  <オプションサフィックス部分>  < EOL > | <個人情報部分>  <名前部分>

  <個人情報>  ::=  <名> | <イニシャル> "."

 <番地>  ::=  <家番号>  <通り名>  <アパート番号>  < EOL >

       <郵便番号部分>  ::=  <町名> "," <州コード>  <郵便番号>  < EOL >

< opt-suffix-part >  ::= "Sr." | "Jr." | < roman-numeral > | ""
     < opt-apt-num >  ::= "Apt" < apt-num > | ""

これを英語に翻訳すると次のようになります。

• 郵便番号は、名前部分、番地部分、郵便番号部分の順で構成されます。
• 名前部分は、個人部分の後に姓、オプションの接尾辞（Jr. Sr.、または家系番号）と行末が続くか、個人部分の後に名前部分が続くかのいずれかで構成されます（このルールは、 BNFでの再帰の使用を示しており、複数のファーストネーム、ミドルネーム、イニシャルを使用する人のケースをカバーしています）。^[3]
• 個人情報部分は、名前またはイニシャルとそれに続くドットで構成されます。
• 住所は、家番号、通りの名前、オプションのアパート指定子、行末記号で構成されます。
• 郵便番号部分は、町名、コンマ、州コード、郵便番号、改行コードで構成されます。
• opt-suffix-part は、「Sr.」、「Jr.」などのサフィックス、ローマ数字、または空の文字列 (つまり何もない) で構成されます。
• opt-apt-num は、プレフィックス「Apt」とそれに続くアパート番号、または空の文字列 (つまり何もない) で構成されます。

ここでは多くのこと（名前、アパート番号、郵便番号、ローマ数字の形式など）が指定されていないことに注意してください。必要に応じて、追加の BNF ルールを使用して記述できます。

言語の構造を書き換え規則を使って記述するというアイデアは、少なくとも、紀元前6世紀から4世紀の間に生きた古代インドのサンスクリット文法学者であり、ヒンズー教の尊敬される学者であったパーニニの研究にまで遡ることができます。^{[4] [5]}サンスクリット語の単語構造を記述する彼の表記法は、その力においてバッカスの表記法と同等であり、多くの類似した特性を持っています。

西洋社会では、文法は長い間、科学的研究というよりも教育の科目とみなされており、記述は非公式で、実用的使用を対象としていました。20世紀前半には、レナード・ブルームフィールドやゼリッグ・ハリスなどの言語学者が、句構造を含む言語の記述を形式化する試みを始めました。

一方、形式論理システムとしての文字列書き換え規則は、アクセル・トゥー（1914年）、エミール・ポスト（1920年代～40年代）、アラン・チューリング（1936年） などの数学者によって導入され、研究された。MITで情報理論の学生に言語学を教えていたノーム・チョムスキーは、本質的にトゥーの形式主義を自然言語の構文の記述の基礎として採用することで、言語学と数学を組み合わせました。彼はまた、生成規則（文脈自由文法の規則）と変換規則との明確な区別を導入しました（1956年）。^{[6] [7]}

IBMのプログラミング言語設計者ジョン・バッカスは、 新しいプログラミング言語IAL（今日ではALGOL 58 （1959）として知られている）の構文を記述するために、「メタ言語式」^{[2] [9] [10]}のメタ言語を提案した。彼の表記法はALGOL 60レポートで初めて使用された。

BNFはチョムスキーの文脈自由文法の表記法である。バッカスはチョムスキーの研究に精通していた。^[11]

Backus の提案によると、この式は「クラス」を定義し、その名前は山括弧で囲まれている。たとえば、<ab>。これらの名前はそれぞれ、基本記号のクラスを表す。^[2]

ALGOLのさらなる開発はALGOL 60につながった。委員会の1963年の報告書で、ピーター・ナウアはバッカスの表記法をバッカス正規形と呼んだ。ドナルド・クヌースは、BNFは「従来の意味での正規形ではない」ため、 ^[12] 例えばチョムスキー正規形とは異なり、バッカス・ナウア形と読むべきだと主張した。拡張バッカス正規形は正確ではない可能性があり、またパニニが以前に同様の表記法を独自に開発していたことから、パーニニ・バッカス形という名前もかつて提案されたことがあった。^[13]

BNFはALGOL 60レポートの中でピーター・ナウアーによってメタ言語式として説明されている: ^[14]

角括弧 <> で囲まれた文字列は、値がシンボルのシーケンスであるメタ言語変数を表します。記号 "::=" と "|" (後者は "または" の意味) はメタ言語接続子です。式内の変数または接続子ではない記号は、それ自体を表します。式内の記号または変数の並置は、示されたシーケンスの並置を意味します。

ALGOL 60 レポートの別の例は、BNF メタ言語とチョムスキー文脈自由文法の大きな違いを示しています。メタ言語変数には、その形成を定義するルールは必要ありません。その形成は、自然言語で <> 括弧内に記述するだけで済みます。次の ALGOL 60 レポート セクション 2.3 のコメント仕様は、これがどのように機能するかを例示しています。

プログラムのシンボルにテキストを含める目的で、次の「コメント」規則が適用されます。

ここでの同等性とは、文字列の外側で出現するどの箇所でも、プログラムの動作に影響を与えることなく、左の列に表示されている 3 つの構造のいずれも、右の列の同じ行に表示されているシンボルに置き換えることができることを意味します。

ナウルは、バッカスの記号のうち2つを一般に利用可能な文字に変更しました。この::=記号はもともと でした:≡。この記号はもともと「 」または|「 」（上にバーが付いていた）という単語でした。^{[9] : 14}

BNF は、当時も現在も論理回路設計に使用されていた標準形式の ブール代数方程式に非常によく似ています。Backus は数学者であり、FORTRAN プログラミング言語の設計者でした。ブール代数の研究は、一般的に数学のカリキュラムの一部です。Backus も Naur も、 で囲まれた名前を< >非終端記号とは説明しませんでした。Chomsky の用語は、もともと BNF の説明には使用されませんでした。Naur は後に、ALGOL のコース教材でそれらをクラスとして説明しました。^[2]::= ALGOL 60 レポートでは、それらはメタ言語変数と呼ばれていました。 、、|および で囲まれたクラス名以外のメタシンボルは、< >定義されている言語のシンボルです。メタシンボル::=は、「として定義されている」と解釈されます。 は|代替定義を区切るために使用され、「または」と解釈されます。メタシンボルは、< >クラス名を囲む区切り文字です。 BNFはピーター・ナウアとソール・ローゼンによってALGOLについて話すためのメタ言語として説明されている。^[2]

1947 年、ソール・ローゼンは設立間もないAssociation for Computing Machineryの活動に関わり、最初は言語委員会に参加しました。この委員会は後に IAL グループとなり、最終的には ALGOL につながりました。彼は Communications of the ACM の初代編集長でした。^{[明確化が必要]} BNF は、ALGOL 60 レポートで ALGOL 言語について説明するためのメタ言語として初めて使用されました。これは、1962 年にピーター・ナウアが開発した ALGOL プログラミング コースの教材で説明されている方法です。^[2] IBM、ハネウェル、バロウズ、デジタル イクイップメント コーポレーションによる初期の ALGOL マニュアルは、ALGOL 60 レポートに従って、それをメタ言語として使用しました。ソール・ローゼンは著書^[15]で、BNF を ALGOL について説明するためのメタ言語として説明しています。メタ言語としての BNF の使用例としては、算術式の定義が挙げられます。

<式>  ::=  <項> | <式><加算演算子><項>

選択肢の最初のシンボルは定義されるクラスであり、繰り返しは、ナウルスによって説明されているように、選択肢のシーケンスが前の選択肢から再帰的に始まり、任意の回数繰り返すことができることを指定する機能を持ちます。^[2]たとえば、上記は、任意の数の が続くもの<expr>として定義されます。 <term><addop> <term>

SchorreのMETA IIなどの後期のメタ言語では、BNFの再帰繰り返し構造は、シーケンス演算子と引用符で囲まれた文字列を使用して定義されたターゲット言語シンボルに置き換えられました。<と>括弧は削除されました。数学的なグループ化のための括弧()が追加されました。この<expr>規則はMETA IIで次のように表示されます。

EXPR =  TERM $ ( '+'  TERM . OUT (' ADD ')  |  '-'  TERM . OUT (' SUB '));

これらの変更により、META II とその派生プログラミング言語は、自然言語記述、メタ言語変数、言語構成要素記述を使用する能力を犠牲にして、独自のメタ言語を定義および拡張できるようになりました。多くのスピンオフメタ言語は BNF に触発されました。^[要出典] META II、TREE-META、およびMetacompiler を参照してください。

BNF クラスは言語構造の形成を記述します。形成はパターンまたはパターンを形成するアクションとして定義されます。クラス名 expr は、自然言語では<term>の後にシーケンス が続くものとして記述さ<addop> <term>れます。クラスは抽象概念です。クラスは、その形成とは無関係に説明できます。用語は、その定義とは無関係に、expr で追加または減算されるものとして説明できます。用語が特定のデータ型であることや、特定のデータ型の組み合わせを持つ expr の評価方法、またはデータ型をグループ化して式を並べ替えることや、混合型の評価結果について説明できます。自然言語の補足により、コンパイラ実装と ALGOL プログラムを作成するプログラマが使用する言語クラスのセマンティクスの具体的な詳細が提供されました。自然言語の記述により、構文もさらに補足されました。整数ルールは、構文を記述するために使用される自然言語とメタ言語の良い例です。

<整数>  ::=  <数字> | <整数><数字>

上記では空白について特に規定されていません。規則に定められている限り、数字の間に空白があっても構いません。自然言語では、数字シーケンスの数字の間に空白があってはならないことを説明することで、BNF メタ言語を補完します。英語は、考えられる自然言語の 1 つにすぎません。ALGOL レポートの翻訳は、多くの自然言語で利用可能でした。

BNF の起源は、プログラミング言語開発への影響ほど重要ではありません。^[要出典] ALGOL 60 レポートの公開直後の期間中、BNF は多くのコンパイラ コンパイラシステムの基礎となりました。

Edgar T. Irons が開発した「A Syntax Directed Compiler for ALGOL 60」や Brooker と Morris が開発した「A Compiler Building System」など、いくつかは BNF を直接使用しました。 Schorre Metacompilers など、他のコンパイラは、わずかな変更を加えるだけでプログラミング言語にしました。 は<class name>シンボル識別子になり、囲みを削除し<、>対象言語のシンボルに引用符で囲まれた文字列を使用しました。 算術のようなグループ化により、グループ化が唯一の値であるクラスの使用を削除する簡略化が実現しました。 META II 算術式ルールは、グループ化の使用を示しています。 META II ルール内に配置された出力式は、アセンブリ言語でコードとラベルを出力するために使用されます。 META II のルールは、BNF のクラス定義と同等です。 Unix ユーティリティyaccは、META II に似たコード生成を持つ BNF に基づいています。 yacc は、パーサー ジェネレーターとして最も一般的に使用され、そのルーツは明らかに BNF です。

BNF は現在でも使用されている最も古いコンピュータ関連言語の 1 つです。^{[引用が必要]}

BNF の構文自体は、次のような BNF で表すことができます。

 <構文>          ::=  <ルール> | <ルール>  <構文> 
 <ルール>            ::=  < opt-whitespace > "<" <ルール名> ">" < opt-whitespace > " ::= " < opt-whitespace >  <式>  <行末> 
 < opt-whitespace >  ::= " " < opt-whitespace > | ""
  <式>      ::=  <リスト> | <リスト>  < opt-whitespace > "|" < opt-whitespace >  <式> 
 <行末>        ::=  < opt-whitespace >  < EOL > | <行末 > < 行末> <リスト>  :: = <用語> | <用語> < opt - whitespace > <リスト> <用語> ::= <リテラル> | "<" <ルール名> ">"
  <リテラル> ::= '"' <テキスト 1 > '"' | "'" <テキスト 2 > "'"
  <テキスト 1 > ::= "" | <文字1 > <テキスト1 > <テキスト2 > ::= "" | <文字2 > <テキスト2 > <文字> ::= <文字> | <数字> | <記号> <文字> ::=
               
                                
            
        
          "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "I" | "J" | "K" | "L" | "M" | "N" | "O" | "P" | "Q" | "R" | "S" | "T" | "U" | "V" | "W" | "X" | "Y" | "Z" | "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z"
  <数字>           ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
  <記号>          ::= "|" | " " | "!" | "#" | "$" | "%" | "&" | "(" | ")" | "*" | "+" | "," | "-" | "." | "/" | ":" | ";" | ">" | "=" | "<" | "?" | "@" | "[" | "\" | "]" | "^" | "_" | "`" | "{" | "}" | "~"
  <文字1 >      ::=  <文字> | "'"
  <文字2 >      ::=  <文字> | '"'
  <ルール名>       ::=  <文字> | <ルール名>  <ルール文字> <ルール文字> ::= <文字> | <数字> | "-"

        

"" は空の文字列であることに注意してください。

元の BNF では、ルールに示されているように引用符は使用されませんでした<literal>。これは、ルールを適切に解釈するために 空白は不要であると想定しています。

<EOL>適切な行末指定子（ASCIIでは、オペレーティング システムに応じて復帰、改行、またはその両方）を表します。および は<rule-name>、<text>それぞれ宣言されたルールの名前/ラベルまたはリテラル テキストに置き換えられます。

上記の米国の郵便番号の例では、引用ブロック全体が です<syntax>。各行または連続した行のグループはルールです。たとえば、1 つのルールは で始まります<name-part> ::=。そのルールのその他の部分 (行末を除く) は式で、縦棒 で区切られた 2 つのリストで構成されます|。これらの 2 つのリストは、いくつかの用語 (それぞれ 3 つの用語と 2 つの用語) で構成されます。この特定のルール内の各用語は、ルール名です。

BNF には多くのバリエーションと拡張があり、一般的には単純さと簡潔さのため、または特定のアプリケーションに適応させるために使用されています。多くのバリエーションに共通する特徴の 1 つは、やなどの正規表現繰り返し演算子の使用です。拡張バッカス・ナウア記法(EBNF) は一般的な形式です。 *+

もう 1 つの一般的な拡張は、オプション項目を角括弧で囲むことです。元の ALGOL 60 レポートには存在しませんでしたが (数年後にIBMのPL/I定義で導入されました)、この表記法は現在では広く認識されています。

拡張バッカス・ナウア記法（ABNF）とルーティングバッカス・ナウア記法（RBNF）^[16]は、インターネット技術タスクフォース（IETF）プロトコルを記述するために一般的に使用される拡張です。

解析式文法は、 BNF と正規表現の表記法に基づいて、本質的には生成的ではなく分析的な性質を持つ、形式文法の代替クラスを形成します。

現在オンラインで見られる BNF 仕様の多くは、人間が読めるように設計されており、非形式的です。これらには、多くの場合、次の構文ルールと拡張機能が多数含まれています。

• 角括弧で囲まれたオプション項目: [<item-x>].
• 0 回以上存在する項目は、それぞれまたはのように中括弧で囲まれるか、アスタリスク ( *)が末尾に付けられます。<word> ::= <letter> {<letter>}<word> ::= <letter> <letter>*
• 1 回以上存在する項目には、+のように、加算 (プラス) 記号が末尾に付きます<word> ::= <letter>+。
• 終端記号は斜体ではなく太字で表示され、非終端記号は山括弧ではなくプレーンテキストで表示されます。
• 項目がグループ化されている場合は、単純な括弧で囲みます。

• ANTLR 、 Javaで書かれたパーサージェネレーター
• Coco/R 、 EBNFの属性付き文法を受け入れるコンパイラ ジェネレーター
• DMS ソフトウェア リエンジニアリング ツールキット、任意の言語のプログラム分析および変換システム
• GOLD、BNFパーサージェネレーター
• RPA BNFパーサー。^[17]オンライン（PHP）デモ解析：JavaScript、XML
• XACT X4MRシステム^[18] 、プログラミング言語翻訳のためのルールベースのエキスパートシステム
• XPLアナライザは、言語の簡略化されたBNFを受け入れ、その言語のXPLパーサを生成するツールです。提供されているSKELETONプログラムに統合することができ、それを使って言語をデバッグすることができます^[19]（SHAREが寄贈したプログラムで、その前にA Compiler Generator ^[20]がありました）
• bnfparser ^{2 [21]}汎用構文検証ユーティリティ
• bnf2xml、^[22]高度なBNFマッチングを使用したXMLタグによるマークアップ入力
• JavaCC、^[23] Javaコンパイラコンパイラtm（JavaCCtm） - Javaパーサジェネレータ

• GNU bison、 GNU 版の yacc
• Yacc、パーサージェネレーター（最も一般的にはLexプリプロセッサで使用される）
• Racket のパーサー ツール、lex および yacc スタイルの解析 (美しい Racket エディション)
• BIツールであるQlik SenseはスクリプトにBNFの変種を使用している^[24]
• BNFコンバータ（BNFC ^[25]）は、「ラベル付きバッカス・ナウア形式」（LBNF）と呼ばれる変種で動作します。この変種では、特定の非終端記号の各生成にラベルが与えられ、そのラベルは、その非終端記号を表す代数データ型のコンストラクタとして使用できます。コンバータは、 HaskellやJavaを含むいくつかの言語の抽象構文の型とパーサを生成することができます。

• 拡張バッカス・ナウア記法(ABNF)
• コンパイラ記述言語(CDL)
• 定節文法– Prolog で使用される BNF のより表現力豊かな代替手段
• 拡張バッカスナウア記法(EBNF)
• Meta-II – 初期のコンパイラ記述ツールと表記法
• 構文図– 鉄道図
• 翻訳バッカス・ナウア形式(TBNF)
• Van Wijngaarden 文法– Algol68 を定義するために BNF より優先して使用されます
• Wirth 構文記法– 1977 年からの BNF の代替

• Garshol、Lars Marius、BNF と EBNF: これらは何であり、どのように機能するのか?、NO : Priv。
• RFC  5234 — 構文仕様の拡張 BNF: ABNF。
• RFC  5511 — ルーティング BNF: さまざまなプロトコル仕様で使用される構文。
• ISO/IEC 14977:1996(E)情報技術 – 構文メタ言語 – 拡張 BNF 、 「公開」から入手可能、標準、ISOまたは、Kuhn、Marcus、Iso 14977 (PDF)、英国: CAM （後者は表紙がありませんが、それ以外はずっときれいです）

• ベルンハルト、Algol-60 BNF、DE : LRZ ミュンヘン、オリジナルの BNF。
• 「SQL-92、SQL-99、SQL-2003 の BNF 文法」、Savage、AU : Net、 SQL用の無料で利用できる BNF 文法。
• 「BNF Web Club」、DB research、CH : Unige、2007-01-24 にオリジナルからアーカイブ、2007-01-25に取得、SQL、Ada、Java用の無料で利用できるBNF文法。
• 「コンパイラ構築のためのフリープログラミング言語文法」、ソースコード、フリーカントリー、 C/C++、Pascal、COBOL、Ada 95、PL/I用の無料で利用できる BNF/ EBNF文法。
• 「STEP 標準に関連する BNF ファイル」、Exp エンジン ( SVN )、Source forge、2012-12-25 にオリジナルからアーカイブISO 10303 (STEP) 規格のパート 11、14、および 21が含まれます。