読者です 読者をやめる 読者になる 読者になる

巻き舌できるようになった(たぶん)

これまで巻き舌ができなかったが、今日ふと試したらできるようになった。巻き舌といっても、舌を変な形にするほうではなく、Rの音を出すほう。

あんまり参考にならないかもしれないけど、一応どんな風にやったか書いておく

舌を意図的に動かす

ロシア語やイタリア語ではRを巻き舌にするのが普通(全員ができるわけではないので必須ではない)のようで、巻き舌ができなかった僕は次のように巻き舌を真似していた。

  • 巻き舌では舌は上の歯か歯茎あたりに触れる。このとき左右の側面で触れる方法と、舌の先で触れる方法がある。この2つの状態を切り替えるときにはじくような音が出る。
  • 声を出さずにやると、ボイスパーカッションみたいな感じになるので、これを繰り返すとルタルタルタルタルタルタ……という感じになる。
  • これに声を入れると、ルルルルルルルル……という感じになるので、これを高速に行うとそれっぽくなる。

気流で舌を動かす

上のように舌を動かす動作を、舌の筋肉ではなくて気流でやることを考える。

  • 舌と上の歯茎を完全に接触させると、口から空気を出せなくなる。その状態でさらに圧力を加えると、どこかに強制的に隙間があく。この時に、上記と同様にはじくような音が出る。
  • 気流を維持したまま、舌の筋肉を使って舌をもとの位置(舌と上の歯茎を完全に接触させた状態)に戻そうとする。うまくやると、上の動作が繰り返し起こる。
  • 先ほどと同様に、そのまま声を入れる。
  • この時、側面で触れている状態と、舌の先端で触れている状態を行ったり来たりするように意識する。
  • 気流だけで舌がうまく動くようにする。そのためには、それなりに勢いが必要である。気持ちとしては、Rの音をいきなり出すのではなく、予備動作として適当な母音(uとか)をちょっと入れて、そこから一気に息を吹きこみつつ舌を動かす感じでやるとうまくいくことがある。
  • うまくいくと巻き舌のRっぽくなる

ランサムウェアを作ってみた(シェルスクリプトで)

ランサムウェアの暗号化部分についての実証コードを書いてみた。暗号の計算にはOpenSSLのコマンドが使えるので、シェルスクリプトを使って書いた。

github.com

注意

  • このコードを試して起こった損害について作者は責任を追わない。基本的にdocuments/以下にあるテストファイルのみが操作対象だが、シェルスクリプトがザルなので空白を含むファイルなどが混ざっていると少し危いかもしれない。
  • このコードはランサムウェアの暗号化の動作を実証することを目的としたものであり、実際にランサムウェアなどのマルウェアに「応用」することを意図したものではない。もちろん、実際に身代金目的のランサムウェアを作って配布することは違法である可能性が高い。そもそも、このコードは暗号化部分の最低限の実装しかしていないので、実際にランサムウェアを作るにあたって役に立つことはほとんどないだろう。

はじめに

ランサムウェアは起動するとコンピューター内のファイルを暗号化し、復号を見返りに身代金を要求するマルウェアである。支払い後に実際に復号するものとそうではないものがあるらしいが、ここでは実際に復号能力があるものを考える。

ランサムウェアが作者の意図通りに動作するには、以下の条件を満たしてほしいだろう。

  • ランサムウェアの存在が発覚したあとは、そのランサムウェアは解析の対象となるが、それによって身代金なしにファイルを復号されてしまっては困る。
  • ランサムウェアの被害者ごとに、それぞれ身代金を支払ってほしい。
  • 復号時のクライアントとサーバーの通信は最小限に留めたい。

複数の暗号を組み合わせることでこれを実現できる。今回はそれを実証するコードを書いてみた。

仕組み

まず、ランサムウェアの作者は秘密鍵と公開鍵の鍵ペアを作成し、ランサムウェアには公開鍵のみを同梱する。この方法であれば、ランサムウェアが解析されても秘密鍵は復元できない。

この公開鍵を作ってファイルを暗号化することも可能だが、これには次の問題がある。

  • そもそも、公開鍵を使って大きなファイルを暗号化するのはコストが高くつく。
  • また、身代金が支払われたあとの復号の方法が問題になる。仮に秘密鍵を送るとすると、このランサムウェアは被害者1人が身代金を支払うだけで終わってしまう。
  • かといって、サーバー側でファイルを復号すると大量の通信が必要になる。

