XMLの“認識”

檜山正幸 (HIYAMA Masayuki)
Fri Jun 17 2005:start
Tue Jun 21 2005:draft

XMLの構文解析(syntax analysis)に対して、通常のパージングに引き続く 処理過程としてトークン化と構造認識を考える。 これにより、マークアップ構文とデータ構造の(ある程度の)分離が期待でき る。

目次

1. はじめに

上に関連記事として列挙されている一連の記事で、僕が何を背景に想定して いるのか(の一部)を本記事で説明したい。だいたいのところは、 「XMLの構文解析(syntax analysis)に対して、プログラミング言語処理の常套手段を 適用しよう」ということである。その手段(手法)とは、字句解析と構文解析 (狭義;parsing)の2フェーズを使うことである。各フェーズを担当するソフ トウェアは、レクサー(lexer)(*注1)とパーザー(parser)である。構文解 析をレクサーの過程(トークン化)とパーザーの過程(構造の認識)に分ける のは常識的発想だが、それを推し進めれば、当たり前とは言えない展望がひら ける。

スキャナー、トークナイザーとも言う。おしりの長音記号は気分次第で付け たり付かなかったりですね、僕は。

ただしここで、用語的な問題がある! 「パーザー」は、「SAXパーザー」「DOMパー ザー」「Pullパーザー」などと、XMLストリームの読み取り機構の意味で既に 使われている。しょうがないので、「パーザー」の代わりに「レコグナイザー」 (recognizer)を使うことにする。つまり、XMLレクサーXMLレコグナ イザーの話をする。

誤解がないように先に注意しておくが、XMLレクサーとXMLレコグナイザーは、 (通常の用語法における)XMLパージングに引き続き実行される処理系である。

2. 事例の復習

「属性のための正規表現」「属性か内容か?それは問題ではない」に登 場した事例の復習をする。正規表現の種別は、 各種正規表現の(仮)記法の提案に従って区別する。

まず次の集合正規表現(詳細は「属性のた めの正規表現」)から:

この正規表現は、意味的には、sleepコマンドへの正しい引数パターンを示し ている。Secondは秒数指定、Millisecはミリ秒数指定である。自然言語にパラ フレーズすれば:

この正規表現にマッチする集合の全体(集合言語)は次のようになる。

さて次は、人物情報に関するパターン( 詳細は「属性か内容か?それは問題ではない」) である。

見やすくするために、personName, partnerInfoという中間的なパターンを導 入すると、次の形になる。

3. トークンとレクサー

前節の例で出てきたSecond, Millisec と GivenName, FamilyName, Sex, NotMarried, Married, PartnersNameは、次のような属性仕様を表すのだった。

・ sleepコマンドの例

・ 人物情報の例

ただし、属性の一部または全部を子要素に置き換えても正規表現自体はその まま使える。変更を必要とするのは、“Second, ..., PartnersNameなどの記号” と“XMLマークアップ構成素”の対応関係である。

これまでの例に出てきたSecond, ..., PartnersNameなど、大文字ではじまる 記号(*注2)‘トークン’と呼ぶ。トークンは、正規表現を構成する基本記号 である。形式言語理論の「終端記号」がほぼトークンに対応する。

注2

大文字ではじまっているのは、もちろんここだけのローカル・コンベンショ ンに過ぎない。

プログラミング言語処理では、入力ストリームをトークン列に変換する部分 をレクサーと呼ぶ。それに倣い、XMLのSAXイベントやDOMツリーなどからトー クン列(*注3)を作り出す処理系を‘XMLレクサー’と呼ぶ。プログラミング言 語処理のレクサーがそうであるように、XMLレクサーも入力(SAXイベント、 DOMツリー、その他のXML表現)の一部を無視したり、入力に対応物がないトー クンを生成したりできる。必要があれば、溜め込み(バッファリング)、先読 み(ルックアヘッド)なども行う。

注3

実際には、単純な列ではない。入れ子になった列となるので、結局はツリー 構造である。

