emit_block 改め nestag を使った簡易 Wiki フォーマッタ

元祖 Wiki サーバ・スクリプト WikiBase の Wiki フォーマッタ、 PrintBodyText 関数を元にして、 2 年前に書いたコードを久しぶりに改訂します。⇒ https://gist.github.com/tociyuki/1388797⇒ emit_block を使った簡易 Wiki フォーマッタ - Tociyuki::Diary…

トポロジカル・ソート

循環参照なしの有向グラフを次のように入れ子のハッシュ・リファレンスのキーの関係で表現するとします。 my $dependencies = { 'node-a' => { 'depend-a-0' => 何か, 'depend-a-1' => 何か、 'depend-a-2' => 何か、 }, 'node-b' => { 'depend-b-0' => 何か…

gist.github.com のリビジョン・インジケータっぽいもの

gist の履歴に、赤色と緑色のドットを並べて、テキストの変更度合いを表したインジケータがついています。あのインジケータは好きなので、Wiki の差分表示ページで似たものを描く方法を考えてみました。まず、差分をとるページの内容が必要です。 CREATE TAB…

while ループによる木構造の深いコピー

木構造の幅優先探索法を応用して、 最初に配列リファレンスの入れ子構造で表現される木構造の深いコピーを書いてみます。 考え方は単純で、 まずルートを浅いコピーし、 それから幅優先で枝を順に浅いコピーしてさしかえていきます。 枝を浅いコピーして要素…

libtext-mkdown-perl v0.01

私家版 Markdown 処理系 Text-Mkdown を改訂しました。⇒ https://github.com/tociyuki/libtext-mkdown-perl 強調記号の処理に DFA を使うようになりました。 フットノートを使えるようになりました。 定義リストを使えるようになりました。 シングル角括弧で…

Markdown の強調記号の DFA によるナイーブ実装 (その3)

「Markdown の強調記号の DFA によるナイーブ実装 (その2)」の続きです。ついでに、Markdown 方言の中でも広く使われている PHP Markdown がおこなっている便利機能を追加します。 オリジナル Markdown には明記してないのですが、 下のように、 アスタリス…

Markdown の強調記号の DFA によるナイーブ実装 (その2)

昨日のアスタリスク限定「Markdown の強調記号の DFA によるナイーブ実装」を元に、アンダースコアも使えるように拡張しました。アスタリスク並びから HTML マークアップへ変更するとき、昨日は正規表現による文字列置換を使いましたが、記号にアンダースコ…

Markdown の強調記号の DFA によるナイーブ実装

Markdown の実装の難関、強調記号に再挑戦してみます。⇒ Markdown の趣味的な emphasis マークアップ・テストは無視した方が幸せかも - Tociyuki::Diary ⇒ 昨日の「Markdown の強調記号の正規表現によるナイーブ実装」の正規表現の短縮化 - Tociyuki::Diary…

富豪的 multipart/form-data スキャナ

既にメモリ中のバッファに全 POST データを読み取った後に使うことを考えて、そのデータを対象とする multipart/form-data スキャナを書いてみます。multipart/form-data は正規文法なので、構文を正規表現で表せます。今の Perl5 のキャプチャ機構では実用…

ピュア Perl 版 Text-Liq 用の構文解析表生成ツール

これまでのバージョンでは、 手作業で修正しやすいことから構文解析表を 2 次元配列にしていました。 終端記号が 50 個。 非終端記号が 27 個。 合わせて 27 × 50 = 1350 要素の表なのですけど、 ほとんど undef が占めている、すっかすかの疎配列です。 こ…

Text-Liq-XS/XS.c tokenize のマークアップ名認識部をダブル配列に変更

Text-Liq では XS ともども次のパターンで始まるものをマークアップとして認識し、これに出会うと、正規表現を切り替えてマークアップ内部のトークン切り出しをおこないます。 \{%\s* (?: assign | break | capture | case | comment | continue | cycle | e…

escape_html_once の XS 版

Text::Liq の評価器を XS で動かすなら、escape 処理も XS でオーバーヘッドなしでおこないたくなります。 Liquid では html escape は 2 種類あり、一つ目はエスケープするべき文字を必ずエスケープする処理で、二つ目はエスケープ済みの文字リファレンスを…

Text::Liq の XS 化 (途上)

Text::Liq の構文解析器は、C 言語のスタイルで記述してあるわけでして、XS にしたくなるのが自然でありましょう。⇒ https://github.com/tociyuki/libtext-liq-xs-perl5現況: parse XS 化は完了。 tokenize XS 化は完了。 render まだピュア Perl テストは T…

Text-Liq-0.01 - Liquid 風テンプレート・エンジン

Jekyll で使われている Ruby 用の Liquid マークアップ・テンプレートの構文を Ruby ソースから、なんとかフルスクラッチで BNF で書き下すことができたので、LL(1) 文法に変換し、予測分岐構文解析表を生成したものを、Perl で動くようにしてみました。 こ…

マーク&スイープ方式の記憶セット

Perl5 は参照カウンタでメモリ管理をしており、 循環参照を含むデータ構造を扱うときには、 メモリ・リークしないようにコーディングする必要があります。 Cache-Lrq では、 フリー・リストと使用中リストを一括して双方向リンクで管理し、 さらに参照を使わ…

PEG 手打ち用の小さなヘルパ Text-Derivs でも演算子優先順構文解析

「PEG 手打ち用の小さなヘルパ」で「演算子優先順位構文解析器」を使えるようにしました。⇒ https://gist.github.com/tociyuki/4743586 v0.04repeat_precedent がそれです。 優先順位ありの二項演算子で挟まれた記号列を構文解析します。 右および左結合の二…

PEG 手打ち用の小さなヘルパ

すっかり Parsing Expression Grammar (PEG) とバックトラック構文解析器および Packrat 解析器が手に馴染み、最近は、何であれ構文解析をしたいときは、とりあえず PEG の流儀で下向き解析することから手をつけるようになっています。そうしているうちに、…

List::Util の shuffle

配列要素シャッフルの定石は Fisher - Yates shuffle です。この手順は Knuth shuffle の通り名の方が目にすることが多いかもしれません。当初は配列全体に渡ってランダムに選んだ 2 つを入れ替え、徐々に入れ替え範囲を狭めていくというやりかたです。⇒ htt…

Cache::Lrq - LRU ハッシュによるプロセス内キャッシュ

車輪の再発明で、Least Recently Used (LRU) を使い Perl の配列オブジェクトでキャッシュをおこなうモジュールを作っていました。2013年1月30日修正: v0.02 へ。双方向リンクを使って書き換えました。v0.03 へ。_list をフラットにしました。⇒ https://gith…

Perl から git オブジェクトを覗く

git のオブジェクト・データベースはファイル・ベースのハッシュ・キー・バリュー・ストアになっています。2形式あり、キーをファイル名にしてエントリごとファイルに格納する単純なものと、複数のエントリをファイルにパックしたものとがあります。git の最…

BerkeleyDB モジュールの CDS 排他制御

Perl の BerkeleyDB モジュールで利用可能な Concurrent Data Store (CDS) による排他制御のサンプルを探してみたのですが、なかなかぴったりのが見つかりません。google によると、次のリンク先にあるプロセスを fork して排他制御動作をテストするコードが…

難読化テトリス perltris リーディング

本日は降雪なり。横浜では朝から大きなみぞれが地面めざして落下し続けてきました。窓のすぐ向こうを落下していくみぞれは大きくて形もいろいろです。朝方、ぼんやりと眺めていたら、テトリスが頭に思い浮かんでいました。ロシアでテトリスが生まれたのは、…

Module-Starter-Smart-0.0.4 を Module-Starter-PBP と連動させる

Module::Starter でモジュールを追加できるようにする Module::Starter::Smart プラグインの最新版 0.0.4 は、~/.module-starter/config の plugins に Module::Starter::PBP を並べていても、Module::Starter::Simple が動いてしまいます。 $ grep plugins …

ピュア Perl YAML 1.2 ローダ YAML-Loaf-0.01

YAML 1.2 のバックトラック解析器からフォークして、ローダを作ってみました。フルスペックの構文をディレクティブを除いて解釈可能ながら、コード行数 700 行程度で済んでいます。もっとも、行数が少ないのは型解析部に手を抜いているせいでもありますが………

YAML 1.2 のバックトラック構文解析器の部分メモライズ化

YAML 1.2 のバックトラック構文解析器の試作品の続きです。この間、バグ取りを進めつつ、構文規則の読み込みを続けてきました。そして、いったん諦めたメモライズを部分的におこなってみました。今のテストでは、メモライズ化前後でのふるまいは変わっておら…

YAML 1.2 のバックトラック構文解析器の試作品

試作品と念を押しているように、これの実用性はありません。テストが不十分で、受け付けるべき入力文字列はテスト済みですが、受け付けるべきでなく構文エラーとするべき文字列のテストの多くをはしょっています。しかも、この解析器がどのような有限入力文…

YAML 1.2 の BNF

YAML 1.2 仕様 http://www.yaml.org/spec/1.2/spec.html から BNF 部分を拾いだしたものを Gist に貼っておきます。⇒ YAML 1.2 BNF from Specification Web Page ― Gist仕様のウェブページをローカルに curl(1) コマンドでゲットしておいたものから、Web::Sc…

UTF-8 エンコーディングの差異まとめ YAML::XS、YAML::Syck、YAML::Old、YAML、YAML::Tiny

Perl の YAML::Any が対象にしている題に並べた 5 つの YAML モジュールの UTF-8 エンコーディング の扱いに、登場した当初から現在にいたるまで差異があり、単純に切り替えて使えないのが現状です。差があるのは仕方がないことで、それぞれの個性と割り切っ…

while ループによる File::Find::Norecursible

ガーベジコレクションやトポロジカルソートで散々書いてきたグラフのノード探索の応用として、Perl の添付モジュール Find::File の簡易版を書いてみます。 再帰呼び出しせず、while ループで深さ優先探索をします。 再帰呼び出ししていないので、croak で素…

Webページのページャ

一続きのエントリを順に並べてWebページ化したいけれど、エントリが大量にありすぎて複数のページに分割して「前へ」と「次へ」のリンクでページ間をつなげたいニーズが良くあります。さらに、近接するページへのリンクを横に並べて、真ん中に現在のページを…