最近twitterでXSSによる攻撃があって大騒ぎだったというのがよく話題になっているようです。

自分も実は某社でwikiのような記法を使って記事が書けるwebサイトを作っているのですが、よく考えないで正規表現でごりごり実装したのでXSSを連発して苦い経験をしました。

そこで今日は、文法とか言語についてだらだらと書きます。
（ちなみに計算機系の学部では、授業で形式言語とか正規文法とかならうと思いますが、それです。）

wiki記法は文脈自由文法だと思ってパースした方がわかりやすいかも？

結局記法パーサをど根性で正規表現を駆使して書いたんですが、よく文法構造を考えてみればもっと簡単にパースが出来ただろうことに最近ふと気づきました。

細かい話は端折りますが、大抵のwiki記法というのは文脈自由文法というもので表現できそうです。
文脈自由文法で生成される言語というのは、正規表現では記述できない文があるので、どうしても無理矢理な実装になってしまうようです。（チョムスキー階層）

文脈自由文法と正規表現をメールアドレスを例にわかりやすく書いてる記事があったのでとりあえずそれをご紹介。

• 正規表現よりも文脈自由文法を

なるほど。確かに入れ子構造とかがあると正規文法よりは文脈自由文法であると考えた方がみやすそうです。（ただしメールアドレスは正規表現だけでかけるようです。）

wiki記法には、例えばテーブル要素などの、入れ子構造を持ったものがあるので正規表現だけでごりごりやっていくのはなかなかに難しそうです。

twitterの文法は何だろな

で、twitterなんですが、基本的に入れ子構造がない文法なのであれはどうやら正規文法である気がします。
なので基本的には正規表現ですっきり記述可能なはずです。（※一行の正規表現でかけるという意味ではありません）

一般的な構造テキストの解析の仕方

構造化テキストの間違ったエスケープ手法についてや(Twitter の XSS 脆弱性に関連して) 構造化テキストの正しいエスケープ手法についてでも軽く触れられてますが、もうちょっとはっきりまとめるとこういう風につくるのが一般的である様に思います。コンパイラのつくりに似てる気がする。（ある意味これもコンパイルなわけですが）

1. 字句解析（トークナイズ） : 文字列をトークンに分割
2. 構文解析（パーサ） : トークンに文法を元に構造を持たせる
3. 出力生成

ちょっとコードを書くのが面倒なので(Twitter の XSS 脆弱性に関連して) 構造化テキストの正しいエスケープ手法についてから拝借します。

PLAIN TEXT
CODE:




my $html = '';


for my $token (split m{(http://[0-9A-Za-z_\.\%\?\#\@/]+|\@[0-9A-Za-z]+)}, $tweet) {


    if ($token =~ m{^http://}) {


        $html .= '<a href="' . encode_entities($token) . '">'


            . encode_entities($token) . '</a>';


    } elsif ($token =~ m{^\@(.*)$}) {


        my $user = $1;


        $html .= '<a href="http://twitter.com/' . encode_entities($user) . '">'


            . encode_entities($token) . '</a>';


    } else {


        $html .= encode_entities($token);


    }


} 

このコードで説明をすると、for my $tokenの行が字句解析にあたり、そのあとのif, elsif,  elseの部分が構造解析と出力生成になっています。

ところで、さっきtwitterの記法は正規文法らしいとかきました。
その意味するところは、凄くおおざっぱに言えば、左から順番に解析していけば いいということです。
つまり、処理したトークンをあとで後方参照する必要がありません。

実際先ほどのコードを見てみると、分割したトークンを順番に処理していけばいい形になっているのがわかるかと思います。

結論

最近自分で実装したwikiパーサで結構後悔してたのもあるんですが、余程ややこしい記法でも、大概の場合、文法を意識して字句解析・構文解析をすればすっきり解析できる様に思います。

もし独自の記法をつくりパーサなどを実装することなどがありましたら、ぜひこういったことを思い出してつくってみてください。

※追記：
なんか「エスケープが間違ってた」的な話が多い気がするのだけど、個人的には字句解析とか構文解析の失敗であって、別にエスケープは失敗していない様に思う。
わかりやすく言えば、エスケープ関数にエラーはないわけで（多分