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

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

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

［参照用 記事］

Wiki処理系を作る前に知るべきこと／考えるべきこと

雑記／備忘

Wiki構文（Wiki記法のルール）は山にようにイッパイあります。

「新たにもう1つ構文を付け加えても別にいいだろう」と考えるか、「これ以上新しい構文を増やしてはいけない」と考えるかは人によるでしょう。僕は、「集約・統合してWiki構文を減らすべきだ」と考えています。それで、標準的なWiki構文としてWikiCreole 1.0を採用し、KuwataさんがCreoleパーザーを実装しています。

ところが、WikiCreoleの構文記述が曖昧過ぎてサッパリわからんのです。Kuwataさんもイライラしている様子。このような状況はWikiCreoleに限りません。たいていのWiki構文の記述はイイカゲンです -- いやっ、仕様書があるだけでマシなのです。イイカゲンな仕様に適合した（conformantな）処理系を作れと言われてもそりゃ困りますわな。

WikiCreole仕様の曖昧さは以前にも話題にしたことがあります。

どちらの記事のタイトルにも「少し」が入ってますが、今回は「少し」ではなく「けっこう」突っ込んで話題にします。でも残念ながら、形式的な構文記述には至っていません*1。

内容：

構造的テキスト処理の基本概念

正確な記述やコミュニケーションをするには、まず言葉をきちんと定義しておく必要があります。次のような言葉の（今回の話題における）意味を定義します。自然言語の記述を補うためにBNFも併用します。

  • 文字、文字列、テキスト、要素、内容、空白、区切り記号、データ文字、破棄文字、改行、行頭、行末、行、完全行、不完全行、空行、行頭空白、行末空白

文字

以下で「文字」と言った場合、それはユニコード仕様で定義される印字可能文字と若干の特殊文字（後述）を意味します。Wikiマークアップされたテキストは、まず“文字の列”として認識されます。文字より低水準のレイヤー、バイトとかビットについては考えません。したがって、文字エンコーディングスキームには言及しません。

特定の文字を表記するには、その文字自体をシングルクォートで囲むか、ユニコードの16進文字番号を使います。例えば、'a' または #x61 （U+0061と同じ）のように書きます。16進文字番号を使う記法は、'&'と';'で挟んであげれば(X)HTMLのアンパサンドエスケープになる書き方です。

若干の特殊文字とは、#x09（タブ）、#x20（スペース）、改行です。改行については後で詳しく述べます。

Char ::= {/* #x09, #x20, 改行, ユニコード仕様で定義された印字可能文字 */}

文字列とテキスト

「文字列」と「テキスト」に意味の違いはありません。どちらも、文字の有限列（リニアシーケンス）です。雰囲気的に使い分けているだけです。メモリ内に張り付いたシーケンスだと文字列（ストリング）と呼び、ファイルやパイプやネットワークストリームとして与えられたシーケンスだとテキストと呼びたい気がします。「気がする」だけで、それ以上に区別する根拠はありません。

String ::= Char*
Text   ::= Char*

文字と文字列

構文記述のさいは、単一の文字と長さ1の文字列を区別する必要はほとんどありません。原則としては、単一の文字はシングルクォート、文字列はダブルクォートで囲む記法を使いますが、'a' と "a" を混同しても問題は起きないでしょう。

次のBNF定義は、どれも同じ構文を定義しています。

abc ::= "abc"
abc ::= 'a' 'b' 'c'
abc ::= "a" "b" "c"
abc ::= 'a' "bc"
abc ::= #x61 #x62 #x63
abc ::= #x61 "bc"

要素と内容

Wikiマークアップされたテキストは、XHTMLに変換することを前提にします。そこで、XMLの要素に対応するテキスト範囲（連続した部分）も「要素」と呼ぶことにします。さらに、XHTMLのpre要素に変換されるべきWikiのテキスト範囲も「pre要素」と呼ぶような、用語の流用（乱用か？）を行ないます。

XMLでは、要素から開始と終了の特殊文字列（開始タグと終了タグ）を除いた部分が内容です。「内容」という言葉もWikiに対して使用します。ただし、「タグ」というXMLの言葉はWikiには使いません。

空白

「空白」（space, blank, whitespace）という言葉も曖昧に使われて混乱をまねきます。ここでは、SP（#x20）、TAB（#x09）、STS（SP-TAB String）という記号を使って識別することにします。

