このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

［参照用 記事］

抽象構文記法に基づく構文記述と一般代数系

雑記／備忘

BNF（バッカス／ナウア記法）は、構文を正確に記述するためにとても便利です。僕はよく使ってますし、このダイアリーでもけっこう言及してますね。

BNFでは区切り記号や予約語なんかも具体的に記述しますが、パージングが終わった後のデータ（抽象構文木とか）では、区切り記号や予約語の文字や綴りはどうでもいいモノです。構文的なデータ構造だけが問題となります。

パーズ済みデータをプログラムで扱うときは、BNFの情報は具体的で詳しすぎてかえって迷惑です。そこで思い出したのが抽象構文記法（Abstrac Syntax Notation）です。抽象構文記法と一口に言っても、いろいろな流儀・解釈があったりします。ここでは、「構文的データ構造を操作する関数達を使って、構文を定義する方法」くらいに捉えます。

いくつかの例を使って、抽象構文記法に基づく構文記述と構文的操作について説明します。まんなかへんの算術式の例が退屈なら、そこは飛ばして最後だけ読んでみるのもいいかと思います。

内容：

  1. 簡単な事例
  2. 構文構成子
  3. 構文判定子
  4. 構文抽出子
  5. 述語と等式による条件
  6. これは何をやっているのか？

簡単な事例

「高階関数を持たないが型の順序を持つラムダ計算」で出てきたラムダ計算の項を例とします。ラムダ抽象（lambda abstraction）の構文をBNFで定義してみると：

  • Abst ::= 'λ' LambdaList '.' Expr

ここで、'λ' や '.' に絶対的な必然性があるわけではなくて、次のようでもかまいません。

  • Abst ::= 'lambda' LambdaList '->' Expr

'->' をラムダ抽象を作る中置演算子と考えれば、先頭の 'lambda' はなくてもいいでしょう。

  • Abst ::= LambdaList '->' Expr

要するに、Abstは「LambdaList と Expr という2つの部分から組み立てられる」という事実が大事なのです。

そこで、LambdaList と Expr から Abst を作る構文構成子を MakeAbst として、MakeAbst の関数宣言を次のように書きます。

  • MakeAbst[x:LabmdaList, y:Expr]

この宣言は、最初に出したBNF規則の代わりに使えます。具体的な区切り記号や予約語の情報は失われていますが、「Abst は LambdaList と Expr から作られる」という本質的情報は残されています。

構文構成子

抽象構文記法では、構文生成規則というよりは、“構文的操作を行う関数”達の宣言と定義により構文を記述します。関数のネーミングや宣言の書き方はどのようにしたら便利でしょうか？

BNFに出現する構文変数（非終端記号）は、構文的な集合と考えることができます。「高階関数を持たないが型の順序を持つラムダ計算」に出てきた Const, Var, Func などはBNFの構文変数になりますが、それぞれ次のような集合を表します。

  1. 定数記号の集合
  2. 変数記号の集合
  3. （組み込みの）関数記号の集合

そこで、構文変数はそのまま集合の名前と解釈します。構文構成子には大文字始まりの関数名を使うことにします。また、構文変数名を（ドット区切りの）接頭辞に使うことにします。次の「算術式の構文を記述するBNF」を例とします。



Expr ::= Term | Term '+' Term ('+' Term)*

Term ::= Factor | Factor '*' Factor ('*' Factor)*

Factor ::= Const | Var | '(' Expr ')'

これを、抽象構文記法に直すと次のようになります。



Expr.Term[t:Term]

Expr.Sum[t1:Term, t2:Term, restT:list<Term>]
Term.Factor[f:Factor]

Term.Mult[f1:Factor, f2:Factor, restF:list<Factor>]
Factor.Const[c:Const]

Factor.Var[v:Var]

Factor.Paren[e:Expr]

restT, restF は可変引数の残余部分と思ってください。list<Term>（Termのリスト）というデータ構造を認めています。

パラメータ名（引数変数名）はどうでもいいので、圏論の射のように書いたほうが分かりやすいでしょう。



Expr.Term : Term → Expr

Expr.Sum : Term×Term×Term* → Expr
Term.Factor : Factor → Term

Term.Mult : Factor×Factor×Factor* → Term
Factor.Const : Const → Factor

Factor.Var : Var → Factor

Factor.Paren : Expr → Factor

構文判定子

算術式の全体からなる集合はExprですが、集合Exprは、型構成子Expr.Termで作られた領域と型構成子Expr.Sumで作られた領域に別れます。どちらの領域に属するかを判定する関数を Expr.isTerm、Expr.isSum としましょう。

