第4回
BNF記法入門（1） ─XML関連仕様を読むために─

W3Cの勧告として発表されているXML 1.0の仕様書は、XMLの構文を厳密に定義するためにBNFと呼ばれる記法で記述されている。XML関連の仕様書を読みこなそうとすれば、BNFの理解は不可避だ。今回はそのBNFを解説しよう。

■話題　BNF記法
■程度　C （XMLに関するひととおりの知識を持っている人を対象とする）
■目的　基礎的な知識の解説
この連載を初めてお読みになる方は、「XML深層探求について」をご覧ください。

今回のおもな内容
1. はじめに
2. 整数の表現を例として
3. 正整数で小手調べ
4. 整数の表現を完成させる
5. XML1.0におけるBNF
6. いくつかの補足事項
7. まとめ

檜山正幸
2000/11/22

1. はじめに

　XML 1.0仕様（http://www.w3.org/TR/REC-xml）は、XMLの構文を厳密に定義している。ところで、「構文を厳密に定義する」ために、どのような記述方法を使っているのだろうか？

　実物を見てみよう。次は、XML 1.0からの抜粋である。

[40] STag ::= '<' Name (S Attribute)* S? '>'

　なにやら不思議な記号の羅列のようにも見えるが、これは、非常に広く使われている構文記述のための表記法の一例となっている。XML 1.0で（そしてそのほか多くの言語仕様において）使われているこのような表記法は、BNF(Backus Naur Form)記法と呼ばれる。今回は、XML 1.0を読むために必要なBNFの基礎を学ぼう。

Note： BNF記法は、プログラミング言語ALGOL 60の構文記述のために考案されたものである。1962年の改訂版(制定は1960年)の文書“Revised Report on the Algorithmic Language ALGOL 60”において、ALGOL 60の構文がBNFにより定義された。この文書の主著者がJ.W.バッカス（J.W. Backus）、編集者がピーター・ナウア（Peter Naur）である。

BNFの生みの親バッカスは、1950年代中ごろ、IBMのチームを率いて史上初の高水準プログラミング言語FORTRANを設計開発した人である。そのとき、バッカスは20代の青年であった。その後、より洗練された言語ALGOL 60、1970年代後半には、コンビネータ理論に基づく超高水準関数型言語FPを提唱している。 理論と実践の両面において、常にプログラミング言語のフロンティアにいた人物だ。

Note： 現在使われているBNF記法は、オリジナルに対して拡張が行われている。拡張されたBNFを特にEBNF(Extended BNF)と呼ぶこともある。ただし、EBNFにもいろいろな方言（変種）がある。 “ISO/IEC 14977:1996 Information technology -- Syntactic metalanguage -- Extended BNF”において標準が定義されているが、遵守されているようすはない。そもそも、この標準の存在があまり知られていないだろう。 ISO規格の入手が困難な点が災いしている。

RFC2234“Augmented BNF for Syntax Specifications: ABNF”（http://www.ietf.org/rfc/rfc2234.txt）では、BNFの一変種であるABNFが定義されている。ほかのRFCでABNFを使っているケースもあるが、通常のEBNFとかなり食い違っており、国際化も考慮されていない。 （少なくとも私は）使う気になれない。

Note： この記事では、「BNF記法」という言葉を使った。BNFのFはformだから、形式とか記法の意味が含まれる。だから、「BNF記法」は、「馬から落馬」のような冗長な表現だ。だが、「ASCIIコード」（ASCIIのCはcode）、「XML言語」（XMLのLはlanguage）など、「馬から落馬」方式はけっこうよく使われるから気にしないことにしよう。

　

2. 整数の表現を例として

　まずは、簡単な例から始める。いま、整数を表現する方法を定義するとしよう。「そんなことをあらためて定義する必要なんてないじゃないか？」と、そう感じる方もいるだろう。 ‘0, 1, 2, 155, -10’などが整数の表現である。この程度の例を出しておけばだれでも理解できるではないか -- はたしてそうだろうか？

  1. 正の整数には、プラス記号を付けてもよいか？ （例： ‘+12’）
  2. ゼロにプラス記号やマイナス記号を付けてもよいか？ （例： ‘-0’）
  3. 先頭に余分な ‘0’を付けてもよいか？ （例：‘012’）
  4. 小数点があっても、小数部が‘0’だけからなれば、整数とみなすか？（例：‘12.00’）