そこで、次のようにする。

  • ランサムウェアは起動したらまず新規に共通鍵を生成する。
  • 共通鍵を公開鍵で暗号化し、保存する。
  • メモリ上にある共通鍵を使って、ファイルを暗号化する。全ての暗号化が終わったら、共通鍵は捨てる。

被害者は身代金を支払う際に暗号化された共通鍵を添付する。ランサムウェアの作者はこれを手元の秘密鍵で復号して送り返す。ファイルの復号は手元で行うことができる。

使い方

RSAやAES-CBCなどの暗号はOpenSSLのコマンドとして用意されているため、このデモはシェルとOpenSSLがあれば動かすことができる。

まず、デモコードを取得する。

~$ git clone https://github.com/qnighy/ransomware-demo.git
~$ cd ransomware-demo
マスター鍵対を作成する
~/ransomware-demo$ ./genmaster.sh

これによってRSA鍵対が作成される。秘密鍵ランサムウェアの作者が保有し、公開鍵はランサムウェアに埋め込まれる。

ランサムウェアを実行する

ランサムウェアが配布され、被害者のコンピューター上で実行されたとする。

~/ransomware-demo$ cd client
~/ransomware-demo/client$ find documents
documents
documents/lipsum.txt
documents/hello.txt
~/ransomware-demo/client$ cat documents/hello.txt
Hello, world!
~/ransomware-demo/client$ ./encrypt.sh
~/ransomware-demo/client$ find documents
documents
documents/hello.txt.enc
documents/hello.txt.iv
documents/hello.txt.sha256
documents/lipsum.txt.enc
documents/lipsum.txt.iv
documents/lipsum.txt.sha256

この ./encrypt.shランサムウェアによる暗号化である。ここでは3つのことが起こっている。

  • バイスごとの共通鍵が作成される。
  • この共通鍵を使ってファイルが暗号化される。
  • 共通鍵はマスター鍵を使って暗号化される。
支払いとデバイス鍵の復元

ファイルを復号するためには、まずランサムウェアの作者に身代金を払ってデバイス鍵を復元する必要がある。

~/ransomware-demo/client$ ./decrypt.sh
device_key.dat not found. First pay for us!
~/ransomware-demo/client$ cp device_key_encrypted.dat ../server/
~/ransomware-demo/client$ mv ../server/
~/ransomware-demo/server$ ./decrypt-key.sh
~/ransomware-demo/server$ cp device_key.dat ../client/
~/ransomware-demo/server$ mv ../client/
復号

バイス鍵を復号したら、これを使ってファイルを復号できる。

~/ransomware-demo/client$ ./decrypt.sh
~/ransomware-demo/client$ find documents
documents
documents/lipsum.txt
documents/hello.txt
~/ransomware-demo/client$ cat documents/hello.txt
Hello, world!

まとめ

ランサムウェアにおけるファイルの暗号化は決して複雑ではないが、複数の暗号を組み合わせて実現されている。この記事では暗号化のOpenSSLのコマンドを使って、ランサムウェアがどのように暗号を組み合わせているかを示すデモを作成した。

とある偽シャッフルアルゴリズムとその分布

次のようなシャッフルアルゴリズムを考える(簡単のためrand()%Nと表記したが、この部分で0以上N-1未満の一様な整数乱数が生成されると仮定して議論する)。出力されるものは 0, ..., 255 を並び換えたもの(置換)である。

std::vector<int> a(N);
for(int i = 0; i < N; ++i) {
  a[i] = i;
}
for(int i = 0; i < N; ++i) {
  std::swap(a[i], a[rand()%N]);
}

このアルゴリズムは均一ではない。a[i]==jとなる確率は、 i < jのときに高くなり、j <= iのときに低くなる。グラフにすると以下のようになる。

f:id:qnighy:20160605175316p:plain

定理

上のシャッフルアルゴリズムで得られる aについて、 a[i]==jとなる確率は、

{
\begin{cases}
\frac{1}{N}\left(1-\frac{1}{N}\right)^{N-1-i} + \frac{1}{N}\left(1-\frac{1}{N}\right)^j - \frac{1}{N}\left(1-\frac{1}{N}\right)^{N-1-i+j} & j \leq i \\
\frac{1}{N}\left(1-\frac{1}{N}\right)^{N-1-i} + \frac{1}{N}\left(1-\frac{1}{N}\right)^j & i < j
\end{cases}
}

