BNF
この文章は、2004/08/05から2004/08/10のブログを編集したものです。
2005/12/24 平易な説明を追加しました。
2006/09/07 ISO/IEC 14977:1996がフリーで閲覧できることを追記しました。(影佑樹さんからの情報)
2007/01/29 1959年のペーパーについて追記しました。
2007/03/09 リンク切れを修正しました。
BNF (Backus Naur Form) †
FORTRANの開発を行っていたJohn Warner Backus氏が1959年に提唱したメタ言語です。
The syntax and semantics of the proposed international algebraic language of the Zuerich ACM-GAMM conference. In International Conference on Information Processing, p125-132, June 1959
とあります。
1960年には、Algol 60での定義に用いられました。
とにかく亜種が多い言語でもあります。
明確な定義や、拠り所となる仕様を明らかにせずに、近場にある使用例を元に二次使用(n次使用?)してしまうことが多いため、さらなる亜種を生んでいく悪循環に陥っている気がします。
そこで、しばらくBNFについて調べてみたいと思います。
1959年のペーパー †
The syntax and semantics of the proposed international algebraic language of the Zuerich ACM-GAMM conference. In International Conference on Information Processing, p125-132, June 1959
としてよく参照されるものです。
Information processing : proceedings of the international conference on information processing, Unesco, Paris 15-20 June 1959
というタイトルで理系の大学の図書館にはよく所蔵されています(NCID=BA08384894)。ちなみに、国会図書館には無いようです。
ここで、IALの文法の定義のためにBNFが登場します(この時点ではBNFとは呼ばれずに単にメタ言語としか書かれていません)。
例として
<ab> :≡ ( or [ or <ab>( or <ab> <d>
が挙げられています。
次に挙げる「Algol60のメタ言語としてのBNF」との違いは、
:≡ が :== になった点と、
or が | になった点です。
どうやら==と2つ並べるのは≡が由来のようです。
Algol60のメタ言語として使用されているBNF †
現在、一般に入手できる最古のBNFです。これが素のBNFと言われることも多いようです。
特徴 †
とにかくシンプル。
選択(|)以外には、グループも繰り返しも範囲での指定も無い。
概要 †
例) <ab> :== ( | [ | <ab> ( | <ab> <d>
ここで、( [ はただの文字に過ぎないことに注意。
識別子(metalinguistic variables)は、<>で囲む。
生成規則には :== を用いる。
選択は | で表す。
参考文献 †
http://www.masswerk.at/algol60/report.htm
ISO/IEC 14977:1996 Extended BNF †
BNFは、ISOでも定義されています。しかし、知名度はいまいちです。
ISOですが無料で閲覧可能です。
特徴 †
foo = "bar" | "baz" ; のように書く。;が最後に来る。
集合から要素を取り除く操作がある(-)。
{foo} で、0回以上の繰り返し、{foo}-で、1回以上の繰り返しとなる。やや特殊。
任意回の繰り返しは、n * foo とする。
[foo]は0回または1回となる。
キャラクタの連続範囲の指定は無い。
コメントは、(* hoge *)
概要 †
識別子(meta identifier)
英字から始め、英数字が続く。
文字列
文字列のクオートは、' ' か、" " で行う。
生成規則
= を用い、; で終わる(;の代わりに. も使える)。
接続
, で区切る。
選択
| を使う(/、!も使える)。
コメント
(* *)で囲む。
繰り返し
{}で囲まれた記号を 0回以上の繰り返す。
{}- で、1回以上の繰り返しとなる。これは、除外の特殊な使用例。
例){"A"}-は、"A" | "AA" | "AAA" | ...
指定回数の繰り返し
整数 * 式で、整数回の繰り返しを表す
例)
aa = "A"
bb = 3 * aa
これは、"AAA"になる
cc = 3 * [aa]
これは、empty | "A" | "AA" | "AAA"になる。
省略
[]で囲まれた記号は、0回または1回の繰り返しとなる。
グループ化
()で囲むことでグループ化できる。
sepcial sequence
? ?で囲む。内容は、ISOでは定義されない。
empty sequence
空
exception
- で除外を表せる。
例)
aa = "A" | "B" | "C" | "D"
bb = "B"
cc = aa - bb
ccは "A" | "C" | "D"となる。
参考文献 †
http://isotc.iso.org/livelink/livelink/fetch/2000/2489/Ittf_Home/PubliclyAvailableStandards.htm
ABNF(RFC2234) †
RFCのためのBNF。かなりのローカルルールで、しかも、RFCは全てこれで統一されているというわけでもない。
数値主体の徹底ぶりがネットワーカーらしい。
特徴 †
定義には、= を用いる。
選択には / を用いる。
終端記号は全て数値が基本となる。2,10,16進が定義済み。
なんと、文字列もcase-insensitive。
繰り返しの指定が1*3(foo bar)のように範囲指定できる。
概要 †
識別子
英字で始め、英字、数字、-を用いる。
大文字小文字の区別をしない。
<>で囲む必要はない(使っても良い)。
生成規則
name = elements crlf(改行)
複数行に渡るときには、見やすくするために次行以降をインデントする。
終端記号
ABNFでは、文字もエンコードされた非負の整数として扱う。
数値の表現には、2,10,16進数が定義されている。
例えば、13は以下のように表される。%b1101 %d13 %x0D
複数の数値を表す場合には、"."で区切り連続して表記することができる。
例えば、"ABC"は以下のように表せる。%x41.42.43
""で囲むことで文字列も使える。
ただし、ABNFの文字列は大文字小文字の区別がない。
キャラクタセットにはus-asciiを使う。
例えば、"AbC"は、"abc","Abc","AbC","ABC"などと区別されない。
他のキャラクタセットを使うこともできる。
演算
Concatinates Rule1 Rule2
特別な記号を必要としない。空白で繋げばよい。
Alternatives Rule1 / Rule2
選択には | ではなく、/を用いる。
Incremental Alternatives Rule1 /= Rule2
ABNFではインクメンタルな定義が用意されている。
Value Range Alternatives %c##-##
例)%x30-39
Sequence Group (Rule1 Rule2)
()でグループ化することができる。
Variable Repetition <a>*<b>Rule
a回以上b回以下の一致する。
省略時はそれぞれ0と無限大。
例)1*2<element> は、elementの1〜2回の繰り返し
Specific Repetition <n>Rule
<n>Ruleは、<n>*<n>Ruleと同じ
Optional Sequence [Rule]
[RULE]は、*1(RULE)と同じ。
Comment ;
;から改行まではコメントになる。
優先順位
1. Strings, Names formation
2. Comment
3. Value range
4. Repetition
5. Grouping, Optional
6. Concatination
7. Alternative
参考文献 †
http://www.ietf.org/rfc/rfc2234.txt
XML 1.0の表記法 †
XMLは、自身が使う表記法を仕様に含んでいます。
正規表現的な記述を取り込んだ、今現在よく使われることが多い表記法です。でも、意味論的制約はちょっとやりすぎな気がします。
特徴 †
コードによる文字指定は、#xNの形式で書く。
正規表現に似ている表現が多い。(A|B,A?,A*,A+,範囲指定)
正規表現でおなじみの範囲指定([abc],[a-c],[a-c,d][^a-c][^#x0d])がある。
差分がある(A-B)
[wfc:][vc:]などで、意味論的制約が指定できる。
概要 †
生成規則
symbol ::= expression
識別子
開始記号は大文字で始め、その他は小文字で始める。
終端記号
文字列は引用符で囲む。"" と '' のどちらでもよい。
#xN
ISO/IEC 10646 のコードで文字を指定する。
例)#x0d, #xd
範囲(Range) [a-zA-Z],[#xN-#xN]
指定範囲の任意の文字にマッチする。
列挙(Enumeration) [abc],[#xN#xN#xN]
列挙した任意の文字にマッチする。
1つの[]の中に、範囲と列挙を複数回使うことができる。
範囲除外(Range of forbidden) [^a-z],[^#xN-#xN]
指定した範囲以外の任意の文字にマッチする。
列挙除外(Enumeration of forbidden) [^abc],[^#xN#xN#xN]
列挙した以外の任意の文字にマッチする。
1つの[]の中に、範囲除外と列挙除外を複数回使うことができる。
グループ化 (expression)
()で囲まれた式を1つの単位として扱う。
A?
Aは省略できることを表す。
A | B
A または Bとマッチする。
A - B
Aにマッチし、Bにマッチしないこと。
A+
1回以上のAにマッチする。|よりも優先される。
A*
0回以上のAにマッチする。|よりも優先される。
/* */
コメント
well-formedness constraint [wfc: ...]
well-formed documentで定義される制約を名前で指定する。
validity constraint [vc: ...]
valid documentで定義される制約を名前で指定する。
参考文献 †
Extensible Markup Language (XML) 1.0 (Third Edition)
http://www.w3.org/TR/REC-xml/#sec-notation
文脈自由文法 †
注)今回はいつにも増して、適当な知識と適当な資料で書いてます。ツッコミ大募集中です。
BNFは、文脈自由文法の1つです。
用語で迷わないように、文脈自由文法について軽くまとめてみました。
文脈自由文法(CFG:Context Free Grammar) †
一般に言語モデル(文法)は以下のように表される(注:CFGのみに限っていません)。
(N,Σ,P,S) N 非終端記号の集合 Σ 終端記号の集合 (N∩Σ=φ) P 生成規則の集合 (P⊂(N∪Σ)+×(N∪Σ)*) S 開始記号 (S∈N)
非終端記号は、生成規則により書き換え可能な記号のこと。
終端記号は、生成規則により書き換えられない記号のこと。
生成規則は、非終端記号を、非終端記号・終端記号の列に書き換えるための規則のこと。
開始記号は、非終端記号の要素である。ある文が与えられたときに、開始記号から導出可能であれば、その文は妥当(Valid)である。
文脈自由文法では、生成規則は以下のように表される。
p(A,α) (A∈N, α∈(N∪Σ)*)
pは2項述語記号で、計算機言語論では通常→を用い
A→α
と表記する。
補足ノート †
(P⊂(N∪Σ)+×(N∪Σ)*)について
A*は0回以上の連接です。つまり、NかΣの要素を任意個繋げたもので、空集合を含みます。Kleene閉包、スター閉包、閉包、スターなどと呼ばれます。
A+は1回以上の連接です。A* - {ε}です。
×は直積集合を表します。
つまり、P⊂(N∪Σ)+×(N∪Σ)*)は、NとΣの1回以上の繰り返しと、NとΣの0回以上の繰り返しとの対応関係全体の一部(全部を含む)ということです。
モデルは(N,Σ,P,S)のように()を使用することが多いようです。同様のモデルがある、多分そちらが由来だと思うのですが、集合論では<D,Φ>のように<>を使うことが多いです。
Sから導出される文全体からなる集合を言語といい、モデルGに対してL(G)で表す。
2項述語記号は、計算機言語論では
A→α
と表記することが多いが、BNFなどでは ::=であったり、=であったりする。また、2項間に記号を書くだけでなく
A ::= α ;
のように表記することもある。
コメント †
- 影佑樹 2006-09-03 (日) 01:40:36
Publicly Available Standards:http://isotc.iso.org/livelink/livelink/fetch/2000/2489/Ittf_Home/PubliclyAvailableStandards.htm
ISO/IEC 14977 の無料版が公開されてます - vvp 2006-09-07 (木) 23:49:00
情報ありがとうございます。
JISと同じようなコピーの制限のある無料版のようですね。