◇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に則った 形で構文解析を行うと、構文木は次のように

[auient]

構文木から見たBNFの繰り返し表現の考察。

[xxxxxeeeee]

結局プログラム上で考えるときは全ての構文が「ある1つのものに対する操作」「ある2つのものに対する操作」程度に抽象化されている方が楽で、「あるN個のものに対する操作」は再帰で定義するのが当然に楽。