となる。

証明

2個目のループの本体が {t}{(0 \leq t \leq N)} 実行された時点で a[i]==j となる確率を {p_{t,i,j}} とおく。プログラムをジッと睨むと、以下の式を得る:

{
p_{0,i,j} = \begin{cases}
  1 & i = j \\
  0 & i \neq j
\end{cases}
}

{
p_{t+1,i,j} = \begin{cases}
  \frac{1}{N} \sum_{k=0}^{N-1} p_{t,k,j} & i = t \\
  \left(1-\frac{1}{N}\right)p_{t,i,j} + \frac{1}{N}p_{t,t,j} & i \neq t
\end{cases}
}

さらに、不変条件 {\sum_{k=0}^{N-1} p_{t,k,j} = 1} に注目すると、後者の式は

{
p_{t+1,i,j} = \begin{cases}
  \frac{1}{N} & i = t \\
  \left(1-\frac{1}{N}\right)p_{t,i,j} + \frac{1}{N}p_{t,t,j} & i \neq t
\end{cases}
}

となる。このとき、以下が成り立つことを示す。 {t=N} の場合が定理の主張に他ならない。

{
p_{t,i,j} = \begin{cases}
  \frac{1}{N}\left(1-\frac{1}{N}\right)^{t-1-i} + \frac{1}{N}\left(1-\frac{1}{N}\right)^j - \frac{1}{N}\left(1-\frac{1}{N}\right)^{t-1-i+j} & j \leq i < t \\
  \frac{1}{N}\left(1-\frac{1}{N}\right)^{t-1-i} + \frac{1}{N}\left(1-\frac{1}{N}\right)^j & i < j < t \\
  \frac{1}{N}\left(1-\frac{1}{N}\right)^j & j < t \leq i \\
  \frac{1}{N}\left(1-\frac{1}{N}\right)^{t-1-i} & i < t \leq j \\
  \left(1-\frac{1}{N}\right)^t & t \leq i = j \\
  0 & t \leq i, t \leq j, i \neq j
\end{cases}
}

{t} に関する帰納法で示す。まず、 {p_{0,i,j}} が上記を満たすことはすぐにわかる。

{i,j} について {p_{t,i,j}} が上記を満たすと仮定する。このとき、各 {i,j} について {p_{t+1,i,j}} も上記を満たすことを示す。そのために以下のように場合分けをする。

  • {j \leq i < t} のとき。
  • {j \leq i = t} のとき。
  • {i < j < t} のとき。
  • {i < j = t} のとき。
  • {i < t < j} のとき。
  • {i = t < j} のとき。
  • {j < t < i} のとき。
  • {j = t < i} のとき。
  • {t < i = j} のとき。
  • {t < i, t < j, i \neq j} のとき。

各場合分けは簡単な式変形で示せる。

正しいアルゴリズム

例えば、以下のようにする。(別途、rand()%(i+1)の部分をより適切な擬似乱数に置き換える必要がある。)

std::vector<int> a(N);
for(int i = 0; i < N; ++i) {
  a[i] = i;
}
for(int i = 0; i < N; ++i) {
  std::swap(a[i], a[rand()%(i+1)]);
}

この方法の場合、2個目のループ本体が {t} 回実行された時点で a[0], ..., a[t-1] が一様にランダムな置換になっていることが保証できる。

このアルゴリズムKnuth shuffleとかFisher-Yates shuffleと呼ばれている。

相関に関する補足

この記事では偽シャッフルアルゴリズムについて、要素ごとの確率分布に注目して解析したが、これだけでは不十分な場合もある。例えば、以下のアルゴリズムは明らかに正しくないシャッフルアルゴリズムだが、要素ごとの確率分布は一様である。

std::vector<int> a(N);
int s = rand()%N;
for(int i = 0; i < N; ++i) {
  a[i] = (i+s)%N;
}

C/C++の静的解析ツール・事例まとめ

C/C++の静的解析は、どう考えても大変なんだけどどう考えても需要が高いので、やはり色々なソフトウェアや事例があるようだ。まとまった情報が欲しいけど見つからなかったので自分の調べた範囲でまとめることにした。

他にも耳寄りな情報があったら教えてほしい。

静的解析を行うことができるソフトウェア

調べてみると結構たくさんある。それぞれの特徴とかあまりよくわからない。