Expr.isTerm、Expr.isSum のように、構文的集合の上ので定義された述語を構文判定子と呼ぶことにします。算術式では、次のような構文判定子が必要となります。



Expr.isTerm : Expr → boolean

Expr.isSum : Expr → boolean
Term.isFactor : Term → boolean

Term.isMult : Term → boolean
Factor.isConst : Factor → boolean

Factor.isVar : Factor → boolean

Factor.isParen : Factor → boolean

構文抽出子

構文抽出子とは、構文的なデータ構造の一部を抜き出す関数です。算術式の例で見てもらうのが早いでしょう。構文抽出子は小文字始まりの関数名として、適当な接頭辞を付けます。構文抽出子は、構文集合の部分集合でしか定義されない場合が多いので、定義域を条件付きの集合（集合の内包記法）で書くことにします。



Expr.term : {e∈Expr | Expr.isTerm(e)} → Term

Expr.first : {e∈Expr | Expr.isSum(e)} → Term

Expr.second : {e∈Expr | Expr.isSum(e)} → Term

Expr.rest : {e∈Expr | Expr.isSum(e)} → Term*
Term.factor : {t∈Term |Term.isFactor(t)} → Factor

Term.first : {t∈Term | Term.isMult(t)} → Factor

Term.second : {t∈Term | Term.isMult(t)} → Factor

Term.rest : {t∈Term | Term.isMult(t)} → Factor*
Factor.const : {f∈Factor | Factor.isConst(f)}  → Const

Factor.var : {f∈Factor | Factor.isVar(f)} → Var

Factor.paren : {f∈Factor | Factor.isParen(f)} → Expr

述語と等式による条件

構文構成子と構文判定子のあいだには次の関係が成立します。実際には、∀t∈Term のような全称限量子が付きますが、それは省略しています。

  1. Expr.isTerm(Expr.Term(t))
  2. Expr.isSum(Expr.Sum(t1, t2, restT))
  3. Term.isFactor(Term.Factor(f))
  4. Term.isMult(Term.Mult(f1, f2, restF))
  5. Factor.isConst(Factor.Const(c))
  6. Factor.isVar(Factor.Var(v))
  7. Factor.isParen(Factor.Paren(e))

構文構成子と構文抽出子のあいだの関係は次のようです。やはり全称限量子は省略しています。

  1. Expr.term(Expr.Term(t)) = t
  2. Expr.first(Expr.Sum(t1, t2, restT)) = t1
  3. Expr.first(Expr.Sum(t1, t2, restT)) = t2
  4. Expr.rest(Expr.Sum(t1, t2, restT)) = restT
  5. Term.factor(Term.Factor(f)) = f
  6. Term.first(Term.Mult(f1, f2, restF)) = f1
  7. Term.second(Term.Mult(f1, f2, restF)) = f2
  8. Term.rest(Term.Mult(f1, f2, restF)) = restF
  9. Factor.const(Factor.Const(c)) = c
  10. Factor.var(Factor.Var(c)) = c
  11. Factor.paren(Factor.Paren(e)) = e

これは何をやっているのか？

BNFによる構文定義（生成規則）に直接的に対応する抽象構文記法は、型構成子だけです。ここでは、型判定子と型抽出子も追加しました。これにより、構文領域（構文的集合の集まり）の構造がより良く理解できるようになります。この“構文領域の構造”とは、多ソート代数と呼ばれる代数構造です。

多ソート代数は、いくつかの集合を台とします。例えば算術式では、Const, Var, Factor, Term, Expr を台、つまりソートと考えることができます。基本となるソート（台集合）とそれらの直積の上の部分集合、関数、部分関数などが演算系を構成します。いくつかのソートといくつかの演算の組み合わせは代数系の指標となります。そして、「述語と等式による条件」に記述した論理式群が公理系を与えます。

指標と公理系があれば、一般代数（Universal Algebra）の枠組み従って、モデルと準同型が定義できます。モデルは実際の構文的構造であり、準同型は構文的な類似性や同値性を与える写像です。モデルを対象、準同型を射とする圏も定義できます。さらに、指標のあいだの写像とそれに伴う論理式の翻訳をうまく定義できれば、インスティチューションを定義できます。

つまり、抽象構文記法は構文的インスティチューションの指標を記述する方法だったのです。構文構成子だけでなく、構文判定子や構文抽出子を定義し公理系を定めれば、より精密でリッチな代数構造ができて、その上に構文的操作の体系を組み立てることができます。様々な構文的操作を定義することは、代数構造の上でプログラミングする典型的な例を与えます。

「代数構造（台集合と基本的な演算と法則性）の上でプログラミングする」という発想は、けっこう重要・有益だろうと思います。