検索

Google
Web www.icefree.org

RSS of recent changes

 

BNF

2017-06-20 (火) 23:23:54 (1453d)

この文章は、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 ::= α ;

のように表記することもある。

コメント


Counter: 3248, today: 2, yesterday: 2