(個人的には、とりわけ網羅的な形式的検証ができるツールの性能に興味があるので、それを中心に集めていたが、やはり網羅的とは限らないで探すともっとたくさん見つかるようだ。もちろん網羅性にはトレードオフがある)

  • Frama-C …… C言語に形式手法を適用するための汎用のフレームワークで、静的検証のためのプラグインも多数(WPとかValueとか)存在する。網羅的な検証から発見的な手法、動的な手法まで様々ある。研究で使うのに便利そう
  • Astrée Runtime Error Analyzer …… 飛行機などミッションクリティカル環境を主に想定した網羅的な静的分析器のようだ。昔のページ→The Astrée Static Analyzerを見ると、再帰と動的メモリ確保のないプログラムを対象としていたようだが、現在は再帰のないプログラムなら動的メモリ確保があっても検査できるようだ。フランスのINRIAとかその辺が関わっていそうな雰囲気がある
  • VCC …… 名前に "concurrent" が含まれていたり、並行性が何かとプッシュされているように見える。codeplexに置いてあるしMSRかな
  • SLAyer …… 最近MSが出したらしい。これも分離論理でメモリ安全性を調べるパターン(なので網羅性あるのかな)。
  • VeriFast …… これもCのプログラムが検証できるらしい。
  • Escher C/C++ Verifier …… 説明を見る限り、網羅的な検査をすると言っているように読める。C++も検証できると主張しているので強そう。会社概要を見る限り、これが主力商品のようだ
  • Infer …… Facebookが買収したことで有名。分離論理使うくらいだから何らかの意味で網羅的なんだろうか。一般的なC/C++プログラムを検証できそうな雰囲気
  • CBMC …… 有界モデル検査をするツールのようだ
  • CodeSonar …… Z3使うらしい(ということはwhite-box testingとかかな)。網羅的とは書いていないように見えるので発見的な手法かな
  • Coverity …… これも静的解析ツールとしては強いらしい。網羅性はパッと見では確認できなかった ← grafiさんが紹介してくれた記事にunsoundと書いてあった
  • QAC …… これも網羅性は確認できなかった

余裕があれば上記のソフトウェアを以下のような観点から整理したい。

  • 標準準拠 …… 言語仕様である ISO C, ISO C++. POSIXの仕様であるSUSやThe Open Group Specification. コーディング標準であるCWE, CERT C, MISRA-C. 安全性の規格であるDO-178B level A, ISO 26262, IEC 61508. ……などがあるらしいので、それぞれへの対応度を調べる。
  • 網羅性 …… 一部の静的解析ツールは、ある種の問題(例えば実行時エラー)がないことを保証できる場合がある。例えばAstréeのページにはsound(健全)という言葉があるが、これはこの網羅性をあらわしている。
  • 精度と再現率 …… 実際の問題に適用したときには、見つけられなかったバグの数や誤検出された問題の数が重要になると考えられる。
  • 適用可能なプログラムの範囲 …… Astréeは再帰のないプログラムに限定して検証すると書かれている。このように、適用対象を絞ることで高性能な静的解析を提供している場合があるようだ。
  • 適用可能なアサーションの表現力 …… プログラムにコメントでアサーションを入れるタイプの静的解析ツールでは、そのアサーションの表現力に違いがあるかもしれないので、その辺りを調べる。また、そうでない静的解析ツールでは、発見できるバグの種類がこれに相当すると考えられる。

検証済みコンパイラ

コンパイラ自体が(主に最適化まわりで)バグってることはたまにあるので、ミッションクリティカルな用途ではコンパイラ自体の正しさも気になるという事情があるようだ。

  • CompCert …… Astréeと同じあたりが作ってるやつ。

プログラミング言語の形式仕様

C言語のプログラムやコンパイラに関して正確に論証したいとなるとそもそも仕様が必要になるが、ここで紹介しているのがまさにそれだ。

  • Verifiable C …… Coqで書かれたC言語の仕様。便利そう。CompCertの正しさはこの仕様と照らしあわせて検証されている。

動的検査するやつ

静的解析ではないような気がするけど。

更新履歴

latexmk設定メモ

LaTeX文書のコンパイルをよしなにやってくれるlatexmkについて。

全体設定である ~/.latexmkrcには以下のように記入してある。

#!/usr/bin/env perl

$pdf_mode = 3;
$latex = 'uplatex -kanji=utf8 -synctex=1 -file-line-error -halt-on-error -interaction=nonstopmode %O %S';
$bibtex = 'upbibtex %O %B';
$dvipdf = 'dvipdfmx %O -o %D %S';