SP、TABに改行も含めて空白（ホワイトスペース）と呼ぶことも多いのですが、Wikiでは改行を特別扱いするので、改行を空白の一種（または一部）とは呼ばないことにします。

SP   ::= #x20
TAB  ::= #x09
STS  ::= (SP | TAB)+ /* 空列は含めない */

区切り記号

Wiki処理系が認識すべき特殊文字列を区切り記号と呼びます。通常「Wikiマークアップ」と呼ばれるものは、区切り記号のことでしょう。区切り記号は、次の3種に分類します。

  1. 開始記号 -- 要素の開始を示します。
  2. 終了記号 -- 要素の終了を示します。
  3. 分離記号 -- 内容が複数の部分から構成されるときの境界を示します。

WikiCreoleのリンク（アンカー、XHTMLのa要素に対応）の構文は、[[＜URL＞|＜アンカーテキスト＞]] ですが、この例では：

  • '[[' は開始記号
  • '|' は分離記号
  • ']]' は終了記号

となります。

Wikiでやっかいなことは、区切り記号が文脈に依存することです。ある文脈における区切り記号は、別な文脈では区切り記号にならないことが多いのです。

データ文字と破棄文字

Wiki処理系が、そのまま出力にデータとして書き出す文字をデータ文字と呼ぶことにします。区切り記号の一部ではないのに、データ文字でもないような文字があります。そのような文字はWiki処理系が捨ててしまうので、破棄文字と呼ぶことにします。破棄文字の例は、インデントのためのSP（#x20）やTAB（#x09）です。また、連続するデータ文字の並びをデータ文字列、連続する破棄文字の並びを破棄文字列と呼ぶことにします。

データ文字（列）、破棄文字（列）という概念も文脈に依存します。段落内での行頭空白（正確な定義は後述）は破棄文字列ですが、pre要素内の行頭空白はデータ文字列です。

改行

Wiki構文では改行が重要な意味を持ちます。改行の表現はOS／プラットフォームごとに違います。なんらかの正規化がしてあることを仮定して、改行を表す文字列をNL（new-line）と表記します。NLの実体が1文字であるとは限りません。#x0D, #x0A の2文字の組み合わせ（CRLF）かも知れません。しかし以下では、改行はあたかも1文字であるかのように扱います。LF（#x0A）が改行である環境では、実際に改行は1文字です。

改行は、後述する行頭、行末とは異なる概念で、実在するデータです。

行頭、行末、行

行頭、行末は、テキスト（文字の列、ストリーム）に含まれる文字や文字列を意味しません。テキスト内の位置（position）です。ここでいう「位置」は、テキスト全体の最初と最後、文字と文字のあいだを示す番号と考えてください。テキストがn個の文字を含むなら、0からnまでの(n + 1)個の位置が存在します。

2文字のテキストなら、3つの位置を持つ。


_ (文字)_(文字)_
^       ^      ^
|       |      3番目の位置（番号は2）
|       2番目の位置（番号は1）
最初の位置（番号は0)

NL（改行）が存在すると、NLの直前の位置（直前の文字ではない！）が行末位置、NLの直後の位置（直後の文字ではない！）が行頭位置になります。NLが存在しなくても、テキスト（ファイルと思っていいです）全体の先頭（位置0）は行頭位置、テキスト全体の最後（位置n）は行末位置となります。

行頭＼行末の定義から、行頭から次の行末の範囲にNLは存在できません。行頭から次の行末の範囲を「行」と呼びます； と、この「行」の定義はまだ曖昧です。「次の行末」がハッキリしてないからです。例えば、どんなテキストでも位置0は行頭です。さて、「次の行末」はどこでしょう？

位置の大小を位置番号の大小と考えて不等号（「＜」や「≦」）を使うことにします。不等号を使って「次の行末」を定義します。

  • 位置nの次の行末（位置）は、n≦k である行末（位置）で、値が最小のものである。

「行頭」「行末」「次の行末」の定義から、次が言えます*2。

  • どんな行頭nに対しても、一意的に次の行末が存在する。

これによって、先ほどの「行」の定義が合理化されます。

正規表現では、行頭を'^'、行末を'$'というメタ文字で表しますが、ここでは行頭をBOL（beginning of line）、行末をEOL（end of line）で表します。NLとは違い、BOLとEOLにはデータが伴わないことに注意してください。