トークンは互いに区別できる記号(通常は整数値でエンコードされる)だが、 付随データを持つかもしれない。例えば、Secondというトークンには秒数の整 数値が、GivenNameというトークンには名前の文字列が付随するだろう。

次のコードは、トークンをJavaクラスで表現した例である。付随データを持 たないトークンや、付随データがあってもそのデータが有限種類しかないトー クンなら、オブジェクト生成を抑制することができるが、そのような効率化は とりあえず考えない(*注4)。Javaコードを見たくないならスキップしても問題 ない(後で抽象化した定義を出す)。

注4

現実的にも、このような効率化がどれほどの意味があるかは疑問である。

/* Token.java */
public abstract class Token {
  public abstract int getCode();
}
/* TokenCode.java */
public interface TokenCode {
  public final int GivenName = 1;
  public final int FamilyName = 2;
  public final int Sex = 3;
  public final int NotMarried = 4;
  public final int Married = 5;
  public final int PartnersName = 6;
}
/* GivenName.java */
public class GivenName extends Token {
  private String data;
  public GivenName(String data) {
    this.data = data;
  }
  public int getCode() {
    return TokenCode.GivenName;
  }
  public String getData() {
    return data;
  }
}
/* FamilyName.java */
public class FamilyName extends Token {
  private String data;
  public FamilyName(String data) {
    this.data = data;
  }
  public int getCode() {
    return TokenCode.FamilyName;
  }
  public String getData() {
    return data;
  }
}
/* Sex.java */
public class Sex extends Token {
  public static final int MALE = 1;
  public static final int FEMALE = 2;

  private int data;
  public Sex(int data) {
    this.data = data;
  }
  public int getCode() {
    return TokenCode.Sex;
  }
  public int getData() {
    return data;
  }
}
/* NotMarried.java */
public class NotMarried extends Token {
  public NotMarried() {
    // do nothing
  }
  public int getCode() {
    return TokenCode.NotMarried;
  }
}
/* Married.java */
public class Married extends Token {
  public Married() {
    // do nothing
  }
  public int getCode() {
    return TokenCode.Married;
  }
}
/* PartnersName.java */
public class PartnersName extends Token {
  private String data;
  public PartnersName(String data) {
    this.data = data;
  }
  public int getCode() {
    return TokenCode.PartnersName;
  }
  public String getData() {
    return data;
  }
}
NOTE: トークンの種別判定

上のコードで、トークンの種別はそのクラスに反映されているので、整数値 コードは冗長である。一方、整数値コードだけを使って次のようにトークンを 定義することもできるが、トークン種別が型システムには反映されないこと、 getDataの戻り値のキャスト、無意味なgetData()の存在などが気になる。

public class Token {
 int code;
 Object data;
 public Token(int code, Object data){
   this.code = code;
   this.data = data;
 }
 public Token(int code){
   this(code, null);
 }
 public int getCode() {
   return code;
 }
 public Object getData() {
   return data;
 }
}

4. レキシコン

レクサーは、適当なXML入力ソース(色々な種類がある)から入力(またはスキャ ン)をしながら、トークン列を生成する。レクサーを(完全にハードコードで) 作り込んでもいいが、ある程度の汎用性を持たせるためにパラメトライズされ たレクサーを考えよう。このとき、パラメータとして渡されるデータを‘レキシ コン’(lexicon; 字句辞書)と呼ぶ。

レキシコンは、“トークナイズの方法を記述したルール集”である。今思い ついたイイカゲンな構文で書けば、レキシコン記述はたとえば次のような感じだろ う。

element('person') ==> Person{
 /*1*/ simpleChild('givenName', conent) ==> GivenName(content);
 /*2*/ simpleChild('familyName', conent) ==> FamilyName(content);
 /*3*/ attribute('sex', 'male') ==> Sex(MALE);
 /*4*/ attribute('sex', 'female') ==> Sex(FEMALE);
 /*5*/ attribute('sex', other) ==> Error();
 /*6*/ attribute('married', 'false') ==> NotMarried();
 /*7*/ attribute('married', 'true') ==> Married();
 /*8*/ attribute('married', other) ==> Error();
 /*9*/ simpleChild('partnersName', conent) ==> PartnersName(content);
 /*10*/ #other ==> #Ignore;
}