$biber = 'biber --bblencoding=utf8 -u -U %O %S';
$makeindex = 'mendex %O -o %D %S';

$pvc_view_file_via_temporary = 0;
$pdf_previewer = 'SumatraPDF -reuse-instance'

この設定は、ディレクトリごとの.latexmkrcで上書きできる。

運用

ディレクトリごとに.latexmkrcを置いて作業している。上の設定ファイルのうちビューワー設定以外の部分を、各状況にあわせて変更して使っている。

  • latexmk pdfを作りたいだけのとき
  • latexmk -pvc 継続ビルド。pdfを見ながら編集したいとき
  • latexmk -pvc document.tex 上に同じ、ただしカレントディレクトリに*.tex複数あるときはこのように指定する

ビューワー設定

$pvc_view_file_via_temporary = 0;
$pdf_previewer = 'SumatraPDF -reuse-instance'
  • $pvc_view_file_via_temporary ... latexmk -pvc でPDFを作成するとき、既定では一時ファイルに出力してから目的のファイルに移動する仕様になっているが、この設定ではこれを0にしている。
  • $pdf_previewer ... Adobeなどファイルをロックするビューワーは使わないほうがよいだろう。この環境ではSumatraPDFにパスを通しているが、普通はフルパスを指定する

各種latexに共通のオプション

$latex = 'uplatex -kanji=utf8 -synctex=1 -file-line-error -halt-on-error -interaction=nonstopmode %O %S';
  • -synctex=1 ... *.synctex.gzを生成する。
  • -file-line-error ... エラー出力がわかりやすくなるらしい。
  • -interaction=nonstopmode ... 文法エラーなどのときにユーザーに尋ねなくなる。
  • -halt-on-error ... ファイルが存在しないなどのときにユーザーに尋ねなくなる。

特に最後の2つは、継続ビルドして作業するのには必須だろう

なお、%O %Sはそれぞれオプションとソースファイルを表す。コマンド指定系の変数では、%が全くない場合は自動的に適切なものが付与される。位置を変えたら何故か-interaction=nonstopmodeが効かなくなったので上のような順番がよいだろう。

latexごとの設定

生成経路に応じて数パターンあるが、ここではtex→dvi→pdfの場合と、tex→pdfの場合を書く。$pdf_modeが生成経路を指定している。

tex→dvi→pdf

uplatexを使う例。

$pdf_mode = 3;
$latex = 'uplatex -kanji=utf8 -synctex=1 -file-line-error -halt-on-error -interaction=nonstopmode %O %S';
$bibtex = 'upbibtex %O %B';
$dvipdf = 'dvipdfmx %O -o %D %S';

dvipdfdvipdfm(x)ではオプションの順序が違うらしいので注意

tex→pdf

lualatexを使う例。(upbibtexにしない理由があるらしいが、こちらでは肯定的にも否定的にも未確認)

$pdf_mode = 1;
$pdflatex = 'lualatex -synctex=1 -file-line-error -halt-on-error -interaction=nonstopmode %O %S';
$bibtex = 'pbibtex %O %B';

auxdirについて

-auxdir / $aux_dir というオプションがあり、これを使うと各種の中間生成物の場所を別のディレクトリにできるような気がしてくるが、これは半分正しくない。現在はこのオプションが有効なのはMikTeX版のlatex系コマンドだけらしいので、残念ながら避けるのが無難だろう。

volatileとatomicの違い

volatileとatomicの違いを調べるために、以下のC++プログラムをコンパイルしてみる。

#include <atomic>

void func1(int *p) {
  ++*p; ++*p;
}

void func2(volatile int *p) {
  ++*p; ++*p;
}

void func3(std::atomic_int *p) {
  ++*p; ++*p;
}
$ g++ -std=c++11 -pthread -O2 -Wall -Wextra -g -c func.cpp -o func.o

環境による可能性はあるが、出力された機械語は端的に言うと次のようなものになる。(なおアーキテクチャLinux x86-64)

func1:
	addl	$2, (%rdi)
	ret
func2:
	movl	(%rdi), %eax
	addl	$1, %eax
	movl	%eax, (%rdi)
	movl	(%rdi), %eax
	addl	$1, %eax
	movl	%eax, (%rdi)
	ret
