バッカス・ナウア記法

出典: フリー百科事典『ウィキペディア（Wikipedia）』

バッカス・ナウア記法（Backus-Naur Form）とは、文脈自由文法を定義するのに用いられるメタ言語のことで、一般にBNFやBN記法と略される。現在はこのBNFを拡張したEBNF (Extended BNF) が一般的に使われている。EBNFでは正規表現を用いてより簡単に記述でき、プロトコル規定言語であるASN.1や、XMLの構文定義にも利用されている。

ジョン・バッカスとピーター・ナウアがALGOL 60 の文法定義のために考案。当初は文脈自由文法の本来の定義に則り or（|）以外の定義はなく、繰り返しは再帰を利用して表現されている。*、?等を含む正規表現はBNFを拡張したEBNFによって導入された。コンパイラコンパイラを使用してコンパイラやインタープリタを作成する際に、プログラミング言語の構文規則を記述するために使われる場合もある。

ISO/IEC 14977:1996においてEBNFの標準が定義されているが、EBNFにもいろいろな亜種や変種がある。例えば、RFC2234にはABNFという変種が定義されている。しかし、ABNFは標準のEBNFとかなり異なる部分がある。

[編集] 歴史

ジョン・バッカスは ALGOLの文法を表現するためにこの記法を考案した。1959年、パリで世界初の国際コンピュータ大会議（World Computer Congress）が開催された際、バッカスは "The syntax and semantics of the proposed international algebraic language of the Zurich ACM-GAMM Conference" を発表した。これは後にALGOL 58と呼ばれる IAL の形式記述であった。彼が発表した形式言語は、Emil Post の生成システムに基づいたものであった。形式文法は数学における研究課題のひとつであり、例えばノーム・チョムスキーは自然言語の文法への適用を研究していた^[1] ^[2]。

ピーター・ナウアは、バッカスの記法を単純化し、使用する文字セットを最小化した。これにはドナルド・クヌースの助言があったとされる^[3]。この貢献によって、ナウアの名前も記法名に含まれるようになった。

バッカス・ナウア記法、あるいは BNF 文法は、パーニニの文法規則によく似ている。このため、パーニニ・バッカス記法（Panini-Backus Form）と呼ばれることもある。

[編集] 基本

BNF の表記は導出規則群で構成され、各導出規則は次のようになる。

<symbol> ::= <expression with="with" symbols="symbols">

ここで、<symbol> は「非終端記号」、expression は symbol の並び、または選択を表すバーティカルバー '|' で区切られた symbol の並びであり、左辺の symbol の置換となるものを表している。左辺に現れない symbol は「終端記号」である。

[編集] 例文

以下はすべてのBNFに当てはまるわけではない。

<hoge> ::= <hogehoge>

<hoge> は <hogehoge> である。

<hoge> ::= <abc> | <def>

<hoge> は <abc> または <def> である。

[編集] 具体例

例として、アメリカ合衆国での住所表記（郵便）をBNFで表現する。

<postal-address> ::= <name-part> <street-address> <zip-part>
 
      <name-part> ::= <personal-part> <last-name> <opt-jr-part> <eol> 
                    | <personal-part> <name-part> <eol>
 
  <personal-part> ::= <first-name> | <initial> "." 
 
 <street-address> ::= <opt-apt-num> <house-num> <street-name> <eol>
 
       <zip-part> ::= <town-name> "," <state-code> <zip-code> <eol>

これを言葉に直すと、次のようになる。

住所（postal-address）は、名前（name-part）の後に通りの住所（street-address）があり、その後に郵便番号（zip-part）がある。
name-part は個人名（personal-part）の後に姓（last-name）が続き、さらにオプションの "jr-part"（Jr. とか Sr. 、あるいは○世など）があり、改行コードがある。あるいは、個人名の後に name-part がある（こちらの規則は再帰的定義になっている。ミドルネームが続く場合を表している）。
個人名（personal-part）はファーストネームか、イニシャルにドットが付いたものである。
通りの住所（street-address）は、オプションのアパート指定があり、番地（house-number）、通りの名前（street-name）、改行コードの順となる。
郵便番号（zip-part）は、タウン名（town-name）、カンマ、州コード（state-code）、郵便番号（ZIP-code）、改行コードの順となる。

これは非常に単純化しており、定義されていない部分（first-name、apt-num、ZIP-code など）が多々ある点に注意されたい。それらを新たな BNF 規則を追加することで表現することもできる。