　などの疑問が生じる。厳密に定義するなら、これらの疑問に明確に答えられるような定義を与えなくてはならない。別な言い方をすると、あいまい性がなく、確実な判断ができるような定義が要求されているのだ。

具体的な定義を書き下す前に、方針を決めておく。以下のとおり。

  1. 整数を表現するために使ってよい文字は‘0’から‘9’までの10個の算用数字と、プラス記号‘+’、マイナス記号‘-’だけとする。
  2. 正の整数にはプラス記号を付けても付けなくてもよい（負の整数には、もちろんマイナス記号を付ける）。
  3. ゼロには、プラス記号もマイナス記号も付けない。
  4. 先頭に余分な‘0’を付けてはいけない。ゼロ以外の整数の表現は、‘0’でない数字かプラス・マイナス記号から始まる。
Note： 「数字」、「マイナス記号」などの基本的な言葉にさえあいまい性が含まれる。算用数字以外にも数字は存在するし（例えば、漢数字）、経理の分野では、マイナス記号として‘△’を使ったりもする。次の節では、このあいまい性を除くため、すべての数字と記号を列挙している。

Note： 抽象的な値としての整数と、数字による整数表現は異なるものである。だが、あまり厳密に区別すると、かえってうっとうしいので、多少混同した言葉遣いもしている。例えば、「負の整数にマイナス記号を付ける」は、「負の整数の表現の先頭文字は、マイナス記号である」とでもするのが正しい。

3. 正整数で小手調べ

　さて、いよいよBNFの登場である。まずは、予備的な定義をBNFで記述してみる。

数字 ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
非ゼロ数字 ::= '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

　これは、使用可能なすべての数字と、ゼロでない数字を列挙により定義している。記号‘::=’は、「〜とは…である」と読むとよい。つまり、「数字 ::= …」なら、「数字とは…である」と読む。 ‘::=’の右側が実際の定義である。縦棒‘｜’ は、「または」と読む。よって、1番目のBNFルールは、次のように読める。

数字とは、「0」または「1」または（途中省略） または「9」である。

　2番目のルールも、数字‘0’が含まれないだけで、同様である。

　次に、正の整数の表現を考えよう。正整数が1桁の数なら、それは1文字の非ゼロ数字である。つまり、

1桁の正整数 ::= 非ゼロ数字

　2桁なら、

2桁の正整数 ::= 非ゼロ数字 数字

である。ここで、2桁の整数を定義するルールは、次のことを意味する。

2桁の正整数とは、非ゼロ数字と数字を（この順序で）並べたものである。

　これで、‘0’から‘9’までの1桁の整数、‘10’から‘99’までの2桁の整数が正確に定義された。では3桁の定義を……、とやっているとキリがない。そこで次の表現法が登場する。

正整数 ::= 非ゼロ数字 数字*

　星印‘*’は、0回以上の繰り返しを意味する（「0回の繰り返し」とは「何も存在しない」ことである）。つまり、1つの星印で次のような無限のケースを一挙に表現する。

0回の繰り返し：
1回の繰り返し：数字
2回の繰り返し：数字 数字
3回の繰り返し：数字 数字 数字
4回の繰り返し：数字 数字 数字 数字
……

Note： 名前（識別子）に関する常識をお持ちの方は、「1桁の正整数」という名前の先頭文字が数字なのに気付き「おかしいじゃないか」と思ったかもしれない。確かに、たいていは、数字で始まる名前は許さない。が、説明の都合でこうなったんだから、あまり堅いことはいわないで。

　まだこれでも、正整数の定義は完全ではない。正整数には、プラス記号を付けてもよいのであった。これを考慮すると

正整数 ::= '+'? 非ゼロ数字 数字*