BOL、EOLは文字でも文字列でもありませんが、BNF定義内で使っていいことにしましょう。

LineContent ::= (Char - NL)* /* マイナスは差集合 */
Line ::= BOL LineContent EOL

完全行と不完全行

先の「行」の定義によると、空なテキスト（長さ0のテキスト）でも空な行を持ちます。空テキストの行数は1です -- 常識的な行数概念と食い違います。別に食い違ってもいいのですが、その差と理由がハッキリしないと気持ち悪いですよね。

行には、NLで終端した行とそうでない行（テキストの終了により終わってしまった行）があります。この2種を区別する適当な言葉が見当たらないので、とりあえず次の言葉を使っておきます。

  • NLにより終端した行を完全行と呼ぶ。
  • NLにより終端してない行を不完全行と呼ぶ。

例えば、NLを全部捨てて、“文字列の配列”としてテキストを保持した場合、最後の文字列が「完全行か不完全行か」のフラグ情報を持ってないともとのテキストを再現できません。

完全行／不完全行という言葉と、行に文字を含むかどうかで行を分類すると次のようになります。

  1. 空でない完全行 （直後の改行を含めての長さが2以上）
  2. 空な完全行 （直後の改行を含めての長さが1）
  3. 空でない不完全行 （直後に改行がなく、長さが1以上）
  4. 空な不完全行 （長後に改行がなく、長さが0）

「空な不完全行」をデータとして扱う応用があるでしょうか？ 僕は利用場面を思いつかないです。利用価値がないので、これは行としては認めないことにしましょう。すると、空テキストに存在する「空な不完全行」はカウントされず、行数0となります。

空行

「空白」と同様、「空行」という言葉も定義をしっかりしないと混乱します。空行の定義には2つの可能性があるでしょう。

BlankLine_1 ::= BOL EOL
BlankLine_2 ::= BOL (SP|TAB)* EOL

ほとんどの場合、BlankLine_2を空行の定義に採用していいと思います。

行頭空白、行末空白

行頭空白と行末空白は、それぞれ、「行頭（BOL)から始まる」、「行末（EOL)まで続く」STS（SPまたはTBAの列）です。およそ、次のBNでF定義できるでしょう。

LeadingSTS  ::= BOL (SP | TAB)+
TrailingSTS ::= (SP | TAB)+ EOL

しかし通常は、「長さが最大の」という条件が付きます。SPでもTABでもない文字に出会うまでSTSを伸ばしきった部分文字列が行頭空白、行末空白です。行に、SPとTABしか含まれないときは、行頭空白と行末空白の区別はなくなってしまいます。ですから、行頭空白、行末空白という言葉は、行が非空行のときだけ意味を持つと考えたほうがいいでしょう。

構文の仕様では何を決めるべきか 反面ケーススタディ

構文の仕様では、与えられたテキストの構文的な正しさ（well-formedness）と意味的な正しさ（validity）を完全に判定できるだけの情報を与えなくてはなりません。Wikiでは、意味的な正しさは問題にならない（できない）ので、構文的な正しさだけにフォーカスしましょう。

構文的な正しさが判定できたとして、その後の処理も仕様で定めるべきです。

  1. 構文的に正しいときの処理
  2. 構文的に正しくない（エラーの）ときの処理

Wikiの場合、通常の構文解析と違うのは、構文エラーに対する対処法です。一般的に、構文エラーを発見したときの処理系の動作は次のいずれかでしょう。

  1. 処理を中断して、利用者（人間）にエラーを報告する。
  2. エラーの修復を試みる。
  3. エラーを無視して処理を続行する。

プログラミング言語の処理系などは、構文エラーを許容することは絶対にできないので、中断してエラーを報告します。Wiki処理系の場合、中断もエラー報告もできない場合が多いでしょう。そうなると、エラーを修復するか（たいていは無理）、エラーがあってもテキトーな出力をでっち上げてテキストの最後まで処理を続行するしかありません。

エラー処理やエラー報告の具体的な方法は処理系依存でいいのですが、エラー時に何をすべきかの方針くらいは仕様で定めてないと実装者が途方にくれます。もちろん、構文的に正しかったときの処理（WikiではXHTML出力）の正確な定義も必要です*3。