いちおう説明しておく:タグ名がpersonである要素に対して、波括弧内のルー ルが適用される。

  1. タグ名がgivenNameで、内容がテキストである子要素(単純子要素と呼ぶ) が出現したら、内容テキストを引数にしてGivenNameトークンを生成する。
  2. タグ名がfamilyNameで、内容がテキストである子要素(単純子要素) が出現したら、内容テキストを引数にしてFamilyNameトークンを生成する。
  3. 属性名がsexで、その値が"male"である属性が出現したら、Sex(MALE)トー クンを生成する。
  4. 属性名がsexで、その値が"female"である属性が出現したら、Sex(FEMALE)トー クンを生成する。
  5. 属性名がsexで、その他の値を持つ属性が出現したら、Error()トー クンを生成する。(実際には、エラーに関する情報をトークンに埋め込んで渡すべきだろう。)
  6. 属性名がmarriedで、その値が"false"である属性が出現したら、NotMarried()トー クンを生成する。
  7. 属性名がmarriedで、その値が"true"である属性が出現したら、Married()トー クンを生成する。
  8. 属性名がmarriedで、その他の値を持つ属性が出現したら、Error()トー クンを生成する。
  9. タグ名がpartnersNameで、内容がテキストである子要素(単純子要素) が出現したら、内容テキストを引数にしてPartnersNameトークンを生成する。
  10. その他の構成素は単に無視する(エラーとはしない)。

汎用レクサーが実行時にレキシコンを読み込んで動作する方式もあるし、レ キシコンからレクサー・コードを生成するような方式(コード・ジェネレータ 方式)も考えられる。また、より高水準の宣言的記述からレキシコンを生成す ることもあるだろう。

レクサーとレコグナイザのあいだでの処理の分担やエラー情報の受け渡しな どは、プログラミング言語処理系のときと同様に、ケースバイケースで考えざ るを得ない難しい問題になる。

NOTE: エラー処理

上にあげた(仮の)レキシコン記述で定義されるレクサーでは、 属性sexと属性marriedの値のチェックをトークン生成時に行う。子要素 <givenName>などが単純(テキスト内容しか持たない)かのチェックもレクサーの 仕事だろう。その他のエラーはXMLパーザーとレコグナイザーが担当する。そ の結果、次のようにエラー検出箇所が分散してしまう。

・ 例1 : 同じ名前の属性が2つ → XMLパーザーがエラー検出

<person married="true" married="false">
 <givenName>健夫</givenName>
 <familyName>園部</familyName>
</person>

・ 例2 : sexの値がおかしい → レクサーがエラー検出

<person sex="shemale">
 <givenName>健夫</givenName>
 <familyName>園部</familyName>
</person>

・ 例3 : familyNameがない → レコグナイザーがエラー検出

<person sex="male" married="false">
 <givenName>健夫</givenName>
</person>

5. トークンの抽象化とレクサー再論

先にJavaコードでトークンの実装例を示したが、これは事例にすぎない。 トークンの本質的な特徴は:

  1. 種別を持つ。その種別が整数値にエンコードされるか、それとも(プログ ラミング言語の)クラスで表現されるか、などは本質ではなくて、実装方 式に過ぎない。
  2. 付随データを持つことがある。付随データを番号(順番)で識別するか、 名前で識別するかなどは本質ではない。

さらに考えると、トークンがデータである必要もなくて、 イベントとして表現されてもいい。例えば、GivenName("健夫")と表現される トークンは、givenName("健夫"); というコールバックメソッド呼び出しとし て実現されてもいい。だから、トークン一式を抽象的に定義するには、次のよ うな記述でいいことになる。

tokenset Person {
 GivenName(string);
 FamilyName(string);
 NotMarried();
 Married();
 PartnersName(string);
 Sex(int);
}