となる。疑問符‘?’は、その直前のものがあってもなくてもよいことを示す。つまり、このルールは次のように書いても同じである。

正整数 ::= 非ゼロ数字 数字* | '+' 非ゼロ数字 数字*

もっと分解して書けば

正整数 ::= 符号なし正整数 | 符号付き正整数
符号なし正整数 ::= 非ゼロ数字 数字*
符号付き正整数 ::= '+' 非ゼロ数字 数字*

となる。

Note： grepやPerlのパターン、あるいはXML DTDの内容モデルをご存じの方は、‘|’、‘*’、‘?’が正規表現の特殊記号と同じであることに気付かれただろう。そのとおり、BNF（正確にはEBNF）は、正規表現を用いた構文定義である。

Note： オリジナルのBNFでは、‘*’や‘?’を使っていない。何も存在しない空な表現をEMPTYとすると、‘Foo ::= Bar*’は、

Foo ::= EMPTY | Foo Bar

と、再帰を使って書ける。‘Foo ::= Bar?’なら、

Foo ::= EMPTY | Bar

である。

4. 整数の表現を完成させる

　正整数の定義はできたから、一気にゼロと負整数も定義してしまおう。

ゼロ ::= '0'
負整数 ::= '-' 非ゼロ数字 数字*

そして、整数は、正整数、ゼロ、負整数のどれかだから、次の定義となる。

整数 ::= 正整数　| ゼロ|　負整数

念のため、いままでの定義をすべて書き並べてみる。

[1] 数字 ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
[2] 非ゼロ数字 ::= '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
[3] 正整数 ::= '+'? 非ゼロ数字 数字*
[4] ゼロ ::= '0'
[5] 負整数 ::= '-' 非ゼロ数字 数字*
[6] 整数 ::= 正整数　| ゼロ|　負整数

　この定義では、6個のルールを使って整数の表現を定義したが、長く複雑になるのをいとわなければ、1つのルールで定義することもできる。

整数 ::= '+'? ('1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9')
('0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9')*
| '0'
| '-' ('1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9')
('0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9')*

5. XML1.0におけるBNF

　BNFに慣れたところで、冒頭に引用したXML 1.0のルールを、いままでの知識をもとに解読してみよう。 

[40] STag ::= '<' Name (S Attribute)* S? '>' 
             1--- 2---     3-- 4---  6 7--------  8  9--
                                    5-------------
  1. 先頭の‘40’はルールの番号である。XML 1.0には多数のルールがあるので、番号をふって識別している。
  2. このルールは開始タグ‘STag’を定義している。
  3. 開始タグの最初は小なり記号‘<’である。
  4. 小なり記号の直後に名前‘Name’がくる。名前は別のルールで定義される。
  5. 名前の後に、属性が何個か（0回以上の任意個）出現してもよい。星印‘*’に注目。
  6. 名前と属性の間、属性と属性の間の区切りとして空白‘S’が必要。
  7. 属性‘Attribute’は別のルールで定義される。
  8. 名前または属性の後に空白‘S’があってもなくてもよい。疑問符‘?’に注目。
  9. 開始タグの最後は大なり記号‘>’である。

　このルールのなかで、‘Name’、‘S’、‘Attribute’が使われているが、これらは別なルールで定義されている。実際、‘Name’は5番のルールで、‘S’は3番のルールで、そして‘Attribute’は41番のルールで定義されている。オンラインのXML 1.0仕様書では、ハイパーリンクにより、芋づる式に定義をたどれる。BNFの基本を知った上で、構文定義ルールを順にたどりながら読めば、 XML構文をあいまいさなく完全に知ることができる。

6. いくつかの補足事項

　XML 1.0で使われているBNFで、まだ説明してない記法がいくつかある。それらは次のようなものである。

  1. 1回以上の繰り返し
  2. 文字の番号表記
  3. 文字の列挙と範囲
  4. 例外として排除
  5. 文字範囲の除外
■1回以上の繰り返し

　星印‘*’は0回以上の繰り返しを表す記号だったが、1回以上の繰り返しはプラス記号‘+’で表す。実例を出そう。