以下では、WikiCreole 1.0 に関して、構文的正しさが判断できるか？ 構文的に正しいとき／正しくないときの処理が迷いなく実装できるのかを見ていくことにします。

見出しの処理

WikiCreoleの見出しマークアップ（http://wikicreole.org/wiki/Creole1.0#section-Creole1.0-Headings）は、行頭のイコール記号の連続が開始記号となります。"="ならXHTMLのh1要素、"=="ならh2要素に変換されます。仕様の一部を引用します。大文字化による強調は檜山によるものです。

  • Whitespace is ALLOWED before the left-side equal signs
  • Closing (right-side) equal signs are OPTIONAL, doN'T NEED to be balanced
  • ONLY whitespace characters are PERMITTED after the closing equal signs.
  • Markup parsing is OPTIONAL within headings.

まず、Whitespaceの定義がありません。文脈から次のように推測できるだけです。

Whitespace ::= (SP | TAB)+

equal signs は見出しマークアップのことで、おそらく次のようでしょう。（WikiCreole仕様では、見出しは3レベル以上あればいいと規定しています。6レベルはXHTMLに合わせただけです。）

EqualSigns ::= '='{1,6}

{1,6}は１回以上6回以下の繰り返しのことです。律儀に書き下すなら：



EqualSigns ::= ("=" | "==" | "===" | "====" | "=====" | "======")

全体をBNFで定義すると：

Heading ::= BOL Whitespace? EqualSigns HeadingContent EqualSigns? Whitespace? EOL

しかし問題があります。

  1. Whitespaceはホントに (SP | TAB)+ なのか？ 全角スペースをはじめとするユニコードの“空白的”な文字はどうなのか。
  2. 左側に、6個を超えるイコール記号が出現したときは構文エラーか、それともイコールが6個とみなして処理すべきか。
  3. 6個以上のイコールを6個分とみなすとして、余分なイコールは捨てるのか、データ文字として出力に吐き出すのか。
  4. 右側のオプショナルなEqualSignsの文字個数の制限はどうか？ オプショナルだしバランスする必要もないなら、何個でも許されるのではないか。
  5. 左側のEqualSignsの直後にWhitespaceは不要なのか。
  6. 左側のEqualSignsの直後のWhitespaceは、全て捨てられるのか、それともHeadingContentの一部となるのか、あるいは最初のWhitespece文字以外はHeadingContentの一部となるのか。

HeadingContentがなんであるか／どうなるべきは、仕様からは一切分かりません。"Markup parsing is OPTIONAL within headings." なので実装依存、「勝手に決めていい」ってことでしょう。仮に、HeadingContentは単なる文字列でマークアップを認識しないとします。その仮定で次の事例を考えてみます。[BOL]と[EOL]は行頭と行末を表す記号とします。

  1. [BOL]=heading[EOL]
  2. [BOL]= heading = [EOL]
  3. [BOL]=  heading  = [EOL]
  4. [BOL]= heading = = [EOL]
  5. [BOL]= heading = garbage[EOL]

1番目の例の、イコールの右にSPなしが正しいのかどうかは分かりません。既存の実装の一部ではSPが必要なようです。が、箇条書きを開始する「*」、「**」、「***」などの直後の空白はなくてもいい*4ので、「=」「==」「===」なども同じような気もします。

2番目の例は構文的に正しく、右のイコールとSPは捨てられるでしょう。HeadingContentが" heading "か"heading "か"heading"か（SPの有無）は分かりません。この場合「どうせ大差ない」とも言えますが、SP、TAB、改行のあるなしでプログラムの挙動が変わったりする場合は多いので、ないがしろにしていいものではありません。

3番目の例はSPが余分に入れてありますが、出力データに影響する（すべき）でしょうか？ よく分かりません。

4番目の例の2個目のイコールはHeadingContentの一部として、HeadingContentが"heading = "であると解釈するのが無難でしょうが、そうすべきかどうかは、よく分かりません。EqualSigns（イコールの連続を）を常にend-of-headingとする解釈もあり得ます。

もし、EqualSignsを常にend-of-headingと解釈するなら、5番目の例の"garbage"はどう処理すべきかまったくもって不明となります（だからおそらく、garbageもHeadingContentに入れるのでしょう、あくまで推測ですが）。

もっとも単純だと思われる見出しの解析でさえ、このありさまです。

インライン要素の入れ子関係

