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

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

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

［参照用 記事］

CSS3-JQuery時代のツリーパターン記述

雑記／備忘

ツリーの議論を理論的な文脈でするとき、ツリーまたはツリーのパターンを x<C> のような形で記述することがあります。XMLで言えば、xはタグ名（要素名）でCが内容です。例えば、ol<simpleLi, simpleLi> とか。しかし、内容を囲むのに '<' と '>' を使うのはいかにも混乱しそうですよね。'{' と '}' に変えましょう。'<' と '>' はタグ名を囲むのに使うほうが自然でしょう。

そうすると、<ol>{simpleLi, simpleLi} のような記述になります。この書き方を少し発展させるだけで、たいていの用途に間に合ってしまうような気がします。

内容：

人間による読み書きを重視しよう

W3C XML Schema (XSD) は、スキーマ記述自体がXML形式で書かれます。JSON SchemaもJSONで書かれます。このように、データのスキーマが当該のデータ記述言語で書けることはメリットがあるのですが、人間による読み書きは苦痛になることもあります。実際、W3C XML Schema や JSON Schema を人間の手と目で扱うのは愉快な作業じゃありません。

RELAX NG には、（XML形式もありますが）人が読み書きしやすいRELAX NG Compact Syntax が用意されています。これなら苦痛は感じません。しかし、もっとコンパクトで単純なものが欲しい気もします。

スキーマ言語というと大げさですから、XML文書ツリーのようなツリーのパターンを記述する構文 -- ツリーパターン構文を考えます。用途をあまり広く想定しないで、多くの人が既に知っている知識をそのまま利用します。

正規表現

正規表現は多くの人が知っている構文です。色々と方言がありますが、構文的演算子（メタ文字）には次を採用しましょう。（詳しくは「この機会にマスターしようぜ、正規表現、構文図、オートマトン」）

  1. カンマ「,」 -- 連接
  2. 疑問符「?」 -- 省略可能
  3. 星印「*」 -- 0回以上の繰り返し
  4. プラス記号「+」 -- 1回以上の繰り返し
  5. 縦棒「|」 -- 選択、論理OR

正規表現に登場する名前記号で、最初から意味が決まっているものを構文的定数（あるいは単に定数）、後からユーザーが意味を定義する／した名前を構文的変数（あるいは単に変数）と呼びます。形式言語理論では、定数を終端記号、変数を非終端記号と呼ぶこともあります。

構文的変数に意味を割り当てるには、BNF記法を使いましょう。例えば：

simpleLi ::= <li>{text}

BNFに関しては、「BNF、EBNF、ABNF、まー正規表現だな」、「お絵描きで学ぶ・無限正規ツリーとBNF(バッカス／ナウア形式)」などを参照してください。

定数text

典型的なツリー構造として、XMLのDOMツリーを考えましょう。そのノードには次の種類があります。

番号 記号定数 ノード種別
1 ELEMENT_NODE 要素
2 ATTRIBUTE_NODE 属性
3 TEXT_NODE テキストノード
4 CDATA_SECTION_NODE CDATAセクション
5 ENTITY_REFERENCE_NODE 実体参照
6 ENTITY_NODE 実体
7 PROCESSING_INSTRUCTION_NODE 処理命令
8 COMMENT_NODE コメント
9 DOCUMENT_NODE ドキュメント
10 DOCUMENT_TYPE_NODE 文書型宣言
11 DOCUMENT_FRAGMENT_NODE 文書フラグメント
12 NOTATION_NODE 記法

属性は要素ノードに付随していると考えれば、独立したノードは必要ないでしょう。CDATAセクションと実体参照はテキストに展開してしまってもいいでしょう。処理命令（PI）とコメントは無視します。その他のノードは文書インスタンスのツリーには登場しません。

結局、どうしても必要なノードは要素ノードとテキストノードだけです。

要素に関してはまた後で触れることにして、テキストノードに相当するデータを定数textで表します。必要な定数はこのtextだけです。

textは長さ1以上の文字列です。空文字列とはマッチしません。DOMツリーに正規化を施すと空文字列をデータに持つテキストノードはなくなるからです。このことから、textを特別扱いすることになります。

textの定義から正直に考えると、text, text は長さ2以上の文字列を表現することになります。しかし、text, text をこのような目的で使いたいことはないでしょう。text, text は text と同一視します。つまり、textは連接に関してベキ等になります。このことは、DOM正規化で連続するテキストノードを1つにまとめることとも整合します。