[7] Nmtoken ::= NameChar+

　この例では、名前トークン‘Nmtoken’が名前文字‘NameChar’の1回以上の繰り返しであることを示している。以下のような無限個のケースを一挙に表現している。

Nmtoken ::= NameChar
Nmtoken ::= NameChar NameChar
Nmtoken ::= NameChar NameChar NameChar
Nmtoken ::= NameChar NameChar NameChar NameChar
……

Note： ‘A+’は‘(A A*)’の略記とみなせる。一方、‘A*’は‘(A+)?’で代用できる。つまり、‘*’と ‘+’の両方が絶対に必要なわけではない。

■文字の番号表記

　文字や文字列それ自体を表すには、当該の文字・文字列を引用符で囲めばよい。例えば、‘

'.'’はピリオドを示す。直接書きにくい文字のときは、その文字の代わりに、‘#x’の後に16進のUnicode番号を続けてもよい。例えば、‘#x9’はタブを、‘#xA’はラインフィードを表す。

　1回以上の繰り返しを示す‘+’と、文字の番号表記が理解できれば、次のような、空白‘S’の定義が理解できる。

[3] S ::= (#x20 |#x9 |#xD |#xA)+

■文字の列挙と範囲

　‘( 'a' | 'b' | 'c' | 'd' | 'e' )’のような文字の列挙には、‘[abcde]’という略記法が使える。さらにこれは、‘[a-e]’と短く書いてもよい。‘a-e’は、「‘a’から‘e’まで」と読めばよい。この略記を使うと、‘[a-zA-Z0-9]’で英数字全体を表すことができる。直接文字を書く代わりに、‘[#x20-#xD7FF]’のように、番号表記を使ってもよい。

　文字の範囲を使えば、先に出した例の「数字」と「非ゼロ数字」は、次のように短く書ける。

数字 ::= [0-9]
非ゼロ数字 ::= [1-9]

■例外として排除

　XML 1.0におけるコメントの定義は次のようになっている。

[15] Comment ::= '<!--' ((Char - '-') | ('-' (Char - '-')))* '-->'

　ここで、 ‘(Char - '-')’ という表現に注目してみよう。これは、「マイナス記号を除くすべての文字」を意味する。特殊記号としてのマイナスは除外を意味する。

　‘(Char - '-')’を‘NMChar’（Non-Minus Character）と書くと、コメント内容‘((Char - '-') | ('-' (Char - '-')))*’は、‘(NMChar | '-' NMChar)*’と書ける。これは、マイナスが2つ続けて現れてはいけないことを意味している。だから、‘Char* - (Char* '--' Char*)’と書いても同じことである。

Note： ‘|’は集合の和（合併）に対応し、‘-’は集合の差に対応する。

■文字範囲の除外

　‘Char - [abcd]’は、‘[^abcd]’と書いてもよい。つまり、‘[^’と‘]’の間に文字を並べると、「指定された文字以外の文字」を表す。次の定義を見てみよう。

[14] CharData ::= [^<&]* - ([^<&]* ']]>' [^<&]*)

　ここで、‘[^<&]’は、「小なり記号とアンド記号以外の文字」を表す。

7. まとめ

　今回扱った内容をまとめると、次のようになる。

  1. BNF記法は、広く使われている構文記述の方法である。
  2. ‘::=’は、 「とは」（左辺は右辺で定義される）を意味する。
  3. ‘|’ は、「または」を意味する。
  4. ‘*’は、「0回以上の繰り返し」を意味する。
  5. ‘?’は、「あってもなくてもよい」（オプションである）ことを意味する。
  6. BNF記法を簡略化するために、そのほかにいくつかの便利な略記や代替表現が使われる。
■今回のリンク ■履歴
2000/11/22　公開


「XML深層探求」


XML & SOA フォーラム 新着記事
＠ITメールマガジン　新着情報やスタッフのコラムがメールで届きます（無料）

注目のテーマ

HTML5＋UX 記事ランキング

本日月間
＠IT