この調子でいちいち指摘しているとウンザリするほど長くなりそう（既にウンザリ？）ですから、もうひとつだけ； 強調（em要素、Wikiマークアップは「// .. //」）と重要（strong要素、Wikiマークアップは「** ... **」）とリンク（a要素、Wikiマークアップは[[ ... ]]）の入れ子関係です。

強調も重要も、開始記号と終了記号が同じなので、自分自身の入れ子はできません。しかし交互に"//"と"**"を書いていくと、いくらでも入れ子ができます。

 //start level 1
 **start level 2
 //start level 3
 **start level 4
 and
 end level 4**
 end level 3//
 end level 2**
 end level 1//

対応するXHTMLフラグメントは：

 <em>start level 1
 <strong>start level 2
 <em>start level 3
 <strong>start level 4
 and
 end level 4</strong>
 end level 3</em>
 end level 2</strong>
 end level 1</em>

しかし、次の例を見ると、深さが2の入れ子しか認めてないようです。

**//bold italics//**
//**bold italics**//
//This is **also** good.//

「自分自身の入れ子を認めず、深さ2の相互入れ子だけを認める」というルールを正規文法で書こうとするとやっかいです*5。任意の入れ子（再帰構造）のほうがむしろ簡単。僕らが使っているスキーマ言語（Catyスキーマ）は、「深さ2の相互入れ子だけを認める」みたいな変な制約は書けないので困ります。

僕の想像ですが（って、ほとんど全部が推測と想像だが）、自分自身の入れ子や深い入れ子を許すと、レンダリング（ブラウザでの表示）で区別が付かなくなってしまうので禁止しているのでしょう、いやっ、入れ子の禁止も明確には書いてないのですけど。

だいたい、Wikiでナニカを禁止するなんて言ったってユーザーは書いちゃうわけで、構文エラーは起きます。構文エラーで止まるわけにはいかず、処理は続行しなくちゃならない。なにかしら出力も吐き出す必要がある。だが、仕様には何も書いてない、と。そんな状況なのです。

ところで、リンクと一緒に強調（em）や重要（strong）を使うと、“禁止したいはず（檜山の想像）の入れ子”ができてしうのです。まず、リンク（アンカー）の内容は次のように規定されています。

  • At least images inside links must be supported. Parsing other markup within a link is not required (OPTIONAL).

リンク内容のパージングはオプショナルですから、やりたければ、強調（em）や重要（strong）のマークアップを認識してもいいでしょう。リンク自体を強調や重要の内容に入れるのは許されているので、次のマークアップが可能です。

  • //[[GreatLink|//これはすごいです//]]//
  • **[[GreatLink|//これは**すごい**です//]]**

上記のマークアップをXHTMLに変換するのは簡単ですが、なんか釈然としませんねぇ。

Wiki処理系って簡単なの？

プログラミング言語の入門書に、練習問題として「Wiki処理系を作ってみましょう」みたいのがありますが、どうなんでしょうね？ ある程度の実用性があり、いろいろな技術要素が混じっている例題であることは認めますが、構文解析としては、Wikiの処理はいいかげんスジワルなことをしなくてはいけないので、いただけないなー。Wiki処理系を作らざるをえない状況ならともかく、構文解析の練習なら算術式とか簡単なスクリプト言語を扱ったほうがいいですよ。

さて、（Kuwataさんと僕も含めて）Wiki処理系を作らざるをえない人はどうしたもんでしょうか？ 「Wikiなんて所詮 …」と開き直るのもひとつの手ですが、世の中にひとつくらいは形式仕様を持つWiki処理系があってもいいんじゃないかと思ったり思わなかったり。

*1:形式的な構文記述を書きたいとは思いますが、はたしてやる意味があるのか？ 出来るものなのか？

*2:その根拠は：「非負整数の部分集合が空でないなら唯一の最小値を持つ」からです。

*3:Wikiの場合、出力を制約するのはかえってよくないでしょうが、参照出力はシッカリ定義してほしい。揺らぎを許容してもいいけど、参照的標準がないのは困るのです。

*4:Whitespace is optional before and after the * or # characters, however a space is required afterwards if the list element starts with bold text. と書いてあります。この一文がまた何言っているか曖昧だったりするのですが。

*5:きれいな文法で書けないことは、無限先読み、バックトラック、逆方向からの解析など、構文解析では避けたい方法を使わざるを得ないことを含意します。