« ◇量子力学では観測は本質ではない:神は勝手にサイコロを振る | トップページ | 16進コードメモ:文字コードやアイキャッチなど »

◇BNFは間違っている:繰り返しを再帰で表すべきではない

構文を規定するのにBNF表記を用いることは良くあります。

しかし良く知られているようにBNFには繰り返しが表現できないという 根本的で致命的な欠点があります。

このため、リスト構造は再帰で誤魔化されてBNF化されます。

これは一般的に行われていますが、本来の文法モデルとは異なった ものとなります。

 リストモデルとBNF表記

例えば名前をカンマでつないだ構文があるとします。

 A,B,C,D

これは想定する構文モデルでの構文木はつぎのように考えられます。

   name_list
     name=A
     ,
     name=B
     ,
     name=C
     ,
     name=D

この構文をごく一般的に使われるBNFで表すと

   name_list ::=
       name
     | namelist "," name
という形となります。

一見これで構文構造を表せるように思えます。しかし、このBNFに則った 形で構文解析を行うと、構文木は次のようになるのです。

   name_list
      name_list
         name_list
            name_list
               name=A
            ,
            name=B
         ,
         name=C
      ,
      name=D
想定する構文モデルとは全く異なった形です。

想定する構文モデルを表していないということは、即ち、構文定義として このBNF記述は「間違った定義」なのです。
繰り返しを再帰で表すというのは単にまどろっこしいだけでなく誤りなのです。

トークンの並びを表すということではこのBNFは正しいのですが、 文法モデルとしては適切ではないのです。
そして、このモデルをBNFで表す方法はありません。

もちろん、繰り返しとしてリストではなく階層化したモデルを想定するなら BNF記述は正しいのですが、おそらくそういうモデルを作ることは殆ど ないと思います。

 再帰構造と少しずるさを感じてしまう説明

再帰構造の説明には良く四則演算式が用いられます。

例えば

   A + B * C - D
は、結合則により
  ( ( A + ( B * C ) ) - D )
と解釈されるとし、再帰構造を適用します。

これは納得しやすい説明です。

しかし現実的な文

   X = A + B * C - D ;
   Y = E - F;
   Z = X * Y * G;
といった、"連続"するものはけっして取り上げられません。

この文が並んだ構造を再帰構造

  ( ( ( X = ( A + ( B * C ) ) - D ) )
    ( ( Y = ( E - F ) ) )
      ( Z = ( ( X * Y ) * G ) ) ) )

と解釈するのは無理があるからです。

これを避けるのは説明を複雑にしないためではありません。もし そうであれば単純な並び構造

   東京、大阪、名古屋、高知

のようなものは取り上げるはずです。

単純な並びをBNFでは再帰で表すにもかかわらず、構文論理ではけっして 例として示さないのです。例として示すのは再帰で表して自然なもの だけなのです。

確かに少ない約束事で多くの事象が表現できるというのは"美しい"ことと いう見方もあります。

しかし、それによって得られるものが汚くなるのではどうしようもありません。

 繰り返しの定義

BNFに繰り返しのある記述を持ち込むのは当然行うべきことです。

例えば、1個以上の繰り返しを{..}、0個または1個を[..]で表すとして

     name_list ::= name [{ "," name }] ;
のような表記にするのです。

全体がオプショナルの場合

     name_list ::= [ name [{ "," name }] ] ;
となります。

デリミタを持つ繰り返しは多いので、例えば、若干特殊化した記述として

     name_list ::= { name &","} ;
のような表記もありえます。ここでは&の後ろに繰り返しの際のデリミタ を定義します。

0個以上の繰り返しを0{..}と表す方法も考えられます。[]で囲んで 表すこともできるのでこの表記が必要かどうかは要検討です。

 規約とyaccとbnf

構文解析で広く使われるツールであるyaccはほぼBNFに準拠 した定義法を採用しており繰り返しの定義はありません。

繰り返しのない定義は、構文要素をプログラムの要素(変数) に対応付けるのが容易であり、ツールとしては現実的選択です。

繰り返しは再帰でごまかすことが可能です。

規約としては「繰り返し」は「繰り返し」で表し、

   names ::= [{ name }]   // 0個以上の繰り返し
これをyaccで実装する場合に、あくまでツールの制限上の「再帰」

   /* 0回以上の繰り返し */
   names ::= /* null */
          |  names name
          ;
で取り扱うとすべきです。

 (2010/3/12) 繰り返し定義のある構文解析ツール(実例)

本記事の作成(2009/10/20)以降、繰り返し定義のある構文解析ツール を作成する機会を得ました。

オツアンドサンズで"オツライブラリ-symphonie"という名で仮公開されています。

ライブラリ全体の説明は にあります。
オツアンドサンズのホームページは です。

 2010/3/12

構文定義法の細かな記述を削除しました。この記事に当初書いた構文定義法 がほぼ パッケージotsu.symphonieの説明 で実現されています。

|

« ◇量子力学では観測は本質ではない:神は勝手にサイコロを振る | トップページ | 16進コードメモ:文字コードやアイキャッチなど »

トラックバック


この記事へのトラックバック一覧です: ◇BNFは間違っている:繰り返しを再帰で表すべきではない:

« ◇量子力学では観測は本質ではない:神は勝手にサイコロを振る | トップページ | 16進コードメモ:文字コードやアイキャッチなど »