func3:
	lock addl	$1, (%rdi)
	lock addl	$1, (%rdi)
	ret
  • func1 は、「2を足す」という動作をしている。
  • func2 は、「メモリから読み込んで1を足して書き込む」という動作を2回している。
  • func3 は、「lockしながら1を足す」という動作を2回している。

これは以下の違いによる:

  • volatile は、メモリの読み込みや書き込みを、副作用を伴う動作と見なす。*1 そのため、読み込みや書き込み動作を減らす最適化を行わない。ただし、回数や順番さえ合っていればよいので、他のスレッドに干渉されるかどうかは考えない。
  • atomic は、他のスレッドが同時に読み書きしようとしても、あるひとまとまりの動作の間は独占的に動作するような振舞いになる。x86の場合はlockプレフィックスで実現できる。

動作確認

この動作は以下のプログラムで確認できる。

#include <cstdio>
#include <atomic>
#include <thread>

void func1(int *p);
void func2(volatile int *p);
void func3(std::atomic_int *p);

void count1(int *p) {
  for(int i = 0; i < 1000000; ++i) {
    func1(p);
  }
}

void count2(volatile int *p) {
  for(int i = 0; i < 1000000; ++i) {
    func2(p);
  }
}

void count3(std::atomic_int *p) {
  for(int i = 0; i < 1000000; ++i) {
    func3(p);
  }
}

int main(int argc, char *argv[]) {
  int num = -1;
  if(argc > 1) {
    std::sscanf(argv[1], "%d", &num);
  }
  if(num == 1) {
    int x = 0;
    std::thread th0(&count1, &x);
    std::thread th1(&count1, &x);
    th0.join();
    th1.join();
    std::printf("%d\n", x);
  } else if(num == 2) {
    volatile int x = 0;
    std::thread th0(&count2, &x);
    std::thread th1(&count2, &x);
    th0.join();
    th1.join();
    std::printf("%d\n", x);
  } else if(num == 3) {
    std::atomic_int x = ATOMIC_VAR_INIT(0);
    std::thread th0(&count3, &x);
    std::thread th1(&count3, &x);
    th0.join();
    th1.join();
    std::printf("%d\n", (int)x);
  }
  return 0;
}
$ g++ -std=c++11 -pthread -O2 -Wall -Wextra -g -c main.cpp -o main.o
$ g++ -std=c++11 -pthread -O2 -Wall -Wextra -g func.o main.o -o main
$ ./main 1
2497250
$ ./main 1
2432386
$ ./main 1
3136510
$ ./main 1
2411326
$ ./main 1
3466956
$ ./main 1
2367656
$ ./main 1
2297168
$ ./main 2
2324260
$ ./main 2
3137164
$ ./main 2
2374254
$ ./main 2
2627152
$ ./main 2
2593840
$ ./main 2
2871581
$ ./main 2
2218822
$ ./main 2
2617198
$ ./main 3
4000000
$ ./main 3
4000000
$ ./main 3
4000000
$ ./main 3
4000000
$ ./main 3
4000000
$ ./main 3
4000000
$ ./main 3
4000000

これはマルチコアの動作結果に関わるので環境によって異なる動作をするかもしれない。手元の環境はVirtualBoxで仮想化されたLinux x86-64であった。

atomicでは不十分な場合もある

atomicで一まとまりの動作と見なされる範囲はごく小さい。例えば*pが偶数であったとすると、以下の関数を繰り返し実行しても*pの値が変わらないことが意図される(シングルスレッドではそうなる)が、マルチスレッドではそうはならない。

#include <atomic>

void func(std:atomic_int *p) {
  *p += 1;
  *p ^= 1;
}

このような場合は単に*pをatomicにするだけでは不十分だが、mutexなどを使えばうまくいく。

*1:これはマルチスレッドのための仕組みというよりも、Memory-Mapped I/Oなどでメモリの読み書きが動作を伴う場合が想定されていると思われる。

文脈自由文法(CFG)と解析表現文法(PEG)をHaskellのモナドで説明する話

Haskell

文脈自由文法(Context Free Grammar) と 解析表現文法(Parsing Expression Grammar) は記法が似ているものの、その性質は大きく異なっている。しかし、以下のようにHaskellモナドを用いて、左再帰的でない文脈自由文法をそのままパーサーコンビネーターとして変換すると、PEGはList monadをMaybe monadとして置き換えたものとして説明できる。

-- CFGとPEGの関係を List vs. Maybe として説明するサンプル

import Control.Monad
import Control.Monad.State

