Loading article…
コンピュータ科学において、バッカス・ナウア形式（ BNFまたはPBF 、発音は/ ˌbækəsˈnaʊər / ）は、バッカス正規形とも呼ばれ、プログラミング言語やその他の形式言語の構文を定義するための表記体系であり、ジョン・バッカスとピーター・ナウアによって開発されました。これは文脈自由文法のメタ構文であり、言語構造の規則を正確に概説する方法を提供します。
これは、プログラミング言語理論に関する公式仕様書、マニュアル、教科書などで広く使用されており、文書フォーマット、命令セット、通信プロトコルの記述にも用いられています。時を経て、拡張バッカス・ナウア記法（EBNF）や拡張バッカス・ナウア記法（ABNF）といった派生形が登場し、元のフレームワークに機能が追加されています。
BNF仕様は、構文的に有効なシーケンスを形成するために記号がどのように組み合わされるかを概説します。各BNFは、非終端記号のセット、終端記号のセット、および一連の派生規則という3つのコアコンポーネントで構成されています。[ 1 ]非終端記号は、置換可能なカテゴリまたは変数を表し、終端記号は、最終的なシーケンスに現れる固定のリテラル要素（キーワードや句読点など）です。派生規則は、非終端記号を特定の記号の組み合わせに置き換えるための指示を提供します。
導出規則は次の形式で記述されます。<symbol> ::= __expression__
どこ：
<symbol>[ 2 ]は、山括弧 (<>) で囲まれた非終端記号であり、置換対象のカテゴリを識別します。::=は「～に置き換えられる」という意味のメタシンボルです。__expression__は置換文字列であり、1 つ以上の記号のシーケンスで構成されます。これらのシーケンスは、終端記号 (たとえば、「Sr.」や「,」のようなリテラルテキスト) または非終端記号 (たとえば、 ) のいずれかであり、選択肢は縦棒(|)で区切られ、代替を示します。<last-name>例えば、ルール では、行全体が導出ルールであり、「Sr."」、「Jr."、および "" (空文字列) は終端記号であり、は非終端記号です。<opt-suffix-part>::= "Sr." | "Jr." | ""<opt-suffix-part>
有効なシーケンスを生成するには、指定された開始記号から始めて、導出規則を繰り返し適用する必要があります。[ 1 ]このプロセスにより、シーケンスを段階的に拡張できます。柔軟性を持たせるために、一部の BNF 定義にはオプションの「削除」記号 (空の代替として表される、例: ) が含まれており、構文の妥当性を維持しながら特定の要素を削除できます。[ 1 ]<item> ::=<thing> |
BNFの具体的な例として、簡略化された米国の郵便住所の仕様を挙げます。
<郵便番号> ::= <名前部分> <番地> <郵便番号部分><名前部分> ::= <個人部分> <姓> <オプション接尾辞部分> <EOL> | <個人部分> <名前部分><個人部分> ::= <名> | <イニシャル> "." <番地> ::= <番地> <通り名> <アパート番号> <改行>< zip-part > ::= < town-name > "," < state-code > < ZIP-code > < EOL ><opt-suffix-part> :: = " Sr. " | " Jr. " | <roman-numeral> | "" <opt-apt-num> :: = "Apt" <apt-num> | " " これは英語に翻訳すると次のようになります。
なお、ここでは多くの事項（例えば、名字の形式、アパート番号、郵便番号、ローマ数字など）が規定されていません。必要に応じて、追加のBNF規則を用いて記述することができます。
言語構造を記述するために書き換え規則を使用するという概念は、少なくとも紀元前6世紀から4世紀の間に生きた古代インドのサンスクリット語文法学者パーニニにまで遡ります。[ 4 ]サンスクリット語の単語構造を記述するための彼の記法は、BNFと同等の力があり、多くの類似した特性を示します。[ 5 ]
西洋社会では、文法は長い間、科学的研究というよりは教育の対象とみなされてきました。記述は非公式で、実用的な使用を目的としていました。この見方は20世紀前半に変化し、レナード・ブルームフィールドやゼリッグ・ハリスなどの言語学者が、句構造を含む言語記述の形式化を試み始めました。一方、数学者たちは、1914年のアクセル・トゥー、 1920年代から40年代のエミール・ポスト[ 6 ]、1936年のアラン・チューリングなど、形式論理システムとしての文字列書き換え規則を通して関連するアイデアを探求しました。MITで情報理論の学生に言語学を教えていたノーム・チョムスキーは、言語学と数学を融合させ、トゥーの形式主義を自然言語の構文記述に適用しました。1956年、彼は生成規則（文脈自由文法の規則）と変換規則の明確な区別を導入しました。[ 7 ] [ 8 ]
BNF自体は、 IBMのプログラミング言語設計者であるジョン・バッカスが、 1959年に新しいプログラミング言語IAL（現在ALGOL 58として知られる）の構文を定義するためにメタ言語式のメタ言語を提案したときに出現した。 [ 9 ]この表記法はALGOL 60レポートで形式化され、ピーター・ナウアーは委員会の1963年のレポートでこれをバッカス正規形と名付けた。 [ 10 ]バッカスがチョムスキーの研究に直接影響を受けたかどうかは不明である。[ 11 ] [ 12 ]
ドナルド・クヌースは1964年に、BNFはチョムスキー標準形とは異なり「慣習的な意味での標準形ではない」ため、バッカス・ナウア形式と読むべきだと主張した。[ 13 ] 1967年、ピーター・ジラヒー・インガーマンは、パーニニが以前に独自に同様の記法を開発したことを認めるため、これをパーニニ・バッカス形式と改名することを提案した。[ 5 ]
ALGOL 60 レポートで、Naur は BNF をメタ言語式として説明した。[ 10 ]
括弧 <> で囲まれた文字の並びは、値が記号の並びであるメタ言語変数を表します。記号 "::=" および " | " (後者は「または」の意味) はメタ言語接続詞です。式の中で変数でも接続詞でもない記号は、それ自体を表します。式の中で記号や変数を並置すると、それが表す並びが並置されることを意味します。
これは報告書のセクション2.3に例示されており、そこには以下のコメントが記載されている。
プログラムのシンボルの中にテキストを含める場合、以下の「コメント」に関する慣例が適用されます。
ここでいう等価性とは、左列に示されている3つの構造のいずれも、文字列以外の箇所において、右列の同じ行に示されている記号に置き換えても、プログラムの動作に影響がないことを意味します。
ナウアーはALGOL 60のバックアスの元の記号を変更し、一般的に入手可能な文字を使用して、上線付きの「」または「」をに:≡変更した。[ 14 ]： 14::=|
BNF は、FORTRAN 設計者としての Backus の数学的背景を反映して、（論理回路設計で使用される）標準形式のブール代数方程式と非常によく似ています。 [ 2 ]ブール代数の研究は、数学のカリキュラムの一部として一般的であり、それが Backus のアプローチに影響を与えた可能性があります。Backus も Naur も、囲まれた名前を非終端記号とは説明していません。チョムスキーの用語は、BNF の説明には当初使用されませんでした。Naur は後に、1961 年のコース資料でそれらを「クラス」と呼びました。[ 2 ] ALGOL 60 レポートでは、それらは「メタ言語変数」であり、他の記号がターゲット言語を定義していました。<>
1947年からAssociation for Computing Machineryに関わっていたSaul Rosenは、IALからALGOLへの移行に貢献し、Communications of the ACMの編集者でもありました。彼は1967年の著書でBNFをALGOLのメタ言語として説明しました。[ 15 ] IBM、Honeywell、Burroughs、Digital Equipment Corporationの初期のALGOLマニュアルはこの用法に従いました。
BNFはプログラミング言語の開発に大きな影響を与え、特に初期のコンパイラ・コンパイラシステム の基盤となった。例としては、エドガー・T・アイアンズの「ALGOL 60用構文指向コンパイラ」や、ブルッカーとモリスの「コンパイラ構築システム」などがあり、これらはBNFを直接利用している。[ 16 ]ショアのMETA IIのように、BNFをプログラミング言語に適応させ、引用符付き文字列に置き換え、繰り返し用の$などの演算子を追加したものもある。例：<>
EXPR = TERM $ ( '+' TERM . OUT (' ADD ') | '-' TERM . OUT (' SUB '));これは、BNF の原則に基づいた広く使用されているパーサー生成ツールであるyaccなどのツールに影響を与えました。[ 17 ] BNF は、今日でも参照されている最も古いコンピュータ関連の表記法の 1 つですが、その派生形が現代のアプリケーションでよく使われています。
メタ言語としての使用例としては、算術式の定義などが挙げられる。
<expr> :: = <term> | <expr> <addop> <term>ここでは、再帰的に自身を含めることができ、繰り返し追加することが可能です。<expr>
BNFは現在でも使用されている最も古いコンピュータ関連言語の一つである。
BNFの構文自体は、以下のようなBNFで表現できます。
<構文> ::= <ルール> | <ルール> <構文><ルール> ::= <opt-whitespace> " < " <ルール名> " > " <opt-whitespace> " :: = " <opt-whitespace> <式> <行末><opt-whitespace> :: = " " <opt-whitespace> | " "<式> :: = <リスト> | <リスト> <opt-whitespace> " | " <opt-whitespace> <式><行末> :: = <オプション空白> <EOL> | <行末> <行末><リスト> :: = <用語> | <用語> <opt-whitespace> <リスト><用語> ::= <リテラル> | "<" <ルール名> ">" <リテラル> ::= '"' <テキスト1 > '"' | "'" <テキスト2 > "'" <text1> :: = " " | <character1> <text1><text2> :: = " " | <character2> <text2><文字> ::= <文字> | <数字> | <記号><文字> ::= "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>
上記の米国の郵便住所の例では、引用ブロック全体が です。各行または連続した行のグループはルールです。たとえば、1 つのルールは で始まります。そのルールのもう 1 つの部分 (行末を除く) は式で、縦棒 で区切られた 2 つのリストで構成されます。これらの 2 つのリストは、いくつかの用語 (それぞれ 3 つの用語と 2 つの用語) で構成されます。この特定のルールの各用語はルール名です。<syntax><name-part> ::=|
BNFには多くのバリエーションや拡張版が存在し、一般的には簡潔さや分かりやすさを追求するため、あるいは特定の用途に合わせて調整するために用いられます。多くのバリエーションに共通する特徴の一つは、正規表現の繰り返し演算子（例えば、`\ n`や`\n`*など）の使用です+。拡張バッカス・ナウア記法（EBNF）はよく用いられる形式の一つです。
もう一つの一般的な拡張方法は、オプション項目を角括弧で囲むことです。これはオリジナルのALGOL 60レポートには含まれていませんでしたが（数年後にIBMのPL/I定義で導入されました）、現在では広く認識されています。
拡張バックアス・ナウア記法（ABNF）とルーティングバックアス・ナウア記法（RBNF）[ 18 ]は、インターネット技術タスクフォース（IETF）プロトコルを記述するためによく使用される拡張です。
構文解析式文法は、 BNFと正規表現表記法に基づいて構築され、本質的に生成文法ではなく解析文法である、別の種類の形式文法を形成する。
今日オンラインで見られる多くのBNF仕様は、人間が読みやすいように設計されており、非形式的なものです。これらには、多くの場合、次のような構文規則と拡張機能が含まれています。
[<item-x>]*)を付けて末尾に付けます。<word> ::= <letter> {<letter>}<word> ::= <letter><letter>*+ます。<word> ::= <letter>+{{cite web}}: CS1 maint: 複数の名前: 著者リスト (リンク){{citation}}: CS1 maint: url-status (リンク){{citation}}: CS1 maint: 非推奨のアーカイブサービス (リンク)。ISO 10303 (STEP) 規格のパート 11、14、および 21が含まれます。