飲み会で出た話をすこし考えてみる。
仮説: 正規表現に zero-width positive look-ahead assertion を追加しても対応する言語集合は変化しない。
考えてみると、a(?=b) のようなマッチ対象の外部を参照するものを書けるので、 これは明らかに間違っている。というか、そもそも言語集合という範疇ではとらえられない。 そこで、次のように変える。
仮説: zero-width positive look-ahead assertion を使ったパターンには、 常に r1(?=l1)|r2(?=l2)|...|rn(?=ln) という形の等価な表現が存在する。 ただし、ここで r1, ..., rn, l1, ..., ln は zero-width positive look-ahead assertion を含まない、 通常の正規表現である。
つまり、右端よりも右を参照するために zero-width positive look-ahead assertion を右端においてネスト無しでつかうものの、それ以外では使わなくても済む、ということである。
とりあえず、簡単なところから書き換えでそういう形に到達できそうかどうか考えてみる。
正規集合が共通部分について閉じているのはわかっているし、 l/c もオートマトンを考えて、初期状態を一文字進めたところから始まるオートマトンに変えたと思えばこれも問題ない。
問題は * である。
(r(?=l))* で assertion を外に出すにはどうしたらいいか?
まず、(?=l) を r* を越えて右に動かしても、assersion の種類は有限で抑えられることは想像できる。 これは、assertion になる表現は l/c と l1&l2 のみによって生成されていくからである。
そして、r* に対応する NFA の各状態を assertion の種類によって分割すれば、 (r(?=l))* の状態集合になるのではないか。 だとすれば状態集合が有限で済み、 各受理状態を正規表現に変換し、受理状態に附属している assertion を付加したものを 全部 | で繋げれば assertion を外に出せたことになる。 たぶん。
(?=l)r* も同様にどうにかなるんではないかと思う。
こういうのを帰納段階として構造帰納法を使えばどうにか示せるんじゃないかという気がする。 なんとなく。
そういや、Ragel は正規表現の共通部分が扱えたな...
ふと思ったのだが、文体から著者を推定するのは実用的なレベルになっているのだろうか?
NetNews や ML からサンプルデータを取得して、匿名掲示板に適用するのはどうだろう?
google で「協調ロック」... うぅむ。たった 3件?
「アドバイザリロック」... 9件?
なんかやけに少なくないか? キーワードが適切でない?
「advisory lock」(日本語のページを検索)... 15件
これだけ?
世の中の人はロックについて悩んだりしないのだろうか?
flock だとたくさん見つかるからそういう用語を使わない人が非常に多いというだけの話か?
個人的に、ファイルの内容を書き換える時には、別ファイルをつくって rename するのがアトミックで好きである。
また、ロックファイルはプロセスが死んでも残るので嫌いである。
両方の要求を満たすように、 ロックを行ないつつ変更はアトミックに行なうにはどうしたらいいか?
GNU libsigsegv is a library for handling page faults.
私も google で探しました。
ただ、後半の「人多ければ狼を食らう」で探すと、 「狼多ければ人を食らい、人多ければ狼を食らう」 というのも出てくるようで。
どっちが正しい(元ネタと等しい)かは知りませんが。
ViewCVS に subversion サポートが入り始めてる?
「ファイルロック」... 4170件
「ロックファイル」... 4240件
「ファイルロック ロックファイル」.... 689件
検索結果を眺めていて「スレッド天国」というタイトルのページを見つける。
残念ながら、タイトルから期待したような内容ではなかった。
電源を抜き差しするのに重宝していたエコプラグ(電源差込プラグ用省力アタッチメント)が壊れてしまった。
また買ってこよう。
LD_PRELOAD は static link されてると効かんか。 そりゃそうだよな。
うぅむ。ld は static link なのか...
うぅむ。dynamic link な ld でも効かない?
ld に特別な事情がある? それとも単なる勘違い?
エコプラグではなくエコプルグであった...
ふと、 「進ぬ！電波時計２〜毒電波をきみに。の似非科学」 を読む。楽しい。
ふむ。fcntl によるロックは NFS でも動くことが(むろん動かないことも)あるのか。
現実逃避により、ある名称未定なプログラムの核部分のプロトタイプを作ってしまう。
名称未定なプログラム、というのは依存関係を書かなくてもいい make みたいなもののことであるが、どんな名前がいいか...
google.
"socket AF_INET" 27500
"socket PF_INET" 6190
socket の第一引数に AF_INET を使うのがこんなに多いのはなぜか? 昔の socket(2) には今ほど明確には書いていなかったのだろうか?
AF_INET と PF_INET が実際に異なる環境は存在するか?
ドラゴンブックの演算子優先順位構文解析のところを読む。
ここを読んだのは初めてな気がする。
演算子優先順位構文解析のところを読んだのは別に粋狂というわけではない。 少なくともそのこと自体は直接的には粋狂ではない。 他の話があってそれに参考になりそうだから読んだというだけの話である。 なお、その、他の話が粋狂かどうかはここではおいておく。
さて、むろん、これで構文解析をしようという話ではない。 問題はその逆で、 構文木を文字列に変換する場合に括弧の挿入を最小にするにはどうしたらいいかという話である。
読んでみてわかったのは、まぁ、十分に考えれば何とかなりそうだ、ということである。
というわけで考えているのであるが、 唐突に演算子優先順位構文解析を離れて一般の場合に戻ると、 もっともナイーブなやりかたは、 すべてのトークン列(括弧を挿入可能な場所が構文木上に n個ある場合には 2^n 種類)をとりあえず生成し、パーザに突っ込んで構文木を再生成し、 もとの構文木と(挿入場所の括弧を無視して)比較する、ということであろう。 一致したもののうち挿入した括弧が一番少ないやつが解である。 もちろん、どの構文木も元のと一致しない場合には解がない。
これの効率化の常套手段はバックトラックであろう。 トークン列は括弧の挿入場所までは同じなんだから パーザの状態も同じはずで、 それを毎回計算しなおすのは無駄である。 バックトラックさせればそのへんの計算は共有できる。
ここで、もし、(括弧が挿入されるかどうかで)入力が分岐する場所で、 即座に生成される構文木が元のと一致するかどうか判定できるなら、 難しいバックトラックも必要なく、決定的に計算可能である。 おそらく普通の構文解析に毛が生えた程度のコストで計算できるはずであろう。
そのためには、LL が都合がよく、LR は最低である。 演算子優先順位構文解析はよくわからない。 LL(k) ならあるサブツリーの先頭のトークン k個を読めばサブツリーの トップレベルの構文要素が確定するので、構文木を上から比較することができる。 LR(k) だと確定するのはサブツリーを構成するトークンを全部読んでそこから更に k個読まないと確定しない。 つまり、バックトラックしなければいけない距離が長過ぎる。 (パーザとしてはそこが強力なんだけど。) 演算子優先順位構文解析は、たぶん、左右に制約があるので、 やはりサブツリーの右端まで読んでからバックトラックするはめになることが あるのではないかと思う。
と、考えていると、LL でも右端まで読んでから バックトラックするはめにならないという保証はどこにもないということに気がつく。 たとえば、サブツリーの右端が元のと同じ場所である保証は特にないわけである。
とすると、LL や演算子優先順位構文解析が LR よりもいいところは、 サブツリーの左端で枝刈りができるというところかも知れない。
しかし、そうなると以前から考えていた別の話が浮かんでくる。 LR で、サブツリーの左端でアクションが動かせないかという話である。 いくら LR が逆順右導出だからといっても左から読んでいるには違いないわけで、 オートマトンが進むたびに最初の方から生き残っているパスはどんどん刈り取られ、 ある時点で最初の方の可能性はひとつしか残らなくなっているはずである。 というか、reduce 時にひとつ以上残っていたらエラーになるわけだが。 で、うまいこと最初の方の可能性を数えて、可能性がひとつに減った時点で アクションを実行することができれば、左端とはいわないまでも、 可能な限り左の方で作業ができるのではないかという話である。 たとえば、拡大文法の場合、一番上で適用される導出規則は S' -> S に決まっているわけで、可能性ははなからひとつしか存在しない。 したがって、トークンをひとつも読まなくったってアクションを動かせるわけである。 もちろん、S の中身を参照できるわけではないが。
もし、これが実際的に可能であるなら、これは左導出を LR 的な逆順右導出と 同時にやることになるわけで、LRL とでも呼べるだろうか。 それはともかく、そういうことが可能であれば、 LL や演算子優先順位構文解析と同様にサブツリーの左端での枝刈りが可能にるので LR でもいいかもしれない。
そういうアクションは他にも用途があって (というかそっちで問題になって考えていたわけだが)、 構文木を XML で吐く時に LR だとトップレベルの要素が最後まで決まらないから入力を全部とっておかないといけないという話がある。
などととりとめもないことを考えて現実逃避をしていてはいけないなぁ。
以前から疑問だった、 kterm のスクロールバー上にマウスカーソルがある時に キーボードから入力ができないという問題に取り組んでみる。
しばらく試して、なんとなくわかった。 KTerm*VT100.?.Translations に ~Meta<KeyPress>:insert-seven-bit() が入っていない臭い。 入れれば入力できる。
昔、他の環境では何も問題なく入力できた気がするとか、 scroll-back/scroll-forw とかがここでは効かないとか、 ? のところの名前がよくわからない(たぶん ScrollBar だと思うけど。名前じゃなくてクラスというべきか?)とか、 editres で出てこないとか、 いろいろ疑問は残るが、挙動としては解決したので気にしないことにする。
むろん、これも現実逃避である。
calloc を callcc に見間違える。
こんなにも似ていることに初めて気がついた。
自分の名前を入れてみる。
BASH Debugger provides a patched BASH that enables better debugging support as well as improved error reporting.
論文には Makefile をつける。これは基本である。
だが、問題は LaTeX の依存関係をどう書くかである。 LaTeX は実行時に参照を aux に書き出して、次回に使う。 つまり、aux が aux 自身に依存するというサイクルがあり、 正しく参照を行なうためには、 警告が消えるまで繰り返し処理しなければならない。 これを行なうにはどうしたらいいか? 個人的には(フォント以外の)警告が消えるか ログが不動点に達するまで繰り返し処理するアクションを Makefile に書いてあるが、もっときれいな方法はないか?
また、LaTeX はどのファイルを読んだかログに出力してくれる。 これを make が扱う依存関係にフィードバックできないか?
bibtex をうまく扱う方法はあるか? bib はあまり変わらないので、毎回 bibtex を動かしたくはない。 しかし、cite の情報は aux に入っているので LaTeX が動くたびに 更新されてしまう。効率良く扱えないだろうか?
ちなみに今日は論文の締切であった。 が、論文の Makefile について考えをめぐらしたのは提出した後なので現実逃避ではない。
それはそれとして、提出はソースも含めて tar.gz.uu で送れとのことであった。 Makefile に dist というエントリを作るべきだったかも知れない。
考えてみると、構文解析を持ち出す必要はぜんぜんなかった。
問題は(たとえば)
E = E+E|E*E|V
に従う抽象構文木を
E1 = E1+E2|E2 E2 = E2*E3|E3 E3 = V|(E1)
に従う具象構文木に変換するにはどーしたらいいかということである。
ここで、抽象構文木のノードと 具象構文木のノードには演算子による自明な対応がある。 (というか、そういう抽象構文・具象構文を扱う。) E=E+E なノードだったら E1=E1+E2 だし、 E=E*E だったら E2=E2*E3 である。 具象構文から非終端記号の番号(と E3=(E1) という括弧を生成する規則)をとっぱらったものが抽象構文である、ともいえる。
で、括弧を挿入すべきかどうかは、 非終端記号から簡単にわかる。 E2 があるべきところに E3 がきたら、 E2 -*-> E3 という導出が存在するので括弧を挿入する必要はない。 しかし、E2 があるべきところに E1 がきたら、 E2 -*-> E1 という導出は存在しないので括弧を挿入して E2 -> E3 -> (E1) とする必要がある。
結局、具象構文における 親ノードの期待(右辺の非終端記号)と 子ノードの性質(左辺の非終端記号)を比べれば判断できる。 これは、まぁ、確実に動くことが確信できる。 もちろん、曖昧でない具象構文を書ければ、という仮定はあるけれど。
一般には非終端記号間の関係によって括弧の挿入の必要性が決まるわけであるが、 普通は(とくに yacc の演算子優先順位を使っているような構文なら)演算子の 優先順位から非終端記号にある順序が存在し、その順序で比較するだけでよい。 たとえば、上の例では En の n の大小を比較するだけで十分である。
というわけで書いてみると動いているようだ。
valgrind の suppression file の書き方を調べる。
XML Indent is a XML stream reformatter written in ANSI C.
明日はお出かけしよう。
頭痛。風邪気味?
Principle of Least Surprise でもって There's exactly one way to do it ですか?
[latest]