いつものようにチェスでもするかと、 Windows Vista のスタートメニューの「ゲーム」フォルダを開いてみると
Stream: Dark Messiah Might and Magic :Single Player
という見知らぬタイトルのアイコンが転がっていました。 こんなゲーム入れた覚えないので、 これはゲームの振りして起動させようとするトロイの木馬か何か入れてしまったか…と青くなりながら調べてみると、 こんな2chでの書き込みが引っかかりました。
【DMMM】 Dark Messiah of Might and Magic その7
147 ：UnnamedPlayer：2010/05/23(日) 01:37:15 ID:V/DFzC7D
先ほど知らないうちにWindows 7 (64bit)のゲームフォルダに
Stream: Dark Messiah Might and Magic :Single Player
っていうのがインストールされているのに気づいたんですが
これはウイルスかなんかだろうか。どうやっても削除できない...
148 ：UnnamedPlayer：2010/05/23(日) 01:50:35 ID:V/DFzC7D
自己解決しました
mm.exeという名前のプログラムを一度でも実行すると関係なくても
ゲームにDark Messiah of Might and Magicして登録されるみたいです
Windows 7 適当すぎる
えええー！
たしかに昨日、TCO10 Marathon Match 用のコードにメチャいい加減に mm.cpp と名前をつけてコンパイルして実行してたので、mm.exe という名前には大いに心当たりがありますが…。 私の環境以外でも、幾人かに試してもらってみたところ、7 や Vista で確かに再現するらしい。 Microsoft Answers にも報告 あがっているとのこと。
setup や install という名前の実行ファイルが特別扱いされるという話は聞いていましたが、 こんな風に具体的な製品決め打ちでファイル名判別をしていたりもするんですね。"mm.exe" 以外にもあるのかな。 いやはやビックリしました。
※ 試してみる方へ： mm.exe と見るとNorton先生に消されるという事があるそうなので、大事なソフトをちょっとリネームとかで試さないように注意してください。 試し終わった後にゲームフォルダから消すには、mm.exeを削除すれば自動的にゲームフォルダ側も消える みたいです。
上昇型構文解析 （演算子順位法やLALR(1)法） の説明って、 よく見かけるものはどれも、なんだか既に最適化された状態から始まっていて、 基本的な考え方がわかりにくくなっている気がします。 というわけで、効率などをあんまり考えずにてきとーに手書きした状態でアイデアを語る試み。
（※see also: 『構文解析の話をしよう』）
式 ::= 式+式 | 式-式 | (式) | 数字
足し算と引き算しかない、簡単な文法から。 入力文字列がこの文法にあってるかどうかチェックするルーチンを作ろうと思います。 大事なこととして、上昇型パーザの基本原則はこれだけです： 「１文字ずつ順番に読んでって、文法規則の右辺が見えたら即座に左辺に置き換えろ！！」
# Ruby 1.9
def is_expression(input)
s = "" # s に１文字ずつ読み込みます
loop do
puts "DEBUG> "+s
case s # s の形によって分岐
when /式\+式$/;
s = $` + "式" # 式+式 を見たら 式 に置き換える
when /式\-式$/
s = $` + "式" # 式-式 を見たら 式 に置き換える
when /\(式\)$/
s = $` + "式" # (式) を見たら 式 に置き換える
when /\d$/
s = $` + "式" # 数字 を見たら 式 に置き換える
else
if input[0]
s << input[0] # 次の１文字を読み込む
input = input[1..-1]
else
return s == "式" # 全部読み終わって、全体が 式 ならOK
end
end
end
end
はい、できました。正規表現や Ruby に詳しくない方向けの補足ですが、/...$/ という正規表現は、
文字列 s の「末尾に」マッチするかどうか調べるという意味です。
「右辺が見えたら [即座に] 左辺に置き換え」るので、末尾の出現だけを調べています。
s = $` + "式" の $` は「正規表現にマッチした部分より前にあった文字列」を指します。
ので、このコード例だと、マッチした部分より前はそのまま残して、マッチ部を "式" に置き換えてることになります。
p is_expression("1+(2-3)")
DEBUG>
DEBUG> 1
DEBUG> 式
DEBUG> 式+
DEBUG> 式+(
DEBUG> 式+(2
DEBUG> 式+(式
DEBUG> 式+(式-
DEBUG> 式+(式-3
DEBUG> 式+(式-式
DEBUG> 式+(式
DEBUG> 式+(式)
DEBUG> 式+式
DEBUG> 式
true
p is_expression("1+2--3")
DEBUG>
DEBUG> 1
DEBUG> 式
DEBUG> 式+
DEBUG> 式+2
DEBUG> 式+式
DEBUG> 式
DEBUG> 式-
DEBUG> 式--
DEBUG> 式--3
DEBUG> 式--式
false
簡単ですね。
式 ::= 式+式 | 式-式 | 式*式 | 式/式 | (式) | 数字
掛け算と割り算が増えました。しかし、いくら規則が増えても 「右辺を見たら左辺に置き換える」 これだけです。 ２行増やして下さい。
when /式\*式$/
s = $` + "式" # 式*式 を見たら 式 に置き換える
when /式\/式$/
s = $` + "式" # 式/式 を見たら 式 に置き換える
できました。
…と、これだけではちょっと酷いと思われるかもしれません。 実は、ここまでの例に使った文法はあいまいで、演算子の結合方向や優先順位を考えていませんでした。 考えるようにしましょう。再帰下降パーサだと、文法をもっと詳細にして
式 ::= 項+式 | 項-式 | 項 項 ::= 因子*項 | 因子/項 | 因子 因子 ::= | (式) | 数字
こんな風にしたりすることが多いのですが、面倒なのでやりません。 こうします： 「文法規則の右辺が見えたら、そこに括弧をつけても意味が変わらな時だけ、即座に左辺に置き換えろ！！」。 例えば足し算の式の場合…
when /式\+式$/
s = $` + "式"
今は無条件で置き換えちゃってますが、もし入力が "式+式 * 式" だったとしたら。 これは "(式+式) * 式" とは意味が違います。なので、ここは置き換えをぐっと我慢しなければいけません。 次の１文字を見て判断します。
when s=~/式\+式$/ && !"*/".include?(input[0])
s = $` + "式"
こんな感じで。後ろに、自分より優先度の高い掛け算や割り算が来てない場合だけ置き換えます。
後ろに来ているのが + や - ならば、つまり (式+式)-..
という状態ならば、括弧をつけても意味が変わらないので大丈夫。
終端の扱いだけ気をつけて、全体はこんな感じ。
def is_expression(input)
s = "" # s に１文字ずつ読み込みます
loop do
puts "DEBUG> "+s
x = input[0] # 次の１文字
case
when s=~/式\+式$/ && !(x && "*/".include?(x))
s = $` + "式" # 式+式 を見たら 式 に置き換える
when s=~/式\-式$/ && !(x && "*/".include?(x))
s = $` + "式" # 式-式 を見たら 式 に置き換える
when s=~/式\*式$/
s = $` + "式" # 式*式 を見たら 式 に置き換える
when s=~/式\/式$/
s = $` + "式" # 式/式 を見たら 式 に置き換える
when s=~/\(式\)$/
s = $` + "式" # (式) を見たら 式 に置き換える
when s=~/\d+$/ && !(x && "0123456789".include?(x))
s = $` + "式" # ついでに複数桁の数字に対応
# 普通は構文解析の前に字句解析を通すので、
# 複数桁の数字みたいなものは１つにまとまってくるはずでこんなのはここでは必要ないのですが
else
if x
s << x # 次の１文字を読み込む
input = input[1..-1]
else
return s == "式" # 全部読み終わって、全体が 式 ならOK
end
end
end
end
実行例。置き換えのかかり方の違いがわかりますでしょうか。
p is_expression("1+23*45")
DEBUG>
DEBUG> 1
DEBUG> 式
DEBUG> 式+
DEBUG> 式+2
DEBUG> 式+23
DEBUG> 式+式
DEBUG> 式+式*
DEBUG> 式+式*4
DEBUG> 式+式*45
DEBUG> 式+式*式
DEBUG> 式+式
DEBUG> 式
true
p is_expression("1/2-3")
DEBUG>
DEBUG> 1
DEBUG> 式
DEBUG> 式/
DEBUG> 式/2
DEBUG> 式/式
DEBUG> 式
DEBUG> 式-
DEBUG> 式-3
DEBUG> 式-式
DEBUG> 式
true
左結合だけでなく右結合の演算子もある場合は、
s=~/式=式$/ && !(x && "+-*/=".include?(x))
のように、自分自身が右に来る場合も括弧つけちゃいけないので、それを考慮。
もっと色々と演算子を増やす場合は、 演算子の強さを表にしておいて、
まとめて /式([+-*/])式$/ && precedence_left[$1] >= precedence_right[x]
のような条件式１個で判定すると楽ちんです。
上昇型パーサの考え方は、これだけです。 ややこしいことは何もないのである。
例としてあげたコードを本当にそのまま使うと、 さすがに毎回正規表現で s を全部走査したりしてるので非効率的ですが、 その辺はどうせ末尾の3文字とかしか見てないわけなので、適宜なんとかする感じで。
式 ::= 式+式 | 式-式 | 式*式 | 式/式 | <式> | (式) | 数字
話が多少ややこしくなるのは、同じようなトークンや構文が文脈によって違う使われ方をするケースです。 ちょっと人工的ですが、< と > でくくるたびに +- と */ の優先順位が逆転するような文法のパーザを考えてみる。
ODD = /([^<]*<[^<]*)([^<]*<[^<]*<[^<]*)*/
...
when s=~/<式>$/; s = $` + "式"
# 奇数個の < の中なら優先順逆転
when s=~/^(#{ODD})式\+式$/; s = $1 + "式"
when s=~/^(#{ODD})式\-式$/; s = $1 + "式"
when s=~/^(#{ODD})式\*式$/ && !(x && "+-".include?(x)); s = $1 + "式"
when s=~/^(#{ODD})式\/式$/ && !(x && "+-".include?(x)); s = $1 + "式"
# そうでなければ普通に
when s=~/式\+式$/ && !(x && "*/".include?(x)); s = $` + "式"
when s=~/式\-式$/ && !(x && "*/".include?(x)); s = $` + "式"
when s=~/式\*式$/; s = $` + "式"
when s=~/式\/式$/; s = $` + "式"
こんな感じに、↑単に右辺の形で正規表現マッチするだけじゃなくて、文脈まで見て分岐する感じにするか。
normal = true
loop do
...
case
when !normal && s=~/式\+式$/; s = $` + "式"
when !normal && s=~/式\-式$/; s = $` + "式"
when !normal && s=~/式\*式$/ && !(x && "+-".include?(x)); s = $` + "式"
when !normal && s=~/式\/式$/ && !(x && "+-".include?(x)); s = $` + "式"
when normal && s=~/式\+式$/ && !(x && "*/".include?(x)); s = $` + "式"
when normal && s=~/式\-式$/ && !(x && "*/".include?(x)); s = $` + "式"
when normal && s=~/式\*式$/; s = $` + "式"
when normal && s=~/式\/式$/; s = $` + "式"
...
else
if x
normal = !normal if x=="<" || x==">"
s << x
なんか適当にモード切り替えするとか。これbool変数じゃなくてstrategyパターンみたいにすれば、 もっとモジュール分けされた感じに書けるようになりますがだんだん再帰下降パーサに近づきます。
p is_expression("<1+2*3>+(1+2*3)")
DEBUG>
DEBUG> <
DEBUG> <1
DEBUG> <式
DEBUG> <式+
DEBUG> <式+2
DEBUG> <式+式
DEBUG> <式 # 足し算が先に結合してる
DEBUG> <式*
DEBUG> <式*3
DEBUG> <式*式
DEBUG> <式
DEBUG> <式>
DEBUG> 式
DEBUG> 式+
DEBUG> 式+(
DEBUG> 式+(1
DEBUG> 式+(式
DEBUG> 式+(式+
DEBUG> 式+(式+2
DEBUG> 式+(式+式
DEBUG> 式+(式+式*
DEBUG> 式+(式+式*3
DEBUG> 式+(式+式*式
DEBUG> 式+(式+式 # 掛け算が先に結合してる
DEBUG> 式+(式
DEBUG> 式+(式)
DEBUG> 式+式
DEBUG> 式
true
もーちょい現実にありそうな例だと、
文 ::= 式; | { 文* } | if ( 式 ) { 文* } | ...
「文のまとまりを { } で囲っても一つの文として扱われるんだけど、特に if 文のボディとしてはこれが必須」
みたいな文法を作ったときに、文脈を見ずに "{ 文* }" を "文" にしちゃうとマズい、とか。
おおざっぱに、教科書とかに書いてある手法との対応関係。
最初の２つの例みたいに、演算子の優先順位のみの比較で置き換えたり置き換えなかったりを決める方法が、
だいたい 「演算子順位法」 のやってることです。ちゃんと効率的に言うならスタックがどうとか、<.
と .> みたいな謎括弧を考えてどうとかやりますが、
まあ要するに「括弧つけていいなら右辺を左辺に置き換え」をやってるだけです。
というか、上のコードの s がスタックですね。
LR(0) や SLR(1) や LALR(1) は、厳密には、ここでやったように優先順位でその場で判断するのではなくて、 文法の方を厳密にして、あいまいさが発生しないようにした文法を使って構文解析する手法になりますが、 最終的に構文解析時に起きることはだいたい同じなので気にしない方向でざっくり行くと：
/^#{ODD}式\+式$/」
みたいに、前の方の文脈を見る正規表現を使っても構いません。
if ( 式 ) { 文* } の例だと先読み無しで文脈がいる例になると思う。
純粋な演算子順位法に対して強いのはその辺。
/^#{ODD}... のような文脈情報と先読み情報を組み合わせて
（文脈によって先読みによる分岐パターンを変えて）使うのが「LALR(1)」や「LR(1)」、
それをしないのが「SLR(1)」。
全体としては文脈情報と先読みをどっちも使うけど同時には使わないなら SLR(1) でいいです。
<式> の例がこの違いになっているかな、
と思ったけど厳密に言うとなってないかもしれない（演算子の優先順を使わないで書き直すとSLR(1)でも書けてるかも）
けど細かいことは気にしないことにするとだいたいそんな感じ。
LR(1) と LALR(1) の違いは、今回の説明の仕方だと「どれだけ真剣に正規表現書くかの違い」と言うしかない…
さて、ここまでは is_expression という
「文法的に正しいかどうか判定するだけ」
の関数を実装してきました。
なぜ、例えば「式の値を計算する」のような実際に使いそうな処理を実装しなかったかというと、
めんどうだったからです。
じゃなくて、
文字列以外の物に正規表現＆パターンマッチができない言語だと、
格好良く書くのがなかなか難しかったからです。
しかしパターンマッチだけでもあればそれなりになんとか、 ということで、 mame氏の「Rubyでパターンマッチ」 を借りてやってみます。 mas454 さんの改造Ruby もおすすめです。
要は、単に "式" に置き換えるんじゃなくて、["式", その式の計算結果の値] に置き換えるだけ。
require 'case_class'
include CaseClass
def compute(input)
s = []
loop do
x = input[0]
case
when [["式",a=_],"+",["式",b=_]]===s.last(3) && !(x && "*/".include?(x))
s.pop(3); s << ["式",a+b]
when [["式",a=_],"-",["式",b=_]]===s.last(3) && !(x && "*/".include?(x))
s.pop(3); s << ["式",a-b]
when [["式",a=_],"*",["式",b=_]]===s.last(3)
s.pop(3); s << ["式",a*b]
when [["式",a=_],"/",["式",b=_]]===s.last(3)
s.pop(3); s << ["式",a/b]
when ["(",["式",a=_],")"]===s.last(3)
s.pop(3); s << ["式",a]
when /\d/===s[-1]
s.pop(1); s << ["式",$&.to_i]
else
if x
s << x
input = input[1..-1]
else
if [["式", a=_]] === s then
return a
else
return nil
end
end
end
end
end
同じ要領で、構文木を作りたいときは ["式", tree] にするとよいです。おしまい。
Alice ML という言語を Google Code Jam のために使い始めてみました。 この言語の futures という機能面白いですね。
機能自体はいろんなところにある、というか自分でも java.util.Concurrent にあるのを時々使うんですが、 Alice ML で実装されている "implicit future" （用語は wikipedia://Futures_and_promises より） という形で使ったことがなかったので、予想外に楽で感動しました。io などにもあるらしい。
future というのは、 要するに「今はまだ値が決まってないけど後で未来のいつかには決めるからちょっと待って」という状態を表します。
- open Promise;
- val p = promise ();
val p : '1 promise = promise{|_future|}
- val f = future p;
val f : '2 = _future
- val lst = [1, f, 2, f, 3, f];
val lst : int list = [1, _future, 2, _future, 3, _future]
「リスト作りたくて 2, 4, 6 番目には同じ値が入ることまではわかってるんだけど、 何入れるか決めてないからちょっと待ってて！」
- fulfill (p, 666); val it : unit = ()
「決めた！ 666 が入ります！」
- lst; val it : int list = [1, 666, 2, 666, 3, 666]
とやると、さっき作った future 入りのリストに自動的に 666 が埋まって普通の整数のリストになります。
何が特におもしろいかというと、
val lst : int list = [1, _future, 2, _future, 3, _future]
中に future という怪しげなものが混じっているにも関わらず、
ここが何の変哲もない int の list として扱われているところ。
型を変えてよければ、この機能を実現するのは特に難しくないんですよ。
たとえば C 言語なら int* のリストにして、あとで *f = 666;
としてやれば一発で全部同じ値になる。Java なら List<Future<Integer>>
にして、あとで FutureTask から set すればいい。
でも、それでは int の list には、ならない。
使う側も、まったく普通の int list に見えているので、あとで使うときに *
で参照外ししたり、.get() メソッドで値を取り出したりしなくていい。
こんな風に、future を使っていることを全く外に意識させずに暗黙のうちに future
をすべりこませられるという意味で、implicit と呼ぶらしいです。あ、ちなみに、
まだ値をセットし終わっていない future にアクセスしようとするとデッドロックっぽいです。
（←シングルスレッドの場合。後述するように、
他のスレッドが値をfutureにセットすると、future待ちしていたスレッドはその時に再び動き出します。）
遅延評価を使ったトリックである Circular Programming の例として有名な repMin (与えられたリストやツリーの全要素を、その最小値で置き換えよう。１パスで。) も、とても素直に書けてしまう。
fun repMin (ls : int list) : int list =
let
(*) futureMin にはあとでちゃんと最小値を入れるけどちょっと待って！
val p = Promise.promise ()
val futureMin = Promise.future p
(*) ls を全部 futureMin に置き換えつつ本当に最小値を計算する。１パスで。
fun repMin' [x] = (x, [futureMin])
| repMin' (x::xs) = (fn (m,xs) => (if m<x then m else x, futureMin::xs)) (repMin' xs)
val (realMin, ls') = repMin' ls
in
(*) futureMin は実は realMin でしたー！じゃじゃーん！
Promise.fulfill (p, realMin);
(*) 置き換え済みリストを返す
ls'
end
さきほどの例であげた Promise モジュールを明示的に使う方法は、実はちょっと玄人向けです。 普段から Circular Programming したい人ってあんまりいなそうですしね。 future の第一の用途である並列計算との組み合わせは一単語で。
- fun fib x = if x < 2 then 1 else fib (x-1) + fib (x-2);
val fib : int -> int = _fn
- val z = [spawn fib 30, spawn fib 30, spawn fib 30];
val z : int list = [_future, _future, _future]
- z;
val it : int list = [_future, _future, _future]
(...しばらく待ってから...)
- z;
val it : int list = [1346269, 1346269, 1346269]
spawn で修飾した式は、 「別スレッドで動かしてそこで計算完了したら値が埋まる future」 になります。これも、使う側からはただの int list に見えるのでスレッドを待ったり通信したりするコードを本当に何一つ考えなくてよいという。 計算が終わっていない future にアクセスしようとすると、そこで自動的にブロックされます。 （Promise モジュールを使うと「計算終わってる？」等のチェックも可能です。） しかし現状、ネイティブスレッド１個しか使ってくれないので、code jam で使ってみたけど速くはならなかった…。
もう一つの future の仲間が、遅延評価。Alice ML では lazy と修飾した式は遅延評価されます。
- val z = let val x = lazy fib 30 in [x, x, lazy fib 30] end;
val z : int list = [_lazy, _lazy, _lazy]
(...しばらく待っても...)
- z;
val it : int list = [_lazy, _lazy, _lazy]
ここで、z の先頭要素の値が本当に必要な計算をすると…
- (List.hd z) + 10;
val it : int = 1346279
- z;
val it : int list = [1346269, 1346269, _lazy]
と、その部分だけが評価されます。
Haskell のようにデフォルト遅延評価な言語だと当たり前ですが、
そうでない言語で、"int" と "遅延された int" が同じ型になって、
"force 関数" のようなもので明示的に評価しないでも int が手に入るというのは面白いなーと。
東京～京都まで歩くのを一度やりたいなーと思っているんですけど、 なかなかまとまった時間を取るのは難しそう…と思って、バラで色々歩いてみることにしました。 というわけで、 ゴールデンウィークに駿河湾沿いを行ってみたログ（重いです）。