再帰方程式系とパス方式定義
BNFは、再帰方程式系(Recursive System of Equations, Recursive Equational System;ベクトル記法を使うなら a recursive equation)の最小不動点による定義。このとき、基本型(外延的には基本領域)と型構成子(外延的には集合/領域に対する関数)を適当に決めるのだが、これを注意深く決めれば:
- 再帰方程式系とパス方式定義の表現力が等しくなる
ようにできる。
もちろん、型構成子のレパートリがなんでもいいなら上の条件は簡単にクリアできる。要はバランス感覚。実用的に不都合がない程度の表現力を持たせたい。
任意の正規表現を使ってしまうと無理なのだが、列(シーケンス)型について次の制限をする。
- 中間に欠損項目がないタプル(長さは固定)
- 列前半のタプルと、列の残りはクリーニ・スター
また、ユニオン型は常に弁別子付き(discriminated)だとする。
パスとしては、定数パス(固定的に場所を表す)以外に:
再帰、または循環的定義を表すには、次の構文を使う。
- PathSpec ::= Path Label? : TypeDesc
- Label ::= '[' Name ']'
ラベルで定義された名前は、別な宣言(PathSpec)の型記述(TypeDesc)に使ってよい。
弁別子条件とラベルは、当面要らない気がする。ワイルドカードは必須だが。