text, text ⇒ text であることから、text+ ⇒ text、text* ⇒ text? と簡約されます。

タグパターン

ここでは、要素とタグを区別します。要素は、「開始タグ、内容、終了タグ」の三者で構成されます（内容が空のことがありますが）。図形としてのツリーでは、開始タグと終了タグが単一ノードになり、内容はそのノードの子孫（descendant）達の集合となります。

ちょっと紛らわしいのですが、ツリー上の個々の要素ノードがタグ、その要素から始まるサブツリー全体が要素に対応します。ノードとサブツリーの区別が曖昧で議論がグチャグチャになることがあるので注意しましょう。

さて、タグパターンとは、タグ、つまり単一の要素ノードを記述するパターンです。子孫や（自分以外の）兄弟の情報を必要とせずにマッチングができるパターンです。このタグパターンの構文にCSSセレクター構文を使ってはどうかな、と思うわけです。JQueryのセレクターもCSSとほぼ同じですね。タグパターンに使えるCSSセレクターは、昨日の記事で「現在の情報だけで判断できるセレクター」に分類したものです。

セレクターを '<' と '>' で囲んでタグパターンとして使うことにします*1。いくつかの例を：

textSpan ::= <span>{text}

emptySpan ::= <span>{}

element ::= <*>{(text | element)*} // 再帰的定義

textOrElement ::= (text | element)

para ::= <p, div.para>{textOrElement*}

blankTargetAnchor ::= <a[target="_blank"]>{textOrElement*}

ツリーパターンの書き方

もう、パターン記述の書き方の説明はほとんど終わっています。正規表現とBNF、CSS（あるいはJQuery）の知識を前提にすれば、それに付け加える書き方のルールはごくわずかです。

  1. textという定数を導入する。textは、DOM正規化後のテキストノードを意味する。
  2. タグパターンは、CSSセレクターを '<' と '>' で囲んで書く。
  3. 要素の内容パターンは、正規表現を '{' と '}' で囲んで書く。
  4. パターンに名前を付けるには、BNF記法を使う。

これ以上説明することもないので、もう少し例を挙げます。「//」を使ってコメントを書きます。

// 強調を表す要素
// 内容は空でないテキストのみ
empha ::= <em, strong, span.empha>{text}

// 見出し類
// 内容はテキストとempah要素だけを許す
heading ::= <h1, h2, h3, h4, h5, h6>{(text|empha)+}

// 単純な箇条項目
// 内容は空でないテキストのみ
simpleLi ::= <li>{text}

// 単純な番号付き箇条書き
simpleOl ::= <ol>{simpleLi+}

拡張するなら

以上に述べたことは、「正規表現、BNF、CSSセレクター」というアリモノを繋ぎ合わせただけで、何か機能を追加したりはしていません。それでも、けっこう使えるんじゃないかと僕は思っています。拡張するにしても、以下に述べる2点くらいで十分じゃないでしょうかね。

今述べたツリーパターン記述をスキーマ言語に使うには、属性値やテキスト内容の型付け（typing）能力が不足しています。CSSセレクターでは、「ある属性値が日付時刻形式である」といったことを書けません。一案として、属性セレクターに [名前::型] を追加して、textにも型を書けるようにするとか。

timedText ::= <span [data-dateTime::dateTime]>{text}

price ::= <span.price>{text(currency)}

ここで、dateTimeとcurrencyは型の名前のつもりです。これらの型を定義する型システムが別に必要です。例えば XML Schema Part 2 のデータ型を使えます。でも、背後の型システムを固定すると不自由なので、目的・用途でホスト型システムは変えてもいいでしょう。

SGMLの時代から要素の内容パターン（内容モデル）には、'&'という記号が使えました。これは、順番を考慮しない出現を意味します。例えば a & b は (a, b)|(b, a) を意味します。'&' を含む式を通常の正規表現に直せますが、正規表現の長さが爆発しちゃうので、シーケンス型とは別なバッグ型（マルチセット型）として扱ったほうがいいと思います。つまり、「内容パターンは、正規表現で記述されるシーケンス型か、'&'を含むバッグ型のどちから一方を使う」とするわけです。要素内容としてシーケンス型とバッグ型を混ぜて使いたいってことは、まずないと思います。

*1:記号 '>' は子セレクターのコンビネータとして使われています。しかし、タグパターン内にコンビネータ（を使った文脈セレクター）を書くことはないので問題にはなりません。