上のようなトークンセットの仕様から、トークン種別と付随データを、「ク ラスとプロパティ」、「タイプフィールドとデータフィールド」、「コールバッ クメソッドと引数」のどれで(あるいはその他の方法で)実現するかは実装者 の選択である。

いずれにしても、実装方式を決めてしまえば、トークン種別ごとにトークン データの集合やトークンイベントの集合が確定する。つまり、トークン種別ご との、あるいは全トークンに対するトークン・インスタンスの集合が存在する。

上のような抽象的トークンセット仕様は、具体的なトークン・インスタンス 達を規定しない定義ということになる。逆に言えば、トークン・インスタンス の実現や表現は自由だということになり、その自由の範囲内で決定を行うことが 実装方式の選択になる。

実装方式の一例として、トークン・インスタンスがXMLで表現されてもいいわ けで、 <givenName>健夫</givenName><givenName data="健夫" />givenName="健夫" は、いずれもトークン・インスタンスの表現となる。 前節では、トークンとは処理系(フェーズ)のあいだで受け渡されるデータと いう定義をしたが、抽象化してしまえば、XMLインスタンス(の部分;構成素) もトークンの実例となってしまう。これは妙なことではない。レコード風デー タ、イベント、構文構成素などは抽象的情報要素とみれば同じものであり、トー クンもまた同様な(抽象化すれば同一な)情報要素だったというだけのことだ。

以上の観察をふまえて、XMLレクサー(トークナイザ)とは何かと再び考えて みると、それは抽象トークンセット仕様に関する2つの実現のあいだの変換器 ということになる。ただし、一方の実現がXML構成素を使った実現(表現)で あり、入力側になっている。レキシコンは2つの実現のあいだの変換ルール記 述(対応関係の記述)ということになる。

FIG: XMLレクサーは変換器
            抽象的定義
             /  \
 具象化↓  /      \
         /   変換   \
      実現1 ------→ 実現2

もっと一般的なレクサーを考えるなら、なにか構文的に実現されたトークン セットをプログラムに扱いやすいデータやイベントに変換する機構である。こ の定義では、SAXパーザーもレクサーとみなせそうだ。

6. レコグナイザーとその仕様

この節は、他の記事を読んでないと理解しにくい部分があるかもしれない。 ザッと読んで次の節に移り、後で読み直せばいいだろう。

レクサーは、入力を上手に切り刻んでトークン列を発生させるのが仕事であ り、トークン列の組み合わせが正しいかどうかには頓着しない。トークン列の 全体的な組み合わせ(マクロな構造)を認識するのはレコグナイザーの役割と なる。ここでは、‘レコグナイザー’をトークン列(入れ子の列かもしれない) を入力として、その構造をチェックして、適当なデータ構造を作り出す処理系 と考える。

レコグナイザー(特に構造チェック部)は、オートマトンのようなものだと 思ってよいが、列の認識系に限定する必要はなく、バッグや集合の認識系でも よい。今扱っている例のPersonでは、次のBNF風構文が、レコグナイザーの仕 様を与えると考えてよい。

personName ::= {GivenName & FamilyName}
partnerInfo ::= {NotMarried | (Married & PartnersName?)}
person ::= {personName & Sex? & partnerInfo?}

このBNF定義は、レクサーに対するレキシコンと同様な役割を持つ。そしてこ れは集合言語を定義することになる。演算子記号「&」「|」「?」をunion, choice, optionに直して、関数呼び出し形式にすれば、右辺の集合正規表現は 次のように書き換えられる。

さて、union, choice, optionは集合言語から集合言語を作り出す操作だから、 集合言語をSetと書けば(実際はset of setsだが)、次のようなプロファイル を持つ関数記号となる。

union: Set, Set ->Set;
choice: Set, Set ->Set;
option: Set ->Set;

大文字で表したトークンが表すものは、属性や単純要素などのXML構成素の集 合である。よってトークン記号はConstituent(構成素)という“型”を持つ としよう。そして、ConstituentはSetの特別なものである。

以上の事情を「代数と余代数 最初の一歩」 の第3節で導入した形式的体系の指標(シグニチャ)として表現すれば、次 のようになる。