[編集] 別の例

BNF の文法は BNF を使って以下のように表現できる。

<syntax> ::= <rule> | <rule> <syntax>
 <rule> ::= <opt-whitespace> "<" <rule-name> ">" <opt-whitespace> "::=" 
            <opt-whitespace> <expression> <line-end>
 <opt-whitespace> ::= " " <opt-whitespace> | ""  <!-- "" は空文字列。つまり空白がない -->
 <expression> ::= <list> | <list> "|" <expression>
 <line-end> ::= <opt-whitespace> <eol> | <line-end> <line-end>
 <list> ::= <term> | <term> <opt-whitespace> <list>
 <term> ::= <literal> | "<" <rule-name> ">"
 <literal> ::= '"' <text> '"' | "'" <text> "'" <!-- 実際には、本来のBNFではクォートは使われない -->

ここでは、構文規則を正しく翻訳するには空白（whitespace）が必要であるとしている。<eol> は適当な行末を示す記号（改行コード）である。<rule-name> は宣言された規則の名前/ラベル、<text> はテキストに置換される。

[編集] 派生

BNF には様々な派生と拡張が存在し、一般に単純さと簡潔さのために拡張/修正されるか、特定の用途向けに適用させるべく拡張/修正されている。特によく行われる拡張は * や + といった正規表現の繰り返しオペレータの導入である。典型的な例として EBNF（Extended Backus-Naur form）がある。実際、上記の例は ALGOL 60 リポートで使われたオリジナルそのままの形式ではない。"[]" という括弧を使った記法は、IBMのPL/Iの定義で初めて使われ、現在では一般化している。ABNF（Augmented Backus-Naur form）は、IETF の通信プロトコルの定義などに使われている。

解析表現文法 (PEG) は BNF と正規表現に基づき、新たな形式文法のクラスを形成したものである。その性質は生成的というよりも基本的に解析的である。

今日、インターネット上で見つかるBNF表現の多くは人間が読むことを重視しており、非形式的である。そのため、以下のような構文規則の拡張をしていることが多い。

省略可能なアイテムは角括弧で囲む。例えば、 [<item-x>]
0回以上繰り返すアイテムは中括弧で囲む。例えば、 <word> ::= <letter> { <letter> }
1回以上繰り返すアイテムには '+' を後置する。
終端記号をボールド体、非終端記号を通常の文字で表し、イタリック体や山括弧を使わない。
アイテムの繰り返しを '*' を後置することで表すことが多い。
生成時の選択肢を '|' 記号で区切って列挙する。例えば、 <alternative-a> | <alternative-b>
アイテムをグループ化する必要があるときは、普通の括弧で囲む。

[編集] 関連項目

ジョン・バッカス (J.W. Backus)
ピーター・ナウア (Peter Naur)
ALGOL 60
プログラミング言語
コンパイラコンパイラ
文脈自由文法
Ashtadhyayi （数学的構造を持ったサンスクリット語文法）
正規表現
Yacc 構文解析器生成ソフト
Bison GNU 版 yacc
ANTLR

[編集] 参考文献

この記述は GNU Free Documentation License のもとに公開されているコンピュータ用語辞典『 Free On-line Dictionary of Computing (FOLDOC) 』に基づいています。

[編集] 脚注

^ Chomsky, Noam, "Three Models for the Description of Language," IRE Transactions on Information Theory, Vol. 2 No. 2, pp. 113-123, 1956.
^ Chomsky, Noam, Syntactic Structures, Mouton, The Hague, 1957.
^ Knuth, Donald E. "Backus Normal Form vs. Backus Naur Form," Communications of the ACM 7(12):735-736, 1964

[編集] 外部リンク

Algol-60 BNF - オリジナルのBNF
BNF Web club - サンプルの文法がある。
[1] - news:comp.compilers へのポスト。2つの名称（バッカス・ナウア記法とバッカス・ノーマル記法）の歴史について説明している。
BNF and EBNF: What are they and how do they work? by Lars Marius Garshol.
RFC 4234 Augmented BNF (ABNF)
Comparision of different variants of BNF
Syntax diagram of EBNF
Generation of syntax diagrams from EBNF

この「バッカス・ナウア記法」はコンピュータに関連した書きかけ項目です。この記事を加筆して下さる人を求めています（Portal:コンピュータ）。

See also ebooksgratis.com: no banners, no cookies, totally FREE.