-- 型の説明 : StateT String m a
-- StateT String ... 構文解析の残りの文字列を記憶している。
-- m ... 正否をあらわす。ListにするとCFG, MaybeにするとPEGになる
-- a ... 今回は構文解析の正否のみに興味があるので () にする。

-- 演算子の説明
-- A >> B ... 構文要素の連接を表す。
-- A `mplus` B ... 構文要素の選択を表す。

-- CFG/PEG共通 : 指定した1文字を読む。
readChar :: MonadPlus m => Char -> StateT String m ()
readChar ch = do
  (ch0:str) <- get
  guard $ ch0 == ch
  put str

-- CFG/PEG共通 : 文字列の終端か検査する。
eof :: MonadPlus m => StateT String m ()
eof = do
  [] <- get
  return ()

-- 文法その1
-- S -> A $
-- A -> "a" A "a" | "a"
a :: MonadPlus m => StateT String m ()
a = (readChar 'a' >> a >> readChar 'a')
    `mplus` readChar 'a'

grammar1 :: MonadPlus m => StateT String m ()
grammar1 = a >> eof


-- 文法その2
-- S -> B $
-- B -> "a" B "a" | "b" B "b" | ""
b :: MonadPlus m => StateT String m ()
b = (readChar 'a' >> b >> readChar 'a')
    `mplus` (readChar 'b' >> b >> readChar 'b')
    `mplus` return ()

grammar2 :: MonadPlus m => StateT String m ()
grammar2 = b >> eof


-- 文法を(左再帰的でない)CFGとして検査する
checkCFG :: StateT String [] () -> String -> Bool
checkCFG grammar str = runStateT grammar str /= []

-- 文法をPEGとして検査する
checkPEG :: StateT String Maybe () -> String -> Bool
checkPEG grammar str = runStateT grammar str /= Nothing


main :: IO ()
main = do
  forM_ [
      "",
      "a",
      "aa",
      "aaa",
      "aaaa",
      "aaaaa",
      "aaaaaa",
      "aaaaaaa"
    ] (\str -> do
      putStrLn $ "checkCFG grammar1 " ++ show str ++ " = " ++ show (checkCFG grammar1 str)
      putStrLn $ "checkPEG grammar1 " ++ show str ++ " = " ++ show (checkPEG grammar1 str)
    )
  forM_ [
      "aa",
      "abba",
      "bbbbbb",
      "baaaab"
    ] (\str -> do
      putStrLn $ "checkCFG grammar2 " ++ show str ++ " = " ++ show (checkCFG grammar2 str)
      putStrLn $ "checkPEG grammar2 " ++ show str ++ " = " ++ show (checkPEG grammar2 str)
    )

実行結果

checkCFG grammar1 "" = False
checkPEG grammar1 "" = False
checkCFG grammar1 "a" = True
checkPEG grammar1 "a" = True
checkCFG grammar1 "aa" = False
checkPEG grammar1 "aa" = False
checkCFG grammar1 "aaa" = True
checkPEG grammar1 "aaa" = True
checkCFG grammar1 "aaaa" = False
checkPEG grammar1 "aaaa" = False
checkCFG grammar1 "aaaaa" = True
checkPEG grammar1 "aaaaa" = False
checkCFG grammar1 "aaaaaa" = False
checkPEG grammar1 "aaaaaa" = False
checkCFG grammar1 "aaaaaaa" = True
checkPEG grammar1 "aaaaaaa" = True
checkCFG grammar2 "aa" = True
checkPEG grammar2 "aa" = True
checkCFG grammar2 "abba" = True
checkPEG grammar2 "abba" = True
checkCFG grammar2 "bbbbbb" = True
checkPEG grammar2 "bbbbbb" = True
checkCFG grammar2 "baaaab" = True
checkPEG grammar2 "baaaab" = False

文法の例として挙げたもの

S -> A
A -> "a" A "a"
A -> "a"

このCFGは奇数個のaからなる文字列を受理する。

S <- A
A <- "a" A "a"
   / "a"

このPEGは(2の冪-1)個のaからなる文字列を受理する。

S -> B
B -> "a" B "a"
B -> "b" B "b"
B -> ε

このCFGはaとbからなる偶数文字の回文を受理する。

S <- B
B <- "a" B "a"
   / "b" B "b"
   / ε

このPEGはよくわからないが回文でも受理しない場合がある。(上の実行結果を見よ。)