signature SetAlgebra {
 sort: Constituent, Set;
 order: Constituent < Set;
 function:
   empty:->Set;
   union: Set, Set ->Set;
   choice: Set, Set ->Set;
   option: Set ->Set;
}

「『正規(regular)』とは何なんだ」の第7節と 同じ手順で、BNF定義と指標(関数のプロファイル定義)から次のような再帰 代入系の記述を得ることができる。

input: Constituent GivenName, FamilyName, NotMarried, 
                   Married, PartnersName, Sex;
output: Set person;
working: Set personName, partnerInfo;
 
  personName = union(GivenName, FamilyName);
  partnerInfo = choice(NotMarried, union(Married, option(PartnersName)));
  person = union(personName, option(Sex), option(partnerInfo));

こうして、レコグナイザーが認識すべき集合言語の仕様は、適当な指標に対 する再帰代入系として書ける。

7. 具体例

次のようなXML要素がどのように認識されるかを具体的に追ってみよう。

<person sex="male" married="false" >
 <givenName>健夫</givenName>
 <familyName>園部</familyName>
</person>

XML要素は構成素の集合に分解される。それは次のように記述される。

{attribute('sex', "male"), 
 attribute('married', "false"), 
 simpleChild('givenName', "健夫"),
 simpleChild('familyName', "園部")}

この段階でツリー構造はなくなってしまうが、構成素が属性か単純子要素か の区別は残っている。それがレクサー(トークナイザ)でトークン列に変換さ れると、次のようになる。

Sex(MALE), NotMarried(), GivenName("健夫"), FamilyName("園部")

レコグナイザーはこれを受理して、集合(順序なしの集まり)として認識する。 つまり、次の集合がレコグナイザーによる認識結果となる。

{Sex(MALE), NotMarried(), GivenName("健夫"), FamilyName("園部")}

8. マークアップ中立な構造認識

レコグナイザーは、トークン集合言語を定義する。 {Sex(MALE), NotMarried(), GivenName("健夫"), FamilyName("園部")} はその言語に属する トークン集合の事例である。 {GivenName("健夫"), FamilyName("園部")} もま た事例となる。一方、 {NotMarried(), GivenName("健夫"), FamilyName("園部"), PartnersName("幸代")} は受け入れられないトークン集 合である(独身なのに配偶者がいるのは変!)。

さてここで、次のような奇妙なマークアップを考えよう。

<園部 sex="male" married="false">健夫</園部>
これは、タグ名がfamilyNameを表し、内容がgivenNameになっている。こんな マークアップは決してお勧めできないが、次のようなレキシコンを使えば、同 じレコグナイザーにより認識を行うことができる。

element() ==> Person{
 simpleContent(content) ==> GivenName(content);
 tagName(name) ==> FamilyName(name);
 attribute('sex', 'male') ==> Sex(MALE);
 attribute('sex', 'female') ==> Sex(FEMALE);
 attribute('sex', other) ==> Error();
 attribute('married', 'false') ==> NotMarried();
 attribute('married', 'true') ==> Married();
 attribute('married', other) ==> Error();
 attribute('partnersName', conent) ==> PartnersName(content);
 #other ==> #Ignore;
}

つまり、ある程度抽象化した構造を扱うレコグナイザーと実際のマークアッ プ構文の中間にレクサーが入ることになる。これにより、レコグナイザーはマー クアップの詳細に気を取られることなく認識を行え、レクサー(レキシコン) の取り替えによりマークアップ構文の変更に(ある程度は)対応できることに なる。これは、データ構造設計とマークアップ (具象的/最終的な表現構文)設計を(ある程度は)分離できることを意味する。

NOTE: 最後の注意

この記事では、データ構造とマークアップ構文の分離を提唱してはいるのだ が、データ構造レイヤーがマークアップ構文レイヤーを隠蔽するような仕組み を考えているわけではない。別に説明が必要なことではあるが、構文の詳細を 分離はしても隠蔽はしないほうが良い。必要なときに構文情報にアクセス できないと、XMLの利点の多くが失われることになる。